분할 정복 (Divide and Conquer)

정의

분할 정복 (Divide and Conquer) 은 문제를 더 작은 부분 문제로 나누고 (Divide), 각각 해결한 후 (Conquer), 결과를 합쳐 (Combine) 원래 문제의 답을 얻는 알고리즘 설계 패러다임.

핵심 3 단계:

1. Divide: 문제를 k 개 (보통 2 개) 부분 문제로 분할
2. Conquer: 재귀적으로 각 부분 문제 해결 (base case 에서 직접 풀기)
3. Combine: 부분 해를 합쳐 전체 해 구성

대표 알고리즘: 병합 정렬 (Merge Sort), 퀵 정렬 (Quick Sort), 이진 탐색 (Binary Search), 고속 푸리에 변환 (FFT), 카라츠바 곱셈.

문제 상황과 동기

정렬 문제 예시:

• naive (버블 정렬): O(N^2), N = 10^6 이면 10^12 연산, 불가능.
• 분할 정복 (병합 정렬): O(N log N), N = 10^6 이면 ~2 × 10^7, 0.1 초.

핵심 통찰: 큰 문제를 반으로 나누면 T(N) = 2T(N/2) + O(N) → O(N log N). 재귀 깊이 log N, 각 레벨 O(N) 작업 → 총 O(N log N).

자주 등장하는 컨텍스트:

• PS: 정렬, 탐색, 수학 (거듭제곱, 행렬 곱), 기하 (가장 가까운 점 쌍)
• 실무: 정렬 알고리즘 (Merge Sort, Quick Sort), MapReduce, 병렬 처리

시각화

핵심 아이디어

재귀 관계식 (Master Theorem):

T(N) = a × T(N/b) + f(N)

a = 부분 문제 개수
b = 분할 크기 (N/b)
f(N) = 분할 + 합치기 비용

Master Theorem 결론:

1. f(N) = O(N^c), c < log_b(a) → T(N) = Θ(N^(log_b(a)))
2. f(N) = Θ(N^c log^k N), c = log_b(a) → T(N) = Θ(N^c log^(k+1) N)
3. f(N) = Ω(N^c), c > log_b(a) → T(N) = Θ(f(N))

병합 정렬 예시:

T(N) = 2 × T(N/2) + O(N)
a = 2, b = 2, f(N) = N
log_2(2) = 1, c = 1 → case 2
T(N) = O(N log N)

퀵 정렬 예시 (평균):

T(N) = 2 × T(N/2) + O(N)  (pivot 가 중간값이면)
→ O(N log N) 평균
최악 O(N^2) (pivot 가 최소/최대)

알고리즘

병합 정렬 (Merge Sort):

merge_sort(arr, left, right):
    if left >= right: return

    mid = (left + right) / 2
    merge_sort(arr, left, mid)      // Divide
    merge_sort(arr, mid + 1, right) // Divide
    merge(arr, left, mid, right)    // Combine

merge(arr, left, mid, right):
    L = arr[left..mid]
    R = arr[mid+1..right]
    i = 0, j = 0, k = left
    while i < len(L) and j < len(R):
        if L[i] <= R[j]:
            arr[k] = L[i]; i++
        else:
            arr[k] = R[j]; j++
        k++
    while i < len(L): arr[k++] = L[i++]
    while j < len(R): arr[k++] = R[j++]

구현

// 병합 정렬 (Merge Sort), O(N log N)
#include <bits/stdc++.h>
using namespace std;
​
void merge(vector<int>& arr, int left, int mid, int right) {
  vector<int> L(arr.begin() + left, arr.begin() + mid + 1);
  vector<int> R(arr.begin() + mid + 1, arr.begin() + right + 1);
  int i = 0, j = 0, k = left;
  while (i < (int)L.size() && j < (int)R.size()) {
      if (L[i] <= R[j]) arr[k++] = L[i++];
      else arr[k++] = R[j++];
  }
  while (i < (int)L.size()) arr[k++] = L[i++];
  while (j < (int)R.size()) arr[k++] = R[j++];
}
​
void merge_sort(vector<int>& arr, int left, int right) {
  if (left >= right) return;
  int mid = (left + right) / 2;
  merge_sort(arr, left, mid);
  merge_sort(arr, mid + 1, right);
  merge(arr, left, mid, right);
}
​
int main() {
  int n; cin >> n;
  vector<int> arr(n);
  for (auto& v : arr) cin >> v;
  merge_sort(arr, 0, n - 1);
  for (int v : arr) cout << v << " ";
  cout << "\n";
}

