분할 정복 알고리즘

분할 정복(Divide-and-Conquer) 알고리즘이란 ?

주어진 문제의 입력을 분할하여 문제를 정복하는 방식의 알고리즘이다. 

 

분할 정복 알고리즘 수행 방식

분할된 입력에 동일한 알고리즘을 적용하여 해를 계산하고, 이들의 해를 취합하여 원래 문제의 해를 얻는다.

입력 크기가 1이 되어 더이상 분할할 수 없게 될 때까지 분할한다.

입력 크기가 N일때, 분할한 총 횟수를 K라고 하면, 한번 분할 후 입력 크기는 $\frac{N}{2}$ 이다.

k번 반복한다면 입력 크기는 $\frac{N}{2^k}$ 이 되고, $\frac{N}{2^k}$ =1 일 때 더 이상 분할할 수 없으므로 $k=\log_{ 2 } n$ 을 만족한다. 

 

분할 정복 알고리즘 분류

- 합병정렬( Merge Sort)

- 최근접 점의 쌍 찾기

- 공제선 문제

- 큰 정수의 곱셈

- 퀵 정렬

- 이진탐색

- 선택 문제 알고리즘

- 삽입정렬

- 피보나치 수의 계산