분할 정복

분할 정복은 큰 문제를 같은 모양의 작은 문제로 쪼개서 풉니다. 작은 문제의 답을 모아 원래 문제의 답을 만듭니다. 쪼갠 조각이 충분히 작아지면 바로 풀 수 있다는 점을 이용합니다. 병합 정렬과 이진 탐색이 이 방식으로 짠 알고리즘입니다.

상세

분할 정복(divide and conquer)은 알고리즘을 짜는 한 가지 방식입니다. 문제 하나를 푸는 특정한 절차가 아닙니다. 여러 알고리즘이 함께 쓰는 뼈대입니다.

이 절은 먼저 그 뼈대를 이루는 세 단계를 봅니다. 다음으로 뼈대를 코드로 적는 법을 봅니다. 이어서 이 방식으로 짠 알고리즘 셋을 비교하고, 비용을 재는 법과 이 방식이 안 맞는 문제를 봅니다. 끝으로 조각을 여러 코어와 디스크로 나눠 맡기는 법을 봅니다.

나누기 · 풀기 · 합치기

분할 정복은 세 단계를 밟습니다. 먼저 문제를 같은 모양의 작은 문제로 나눕니다. 작은 문제를 각각 풉니다. 마지막으로 작은 답들을 합쳐 원래 문제의 답을 만듭니다.

이름의 「분할」이 나누기이고 「정복」이 작은 문제를 푸는 단계입니다. 합치기는 이름에 없어도 세 단계 가운데 하나입니다. 알고리즘에 따라서는 합치기에 할 일이 거의 없기도 합니다.

「같은 모양」이 핵심입니다. 카드 여덟 장을 정렬하는 문제를 반으로 나누면 카드 네 장을 정렬하는 문제 둘이 됩니다. 크기만 줄었고 할 일은 같습니다. 그래서 작은 문제를 풀 때도 같은 세 단계를 다시 밟을 수 있습니다.

나누기를 되풀이하면 언젠가 더 나눌 필요가 없는 크기에 닿습니다. 카드 한 장짜리 묶음은 이미 정렬돼 있습니다. 이렇게 바로 답이 나오는 가장 작은 경우를 기저 사례(base case)라고 합니다. 기저 사례가 있어야 나누기가 끝납니다.

한 문제를 받았을 때 거치는 흐름을 그리면 아래와 같습니다. 나눠서 생긴 작은 문제 하나하나가 이 그림을 맨 위에서부터 다시 밟습니다.

flowchart TD
    A["문제 하나"] --> B{"바로 풀 만큼 작은가"}
    B -->|예| C["바로 푼다 · 기저 사례"]
    B -->|아니오| D["같은 모양의 작은 문제로 나눈다"]
    D --> E["작은 문제를 각각 맨 위에서부터 다시 푼다"]
    E --> F["작은 답들을 합친다"]

재귀로 적는 법

작은 문제가 원래 문제와 모양이 같으므로 코드도 같은 함수를 다시 부르면 됩니다. 함수가 자기 자신을 부르는 것을 재귀라고 합니다. 분할 정복은 대개 재귀 함수로 적습니다.

아래는 수 목록의 합을 분할 정복으로 구하는 함수입니다. 목록을 반으로 나눠 반마다 합을 구하고 두 합을 더합니다. 원소가 하나면 그 원소가 곧 합이라 바로 돌려줍니다.

def total(xs):
    if len(xs) == 1:
        return xs[0]
    mid = len(xs) // 2
    left = total(xs[:mid])
    right = total(xs[mid:])
    return left + right

total([3, 1, 4, 1])  # 9
total([3, 1])        # 4
total([4, 1])        # 5

첫 if 두 줄이 기저 사례입니다. 가운데 세 줄이 나누기와 풀기입니다. 마지막 return 이 합치기입니다. [3, 1, 4, 1] 은 [3, 1] 과 [4, 1] 로 나뉘어 각각 4 와 5 가 됩니다. 둘을 더하면 9 가 나옵니다.

재귀로 부른 함수는 끝날 때까지 호출 스택에 쌓입니다. 호출 스택은 아직 안 끝난 함수 호출을 순서대로 기억해 두는 메모리 영역입니다. 호출이 너무 깊게 쌓이면 이 메모리가 바닥나 프로그램이 멈춥니다.

반씩 나누면 쌓이는 깊이가 얕습니다. 원소 백만 개도 스무 번쯤 반으로 나누면 한 개가 됩니다. 그래서 호출도 스무 개 남짓만 쌓입니다.

합계는 분할 정복의 모양을 보이려고 고른 예입니다. 목록을 앞에서부터 한 번 훑어도 합은 나오고, 더하는 횟수도 같습니다. 나눠서 일이 줄어드는 경우는 다음 소절의 알고리즘들입니다.

이 방식으로 짠 알고리즘 셋

