분할 정복

1. 개요[편집]

분할 정복 Divide and conquer
골격	분할(divide) → 정복(conquer, 재귀) → 결합(combine)
비용 모형	$T(n) = a\,T(n/b) + f(n)$
분석 도구	마스터 정리 · 아크라-바지 정리 · 재귀 트리
고전 사례	병합정렬 · 카라츠바 · 슈트라센 · FFT · 가장 가까운 점 쌍
수치해석	분할 정복 고유값 · FMM · 계층행렬 · 중첩 절단
덤	포크-조인 병렬성 · 캐시 무의식 지역성

분할 정복(divide and conquer)은 문제를 같은 형태의 더 작은 부분문제 여러 개로 쪼개 재귀적으로 푼 뒤, 부분해를 결합해 원 문제의 해를 만드는 알고리즘 설계 패러다임이다. 세 단계의 이름이 그대로 절차다 — 분할, 정복(재귀 호출), 결합.

이 패러다임이 강력한 이유는 비용이 재귀식으로 정확히 서술되고, 그 재귀식이 대개 로그를 하나 붙이는 선에서 풀리기 때문이다. $n$ 을 반으로 자르면 깊이가 $\log_2 n$ 이고, 각 레벨의 총 결합 비용이 선형이면 전체가 $n\log n$ 이 된다. $n^2$ 를 $n\log n$ 으로 바꾸는 것은 $n=10^6$ 에서 5만 배 차이라, 이 한 가지 패턴이 만든 알고리즘만으로도 계산과학의 절반이 돌아간다.

수치해석 쪽에서 분할 정복은 정렬 알고리즘 이야기가 아니다. 고속 푸리에 변환, 분할 정복 고유값 알고리즘, 고속 다중극자법과 계층행렬, 희소행렬 소거 순서의 중첩 절단이 전부 같은 뼈대 위에 서 있고, 심지어 영역 분할법까지 “분할하고 결합한다”는 문장을 공유한다. 여기에 포크-조인 병렬성과 캐시 지역성이 공짜로 딸려 온다는 것이 현대적 가치다.

2. 비용 재귀식과 마스터 정리[편집]

크기 $n$ 을 $b$ 등분해 $a$ 개의 부분문제를 풀고, 분할·결합에 $f(n)$ 이 든다면

$$T(n) = a\,T(n/b) + f(n), \qquad a \ge 1,\ b > 1.$$

재귀 트리를 그려 보면 깊이 $\log_b n$, 레벨 $j$ 의 노드 수 $a^j$, 잎의 총수 $n^{\log_b a}$ 다. 그래서 잎의 비용 $n^{\log_b a}$ 와 뿌리 쪽 결합 비용 $f(n)$ 중 누가 이기는가가 전부다. 이를 정리한 것이 마스터 정리다. $c^{*} = \log_b a$ 로 두면,

1. 잎이 이긴다. 어떤 $\varepsilon>0$ 에 대해 $f(n) = O(n^{c^{*}-\varepsilon})$ 이면 $T(n) = \Theta(n^{c^{*}})$.
2. 비긴다. 어떤 $k \ge 0$ 에 대해 $f(n) = \Theta(n^{c^{*}} \log^{k} n)$ 이면 $T(n) = \Theta(n^{c^{*}} \log^{k+1} n)$.
3. 뿌리가 이긴다. 어떤 $\varepsilon>0$ 에 대해 $f(n) = \Omega(n^{c^{*}+\varepsilon})$ 이고 정규성 조건 $a f(n/b) \le c\,f(n)$ 을 만족하는 $c<1$ 이 존재하면 $T(n) = \Theta(f(n))$.

3번의 정규성 조건을 빼먹는 것이 가장 흔한 오용이다. $f$ 가 다항식적으로 크기만 하면 되는 게 아니라, 한 레벨 내려갈 때 총 결합 비용이 기하급수적으로 줄어야 뿌리가 지배한다. 다항식 형태의 $f$ 는 자동으로 만족하지만 $f(n)=n^2\log n$ 처럼 로그가 섞이거나 진동하는 함수는 확인이 필요하다.

또 하나, 마스터 정리에는 구멍이 있다. 세 경우는 $f$ 와 $n^{c^{*}}$ 의 비가 다항식적으로 벌어지거나 로그 거듭제곱만큼 벌어지는 경우만 덮는다. 예를 들어 $f(n) = n^{c^{*}}/\log n$ 은 1번보다 크고 2번($k \ge 0$)에 안 들어가며 3번보다 작다 — 어느 경우도 아니다. 이때의 참값은 $\Theta(n^{c^{*}} \log\log n)$ 이고, 마스터 정리로는 절대 안 나온다.¹

