[Algorithm] Divide-and-conquer (분할 정복)

Divide-and-conquer (분할 정복)은 알고리즘 설계 패러다임 중 하나이다. 이번 포스트에서는 Divide-and-conquer 패러다임에 대해 다뤄보자.

Divide-and-conquer 는 하나의 큰 문제를 두 개 이상의 같거나 비슷한 문제로 나누고, 하위 문제들을 해결한 답을 합쳐 원하는 큰 문제의 답을 얻는 패러다임이다. 그래서 Divide-and-conquer 는 하나의 큰 문제가 두 개 이상의 같거나 비슷한 하위 문제로 나누어지고, 하위 문제를 해결한 답을 합치면 상위 문제의 답이 되는 경우에 사용할 수 있다.

Divide-and-conquer 패러다임을 사용하는 알고리즘은 대표적으로 Quick Sort(퀵 정렬)나 Merge Sort(병합 정렬)가 있다. 분할 정복을 더 쉽게 이해하기 위해 병합 정렬을 예시로 살펴보자. Fig1 은 7개의 원소를 병합 정렬을 통해 정렬하는 과정이다.

병합 정렬은 배열을 하나의 원소만 포함하는 배열이 될 때까지 나눈 후, 나눠진 배열들을 다시 병합하면서 정렬하여 최종적으로 입력받은 전체 배열이 정렬되도록해서 배열을 정렬하는 방법이다. 병합하면서 작은 값부터 채워넣으면 되기 때문에, 각 병합 단계(Fig1 에서 수평 한 줄을 의미)에서 N(원소의 개수)번의 순회를 하고 각 단계의 수는 배열을 각 단계마다 둘로 나누었기 때문에 2를 밑으로 하는 logN 번 반복되기 때문에 시간복잡도는 O(NlogN) 임을 알 수 있다.

병합정렬에 대해 간단히 알아보았지만, 이번 포스트에서 우리가 중점적으로 볼 건 Divide-and-conquer 패러다임이 어떻게 적용되었는지이다.

• Divide : 먼저 배열들이 하나의 원소를 갖는 배열이 될 때까지 나누었고, 이 과정이 전체 배열을 정렬하기 위해 하위 문제로 나누는 과정임을 알 수 있다.
• Conquer : 나누어진 배열들을 다시 합치면서, 정렬하여 하위 문제들을 해결한다. 해결된 하위 문제를 합쳤을 때 상위 문제도 해결할 수 있으므로 분할 정복 패러다임을 적용할 수 있다.

Fig1. Divide-and-conquer 를 적용하여 설게된 Merge sort algorithm 의 예시

Reference

1. [Wikipedia] “Divide-and conquer algorithm” — https://en.wikipedia.org/wiki/Divide-and-conquer_algorithm
2. [Wikipedia] “합병 정렬” — https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC