분할 정복

분할 정복 알고리즘

도입분할 정복과 일반적 재귀 호출의 차이일반적 재귀 호출문제를 한 조각과 나머지 전체로 나눔분할정복문제를 항상 거의 같은 크기로 나눔 일반적 재귀 호출분할 정복분할 정복의 구성 요소divide문제를 더 작은 문제로 분할하는 과정merge각 문제에 대해 구한 답을 원래 답으로 병합하는 과정base case매우 작은 문제의 해법예제: 수열의 빠른 합과 행렬의 빠른 제곱가장 간단한 방법은 수식을 이용하여 바로 계산하는 것이다.하지만, 우리는 분할 정복 알고리즘에 익숙해지기 위해 이를 이용하여 계산해보자 1+2+…+n 의 합을 분할 정복을 이용하여 계산해보자 문제를 반으로 나눠보기1부터 n2n\over22n​까지의 합과 n2+1{n\over2}+12n​+1부터 n까지의 합을 구하는 문제로 나눠보자sum(n)..

[BOJ/JAVA] 5904번: Moo 게임

5904번: Moo 게임https://www.acmicpc.net/problem/5904키워드S(0)을 길이가 3인 수열 "m o o”1보다 크거나 같은 모든 k에 대해서, S(k)는 S(k-1)과 o가 k+2개인 수열 "m o ... o" 와 S(k-1)을 합쳐서 만들 수 있다.구현정리하면 S(k) = S(k-1) + “m” + “o”*(k+2) + S(k-1) 이다.dp 를 이용하여 적당한 크기의 S(k)까지 각 수열의 길이를 저장하자.dp(int n)n == 0 인 경우moo 이므로 3을 반환moo[n] ≠ -1 인 경우moo[n] 반환moo[n] 계산moo[n] = dp(n - 1) * 2 + (n + 2) + 1moo[n] 반환findMoo(int k, long left)현재 S(k)이고, 앞에..

[BOJ/JAVA] 16974번: 레벨 햄버거

16974번: 레벨 햄버거https://www.acmicpc.net/problem/16974키워드레벨-0 버거는 패티만으로 이루어져 있다.레벨-L 버거는 햄버거번, 레벨-(L-1) 버거, 패티, 레벨-(L-1)버거, 햄버거번으로 이루어져 있다. (L ≥ 1)구현모든 버거의 상태를 문자열로 나타낼 수 없다. (메모리를 많이 잡아먹기 때문)각 레벨의 버거마다 버거의 사이즈, 버거에 들어가는 패티의 양을 저장한다.buggers[]patties[]위 두 배열을 dp를 사용하여 값을 저장한다.dp(int level)현재 레벨이 level-버거일 때 버거의 크기를 반환한다.level == 0 인 경우패티만 존재하므로 1 반환이미 계산한 값인 경우계산한 값 반환계산하기버거의 크기는 [번] [(level-1)-버거] ..

[BOJ/JAVA] 1074번: Z

1074번: Zhttps://www.acmicpc.net/problem/1074키워드2^N× 2^N인 2차원 배열을 Z모양으로 탐색N > 1인 경우, 배열을 크기가 2^(N-1)× 2^(N-1)로 4등분 한 후에 재귀적으로 순서대로 방문구현move(int y, int x, int n)size = 2^n가장 작은 경우 size가 2^0인 경우좌상단좌상단에 r, c의 범위가 있는 경우1/4 사이즈로 재귀호출한다. 시작 위치는 좌상단이므로 동일move(y, x, n - 1);좌상단에 r, c의 범위가 없는 경우좌상단의 크기만큼 count 증가우상단우상단에 r, c의 범위가 있는 경우1/4 사이즈로 재귀호출한다. 시작 위치는 우상단이므로 x 값만 (size/2)만큼 이동move(y, x + (size / 2),..

[BOJ/JAVA] 10830번: 행렬 제곱

10830번: 행렬 제곱크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.https://www.acmicpc.net/problem/10830키워드크기가 N*N인 행렬 A가 주어진다.A의 B제곱을 구하는 프로그램구현matrixMultiply두 정방행렬의 곱을 구하는 메소드시간복잡도 O(N^3)정방행렬의 곱은 다음과 같다.[a1a2a3a4]∗[b1b2b3b4]=[a1b1+a2b3a1b2+a2b4a3b1+a4b3a3b2+a4b4]\begin{bmatrix} a_1 & a_2 \\ a_3 & a_4 \end{bmatrix} * \begin{bmatrix} b_1 & b_2 \\ b_3 &..