아크라-바지 정리(Akra–Bazzi, 1998)는 이 제약을 크게 푼다. 부분문제 크기가 서로 다르고, 반올림 때문에 정확히 $n/b$ 가 아니어도 된다.

$$T(x) = g(x) + \sum_{i=1}^{k} a_i\, T(b_i x + h_i(x)), \qquad a_i>0,\ 0<b_i<1$$

에서 $\sum_i a_i b_i^{\,p} = 1$ 을 만족하는 유일한 $p$ 를 찾으면

$$T(x) = \Theta\!\left( x^{p}\left( 1 + \int_1^{x} \frac{g(u)}{u^{p+1}}\, du \right) \right).$$

$T(n)=T(n/3)+T(2n/3)+O(n)$ 같은 불균등 분할이 곧바로 풀린다($p=1$, 따라서 $\Theta(n\log n)$). 마스터 정리는 $k=1$ 인 특수 경우다.

3. 고전 사례들이 보여주는 것[편집]

• 병합정렬. $T(n)=2T(n/2)+\Theta(n) \Rightarrow \Theta(n\log n)$. 결합(병합)이 무거운 대신 분할이 공짜다. 안정 정렬이고 최악에도 $n\log n$ 이라 외부 정렬·연결 리스트 정렬의 국룰.
• 퀵정렬. 반대로 분할이 무겁고 결합이 공짜다. 피벗으로 분할해 놓으면 재귀가 끝나는 즉시 정렬돼 있다. 평균 $\Theta(n\log n)$, 최악 $\Theta(n^2)$ — 무작위 피벗이면 최악은 확률적으로 사라진다. 결정적 선형 시간 중앙값 선택(median of medians, 1973)을 쓰면 최악도 $n\log n$ 이 되지만 상수가 커서 실무에서는 안 쓴다. 대신 재귀 깊이가 임계를 넘으면 힙정렬로 갈아타는 인트로정렬이 표준 라이브러리의 답이다.
• 카라츠바 곱셈. $n$ 자리 수 두 개를 절반씩 잘라 $x=x_1B+x_0$, $y=y_1B+y_0$ 로 쓰면 소박하게는 곱셈 4번이 필요한데, $x_1y_1$, $x_0y_0$, $(x_1+x_0)(y_1+y_0)$ 세 번만 하고 나머지를 뺄셈으로 만들 수 있다. $T(n)=3T(n/2)+O(n) \Rightarrow \Theta(n^{\log_2 3}) \approx \Theta(n^{1.585})$. 1960년 카라츠바가 ”$n^2$ 보다 빠를 수 없다”는 콜모고로프의 추측을 일주일 만에 깬 사건이라, 재귀 한 겹으로 곱셈 하나를 아끼는 이 트릭은 이후 모든 빠른 곱셈의 원형이 됐다. 툼-쿡으로 일반화되고, FFT 기반 쇤하게-슈트라센을 거쳐 지금은 $O(n\log n)$ 이 알려져 있다.
• 슈트라센 행렬 곱셈. 같은 발상을 블록 행렬에 적용해 $2\times2$ 블록 곱셈의 8번을 7번으로 줄인다. $T(n)=7T(n/2)+\Theta(n^2) \Rightarrow \Theta(n^{\log_2 7}) \approx \Theta(n^{2.807})$. 자세한 것과 지수 $\omega$ 를 2.37 언저리까지 끌어내린 이후 연구는 행렬 곱셈 문서로 넘긴다. 수치 쪽 단서 하나만 적어 두면, 슈트라센은 성분별 오차 한계를 잃는다 — 노름 기준 안정성은 유지되지만 고전 알고리즘이 주는 성분별 보장은 깨진다. 그래서 LAPACK 급 라이브러리가 기본으로 켜지 않는다.
• 고속 푸리에 변환. $T(n)=2T(n/2)+\Theta(n) \Rightarrow \Theta(n\log n)$. 짝수·홀수 인덱스로 쪼개는 쿨리-투키가 분할 정복의 가장 유명한 얼굴이다.
• 가장 가까운 점 쌍. 점을 $x$ 좌표로 반 갈라 양쪽에서 최소거리 $\delta$ 를 얻은 뒤, 경계로부터 폭 $\delta$ 인 띠만 검사한다. 핵심 보조정리는 띠 안에서 $y$ 로 정렬해 두면 각 점은 뒤따르는 7개만 보면 충분하다는 것 — $\delta \times 2\delta$ 직사각형에 서로 $\delta$ 이상 떨어진 점은 8개를 넘을 수 없기 때문이다. 그래서 결합이 선형이 되고 전체가 $\Theta(n\log n)$. “결합 단계에서 기하학적 논증으로 상수를 잡아내는” 계산기하의 전형이다.

