토픽 18 / 82

분할 정복 (Divide and Conquer)

문제를 작은 부분 문제로 나누어 재귀적으로 해결한 후 결과를 합쳐 원래 문제를 해결하는 알고리즘 설계 기법

목적: 복잡한 문제 단순화, 효율적 해결, 병렬화 가능

특징: 재귀, 3단계(분할·정복·결합), 독립 부분 문제

3단계

조건: 부분 문제가 독립적, 결합 가능

시간 복잡도: 주로 O(n log n), 재귀 관계식(Master Theorem)

Master Theorem: T(n) = aT(n/b) + f(n) → O(n^log_b(a)), O(n^log_b(a) log n), O(f(n))

장점: 효율적(O(n log n)), 병렬화 가능, 복잡한 문제 단순화

단점: 재귀 오버헤드, 스택 깊이, 기저 케이스 중요

적용사례: 병합 정렬, 퀵 정렬, 이진 검색, 큰 정수 곱셈(Karatsuba), FFT, 행렬 곱셈(Strassen)

비교: 분할 정복(독립/재귀/결합) vs 동적 프로그래밍(중복/메모이제이션) vs 탐욕(지역 최적)

연관: 재귀, 병합 정렬, 퀵 정렬, 이진 검색, Master Theorem