분할 정복

분할 정복(Divide and Conquer)은 그대로는 풀기 어려운 문제를 같은 형태의 더 작은 문제로 쪼개 해결하는 방법이다. 대표적인 예로 병합 정렬, 퀵 정렬, 이분 탐색, 거듭제곱 빠르게 계산하기, 고속 푸리에 변환(FFT) 등이 있다.

세 단계

Divide(분할): 원래 문제를 비슷한 유형의 더 작은 하위 문제로 나눈다.
Conquer(정복): 하위 문제를 재귀적으로 푼다. 더 나눌 수 없을 만큼 작아지면(종료 조건) 직접 푼다.
Combine(결합): 하위 문제의 답을 합쳐 원래 문제의 답을 만든다.

분할 정복 과정

분할을 잘 설계하면 정복은 자연스럽게 쉬워진다. 그래서 어떻게 나눌지가 가장 중요하다.

특징

나뉜 문제는 원래 문제와 성격이 같고 입력 크기만 작다.
나뉜 문제들은 서로 독립적이다. 같은 하위 문제가 반복해서 등장하지 않는다. (반복해서 등장한다면 동적 계획법을 쓴다.)
보통 하위 문제를 두 개 이상 만들기 때문에 재귀 호출이 여러 갈래로 뻗는다.

장점	단점
재귀(Top-down)로 구현해 코드가 직관적이다.	재귀 호출 오버헤드가 생긴다.
하위 문제가 독립적이라 병렬로 처리하기 좋다.	재귀가 깊으면 스택 메모리를 많이 쓰고, 스택 오버플로우가 날 수 있다.

대표 예시

병합 정렬과 퀵 정렬

병합 정렬: 결합에서 작업한다. 균등하게 둘로 나누고, 정렬된 두 리스트를 합칠 때 비교가 일어난다. 항상 O(n log n).
퀵 정렬: 분할에서 작업한다. 피벗 기준으로 나눌 때 비교가 일어나고, 결합은 이어 붙이기뿐이다. 평균 O(n log n), 최악 O(n²).

자세한 동작과 비교는 병합 정렬과 퀵 정렬에 있다.

이진 탐색

정렬된 배열을 반으로 나눈 뒤 한쪽만 계속 탐색한다. 하위 문제가 하나뿐인 분할 정복(감소 정복)으로 볼 수 있다. O(log n).

거듭제곱 빠르게 계산하기

xⁿ = (x^(n/2))² 임을 이용하면 곱셈을 O(log n)번만 하면 된다.

def power(x, n):
    if n == 0:
        return 1
    half = power(x, n // 2)
    if n % 2 == 0:
        return half * half
    return half * half * x
 
print(power(2, 10))  # 1024

시간 복잡도: 점화식으로 구하기

분할 정복의 실행 시간은 자기 자신을 부르는 꼴의 점화식으로 나온다. 크기 n인 문제를 크기 n/b인 하위 문제 a개로 나누고, 나누기와 합치기에 f(n)이 들면 다음과 같다.

T(n) = a·T(n/b) + f(n)
 
병합 정렬   T(n) = 2T(n/2) + Θ(n)   절반 둘, 합치기 선형
이진 탐색   T(n) = T(n/2) + Θ(1)    절반 하나만
퀵 정렬 최악 T(n) = T(n-1) + Θ(n)    한쪽이 텅 빈 분할

점화식을 푸는 방법은 세 가지다.

방법	하는 일	예
반복 대입	T(n/b)에 점화식을 거듭 넣어 펼친 뒤 기저까지 더한다	`2T(n/2) + n`을 k번 펼치면 `2ᵏ·T(n/2ᵏ) + k·n`. k = log n이면 `n + n log n` = Θ(n log n)
추정 후 증명	답을 짐작하고 수학적 귀납법으로 `T(n) ≤ c·g(n)`을 보인다	`2T(n/2) + n ≤ cn log n`을 가정해 대입하면 c ≥ 1에서 성립한다
마스터 정리	f(n)과 h(n) = n^(log_b a)의 크기만 비교한다	아래 표

h(n) = n^(log_b a)는 재귀 트리의 잎(기저 문제) 개수다. 마스터 정리는 잎에서 드는 일과 각 단계의 나누기·합치기 일 f(n) 중 어느 쪽이 지배하는지를 본다.

경우	조건	결과
잎이 지배	어떤 ε > 0에 대해 f(n) = O(h(n) / n^ε)	T(n) = Θ(h(n))
균형	f(n) = Θ(h(n))	T(n) = Θ(h(n)·log n)
합치기가 지배	f(n) = Ω(h(n)·n^ε)이고, 충분히 큰 n에서 a·f(n/b) ≤ c·f(n) (c < 1)	T(n) = Θ(f(n))

2T(n/3) + c: h(n) = n^(log₃2) ≈ n^0.63이 상수 f를 이긴다 → Θ(n^(log₃2))
2T(n/2) + n: h(n) = n = f(n) → Θ(n log n). 병합 정렬이다
2T(n/4) + n: h(n) = √n보다 f(n) = n이 크다 → Θ(n)

T(n-1) + n처럼 크기가 비율이 아니라 빼기로 줄면 마스터 정리를 쓸 수 없다. 이때는 반복 대입으로 n + (n-1) + … + 1 = Θ(n²)을 얻는다. 퀵 정렬의 최악이 이 꼴이다. 피보나치처럼 상수 계수 선형 점화식은 선형 점화식의 일반항으로 푼다.

핵심 정리

분할 → 정복 → 결합, 하위 문제는 서로 독립적
하위 문제가 겹치면 동적 계획법, 겹치지 않으면 분할 정복
병합 정렬, 퀵 정렬, 이진 탐색, 빠른 거듭제곱이 대표 예시
실행 시간은 T(n) = a·T(n/b) + f(n) 꼴 점화식이고, f(n)과 n^(log_b a)를 비교하는 마스터 정리로 대부분 바로 푼다

버그 제보