4. 수치해석에서의 분할 정복[편집]

대칭 삼중대각 고유값 문제. 삼중대각 행렬 $T$ 를 반으로 자르면 딱 하나의 비대각 원소가 남는데, 이것을 랭크-1 수정으로 분리해 $T = \begin{pmatrix} T_1 & \\ & T_2\end{pmatrix} + \rho\, vv^{\top}$ 로 쓴다. 두 부분의 고유분해를 재귀로 얻고, 결합 단계는 세큘러 방정식의 근을 푸는 것으로 끝난다. 쿠펜(Cuppen, 1981)의 이 알고리즘은 디플레이션 덕분에 실측이 이론($O(n^3)$)보다 훨씬 빠르고, 대형 대칭 문제에서 QR 알고리즘을 이긴다. 자세한 내용은 분할 정복 고유값 알고리즘 문서에 있다. 여기서 짚을 것은 “결합이 싼 절단면을 찾는 것”이 알고리즘 설계의 전부라는 점이다 — 삼중대각 구조가 절단면을 랭크 1로 만들어 주지 않았다면 이 알고리즘은 존재하지 않는다.

계층적 저랭크 근사. $N$ 개 입자의 상호작용을 다 계산하면 $O(N^2)$ 인데, 고속 다중극자법은 공간을 재귀적으로 쪼개고(옥트리) 멀리 떨어진 덩어리끼리의 상호작용을 다중극 전개로 뭉뚱그려 $O(N)$ 으로 끝낸다. 같은 사상을 행렬 언어로 옮긴 것이 계층행렬(H-matrix, Hackbusch 1999)이다. 지표 집합을 트리로 쪼개고, 블록 $(t,s)$ 가 허용성 조건(대략 “두 덩어리의 지름이 그들 사이 거리보다 충분히 작다”)을 만족하면 그 블록을 랭크 $k$ 의 저랭크 근사로 대체하고, 아니면 더 잘게 쪼갠다. 저장량과 행렬-벡터 곱이 $O(kN\log N)$ 이 되고, 근사 LU 분해까지 계층 구조 위에서 재귀적으로 정의된다. 경계요소법의 조밀행렬을 다룰 수 있게 만든 것이 이 재귀 분할이다.

중첩 절단. 희소행렬의 소거 순서를 정하는 문제도 분할 정복이다. 그래프를 작은 분리자(separator)로 두 덩어리로 가르고, 양쪽을 재귀적으로 먼저 번호 매긴 뒤 분리자를 마지막에 둔다. 그러면 양쪽 덩어리 사이에는 채움이 생기지 않는다. $\sqrt{n}\times\sqrt{n}$ 격자에서 분리자 크기가 $\sqrt{n}$ 이므로 채움은 $O(n\log n)$, 연산은 $O(n^{3/2})$ 이고 이게 점근적으로 최적이다(George, 1973). 실제 코드에서 분리자를 찾는 일은 그래프 분할이 맡는다.

영역 분할법과의 관계. 도메인을 쪼개 각 조각의 PDE 를 따로 푼다는 점에서 분할 정복과 문장이 같다. 다만 결합이 싸지 않다. 조각 내부 자유도를 소거하고 나면 인터페이스 위의 슈어 보수 시스템이 남고, 이건 값 몇 개를 병합하는 게 아니라 또 하나의 방정식계를 푸는 일이다. 그래서 이 분야의 연구는 대부분 “인터페이스 문제를 어떻게 싸게 풀 것인가”(전처리자, 조대 공간)에 몰려 있다. 알고리즘 교과서의 분할 정복이 결합이 싼 경우만 다룬 특수 사례라는 것을 보여주는 좋은 대조다.

5. 공짜로 딸려 오는 것들 — 병렬성과 캐시[편집]

포크-조인 병렬성. 부분문제들이 서로 독립이면 그냥 동시에 돌리면 된다. 이때의 성능은 작업량(work, 총 연산 $W$)과 스팬(span, 임계 경로 $S$)으로 서술되고, 이상적인 스케줄러에서 $P$ 개 프로세서의 시간은 $O(W/P + S)$ 다. 병합정렬은 병합을 직렬로 두면 스팬이 $\Theta(n)$ 이라 병렬성이 $\Theta(\log n)$ 밖에 안 나오지만, 병합 자체를 이분 탐색으로 분할 정복하면 스팬이 $\Theta(\log^3 n)$ 으로 떨어져 병렬성이 거의 $n$ 이 된다. 재귀를 한 겹 더 넣어 임계 경로를 부수는 이 패턴은 분할 정복 병렬화의 표준 수법이다.

