왜 분할정복이 따로 필요한가

07편에서 다룬 퀵 정렬·병합 정렬은 사실 “큰 문제를 작은 문제로 쪼개 각각 풀고 합친다”는 하나의 공통된 설계 원리를 공유한다. 이 원리를 정렬에만 한정하지 않고 일반화하면, 정렬 말고도 거듭제곱 계산, 최근접 점 쌍 찾기, 행렬 곱셈처럼 전혀 다른 문제에도 똑같이 적용할 수 있다. 분할정복(divide and conquer)은 이렇게 “문제를 작게 나누고, 작은 문제를 풀고, 결과를 합친다”는 패턴 자체를 하나의 설계 기법으로 다루는 관점이다.

쉽게 말하면: 분할정복은 큰 문제를 그대로 풀기 어려우니, 작은 조각으로 쪼개 각 조각을 풀고 그 답들을 이어 붙여 원래 문제의 답을 만드는 전략이다.

분할정복의 세 단계

분할정복 알고리즘은 항상 다음 세 단계로 구성된다.

1. 분할(divide): 원래 문제를 같은 종류의 더 작은 부분 문제 여러 개로 나눈다.
2. 정복(conquer): 각 부분 문제를 재귀적으로 푼다. 부분 문제가 충분히 작아지면(기저 사례, base case) 더 나누지 않고 직접 답을 구한다.
3. 결합(combine): 부분 문제들의 답을 모아 원래 문제의 답을 만든다.

07편의 병합 정렬로 이 세 단계를 다시 확인하면, 분할은 “배열을 절반으로 나누는 것”, 정복은 “각 절반을 재귀적으로 정렬하는 것”, 결합은 “정렬된 두 절반을 하나로 병합하는 것”이다. 반면 퀵 정렬은 분할 단계(피벗 기준으로 나누기)에서 대부분의 일을 끝내고 결합 단계는 사실상 아무 일도 하지 않는다는 점이 병합 정렬과 대조적이다.

대표 예제 1 — 빠른 거듭제곱 계산

거듭제곱 $a^n$을 계산하는 가장 단순한 방법은 $a$를 $n$번 곱하는 것으로, $O(n)$번의 곱셈이 필요하다. 분할정복을 적용하면 이를 $O(\log n)$으로 줄일 수 있다.

핵심 아이디어는 $a^n$을 절반 크기의 거듭제곱으로 표현하는 것이다.

• $a^{n/2}$: 지수를 절반으로 줄인 부분 문제. 이 값을 한 번만 계산하고 제곱해서 재사용하는 것이 핵심이다(만약 $a^{n/2}$을 두 번 따로 계산하면 나이브 방식과 다를 게 없어진다).
• $n$이 홀수일 때는 짝을 맞추기 위해 $a$ 하나를 따로 곱해 준다.

Power(a, n):
  만약 n == 0이면 1을 반환한다  (기저 사례)
  절반값 = Power(a, n을 2로 나눈 몫)   (분할 + 정복: 절반 크기 부분 문제를 재귀로 품)
  만약 n이 짝수이면 절반값 × 절반값을 반환한다        (결합)
  그렇지 않으면(n이 홀수) a × 절반값 × 절반값을 반환한다  (결합)

작은 예시로 추적하기

$3^{13}$을 계산하는 과정을 재귀 호출 트리로 추적한다.

호출 순서를 보면 $13 \to 6 \to 3 \to 1 \to 0$으로, 매 호출마다 $n$이 대략 절반으로 줄어든다. 실제로 $3^{13} = 1{,}594{,}323$이 맞는지는 $3^{13} = 3^8 \times 3^4 \times 3^1$로 검산할 수 있다. 나이브 방식이라면 곱셈을 12번 해야 했을 자리를, 분할정복은 재귀 호출 4번(그리고 각 단계에서 곱셈 1~2번)만으로 끝낸다.

쉽게 말하면: 지수를 계속 반으로 접어 나가면서, “절반을 한 번만 계산하고 제곱해서 재사용”하는 것이 곱셈 횟수를 크게 줄이는 비결이다.

대표 문제 2 — 최근접 점 쌍 문제(개요)

평면 위에 점이 $n$개 있을 때 서로 가장 가까운 두 점을 찾는 최근접 점 쌍(closest pair of points) 문제도 분할정복으로 풀 수 있는 대표적인 문제다. 모든 점 쌍의 거리를 다 재는 나이브 방식은 $O(n^2)$이 걸리지만, 분할정복은 다음과 같은 흐름으로 이를 줄인다.

• 분할: 점들을 x좌표 기준으로 정렬한 뒤, 중간을 기준으로 왼쪽 절반과 오른쪽 절반으로 나눈다.
• 정복: 각 절반에서 재귀적으로 최근접 점 쌍을 구한다.
• 결합: 왼쪽과 오른쪽 최솟값 중 더 작은 값을 $d$라 하고, 경계선 근처 폭 $2d$ 안에 있는 점들만 따로 모아 그 안에서만 추가로 거리를 비교한다(경계 안의 점들만 보면 되므로 이 결합 단계가 $O(n)$에 끝난다는 것이 이 알고리즘의 정교한 부분이다).

