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

분할 정복 알고리즘이랑 어떤 문제를 여러개의 하위 문제들로 나누고 각 하위 문제들의 솔루션을 찾은 뒤 이들을 병합하여 최선의 솔루션으로 만드는 것입니다. 각 하위의 문제들은 모두 개별적으로 문제를 해결하게 되는데, 이렇게 하는 이유는 작은 문제로 나누었을 경우 더 쉽게 해결책을 찾을 수 있기 때문입니다. 문제를 잘게 쪼개어 더 작은 문제로 만들고 이를 반복하다보면 결국 더이상 쪼갤 수 없는 문제가 되고 이렇게 쪼개어진 문제들의 해결책을 찾아서 병합하면 문제들을 나누기 전 최초의 문제에 대한 해결책을 만들 수가 있습니다. 아래 그림처럼 말이죠.

크게 봤을 때 분할 정복 알고리즘은 3 단계를 거치게 됩니다.

나누기/쪼개기

• 이 단계는 주어진 문제를 작은 단위의 문제들로 나누는 것입니다. 작게 나누어진 문제는 본래 문제의 일부를 나타내야 하며 나누어진 문제들을 합쳤을 때 나누기 전의 문제와 동일해야 합니다. 이 단계는 일반적으로 재귀적 접근을 하게 됩니다. 더 이상 쪼갤 수 없을 때까지 계속 쪼개는 것이죠. 이 단계에서 하위 문제들은 atomic 상태에 이르게 되고, 최초에 주어진 문제의 일부를 여전히 표현할 수 있어야 합니다.

정복하기/해결하기

• 이 단계는 작게 나누어진 문제들의 해결책을 찾는 단계입니다. 일반적으로 이 단계에서 각각의 문제들은 해결되었다고 간주됩니다. 더이상 나눌 수 없을 만큼 잘게 쪼개어 졌기 때문에 해결되었다고 보는 것이죠.

병합/조합하기

• 잘게 쪼개어진 문제들이 해결이 되었다면, 이제 이 단계에서는 재귀적으로 각각의 해결책을 병합하여 원래 문제의 해결책을 찾게 됩니다.

이 알고리즘은 재귀적 접근법으로 동작하며 정복하고 병합하는 단계는 구분하기 힘들정도로 마치 한 단계처럼 동작하게 됩니다.

분할 정복 알고리즘을 사용하는 예

• Merge Sort (병합 정렬)
• Quick Sort (퀵 정렬)
• Binary Search (이진 탐색)
• Strassen's Matrix Multiplication (스트라센의 매트릭스 곱)