분할 정복(Divide and conquer)

분할 정복은 재귀⁠(recursion)⁠의 한 형태입니다. 크기 n인 문제를 크기 n/2인 문제 몇 개로 나누고(분할), 각각을 같은 방법으로 푼 뒤(정복), 답을 합칩니다. 가장 잘 알려진 예가 병합 정렬입니다. 목록을 반으로 나눠 각각 정렬하고, 정렬된 두 목록을 앞에서부터 하나씩 비교하며 합칩니다. 길이 8인 두 목록을 합칠 때는 원소⁠(element)⁠ 16개를 하나씩 비교해 옮기므로 16번쯤 일합니다.

병합 정렬 전체의 일을 세어 봅시다. n = 16이면 반씩 나누기를 16 → 8 → 4 → 2 → 1로 4번 하므로, 합치는 일이 일어나는 층이 4개(크기 16, 8, 4, 2인 층) 생깁니다. 일반적으로 n을 1이 될 때까지 반으로 나누는 횟수가 $\log_2 n$('로그 2의 n', 2를 몇 번 곱해야 n이 되는가)입니다. 맨 위층에서는 길이 8인 두 목록을 합치니 16번쯤, 그 아래층에서는 길이 4인 목록 둘씩을 두 번 합치니 8 + 8 = 16번쯤입니다. 이처럼 어느 층에서든 그 층의 조각들을 합치는 일은 모두 합쳐 n번쯤입니다. 그래서 전체는 n번씩 $\log_2 n$층, 모두 $n \log_2 n$ 정도입니다(정렬 알고리즘⁠, sorting algorithm⁠).

이제 일반화합니다. 한 문제를 반 크기 문제 a개로 나누고, 나누고 합치는 데 $n^d$만큼 일한다고 합시다. $n^d$는 n을 d번 곱한 것으로, d = 0이면 1(상수), d = 1이면 n, d = 2이면 $n^2$입니다. 병합 정렬은 a = 2, d = 1입니다. 재귀가 만드는 나무를 층별로 보면, 층 i에는 문제가 $a^i$개이고 각각의 크기가 $n/2^i$이므로 문제 하나의 일은 $(n/2^i)^d$입니다. 그 층의 일을 모두 더하면

$a^i \cdot \left(\dfrac{n}{2^i}\right)^d = a^i \cdot \dfrac{n^d}{(2^d)^i} = n^d \left(\dfrac{a}{2^d}\right)^i$

입니다. 병합 정렬이면 $a/2^d = 2/2 = 1$이라 어느 층이든 n입니다. 일반적으로는 한 층 내려갈 때마다 같은 비율 $r = a/2^d$이 곱해지므로, 전체 일은 등비급수(각 항에 같은 수를 곱해 다음 항을 얻는 수들의 합)입니다. 아래 그림과 위의 식에 나오는 $\Theta(g)$('세타 g')는 'n이 커질 때 상수배를 무시하면 g만큼 자란다'로 읽습니다. 점근 표기법⁠(asymptotic notation)⁠의 O가 위쪽 한계만 말한다면, Θ는 위아래를 함께 말합니다.

하위 문제 수 $a =$ , 나누고 합치는 일 $n^d$에서 $d =$ . d = 1로 두고 a를 1부터 8까지 올려 보세요. 왼쪽은 n = 16일 때 층마다 문제가 몇 개인지, 오른쪽은 층마다 하는 일의 양입니다. 가장 무거운 층(노랑)이 맨 위에서 맨 아래로 옮겨 가는 순간을 찾아보세요.

비율 $r =$ . d = 1이면 a = 2에서 r = 1이 되어 모든 층이 노랗게 바뀌고, 그보다 작으면 맨 위층이, 크면 맨 아래층이 가장 무겁습니다.

정리하면, 가장 무거운 층이 전체의 크기를 정합니다. r ≠ 1이면 전체는 가장 무거운 층(맨 위층이나 잎⁠(leaf)⁠ 층)의 상수배이고, r = 1이면 모든 층이 똑같이 나눠 가져 한 층의 일에 층 수 $\log_2 n$을 곱한 만큼입니다. 등비급수⁠(geometric series)⁠의 합이 r < 1이면 첫 항의 $1/(1-r)$배 이하, r > 1이면 끝 항의 $r/(r-1)$배 이하가 되기 때문입니다. 흔히 가장 무거운 층이 일의 대부분을 한다고 생각하지만, r이 1에 가까우면 그렇지 않습니다. 그림에서 a = 5, d = 2(r = 1.25)로 두면 잎 층의 일 625가 가장 크지만 전체 2,101의 30%쯤입니다. 그래도 전체는 그 층의 5배를 넘지 않으므로 Θ로는 같습니다.

r > 1일 때 전체를 정하는 잎 층을 세어 봅시다. 잎 하나의 일은 상수이므로 잎 층의 일은 잎의 개수에 비례합니다. 맨 아래층에는 잎이 $a^{\log_2 n}$개 있고, 이 수는 $n^{\log_2 a}$와 같습니다. 양쪽에 $\log_2$를 씌우면 둘 다 $\log_2 n \times \log_2 a$가 되기 때문입니다. 예를 들어 n = 16, a = 3이면 $3^4 = 81$이고, $16^{\log_2 3} = (2^4)^{\log_2 3} = (2^{\log_2 3})^4 = 3^4 = 81$입니다. 세 경우를 모은 것이 위의 식이고, 이는 마스터 정리라 부르는 더 일반적인 결과(반이 아니라 1/b씩 나누는 경우까지 다룹니다)의 한 경우입니다.

