분할 정복

분할 정복은 큰 문제를 같은 모양의 작은 문제로 쪼개서 풉니다. 작은 문제들의 답을 모아 원래 문제의 답을 만듭니다. 풀 문제 하나를 넣으면 그 문제의 답이 나옵니다. 병합 정렬과 이진 탐색이 이 방식으로 짠 알고리즘입니다.

상세

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

뼈대는 이렇습니다. 문제가 쉬우면 바로 풉니다. 대개는 크기가 작아서 쉽습니다. 쉽지 않으면 둘 이상의 작은 문제로 나눕니다.

나눈 작은 문제는 같은 방식으로 다시 풉니다. 그 답들을 합쳐 원래 문제의 답을 만듭니다. 나누기 · 풀기 · 합치기, 이 세 단계가 뼈대의 전부입니다.

카드 여덟 장을 정렬하는 문제를 반으로 나누면 카드 네 장을 정렬하는 문제 둘이 됩니다. 크기만 줄었습니다. 할 일은 같습니다. 네 장짜리도 다시 반으로 나눌 수 있습니다.

같은 모양과 재귀

「같은 모양」이 이 방식의 핵심입니다. 작은 문제가 원래 문제와 모양이 같으므로 같은 풀이를 다시 쓸 수 있습니다. 코드로는 같은 함수를 다시 부르면 됩니다.

함수가 자기 자신을 부르는 것을 재귀(recursion)라고 합니다. 분할 정복은 대개 재귀 함수로 적습니다. 작은 문제 하나하나가 재귀 호출 하나입니다.

기저 사례

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

기저 사례가 있어야 나누기가 끝납니다. 기저 사례가 없으면 재귀 호출이 끝없이 이어집니다.

이름

「분할」은 나누기입니다. 「정복」은 작은 문제를 푸는 단계입니다. 문제를 여러 작은 문제로 나눠서 정복한다는 뜻으로 붙은 이름입니다. 합치기는 이름에 없어도 세 단계 가운데 하나입니다.

작은 문제끼리는 독립이다

분할 정복은 작은 문제끼리 서로 독립이라고 봅니다. 카드 앞 넷과 뒤 넷에는 겹치는 카드가 없습니다. 작은 문제마다 한 번씩만 풀면 됩니다.

독립이면 순서도 상관없습니다. 앞 넷을 먼저 풀든 뒤 넷을 먼저 풀든 답이 같습니다. 두 묶음을 서로 다른 코어에서 동시에 풀어도 됩니다.

왜 쪼개나

정렬처럼 한 번에 풀면 비싼 문제가 있습니다. 카드를 한 장씩 앞의 카드들과 비교해 끼워 넣는 정렬을 보겠습니다. 이 정렬은 카드를 한 장과 나머지로 치우쳐 나누는 셈입니다. 카드가 거꾸로 놓인 최악에는 카드 수가 두 배가 될 때 비교 횟수가 네 배 가까이 늡니다. 카드가 이미 정렬돼 있으면 한 장에 한 번씩만 비교합니다.

반으로 고르게 나눠 각각 정렬한 뒤 합치면 비교가 그보다 훨씬 덜 늡니다. 정렬된 두 묶음은 맨 앞 카드끼리 비교해 작은 것을 하나씩 내려놓으면 합쳐집니다. 합치는 데 드는 비교는 카드 수를 넘지 않습니다.

쪼개서 이득이 나려면 세 조건이 함께 서야 합니다. 첫째, 한 번에 풀면 비싸야 합니다. 둘째, 한쪽으로 크게 치우치지 않게 나눌 수 있어야 합니다. 셋째, 합치기가 원소 수에 비례할 만큼 싸야 합니다. 얼마나 덜 느는지는 아래 복잡도 절에서 셉니다.

복잡도

분할 정복 알고리즘의 비용은 레벨마다 드는 일을 모두 더한 값입니다. 레벨은 문제를 한 번 나눌 때마다 하나씩 늘어나는 깊이입니다. 반씩 고르게 나누면 입력이 두 배가 될 때 레벨이 하나만 늘어납니다.

