자바
-
BOJ) 캐슬 디펜스 (17135 번)알고리즘/백준 2021. 2. 3. 18:03
캐슬 디펜스 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 생각보다 많이 어려웠던 문제였다. 적을 제거하는 규칙을 찾아 글로는 정리가 됐지만, 어떻게 코드로 구현해야할지 감이 오질 않았다. 그래서, 다른 블로그 글을 찾았고, 여기글을 많이 참고했다. 궁수가 적을 죽이는 순서는 삼각형을 그렸을 때, 좌측, 상단, 우측의 꼭지점 순서라고 생각하면 편하다. 공격 범위에 따라 위와 같은 순서로 적을 죽이게 된다. 범위 : 1 => y-1 범위 : 2 => (x-1,y-1) ~> (x, y-2) ~> (x+1, y-1) 이런 식..
-
BOJ) 조합 (2407 번)알고리즘/백준 2021. 2. 3. 17:43
조합 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 수학의 조합(Combination)을 구현하는 문제다. 조합 자체는 여러 방법으로 구할 수 있지만, 반복문을 통해 풀기로 했다. 그래서 combination을 직접 몇 개 써보면서 규칙을 찾았다. nCm => n! / ((n - m)! * m!) 이라는 공식이 있는데, 이를 약분하면 nCm => (n*n-1*... *n-m+1) / (m*m-1*...*1) 라는 식이 나온다. n =10인 경우를 살펴보자 N M 식 값 10 0 10! / ( (10 -0)! * 0! ) => 10! / 10! 1 10 1 10! / ( (10-1)! * 1! ) => 10! / 9! => ..
-
BOJ) 스택 수열 (1874 번)알고리즘/백준 2021. 2. 3. 17:26
스택 수열 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 1 ~ n의 수를 스택에 넣었다가 뽑아 늘어놓아서 하나의 수열을 만든다. 이때, 스택에 push하는 순서가 반드시 오름차순을 지켜야한다. 조건에 맞으면 push와 pop하는 행위에 대한 문자열을, 충족하지 못하면 NO를 출력하는 문제다. 문제는 간단했다. 배열을 돌면서 현재 스택의 top과 같은지, 혹은 대소인지 비교해주어 문제를 풀었다. 스택의 top보다 순회중인 배열..
-
BOJ) 좋은 친구 (3078 번)알고리즘/백준 2021. 2. 2. 18:37
좋은 친구 3078번: 좋은 친구 첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N) 다음 N개 줄에는 상근이네 반 학생의 이름이 성적순으로 주어진다. 이름은 알파벳 대문자로 이루어져 있고, 2글자 ~ 20글자이다. www.acmicpc.net N명 학생들의 이름이 성적순으로 주어졌을 때, 좋은 친구가 몇 쌍이나 있는지 구하는 문제다. 좋은 친구는 등수의 차이가 K보다 작거나 같으면서 이름의 길이가 같은 친구 라고 정의하고 있다. 또한, 이름의 길이는 2 ~ 20 사이이다. 풀이 먼저, 이름의 길이에 따라 학생을 저장할 배열 bestFriends와 Sliding Window를 도와줄 Queue를 초기화했다. 위의 배열에는 이름의 길이가 2 ~ 20까지인 학생들이 몇명인지 ..
-
BOJ) 파일 합치기 (11066 번)알고리즘/백준 2021. 2. 2. 18:22
파일 합치기 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net DP로 분류된 문제인데, 정답률에 비해 굉장히 어렵게 느껴졌다. 연속된 소설 파일들을 합치는데, 연속이 되도록 파일을 합쳐야한다. 즉, 인접한 두 파일만을 합칠 수 있을 때, 가장 최소 비용을 구하는 문제다. 이 문제는 풀지 못했다. 정말 모르겠어서 다른 분들의 풀이를 참고해서 블로그를 포스팅한다. 참고한 링크는 하단에 걸어두었다. dp[i][j]는 i부터 j까지 합쳐지는데 최솟값을 저장한다. ( i ~ j 장 까지 합치는데 드는 최소 비용)..
-
BOJ) 문자열 폭발 (9935 번)알고리즘/백준 2021. 1. 29. 17:22
문자열 폭발 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 이전에 시도했다가 실패했던 문제다. replaceAll이라는 좋은 메소드를 제공해주는데 굳이 구현을 해야할까? 싶어서 시도했었는데 역시나 시간초과였다. 자바는 문자열에 참 약하다...ㅠ 어떻게 풀어야할까 생각하다가 문제의 하단에 있는 알고리즘 분류를 봤는데 스택이 있었다. 그래서 스택을 이용해서 먼저 문제를 풀었다. 문자열을 돌면서 문자를 스택에 넣어주는데, 넣을 차례의 문자가 폭탄의 마지막 문자와 같은 경우 기존 스택에서 값을 꺼내면..
-
BOJ) 특정한 최단 경로 (1504 번)알고리즘/백준 2021. 1. 29. 17:14
특정한 최단 경로 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 다익스트라를 사용한다는 조건에 노드 두 개를 거쳐야하는 경로에 포함해야하는 문제다. 처음에는, 기본적인 다익스트라로 경로를 이동하면서 입력받은 두 노드를 거쳤는지 정보도 함께 포함했었다. 하지만, 틀린 것을 확인하고 두 경로 모두 거쳐야하는 조건을 제대로 파악하기 어렵다고 생각했다.그래서 경로가 두개만 주어지기 때문에, 해당 경로를 거치는 경우의 수를 다익스트라로 표현하면 된다고 생각했다. 풀이 1번..
-
BOJ) 트리 (1068 번)알고리즘/백준 2021. 1. 29. 17:08
트리 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 풀이 트리의 정보가 주어지고 특정 노드를 제거할 때, 리프노드가 몇 개 인지 찾는 문제다. 먼저, 트리의 각 노드는 하나의 부모를 가지고 있기 때문에 find-union을 사용해야겠다고 생각했다. 이전 find-union과 다른 점은 이미 부모에 대한 정보가 주어졌기 때문에, find할 때 더 상위 부모로 값을 최신화하지 않았다는 것이다. (최신화를 하게되면 루트 노드로 이어지기 때문에, 특정 노드를 제거했을 때, 자식노드를 제거할 수 없음) 다음으로..