곱셈이 좋은 예입니다. n자리 수 두 개를 초등학교 방식으로 곱하면 한 자리 곱셈을 $n^2$번 합니다. 두 수를 앞 절반과 뒤 절반으로 나누어 $x = x_1 \cdot 10^{n/2} + x_0$, $y = y_1 \cdot 10^{n/2} + y_0$로 쓰면

$xy = x_1y_1 \cdot 10^n + (x_1y_0 + x_0y_1) \cdot 10^{n/2} + x_0y_0$

입니다. 그대로 계산하면 반 크기 곱셈 $x_1y_1, x_1y_0, x_0y_1, x_0y_0$ 네 번이 필요해서(a = 4, d = 1, r = 2) 여전히 $n^{\log_2 4} = n^2$입니다.

1960년 모스크바 대학의 학생이던 아나톨리 카라추바는 곱셈을 세 번으로 줄였습니다. $(x_1 + x_0)(y_1 + y_0)$를 한 번 곱한 뒤, 어차피 구해야 하는 $x_1y_1$과 $x_0y_0$을 빼면 가운데 항 $x_1y_0 + x_0y_1$이 나옵니다. 12 × 34로 확인해 봅시다. $x_1 = 1, x_0 = 2, y_1 = 3, y_0 = 4$입니다.

• 첫째 곱: $x_1y_1 = 1 \times 3 = 3$
• 둘째 곱: $x_0y_0 = 2 \times 4 = 8$
• 셋째 곱: $(1 + 2)(3 + 4) = 21$, 가운데 항은 $21 - 3 - 8 = 10$(실제로 $1 \times 4 + 2 \times 3 = 10$)
• 합치기: $3 \times 100 + 10 \times 10 + 8 = 408$, 그리고 실제로 12 × 34 = 408입니다.

더하고 빼는 일은 n에 비례하니(a = 3, d = 1) 그 결과는 $\Theta(n^{\log_2 3})$, 다시 말해 약 $n^{1.585}$입니다. 이 결과는 곱셈은 $n^2$보다 빠를 수 없다는 콜모고로프의 추측을 깨뜨렸습니다.

같은 요령은 행렬⁠(matrix)⁠에도 통합니다. 1969년 독일의 수학자 폴커 슈트라센은 행렬을 2×2 블록으로 나눈 행렬의 곱⁠(matrix multiplication)⁠을 여덟 번이 아닌 일곱 번의 블록 곱으로 해냈습니다. 블록 곱 하나는 반 크기 행렬의 곱이고, 블록을 더하는 일은 $n^2$에 비례하니(a = 7, d = 2) 전체는 $n^{\log_2 7} \approx n^{2.81}$입니다.

이어지는 곳.

• 고속 푸리에 변환: 신호를 여러 주파수의 파동의 합으로 나누는 계산(이산 푸리에 변환⁠, discrete Fourier transform⁠)을 $n^2$이 아닌 $n \log n$에 해내는 분할 정복입니다. n이 2의 거듭제곱일 때 값을 짝수 번째와 홀수 번째로 나누면, 1의 거듭제곱근(거듭제곱하면 1이 되는 복소수⁠(complex number)⁠)의 대칭 덕분에 반 크기 문제 두 개가 됩니다(a = 2, d = 1). 1965년 쿨리와 튜키가 발표해 널리 퍼졌는데, 가우스가 1805년 무렵 소행성 궤도⁠(orbit)⁠를 계산하며 같은 방법을 써 두었다는 사실이 뒤에 밝혀졌습니다.
• 고속 푸리에 변환 덕분에 다항식⁠(polynomial)⁠의 곱셈, 푸리에 급수⁠(Fourier series)⁠의 계수를 수치로 어림하는 일, JPEG 압축에 쓰이는 이산 코사인 변환⁠(discrete cosine transform)⁠을 빠르게 계산할 수 있습니다.
• 이진 탐색⁠(binary search)⁠: 반쪽 하나만 남기고 나머지를 버리는, a = 1, d = 0인 경우입니다.
• 동적 계획법⁠(dynamic programming)⁠: 하위 문제들이 서로 겹치면 분할 정복은 같은 일을 되풀이하게 됩니다. 그때는 한 번 푼 답을 적어 두고 다시 쓰는 이 방법이 낫습니다.
• 병렬 스캔⁠(parallel scan)⁠: 매 걸음 '앞의 값에 한 수를 곱하고 다른 수를 더하는' 되풀이 $h_t = a_t h_{t-1} + b_t$(여기서 $a_t, b_t$는 걸음마다 주어진 수로, 위의 a와는 다릅니다)도 나눠 풀 수 있습니다. 두 걸음을 이으면 다시 '곱하고 더하기' 한 걸음이 됩니다(×2 하고 +1, 이어서 ×3 하고 +4는 ×6 하고 +7). 이 잇기는 어떻게 묶어도 결과가 같으므로(모노이드⁠, monoid⁠), 앞뒤 반을 따로 계산해 잇기를 되풀이하면 일꾼이 충분할 때 약 $\log n$단계에 끝납니다. 상태 공간 모형⁠(state space model)⁠의 하나인 Mamba가 학습 때 이 방법을 씁니다.
• 점화식⁠(recurrence relation)⁠과 수학적 귀납법⁠(mathematical induction)⁠: $T(n) = a\,T(n/2) + n^d$ 같은 식을 일반적으로 풀고 그 답을 증명하는 도구입니다.