병합 정렬처럼 레벨마다 드는 일이 원소 수만큼으로 같으면 입력이 커져도 비용이 천천히 늡니다. 레벨마다 드는 일이 아래로 갈수록 일정 비율로 커지면 맨 아래 레벨이 비용을 정합니다. 위로 갈수록 일정 비율로 커지면 맨 위 레벨이 정합니다. 한쪽으로 크게 치우쳐 나누거나 작은 문제끼리 겹치면 이 계산이 무너집니다. 매번 한 원소만 떼어 내는 치우침이면 비용이 크게 늡니다.

이 절은 세 알고리즘으로 비용을 셉니다.

레벨을 따라 세기

나누기 전의 배열 전체가 레벨 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 로 같습니다.

병합 정렬은 아래 레벨의 조각을 둘씩 합쳐 한 레벨 위의 조각을 만듭니다. 레벨 2 의 조각 넷은 레벨 3 의 원소를 둘씩 합쳐 만듭니다. 레벨 1 과 레벨 0 도 같은 방법으로 만듭니다. 맨 아래 레벨 3 은 원소 하나짜리 조각이라 합칠 것이 없습니다.

합치는 일이 드는 레벨은 레벨 0 부터 레벨 2 까지 셋입니다. 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 개가 됩니다. 아래 「최악이 오는 조건」이 그 계산입니다.

점화식과 마스터 정리

이런 계산은 흔히 점화식으로 적습니다. 점화식은 크기 n 의 비용을 더 작은 크기의 비용으로 적은 식입니다. 크기 n 인 문제를 푸는 비용을 T(n) 이라고 쓰면 분할 정복의 비용은 아래 식이 됩니다.

T(n) = a · T(n/b) + f(n)

각 항이 세는 것은 이렇습니다.

a 는 1 이상, b 는 1 보다 큰 상수입니다. 병합 정렬은 T(n) = 2T(n/2) + n 입니다. 절반 크기 문제 둘을 푸는 비용에 합치는 비용 n 을 더한다는 뜻입니다. 이진 탐색은 T(n) = T(n/2) + 1 입니다. 반 하나만 풀고 비교를 한 번 더합니다.

이 점화식을 레벨마다 펼치면 아래 모양이 됩니다. 한 레벨 내려갈 때마다 조각 수는 a 배가 됩니다. 조각 크기는 1/b 이 됩니다.

flowchart TD
    subgraph R0["레벨 0 · 조각 1개 · 크기 n"]
        A["나누고 합치는 일 f(n)"]
    end
    subgraph R1["레벨 1 · 조각 a개 · 크기 n/b"]
        B["레벨의 일 합 a · f(n/b)"]
    end
    subgraph R2["레벨 2 · 조각 a²개 · 크기 n/b²"]
        C["레벨의 일 합 a² · f(n/b²)"]
    end
    subgraph RL["맨 아래 · 크기 1 · 기저 사례"]
        D["조각 n^(log_b a)개 · 일의 합도 n^(log_b a) 에 비례"]
    end
    A --> B
    B --> C
    C -->|"크기가 1 이 될 때까지 내려간다"| D

크기 n 이 1 이 되려면 b 로 log_b n 번 나눠야 합니다. 조각 수는 그동안 a 배씩 늘어 맨 아래에서 a^(log_b n) 개가 됩니다. 이 값은 n^(log_b a) 와 같습니다. 기저 사례 하나는 정해진 만큼만 일하므로 맨 아래 레벨의 일은 n^(log_b a) 에 비례합니다.

n^(log_b a) 는 n 을 「b 를 밑으로 한 a 의 로그」만큼 거듭제곱한 값입니다. 병합 정렬은 a 와 b 가 모두 2 입니다. log₂ 2 = 1 이라 n¹, 곧 n 입니다. 이진 탐색은 a 가 1 입니다. log₂ 1 = 0 이라 n⁰, 곧 1 입니다.