# 병합 정렬 (Merge Sort), O(N log N)
import sys
input = sys.stdin.readline
​
def merge_sort(arr):
  if len(arr) <= 1:
      return arr
  mid = len(arr) // 2
  left = merge_sort(arr[:mid])
  right = merge_sort(arr[mid:])
  return merge(left, right)
​
def merge(left, right):
  result = []
  i = j = 0
  while i < len(left) and j < len(right):
      if left[i] <= right[j]:
          result.append(left[i])
          i += 1
      else:
          result.append(right[j])
          j += 1
  result.extend(left[i:])
  result.extend(right[j:])
  return result
​
n = int(input())
arr = list(map(int, input().split()))
sorted_arr = merge_sort(arr)
print(" ".join(map(str, sorted_arr)))

// 병합 정렬 (Merge Sort), O(N log N)
import java.util.*;
import java.io.*;
​
public class Main {
  static void merge(int[] arr, int left, int mid, int right) {
      int n1 = mid - left + 1, n2 = right - mid;
      int[] L = new int[n1], R = new int[n2];
      System.arraycopy(arr, left, L, 0, n1);
      System.arraycopy(arr, mid + 1, R, 0, n2);
​
      int i = 0, j = 0, k = left;
      while (i < n1 && j < n2) {
          if (L[i] <= R[j]) arr[k++] = L[i++];
          else arr[k++] = R[j++];
      }
      while (i < n1) arr[k++] = L[i++];
      while (j < n2) arr[k++] = R[j++];
  }
​
  static void mergeSort(int[] arr, int left, int right) {
      if (left >= right) return;
      int mid = (left + right) / 2;
      mergeSort(arr, left, mid);
      mergeSort(arr, mid + 1, right);
      merge(arr, left, mid, right);
  }
​
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      int n = Integer.parseInt(br.readLine());
      int[] arr = Arrays.stream(br.readLine().split(" "))
                        .mapToInt(Integer::parseInt).toArray();
      mergeSort(arr, 0, n - 1);
      System.out.println(Arrays.toString(arr).replaceAll("[\\[\\],]", ""));
  }
}

5
5 3 8 1 2

1 2 3 5 8

6
9 7 5 3 1 0

0 1 3 5 7 9

복잡도

변형 / 활용

1. 퀵 정렬 (Quick Sort)

pivot 을 기준으로 분할. 평균 O(N log N), 최악 O(N^2). 실무에서 정렬 라이브러리 (introsort 등) 의 기본.

2. 이진 탐색 (Binary Search)

정렬된 배열에서 O(log N) 탐색. 분할만 있고 합치기 없음.

3. 카라츠바 곱셈 (Karatsuba Multiplication)

큰 정수 곱셈을 O(N^1.585) 로. 분할해서 3 번만 재귀 곱셈.

4. 고속 푸리에 변환 (FFT)

다항식 곱셈을 O(N log N) 로. 분할 정복 + 복소수 회전.

5. 행렬 거듭제곱

A^N 을 O(log N) 번 곱셈으로.

mat pow(mat A, int N) {
    if (N == 1) return A;
    mat half = pow(A, N / 2);
    mat res = half * half;
    if (N % 2) res = res * A;
    return res;
}

함정

1. Base case 미정의

재귀 종료 조건이 없으면 스택 오버플로우. if (left >= right) return; 필수.

2. 중복 계산

분할 경계가 겹치면 중복 재귀. DP 로 전환 필요.

3. Combine 비용 간과

합치기가 O(N^2) 면 총 복잡도 O(N^2 log N). 병합 정렬은 O(N) 합치기 → O(N log N).

4. 메모리 오버헤드

병합 정렬은 O(N) 추가 공간. 퀵 정렬은 in-place 가능 (O(log N) 스택).

BOJ 연습 문제

참고

• 병합 정렬
• 퀵 정렬
• 이진 탐색
• FFT
• 동적 계획법 (중복 부분 문제 해결)