분할 정복의 개념

분할 정복(divide and conquer)은 문제를 같은 모양의 더 작은 문제로 나누고, 작은 문제를 재귀적으로 푼 다음, 그 답을 모아 원래 문제의 답을 만드는 알고리즘 설계 방법입니다. 병합 정렬, 이진 탐색, 빠른 거듭제곱, 퀵셀렉트, 카라추바 곱셈, FFT가 모두 이 틀을 따릅니다. 이 틀을 알아보는 눈이 생기면 O(n^2)이 필요해 보이던 문제를 O(n log n)이나 그보다 빠르게 푸는 경우가 많아집니다.

세 단계

1. 분할(divide): 입력을 부분 문제로 나눕니다. 보통 크기가 비슷하게, 가장 흔하게는 절반씩 나눕니다.
2. 정복(conquer): 각 부분 문제를 재귀적으로 풉니다. 충분히 작아진 부분 문제(기저 사례)는 바로 답을 냅니다.
3. 합치기(combine): 부분 문제의 답으로 전체 입력의 답을 만듭니다.

알고리즘마다 실제 일이 몰리는 단계가 다릅니다. 병합 정렬은 나누기가 간단하고(가운데에서 자름) 정렬된 두 절반을 합치는 병합이 핵심입니다. 퀵 정렬과 퀵셀렉트는 반대로 피벗을 기준으로 나누는 분할이 핵심이고 합치기에는 비용이 들지 않습니다.

def max_value(a, lo, hi):
    """a[lo:hi](비어 있지 않음)의 최댓값을 분할 정복으로 구한다."""
    if hi - lo == 1:                         # 기저 사례: 원소 하나
        return a[lo]
    mid = (lo + hi) // 2                     # 분할
    left = max_value(a, lo, mid)             # 정복
    right = max_value(a, mid, hi)
    return left if left >= right else right  # 합치기

print(max_value([3, 9, 2, 7, 5], 0, 5))  # 9

단순한 반복문보다 빠르지는 않지만, 모든 분할 정복 알고리즘이 공유하는 뼈대인 기저 사례, 분할, 재귀 호출, 합치기를 한눈에 보여 줍니다.

용어

감소 정복

부분 문제 중 하나만 남기고 나머지를 버리는 알고리즘도 있습니다. 이진 탐색은 가운데 원소와 비교한 뒤 한쪽 절반에서만 계속 찾으므로, 남은 범위가 기하급수적으로 줄어 전체 작업이 O(log n)이 됩니다.

def binary_search(a, target):
    lo, hi = 0, len(a)              # a[lo:hi] 안에서 찾는다
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < target:
            lo = mid + 1            # 오른쪽 절반만 남긴다
        else:
            hi = mid                # 왼쪽 절반만 남긴다
    return lo if lo < len(a) and a[lo] == target else -1

print(binary_search([1, 3, 5, 7, 9, 11], 7))  # 3

언제 분할 정복을 쓰는가

부분 문제끼리 서로 독립이고, 합치는 비용이 전체를 처음부터 푸는 비용보다 작을 때 잘 맞습니다. 다음과 같은 신호가 보이면 분할 정복을 떠올려 봅니다.

• 입력이 자연스럽게 나뉩니다. 배열의 두 절반, 수의 상위·하위 자릿수, 평면의 왼쪽·오른쪽이 그렇습니다.
• 전체의 답이 부분의 답과 경계를 가로지르는 정보로 만들어집니다. 경계를 사이에 둔 쌍이나 가운데를 지나는 부분 배열이 그 예입니다.
• 부분 문제끼리 겹치지 않아서 각 부분 문제를 정확히 한 번만 풉니다.

부분 문제가 겹치면 단순한 재귀는 같은 일을 지수적으로 되풀이합니다. 대표적인 경고 신호가 순진한 피보나치 함수로, fib(n - 1)과 fib(n - 2)가 모두 fib(n - 3) 아래를 다시 계산합니다. 이런 경우에는 분할 정복이 아니라 메모이제이션이나 표를 쓰는 동적 계획법이 필요합니다.

calls = 0

def fib(n):
    global calls
    calls += 1
    return n if n < 2 else fib(n - 1) + fib(n - 2)

fib(25)
print(calls)  # 242785번 호출: 부분 문제가 겹친다는 신호

대표 예 한눈에 보기

정리

• 분할 정복은 나누고, 재귀적으로 풀고, 합치는 세 단계로 이루어집니다.
• 기저 사례가 재귀를 멈추고, 대개 합치기 단계가 전체 비용을 결정합니다.
• 부분 문제를 하나만 남기는 감소 정복은 로그 시간이나 선형 시간 알고리즘으로 이어집니다.
• 부분 문제가 독립이면 분할 정복, 겹치면 동적 계획법이 알맞습니다.