이런 점화식을 한 번에 푸는 공식이 마스터 정리입니다. 결론은 맨 위의 「나누고 합치는 일 f(n)」과 맨 아래 기저 사례들의 일 n^(log_b a) 가운데 어느 쪽이 더 빨리 느는지가 비용을 정한다는 것입니다.

첫째 줄의 합 구하기는 아래 동작 절에서 코드로 봅니다. 셋째 경우에는 조건이 하나 더 붙습니다. 아래 레벨로 갈수록 레벨마다 드는 일이 일정 비율 이상 줄어야 합니다. 식으로는 1 보다 작은 상수 c 에 대해 a · f(n/b) ≤ c · f(n) 입니다.

세 경우 사이에 끼는 f(n) 도 있습니다. 그런 점화식은 마스터 정리로 못 풀고 다른 방법으로 풉니다. 레벨마다 드는 일을 직접 더하는 것도 그 하나입니다.

최악이 오는 조건

레벨 수를 log n 으로 세는 계산은 조각 크기가 매번 일정 비율로 줄 때 성립합니다. 반으로 고르게 나누는 것이 그런 경우입니다. 퀵 정렬에서 기준값이 가장 작은 값이면 한쪽이 빕니다. 다른 쪽에는 원소가 하나만 줄어든 채로 남습니다.

flowchart TD
    subgraph S0["레벨 0"]
        A["원소 8개"]
    end
    subgraph S1["레벨 1"]
        B1["빈 쪽"]
        B2["원소 7개"]
    end
    subgraph S2["레벨 2"]
        C1["빈 쪽"]
        C2["원소 6개"]
    end
    subgraph SM["레벨 3 ~ 6 · 같은 모양이 이어진다"]
        M["원소 5개 → 4개 → 3개 → 2개"]
    end
    subgraph S7["레벨 7"]
        D["원소 1개"]
    end
    A --> B1
    A --> B2
    B2 --> C1
    B2 --> C2
    C2 --> M
    M --> D

이 치우침이 매번 이어지면 원소를 하나씩만 덜어 냅니다. 원소 8개를 반씩 나누면 레벨 3 에서 끝납니다. 이렇게 치우쳐 나누면 레벨 7 까지 내려갑니다. 원소가 n 개면 n 번쯤 내려가야 끝납니다.

내려갈 때마다 가르는 일은 남은 원소 수만큼 듭니다. 그 합이 n² 에 비례하므로 비용은 O(n²) 입니다. 퀵 정렬의 최악이 이 경우입니다. 한 장씩 떼어 내는 삽입 정렬이 최악에 O(n²) 인 것도 같은 치우침에서 옵니다.

병합 정렬은 늘 가운데를 자르므로 이런 치우침이 없습니다. 평균과 최악이 같습니다.

아래 표의 호출 스택은 아직 안 끝난 함수 호출을 순서대로 쌓아 두는 메모리 영역입니다. 아래 공간 소절에서 다시 봅니다.

작은 문제가 겹칠 때

작은 문제끼리 겹치면 같은 작은 문제를 여러 번 풉니다. 그만큼 비용이 불어납니다. 피보나치 수열처럼 지수로 불어나기도 합니다. 피보나치 수열은 앞의 두 수를 더해 다음 수를 만드는 수열입니다.

n 번째 수를 구하려면 n−1 번째와 n−2 번째가 필요합니다. 그런데 n−1 번째를 구할 때도 n−2 번째가 또 필요합니다. 이 수열을 분할 정복처럼 재귀로 짜면 같은 작은 문제를 몇 번이고 다시 풉니다. 다시 푸는 횟수는 n 이 커질수록 불어나서 비용이 지수로 늡니다.

이런 문제는 한 번 푼 답을 버리지 않고 다시 쓰는 기법이 맡습니다. 메모이제이션은 한 번 푼 답을 기억해 두었다가 같은 문제가 오면 꺼내 씁니다.

동적 계획법은 작은 답부터 표에 채워 올라가 큰 답을 만듭니다. 작은 문제가 겹치느냐가 분할 정복과 동적 계획법을 가르는 선입니다.