이 문제는 독학사 시험에서 알고리즘을 직접 손코딩하기보다는 “분할정복으로 $O(n \log n)$에 풀 수 있는 대표적인 기하 문제”라는 존재와 흐름 정도를 알아 두면 충분하다.

점화식 세우기와 마스터 정리

분할정복 알고리즘의 시간 복잡도는 대부분 다음과 같은 형태의 점화식으로 나타난다(04편에서 다룬 점화식 기초를 분할정복에 적용한다).

• $a$: 한 번의 호출에서 만들어지는 부분 문제의 개수.
• $n/b$: 부분 문제 하나의 크기(원래 크기를 $b$로 나눈 것).
• $O(n^d)$: 분할과 결합에 드는 비용(재귀 호출 자체를 제외한 비용).

마스터 정리(master theorem)는 $a$, $b$, $d$ 세 값만으로 $T(n)$의 점근적 표기를 바로 구할 수 있게 해 준다. $\log_b a$(밑이 $b$인 $a$의 로그, “부분 문제 개수가 부분 문제 크기의 몇 제곱에 해당하는 속도로 늘어나는가”를 나타내는 지수)와 $d$를 비교한다.

적용 예 1 — 병합 정렬

병합 정렬(07편)의 점화식은 $T(n) = 2T(n/2) + O(n)$이다. 여기서 $a=2$, $b=2$, $d=1$이다.

$\log_b a = 1$이고 $d = 1$이므로 두 값이 같은 경우(두 번째 경우)에 해당해, $T(n) = O(n^1 \log n) = O(n \log n)$이다. 이는 07편에서 재귀 트리로 직접 유도했던 결과와 정확히 일치한다.

적용 예 2 — 빠른 거듭제곱

빠른 거듭제곱의 점화식은 $T(n) = T(n/2) + O(1)$이다. 여기서 $a=1$, $b=2$, $d=0$(분할·결합에 드는 비용이 지수·곱셈 한 번이라는 상수 시간이므로 $n^0$).

$\log_b a = 0$이고 $d = 0$이므로 역시 두 번째 경우에 해당해, $T(n) = O(n^0 \log n) = O(\log n)$이다. 앞서 추적표에서 호출 4번($13\to6\to3\to1\to0$)만으로 끝난 것이 바로 이 $O(\log n)$의 실제 모습이다.

자주 틀리는 점: 마스터 정리를 적용할 때 $d$를 “재귀 호출 자체를 포함한 전체 비용”으로 잘못 넣는 실수가 잦다. $d$는 분할과 결합에만 드는 비용(재귀 호출 부분을 뺀 나머지)이어야 한다. 병합 정렬에서 $d=1$인 것은 “두 배열을 병합하는 데 드는 $O(n)$“만을 가리키며, 재귀로 절반씩 정렬하는 비용은 $a \times T(n/b)$ 항이 이미 따로 표현하고 있다.

분할정복의 장단점과 시험 포인트

자주 틀리는 점: “분할정복은 항상 효율적이다”라고 단정하면 안 된다. 부분 문제들이 서로 겹쳐서(예: 피보나치 수를 단순 재귀로 계산하면 같은 부분 문제를 지수적으로 반복 계산하게 됨) 오히려 비효율적인 경우도 있으며, 이런 경우는 16편의 동적계획법으로 부분 문제의 답을 저장해 재사용하는 편이 낫다.

핵심 정리

• 분할정복은 분할(작은 부분 문제로 나누기), 정복(부분 문제를 재귀로 풀기), 결합(부분 문제의 답을 합치기)의 세 단계로 이루어진다.
• 빠른 거듭제곱 $a^n$은 절반 크기의 거듭제곱을 한 번만 계산해 제곱함으로써 $O(\log n)$에 계산할 수 있다.
• 분할정복 알고리즘의 점화식 $T(n) = aT(n/b) + O(n^d)$은 마스터 정리로 $\log_b a$와 $d$를 비교해 $O(n^d)$, $O(n^d \log n)$, $O(n^{\log_b a})$ 중 하나로 정리된다.
• 부분 문제가 서로 독립적일 때는 분할정복이 유리하지만, 부분 문제가 겹칠 때는 동적계획법이 더 효율적일 수 있다.

마무리 복습

참고 자료

• 설계기법 강의노트 - Divide and Conquer (GeeksforGeeks)  — 분할정복의 일반 패턴, 대표 예제, 마스터 정리 적용법을 정리한 자료.
• 국가평생교육진흥원 독학학위제  — 독학사 4단계 알고리즘 과목의 최신 출제기준·평가영역 확인용 공식 안내.