분할 정복으로 짠 알고리즘은 세 단계 가운데 어디에 일이 몰리는지가 서로 다릅니다. 널리 쓰는 셋을 비교하면 아래 표와 같습니다.

병합 정렬은 나누기가 쉽고 합치기에 일이 몰립니다. 퀵 정렬은 반대입니다. 가를 때 작은 것은 앞에, 큰 것은 뒤에 모아 두므로 두 쪽을 정렬하고 나면 더 할 일이 없습니다. 퀵 정렬에서 가르는 기준값을 피벗(pivot)이라고 부릅니다.

이진 탐색은 문제를 둘로 나누고도 하나만 풉니다. 목록이 정렬돼 있으면 가운데 값과 한 번 비교해 한쪽 반을 버릴 수 있습니다. 찾는 값이 가운데 값보다 크면 왼쪽 반에는 없으니 오른쪽 반만 봅니다. 작으면 반대로 왼쪽 반만 봅니다.

병합 정렬은 나눈 작은 문제를 둘 다 풀지만 이진 탐색은 하나만 남깁니다. 작은 문제 하나만 남기는 이 방식을 감소 정복(decrease and conquer)이라고 따로 부르기도 합니다.

비용을 재는 법

분할 정복 알고리즘의 비용은 나누기가 만드는 레벨을 따라 세면 나옵니다. 이 소절은 병합 정렬로 두 가지를 셉니다. 한 레벨을 합치는 데 드는 일과 합치기를 몇 번 하는지입니다.

나누기 전의 배열 전체가 레벨 0 입니다. 반으로 한 번 나눌 때마다 레벨이 하나 늘어납니다. 한 레벨 내려갈 때마다 조각 수는 두 배가 됩니다. 조각 크기는 반이 됩니다.

flowchart TD
    subgraph L0["레벨 0 · 조각 1개 · 원소 수 8"]
        A["5 2 7 1 6 3 8 4"]
    end
    subgraph L1["레벨 1 · 조각 2개 · 원소 수 8"]
        B1["5 2 7 1"]
        B2["6 3 8 4"]
    end
    subgraph L2["레벨 2 · 조각 4개 · 원소 수 8"]
        C1["5 2"]
        C2["7 1"]
        C3["6 3"]
        C4["8 4"]
    end
    subgraph L3["레벨 3 · 조각 8개 · 원소 수 8"]
        D["한 칸짜리 조각 8개"]
    end
    A --> B1
    A --> B2
    B1 --> C1
    B1 --> C2
    B2 --> C3
    B2 --> C4
    C1 --> D
    C2 --> D
    C3 --> D
    C4 --> D

조각 수가 두 배가 되는 동안 크기는 반이 됩니다. 그래서 레벨마다 원소 수는 모두 8 로 같습니다. 병합 정렬은 아래 레벨의 조각을 둘씩 합쳐 한 레벨 위의 조각을 만듭니다. 한 레벨을 합치는 데 드는 일은 원소 수에 비례하므로 합칠 때마다 드는 일도 같습니다.

합치기는 레벨과 레벨 사이에서 한 번씩 일어납니다. 그러니 셀 것은 레벨의 수가 아니라 한 레벨씩 내려간 횟수입니다. 그림은 레벨 0 부터 레벨 3 까지 네 레벨이고, 그 사이를 세 번 내려갑니다. 8 을 반으로 세 번 나누면 1 이 되는 것과 같습니다(8 → 4 → 2 → 1).

이 횟수를 로그로 적어 log₂ 8 = 3 이라고 씁니다. 원소가 n 개면 합치기는 log₂ n 번 일어납니다. 이제부터는 밑 2 를 빼고 줄여서 log n 이라고 적습니다.

입력이 커질 때 드는 일이 어떤 빠르기로 느는지를 적는 표기가 빅오 표기법입니다. 병합 정렬은 한 번 합칠 때마다 n 만큼 일합니다. 합치기가 log n 번이므로 전체 일은 n log n 에 비례합니다. 빅오 표기법으로 O(n log n) 이라고 적습니다.

이 차이는 입력이 클수록 벌어집니다. 카드를 한 장씩 앞의 카드들과 비교해 끼워 넣는 삽입 정렬은 최악에 O(n²) 입니다. n 이 1,024 면 n² 은 백만이 넘고 n log n 은 1만 남짓입니다.

이런 계산은 흔히 점화식으로 적습니다. 점화식은 크기 n 의 비용을 더 작은 크기의 비용으로 적은 식입니다. 크기 n 문제를 푸는 비용을 T(n) 이라고 쓰면 병합 정렬은 T(n) = 2T(n/2) + n 입니다. 절반 크기 문제 둘을 푸는 비용에 합치는 비용 n 을 더한다는 뜻입니다.

이진 탐색은 T(n) = T(n/2) + 1 입니다. 반 하나만 풀고 비교 한 번을 더하므로 한 레벨 내려갈 때마다 드는 일이 1 입니다. 내려가는 횟수가 log n 번이라 전체는 O(log n) 입니다. 이런 꼴의 점화식을 한 번에 푸는 공식이 마스터 정리입니다.

고르게 못 나눌 때

내려가는 횟수를 log n 으로 세는 계산은 반으로 고르게 나눴을 때 성립합니다. 퀵 정렬에서 피벗이 가장 작은 값이면 한쪽이 빕니다. 다른 쪽에는 원소가 하나만 줄어든 채로 남습니다.

이 치우침이 매번 이어지면 원소를 하나씩만 덜어 내므로 n 번쯤 내려가야 끝납니다. 내려갈 때마다 가르는 일은 남은 원소 수만큼 들어서 비용은 O(n²) 입니다. 퀵 정렬의 최악이 이 경우입니다.

내려가는 횟수가 늘면 호출 스택도 그만큼 깊어집니다. n 번 내려가면 쌓이는 호출도 n 개입니다. 호출 스택에 쓸 메모리가 바닥나 프로그램이 멈추는 오류를 스택 오버플로라고 합니다. 입력이 크면 이 오류가 날 수 있습니다.

작은 문제가 겹칠 때

분할 정복은 작은 문제끼리 서로 독립이라고 봅니다. 병합 정렬의 왼쪽 반과 오른쪽 반은 겹치는 원소가 없습니다. 반마다 한 번씩만 풀면 됩니다.

피보나치 수열은 이 전제가 깨지는 예입니다. 피보나치 수열은 앞의 두 수를 더해 다음 수를 만드는 수열입니다. n 번째 수를 구하려면 n−1 번째와 n−2 번째가 필요합니다. 그런데 n−1 번째를 구할 때도 n−2 번째가 또 필요합니다.

이 수열을 분할 정복처럼 재귀로 짜면 같은 작은 문제를 몇 번이고 다시 풉니다. 다시 푸는 횟수는 n 이 커질수록 불어나서 비용이 지수로 늡니다.

이런 문제는 한 번 푼 답을 버리지 않고 다시 쓰는 기법이 맡습니다. 메모이제이션은 한 번 푼 답을 기억해 두었다가 같은 문제가 오면 꺼내 씁니다. 동적 계획법은 작은 답부터 표에 채워 올라가 큰 답을 만듭니다.

조각을 따로 돌리기

이 소절은 나눈 조각을 따로 돌리는 두 경우를 봅니다. 하나는 여러 코어에서 조각을 동시에 푸는 경우입니다. 다른 하나는 메모리에 다 안 들어가는 데이터를 조각씩 정렬하는 경우입니다.

작은 문제끼리 독립이면 동시에 풀어도 됩니다. 왼쪽 반과 오른쪽 반을 서로 다른 코어에 맡깁니다. 둘 다 끝나면 합칩니다. 앞의 합계 함수도 이렇게 나누면 여러 코어가 일을 나눠 맡습니다.

일을 쪼개 여러 작업으로 띄우고(fork) 모두 끝나기를 기다려 합치는(join) 방식을 fork-join이라고 부릅니다. 분할 정복의 나누기와 합치기를 병렬 실행으로 옮긴 모양입니다.

메모리에 다 안 들어가는 데이터를 정렬할 때도 같은 생각을 씁니다. 데이터를 메모리에 들어가는 조각으로 나눠 조각마다 정렬해 디스크에 적습니다. 그다음 정렬된 조각들을 병합 정렬의 합치기처럼 앞에서부터 비교하며 합칩니다. 이 방식을 외부 정렬이라고 합니다.

관련 항목

분할 정복으로 짠 알고리즘

병합 정렬 · 퀵 정렬 · 이진 탐색 · 카라츠바 알고리즘 · 슈트라센 알고리즘 · 고속 푸리에 변환 · 최근접 점쌍 문제

분할 정복과 나란히 쓰는 설계 기법

감소 정복 · 그리디 알고리즘 · 완전 탐색 · 재귀 백트래킹 · 분기 한정

작은 문제가 겹칠 때 넘어가는 기법

동적 계획법 · 메모이제이션 · 중복 부분 문제 · 피보나치 수열

분할 정복의 비용을 재는 도구

점화식 · 마스터 정리 · 재귀 트리 · 빅오 표기법 · 시간 복잡도 · 공간 복잡도

분할 정복을 코드로 받치는 구조

재귀 · 기저 사례 · 호출 스택 · 스택 오버플로 · 꼬리 재귀

분할 정복을 여러 코어와 디스크로 넓힌 방식

병렬성 · fork-join · 작업 훔치기 · MapReduce · 외부 정렬

분할 정복이 속하는 상위 분류

알고리즘 · 알고리즘 설계 기법 · 정렬 알고리즘 · 탐색 알고리즘