공간

재귀로 부른 함수는 끝날 때까지 호출 스택에 쌓입니다. 쌓이는 깊이는 내려가는 횟수와 같습니다.

반씩 고르게 나누면 깊이가 log n 이라 얕습니다. 원소 백만 개도 스무 번쯤 반으로 나누면 한 개가 됩니다. 치우쳐 나뉘어 n 번 내려가면 호출도 n 개 쌓입니다.

호출 스택에 쓸 메모리가 바닥나 프로그램이 멈추는 오류를 스택 오버플로라고 합니다. 입력이 크고 나누기가 치우치면 이 오류가 날 수 있습니다. 병합 정렬은 이와 따로 두 반쪽을 합칠 때 원소를 옮겨 둘 배열을 n 만큼 더 씁니다.

예시

분할 정복은 작은 문제끼리 독립이라는 전제 덕에 두 방향으로 넓혀 쓰입니다. 하나는 조각을 여러 코어에 나눠 동시에 푸는 것입니다. 다른 하나는 메모리에 다 안 들어가는 데이터를 조각씩 풀어 디스크에 두었다가 합치는 것입니다. 아래는 Java 표준 라이브러리와 PostgreSQL 에서 각각을 봅니다.

Java 의 Arrays.parallelSort

Java 21 의 Arrays.parallelSort 구현은 배열을 하위 배열로 나눠 각각 정렬한 뒤 합칩니다. 하위 배열 길이가 최소 단위(minimum granularity)에 닿으면 더 나누지 않고 Arrays.sort 로 정렬합니다. 이것이 기저 사례입니다. 배열이 처음부터 그 단위보다 짧으면 나누지 않고 바로 Arrays.sort 로 정렬합니다.

나눈 조각을 병렬로 실행하는 일은 ForkJoin 공용 풀(common pool)이 맡습니다. ForkJoin 은 일을 쪼개 작업으로 띄우고(fork) 결과가 나올 때까지 기다려 받는(join) 방식입니다. 이 구현이 쓰는 작업 공간은 원래 배열 크기를 넘지 않습니다.

Java 의 RecursiveAction 으로 짠 정렬

같은 라이브러리의 RecursiveAction 을 상속하면 분할 정복 정렬을 직접 짤 수 있습니다. 아래는 long[] 배열을 정렬하는 SortTask 의 compute() 와 기준 크기입니다.

protected void compute() {
  if (hi - lo < THRESHOLD)
    sortSequentially(lo, hi);
  else {
    int mid = (lo + hi) >>> 1;
    invokeAll(new SortTask(array, lo, mid),
              new SortTask(array, mid, hi));
    merge(lo, mid, hi);
  }
}
// implementation details follow:
static final int THRESHOLD = 1000;

기저 사례 확인과 세 단계가 코드 줄에 하나씩 대응합니다. 정렬할 원소가 THRESHOLD(1000)보다 적으면 sortSequentially 가 Arrays.sort 로 바로 정렬합니다. 이것이 기저 사례입니다. 아니면 가운데 mid 로 반을 가릅니다. 두 반쪽 작업은 invokeAll 에 넘깁니다. 마지막 merge 가 정렬된 두 반쪽을 합칩니다.

결과를 돌려주는 작업은 RecursiveTask 로 짭니다. 아래는 from 부터 to 까지의 곱을 반씩 나눠 구하는 팩토리얼 계산의 한 대목입니다.

FactorialTask leftTask = new FactorialTask(from, mid);
leftTask.fork();         // perform about half the work locally
return new FactorialTask(mid + 1, to).compute()
       .multiply(leftTask.join());

fork() 는 왼쪽 반을 비동기로 실행하도록 맡깁니다. 오른쪽 반은 지금 스레드가 compute() 로 직접 풉니다. join() 은 왼쪽 반의 결과가 계산될 때까지 기다렸다가 받습니다. 두 결과를 multiply 로 곱하는 것이 합치기입니다.

