💡
DP·그리디
병합·퀵·고속 거듭제곱·CCW
강의 23: 분할 정복 (Divide and Conquer)
큰 문제를 작은 동일 구조로 분할해 푸는 패러다임. 행렬 거듭제곱·외적도 함께 다룹니다.
분할 정복고속 거듭제곱
소요 시간
⏱ 약 1시간
난이도
📊 중급
선수 조건
🎯 정렬·재귀
결과물
큰 문제를 작은 동일 구조로 분할해 푸는 패러다임. 행렬 거듭제곱·외적도 함께 다룹니다.
이 강의에서 배우는 것
- 1분할 정복의 3단계(분할/정복/합병)를 병합 정렬로 이해하고, T(n) 점화식을 세울 수 있다.
- 2빠른 거듭제곱(fast exponentiation)을 O(log n)에 구현하고, 모듈러 거듭제곱에 적용할 수 있다.
- 3CCW(Counter-Clockwise) 외적을 이용해 세 점의 방향성을 판별할 수 있다.
소개
분할 정복은 **문제를 더 작은 하위 문제로 분할**하고, 각각 해결한 뒤 **합치는(combine)** 알고리즘 설계 패턴입니다.
text
분할 정복 3단계:
1. 분할 (Divide): 문제를 더 작은 a개의 문제로 나눔 (각 크기 n/b)
2. 정복 (Conquer): 재귀적으로 각 하위 문제 해결
3. 합병 (Combine): 하위 문제 결과를 합쳐 전체 해 구성
점화식: T(n) = a × T(n/b) + f(n)
a = 하위 문제 수
b = 크기 감소 비율
f(n) = 분할+합병 비용마스터 정리 (Master Theorem)
text
T(n) = a × T(n/b) + f(n)에서 c = log_b(a)라 하면:
경우 1: f(n) = O(n^(c-ε)) → T(n) = Θ(n^c)
(f가 n^c보다 다항적으로 느림)
경우 2: f(n) = Θ(n^c) → T(n) = Θ(n^c × log n)
(f와 n^c가 같은 차수)
경우 3: f(n) = Ω(n^(c+ε)) → T(n) = Θ(f(n))
(f가 n^c보다 다항적으로 빠름)
예시:
병합 정렬: T(n) = 2T(n/2) + O(n) → c = log_2(2) = 1, f = O(n) → 경우 2 → O(n log n)
이진 탐색: T(n) = T(n/2) + O(1) → c = log_2(1) = 0, f = O(1) → 경우 2 → O(log n)
카라츠바: T(n) = 3T(n/2) + O(n) → c = log_2(3) ≈ 1.585 → 경우 1 → O(n^1.585)핵심 개념
병합 정렬 분석
text
분할: O(1) (인덱스만 계산)
합병: O(n) (두 정렬된 배열 병합)
T(n) = 2T(n/2) + O(n)
→ 마스터 정리 경우 2
→ T(n) = O(n log n)
병합 정렬 트리:
[8,3,5,1,9,2,6,4] 레벨 0: n
[8,3,5,1] [9,2,6,4] 레벨 1: n/2
[8,3] [5,1] [9,2] [6,4] 레벨 2: n/4
...
각 레벨: O(n) 합병 × log n 레벨 = O(n log n)빠른 거듭제곱
text
x^n = (x^(n/2))^2 if n이 짝수
x^n = x × (x^(n/2))^2 if n이 홀수
예: 2^10 = (2^5)^2 = ((2^2)^2 × 2)^2
→ O(n) 곱셈 → O(log n) 곱셈으로 감소CCW (Counter-Clockwise)
text
세 점 A, B, C가 주어질 때:
외적 = (B-A) × (C-A)
= (Bx-Ax)(Cy-Ay) - (By-Ay)(Cx-Ax)
> 0: CCW (반시계 방향)
= 0: 일직선 (collinear)
< 0: CW (시계 방향)
활용: 볼록 껍질(Convex Hull), 선분 교차 판별복잡도 비교
text
┌──────────────────────┬──────────────┬────────────────────────────┐
│ 알고리즘 │ 시간 │ 점화식 │
├──────────────────────┼──────────────┼────────────────────────────┤
│ 병합 정렬 │ O(n log n) │ T(n) = 2T(n/2) + O(n) │
│ 빠른 거듭제곱 │ O(log n) │ T(n) = T(n/2) + O(1) │
│ 이진 탐색 │ O(log n) │ T(n) = T(n/2) + O(1) │
│ 카라츠바 곱셈 │ O(n^1.585) │ T(n) = 3T(n/2) + O(n) │
│ 가장 가까운 점 쌍 │ O(n log n) │ T(n) = 2T(n/2) + O(n log n)│
└──────────────────────┴──────────────┴────────────────────────────┘예제로 보기
| 파일 | 내용 |
|---|---|
| `src/01_merge_sort_dc.py` | 병합 정렬 분할 정복 + T(n) 분석 |
| `src/02_fast_pow.py` | 빠른 거듭제곱 재귀/반복 |
| `src/03_ccw.py` | CCW 외적, 일직선 판별 |
| `src/04_karatsuba.py` | 카라츠바 곱셈 O(n^1.585) |
자주 하는 실수
- **분할 기저 조건 누락**: `if n <= 1: return` 없이 재귀하면 무한 루프 또는 스택 오버플로
- **모듈러 거듭제곱 순서**: 중간 결과가 넘칠 수 있으므로 `pow(a, b, m)` 사용 권장
- **병합 시 인덱스 오류**: 두 배열 병합 시 남은 원소 처리(`extend`) 빠뜨리면 일부 원소 누락
- **CCW 정수 오버플로**: 좌표가 크면 외적 계산 시 오버플로 주의 (Python은 자동 확장)
- **카라츠바 기저 조건**: 한 자리 숫자에서 재귀를 멈춰야 함 — 너무 일찍 멈추면 오히려 느려짐
정리
- **분할 정복**: 분할 → 재귀 해결 → 합병
- **마스터 정리**: T(n) = aT(n/b) + f(n) → 세 경우로 복잡도 결정
- **빠른 거듭제곱**: O(n) → O(log n) — 모듈러 연산과 함께 자주 사용
- **CCW**: 기하 알고리즘의 핵심 연산 — 볼록 껍질, 선분 교차에 활용
직접 해 보기
- 퀵 정렬도 분할 정복 — T(n) 최선/최악 분석
- 가장 가까운 점 쌍(Closest Pair of Points) 구현 O(n log n)
- FFT(고속 푸리에 변환)의 분할 정복 원리 이해
과제
📂 `homework/README.md` 참조
- 백준 1629 (곱셈) — Silver I
- 백준 2630 (색종이 만들기) — Silver II
- 백준 1992 (쿼드트리) — Silver I