Divide and Conquer Algorithm (분할 정복 알고리즘)

* Divide and Conquer Algorithm (분할 정복)?

해결할 수 없는 문제를 더 이상 나눌 수 없는 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘이다. 

Quicksort, Merge sort, Closest Pair of Points 등의 알고리즘이 이 분할 정복 알고리즘에 해당한다. 

분할 정복 알고리즘은 3 부분으로 나뉠 수 있다. 

1. 나누기 (Divide): 문제를 더 작은 문제로 나눈다. 
2. 정복 (Conquer): 하위 문제가 해결될 때까지 재귀적으로 호출하여 하위 문제를 해결한다. 
3. 결합(Combine): 하위 문제가 해결되었기 때문에 문제 해결을 할 수 있다. 

 

보통 재귀적으로 함수를 호출하여 문제를 해결하지만, 재귀적으로 함수 호출이 잦게 되면 함수 호출 스택 오버헤드 때문에 속도가 느려질 수 있다.

따라서 반드시 재귀적으로 함수를 호출하여 문제를 해결하는 것은 아니며, 스택과 큐 같은 자료 구조를 이용하여 분할 정복법을 구현하는 것도 가능하다. 

 

※ 이분 탐색의 경우 분할 정복이라고 생각하기 쉽지만 이분 탐색은 분할 정복이 아니다. 왜냐하면 각 단계에 하위 문제가 하나만 있기 때문에 분할 정복의 예가 되지 않는다. 분할 정복은 각 단계마다 두 개 이상의 하위 문제가 있어야 한다. 이분 탐색은 분할 정복이 아니며 Decrease and Conquer(감소 정복)이다. 

 

* 분할 정복의 예

분할 정복의 한 예인 Merge Sort(합병 정렬)