조각 크기에는 아주 대략적인 기준이 있습니다. 작업 하나가 기본 계산 단계를 100 번보다 많이, 10,000 번보다 적게 하는 것입니다. 작업이 너무 크면 병렬로 돌려도 처리량이 안 늡니다. 너무 작으면 메모리와 작업 관리 부담이 계산을 압도할 수 있습니다.

나눠 맡긴 작업은 다른 작업이 건드리는 변수와 완전히 독립된 변수만 건드리는 것이 이상적입니다. 상세 절의 「작은 문제끼리는 독립이다」가 코드에서는 이 조건이 됩니다.

PostgreSQL 의 외부 정렬

PostgreSQL 은 ORDER BY · DISTINCT · 병합 조인에 정렬을 씁니다. 병합 조인은 두 테이블을 같은 키로 정렬해 맞대어 잇는 조인입니다. 정렬이나 해시 테이블 같은 쿼리 연산 하나가 쓸 메모리의 기본 상한은 설정 work_mem 이 정합니다. 기본값은 4MB 입니다. 정렬이 이 값을 넘으면 임시 디스크 파일에 쓰기 시작합니다.

정렬 모듈 tuplesort.c 는 적은 데이터는 메모리 안에서 정렬합니다. 많은 데이터는 임시 파일과 표준 외부 정렬 알고리즘으로 정렬합니다. 외부 정렬은 메모리에 다 안 들어가는 데이터를 디스크를 써 가며 정렬하는 방식입니다.

외부 정렬은 이렇게 돕니다.

1. 행을 정렬 안 된 배열에 담습니다. 메모리 상한(대개 work_mem)을 넘기 전에 입력이 끝나면 메모리 안에서 정렬해 끝냅니다
2. 넘으면 행을 정렬된 조각(run)으로 만들어 임시 파일에 내보냅니다
3. 입력이 끝나면 메모리에 남은 행을 마지막 조각으로 내보냅니다
4. 조각들을 합칩니다. 힙은 가장 작은 값을 바로 꺼낼 수 있게 담아 두는 자료구조입니다. 조각마다 맨 앞 행만 힙에 담습니다. 힙에서 가장 작은 행을 내보내면 그 행이 나온 조각에 다음 행이 있을 때 그것으로 채웁니다. 힙이 비면 합치기가 끝납니다

분할 정복의 세 단계로 보면 나누기는 메모리가 찰 때마다 조각을 끊는 것입니다. 반씩 나누는 것이 아닙니다. 풀기는 조각마다 정렬하는 것입니다. 합치기는 조각 여럿을 한 번에 합치는 것입니다. PostgreSQL 은 이 합치기를 balanced k-way merge 라고 부릅니다. k-way 는 k 개 조각을 둘씩이 아니라 한꺼번에 합친다는 뜻입니다.

정렬이 메모리에서 끝났는지 디스크로 넘어갔는지는 EXPLAIN ANALYZE 의 Sort 노드에 찍힙니다.

Sort  (cost=713.05..713.30 rows=100 width=488) (actual time=2.995..3.002 rows=100.00 loops=1)
  Sort Key: t1.fivethous
  Sort Method: quicksort  Memory: 74kB

Sort Method 줄은 정렬 방식과 쓴 메모리나 디스크의 양을 보입니다. 위 출력은 메모리 안에서 quicksort 로 끝났습니다. 쓴 메모리는 74kB 입니다. quicksort 는 퀵 정렬이니 메모리 안의 정렬도 분할 정복입니다.

방식 이름은 still in progress · top-N heapsort · quicksort · external sort · external merge 다섯 가지 가운데 하나로 찍힙니다. 공간 종류는 Memory 나 Disk 로 찍힙니다. 디스크로 넘어간 정렬이면 공간 종류가 Disk 가 됩니다.

동작

이 절은 크기 n 인 문제 하나를 받았을 때 분할 정복이 거치는 단계와 끝나는 지점을 봅니다. 분할 정복은 내려가며 나눕니다. 맨 아래 기저 사례에서 바로 풉니다. 그 답을 들고 올라오며 합칩니다.

