[Algorithm] Divide and Conquer

이번 글은 서강대학교 임종석 교수님의 강의와 Richard Neapolitan의「Foundation of Algorithm」, Steven Skiena의 「Algorithm Design Manual」을 참고하여 작성했음을 밝힙니다.

분할 정복(Divide and Conquer) 알고리즘은 큰 문제가 하나 주어지면 이를 둘 혹은 더 많은 부분으로 나누어서 각자를 해결하고, 그 결과를 다시 합치는 방법을 이용하는 알고리즘입니다.

알고리즘은 아래 세 단계로 진행됩니다.

1. 우선, 문제의 instance가 주어지면 몇 개의 작은 instance로 나눈다(devide)
2. 각자의 solution을 찾는다(conquer)
3. 합쳐서 문제의 instance에 대한 solution을 찾는다(combine)

분할 정복 알고리즘을 이용해 각자의 solution을 구할 때, sub instance의 size가 클 경우, recursive하게 Divide and Conquer를 계속해서 적용합니다. 즉, size가 충분히 작아질 때까지 계속 쪼갠다는 뜻입니다.(많은 경우에 size가 1이 될 때까지 계속해서 쪼갭니다.)

분할 정복 알고리즘에는 대표적으로 다음 세 가지가 있는데, 이후 글을 통해 하나씩 살펴보겠습니다.

1. Binary Search
2. MergeSort
3. QuickSort