분할 정복
보이기
분할 정복(Divide and Conquer)는 알고리즘의 설계 방법론 중 하나로, 알고리즘이 푸는 문제를 같은 종류의 작은 여러 하위 문제로 분할한 뒤 재귀적으로 하위문제를 푼 답을 모아 최종 답을 내는 과정을 거친다.
이때 분할된 문제가 계속 분할될 수록 일종의 트리 구조가 형성된다. 이 트리는 데이터의 값의 크기의 log값(밑 2)의 높이를 가진다.
마스터 정리
어떤 n비트의 입력 데이터들에 대한 전체 실행시간을 T(n)이라고 하자. 이때 분할 정복에 따라 T(n) = a*T(n/b) + O(nd)가 되는 경우 다음이 성립한다.[1]
- d > logba인 경우: T(n) = O(nd)
- d = logba인 경우: T(n) = O(ndlog n)
- d < logba인 경우: T(n) = O(nlogba)
가령 두 이진수의 곱셈의 경우 일반적으로는 나올 수 있는 최대 자리수(비트) n의 제곱의 시간 복잡도, O(n2)을 가지지만, 다음 함수를 설계하여 곱셈을 하는 알고리즘을 따를 경우 O(nlog23)의 시간 복잡도를 가진다.[2]
function BinaryMultiply(x, y)
입력: n bit의 이진수 x, y
출력: x와 y의 곱
if n = 1: return xy
xL와 xR = x을 반으로 갈랐을 때 왼쪽 비트들, 그리고 오른쪽 비트들
yL와 yR = y을 반으로 갈랐을 때 왼쪽 비트들, 그리고 오른쪽 비트들
P1 = BinaryMultiply(xL, yL)
P2 = BinaryMultiply(xR, yR)
P3 = BinaryMultiply(xL + xR, yL + yR)
return P1 * 2n + (P3 - P1 - P2) * 2n/2 + P2
- 병합 정렬
- 임의로 배열된 수의 중간값 구하기: 무작위 수를 골라 그보다 작은 수의 배열, 그 수와 같은 수들의 배열, 그보다 큰 수의 배열로 분할하게 된다.
- 세그먼트 트리[3]의 초기화 및 탐색
- 행렬의 곱의 고속화
- Fast Fourier Transform(FFT): 전자기학 등에서 주파수 분석이나 디지털 신호 처리에 사용한다.