아래 흐름도가 호출 한 번입니다. 나눠서 생긴 작은 문제 하나하나가 이 흐름을 맨 위에서부터 다시 거칩니다.

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

흐름도를 번호로 옮기면 넷입니다. 1 번은 기저 사례인지 보는 갈림입니다. 2~4 번이 상세 절의 나누기 · 풀기 · 합치기 세 단계입니다.

1. 문제가 바로 풀 만큼 작은지 봅니다. 작으면 바로 풀어 답을 돌려주고 끝납니다
2. 작지 않으면 같은 모양의 작은 문제로 나눕니다
3. 작은 문제마다 1 번부터 다시 거칩니다
4. 작은 문제들이 돌려준 답을 합쳐 이 문제의 답으로 돌려줍니다

끝나는 지점은 1 번의 기저 사례뿐입니다. 3 번이 아무리 깊이 내려가도 맨 아래에서는 기저 사례에 닿습니다. 거기서 돌려준 답이 4 번을 거치며 한 레벨씩 위로 올라옵니다.

재귀로 적은 모양

아래는 수 목록의 합을 분할 정복으로 구하는 함수입니다. 목록 xs 에서 lo 부터 hi 바로 앞까지를 한 구간으로 맡습니다. 구간을 반으로 나눠 반마다 합을 구한 뒤 두 합을 더합니다.

def total(xs, lo, hi):
    if hi - lo == 1:
        return xs[lo]
    mid = (lo + hi) // 2
    left = total(xs, lo, mid)
    right = total(xs, mid, hi)
    return left + right

목록 전체의 합은 total(xs, 0, len(xs)) 로 구합니다. 원소가 하나 이상인 목록만 받습니다. 빈 목록을 넘기면 기저 사례에 닿지 않아 재귀가 끝나지 않습니다.

첫 if 두 줄이 기저 사례입니다. 원소가 하나면 그 원소가 곧 합이라 바로 돌려줍니다. mid 줄이 나누기입니다. left · right 두 줄이 풀기입니다. 마지막 return 이 합치기입니다.

반쪽을 새 목록으로 떼어 넘기지 않고 구간의 양 끝만 넘깁니다. 반쪽을 새 목록으로 복사하면 나눌 때마다 원소 수만큼 일이 더 듭니다. 구간만 넘기면 나누기는 mid 계산 한 번입니다. 합치기는 덧셈 한 번입니다. 복잡도 절의 T(n) = 2T(n/2) + 1 이 이 함수입니다.

호출이 펼쳐지는 순서

xs 가 [3, 1, 4, 1] 일 때 total(xs, 0, 4) 를 부르면 호출이 아래처럼 펼쳐집니다. 상자마다 그 호출이 맡은 구간의 원소를 함께 적었습니다. 화살표는 위에서 아래로 부른 방향입니다. 화살표 옆 값은 아래에서 위로 돌려준 답입니다.

flowchart TD
    A["total(xs, 0, 4) · 3 1 4 1"] -->|"4"| B["total(xs, 0, 2) · 3 1"]
    A -->|"5"| C["total(xs, 2, 4) · 4 1"]
    B -->|"3"| D["total(xs, 0, 1) · 3"]
    B -->|"1"| E["total(xs, 1, 2) · 1"]
    C -->|"4"| F["total(xs, 2, 3) · 4"]
    C -->|"1"| G["total(xs, 3, 4) · 1"]

먼저 왼쪽 반 3 1 을 끝까지 풉니다. 이 호출은 3 과 1 로 나뉩니다. 둘 다 기저 사례라 3 과 1 을 바로 돌려줍니다. 더해서 4 를 위로 돌려줍니다.

그다음 오른쪽 반 4 1 이 같은 순서로 풀려 5 를 돌려줍니다. 맨 위 호출이 4 와 5 를 더해 9 를 돌려주며 끝납니다.

합계는 분할 정복의 모양을 보이려고 고른 예입니다. 목록을 앞에서부터 한 번 훑어도 합은 나옵니다. 그 비용도 O(n) 입니다. 덧셈 횟수도 원소 수보다 하나 적은 n−1 번으로 같습니다. 한 번에 풀어도 이미 싼 문제라 쪼개서 줄일 일이 없습니다.

갈래

분할 정복으로 짠 알고리즘은 세 단계 가운데 어디에 일이 몰리느냐로 갈립니다. 병합 정렬은 나누기가 쉽습니다. 일은 합치기에 몰립니다. 퀵 정렬은 반대입니다. 이진 탐색처럼 나눈 뒤 한쪽만 풀어 합치기가 거의 없는 경우도 있습니다.

easy split, hard merge

작은 문제로 나누기는 빠르거나 간단합니다. 답을 합치기에 시간이 들거나 복잡합니다. 특히 정렬 알고리즘에서 이런 갈래를 부르는 이름입니다.

병합 정렬이 대표입니다. 가운데를 자르는 데는 계산이 거의 없습니다. 비교는 정렬된 두 반쪽을 합칠 때 몰립니다. 삽입 정렬도 같은 갈래입니다. 나누기는 원소 하나를 떼어 내는 것뿐입니다. 비교는 떼어 낸 원소를 정렬된 나머지 사이에 끼워 넣는 합치기에서 일어납니다.

hard split, easy merge

작은 문제로 나누기에 시간이 들거나 복잡합니다. 답을 합치기는 빠르거나 할 일이 거의 없습니다. 앞의 것과 반대쪽입니다.

퀵 정렬이 대표입니다. 퀵 정렬에서 가르는 기준값을 피벗(pivot)이라고 부릅니다. 가를 때 피벗보다 작은 것은 앞에, 큰 것은 뒤에 모아 둡니다. 두 쪽을 각각 정렬하고 나면 이어 붙이기만 하면 됩니다.

선택 정렬도 같은 갈래입니다. 나누기에서 남은 원소를 다 훑어 가장 작은 값을 골라 떼어 냅니다. 합치기는 그 값을 정렬된 나머지 맨 앞에 두는 것뿐입니다. 기수 정렬과 버킷 정렬은 자릿값이나 값의 구간으로 원소를 먼저 가릅니다. 가른 묶음을 차례로 이으면 합치기가 끝납니다.

한쪽만 푸는 경우

이진 탐색은 문제를 둘로 나누고도 하나만 풉니다. 나누기가 찾을 쪽을 고릅니다. 합치기는 찾은 쪽의 답을 가져오는 것으로 끝납니다. 안 찾는 쪽은 아무것도 안 하는 것으로 푼 셈이라 버려집니다.

배열이 정렬돼 있어서 가운데 값과 한 번 비교하면 한쪽 반을 버릴 수 있습니다. 찾는 값이 가운데 값보다 크면 오른쪽 반만 봅니다. 작으면 왼쪽 반만 봅니다. 작은 문제 하나만 남기는 이 방식을 감소 정복(decrease and conquer)이라고 따로 부르기도 합니다.

비슷한 원리가 여러 자료구조의 바탕에도 있습니다. 이진 탐색 트리는 노드의 키와 비교해 내려갈 가지 하나를 고릅니다. 이진 탐색처럼 한쪽만 남기는 셈입니다. 다진 탐색 트리 · 트라이 · 스킵 리스트 · k-d 트리 · 쿼드트리도 그렇습니다.

관련 항목

분할 정복으로 짠 알고리즘

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

나누기와 합치기 가운데 한쪽에 일이 몰리는 정렬

삽입 정렬 · 선택 정렬 · 기수 정렬 · 버킷 정렬 · 피벗

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

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

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

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

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

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

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

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

분할 정복과 같은 원리를 담은 자료구조

이진 탐색 트리 · 다진 탐색 트리 · 트라이 · 스킵 리스트 · k-d 트리 · 쿼드트리

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

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

분할 정복을 구현한 제품과 설정

Java · ForkJoinPool · Arrays.parallelSort · PostgreSQL · work_mem · EXPLAIN

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

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