분할 정복(divide-and-conquer) 패러다임이란 무엇인가요?

Question

Accepted Answer

**분할 정복**은 (1) 문제를 더 작은 부분 문제로 **나누고(divide)**, (2) 각각을 재귀적으로 **정복하고(conquer)**, (3) 결과를 **결합(combine)**하여 문제를 해결합니다. 많은 효율적인 알고리즘이 이 템플릿을 따릅니다.

## 개념

부분 문제가 독립적이고 빠르게 작아진다면, 전체 작업량은 **Master Theorem(마스터 정리)**으로 분석할 수 있는 점화식을 따릅니다.

## 예시: 분할 정복으로 최댓값 찾기

```python
def max_dc(arr, lo, hi):
    if lo == hi:                       # base case: 원소 하나
        return arr[lo]
    mid = (lo + hi) // 2
    left = max_dc(arr, lo, mid)        # 왼쪽 정복
    right = max_dc(arr, mid + 1, hi)   # 오른쪽 정복
    return max(left, right)            # 결합

max_dc([3, 9, 2, 7], 0, 3)            # -> 9
```

## 전형적인 예시

- **Merge sort / quicksort** — O(n log n) 정렬.
- **Binary search** — O(log n).
- **빠른 거듭제곱, Karatsuba 곱셈, 최근접 점 쌍.**

## 복잡도

흔히 T(n) = a·T(n/b) + f(n)입니다. merge sort의 경우 T(n) = 2T(n/2) + O(n) = **O(n log n)**입니다.

## 언제 사용하나 / 함정

문제가 독립적인 부분 문제로 **깔끔하게 분할**될 때 사용하세요. 부분 문제가 **겹친다면** 재계산을 피하기 위해 dynamic programming을 선호하세요. 작은 입력에서는 재귀 오버헤드와 결합 단계가 지배적일 수 있습니다.

## 왜 중요한가

분할 정복은 효율적인 알고리즘의 큰 부분 뒤에 있는 재사용 가능한 청사진입니다.

패턴을 인식하면 점화식으로 새 알고리즘을 빠르게 도출하고 분석할 수 있습니다.

또한 독립적인 부분 문제는 동시에 실행될 수 있으므로 병렬화에 자연스럽게 대응됩니다.