캐시 무의식 알고리즘. 재귀가 진행되면 부분문제가 어느 시점엔가 캐시에 통째로 들어가고, 그 아래로는 캐시 미스가 발생하지 않는다. 놀라운 것은 이게 캐시 크기 $M$ 이나 라인 크기 $B$ 를 코드에 넣지 않아도 자동으로 일어난다는 점이다(Frigo–Leiserson–Prokop–Ramachandran, 1999). 재귀 블록 행렬 곱셈의 캐시 미스는 $\Theta(n^3/(B\sqrt{M}))$ 로, 이는 홍-쿵의 I/O 하한과 점근적으로 같다 — 즉 타일 크기를 튜닝한 코드와 같은 점근 성능을, 튜닝 없이 얻는다. 다단계 캐시가 여러 층인 현대 하드웨어에서 이 성질은 특히 매력적이라, 통신 회피 알고리즘 연구와 한 뿌리를 공유한다.

물론 재귀에는 값이 있다. 함수 호출 오버헤드와 밑바닥의 자잘한 부분문제가 상수를 갉아먹으므로, 실무 구현은 예외 없이 컷오프를 둔다 — 크기가 임계 이하면 재귀를 접고 반복문 기반 커널(정렬이면 삽입정렬, 행렬이면 블록 GEMM)로 갈아탄다. 슈트라센의 손익분기점, FFT 의 기수 선택, 재귀 GEMM 의 베이스 케이스가 전부 이 이야기다.²

6. 언제 쓰지 말아야 하나[편집]

부분문제가 겹치면 분할 정복은 같은 계산을 지수 번 반복한다. 피보나치를 재귀로 짜면 $\Theta(\varphi^n)$ 이 되는 그 사고다. 부분문제가 겹치는 순간 답은 동적 계획법(메모이제이션 또는 상향식 표)이고, 이 구분이 두 패러다임을 가르는 유일하고 정확한 기준이다.

부분문제가 겹치지 않더라도 결합이 분할한 이득보다 비싸면 손해다. 3번 경우($T(n)=\Theta(f(n))$)에 해당하는 알고리즘은 재귀를 아무리 깊게 해도 뿌리의 비용을 못 줄인다. 그리고 애초에 부분해로부터 전체 해를 구성할 수 있는가가 성립하지 않는 문제가 훨씬 많다 — 그런 문제에는 그리디 알고리즘의 교환 논증도, 분할 정복의 재귀식도 통하지 않고, 결국 백트래킹이나 분지한정법으로 간다.³

7. 관련 문서[편집]

• 동적 계획법 · 그리디 알고리즘 · 백트래킹 · 분지한정법
• 고속 푸리에 변환 · 행렬 곱셈 · 카라츠바 알고리즘
• 분할 정복 고유값 알고리즘 · QR 알고리즘 · 란초스 알고리즘
• 고속 다중극자법 · 다중극 전개 · 반스-헛 알고리즘 · 계층 행렬
• 희소행렬 · 그래프 분할 · 영역 분할법 · 슈어 보수
• 병렬 컴퓨팅 · 통신 회피 알고리즘 · 캐시 무의식 알고리즘 · 마스터 정리
• 깊이 우선 탐색 · 옥트리 · 경계 볼륨 계층

8. Footnotes[편집]

1. 그래서 시험 문제에 $T(n)=2T(n/2)+n/\log n$ 이 나오면 그건 마스터 정리 문제가 아니라 “마스터 정리를 쓸 수 없음을 아는지” 묻는 문제다. 재귀 트리를 직접 그려 레벨별 비용 $n/(\log n - j)$ 를 합하면 조화급수가 튀어나오면서 $\log\log$ 가 등장한다. ↩

2. FFTW 가 “플래너”라는 이름으로 실행 시간에 여러 분해 계획을 실측해 보고 고르는 것도 결국 이 컷오프와 기수 선택을 하드웨어마다 자동으로 찾는 장치다. 알고리즘 상수는 종이 위에서 못 정한다는 것을 인정한 설계라, 자동 튜닝(autotuning)이라는 분야 자체가 여기서 나왔다. ↩

3. 세 패러다임의 관계를 한 줄로 요약하면 이렇다. 부분문제가 독립이면 분할 정복, 겹치면 동적 계획법, 겹치는데 표에 담을 수 없을 만큼 상태가 많으면 탐색이다. 그리고 현실의 시뮬레이션 코드는 대체로 세 번째다. ↩