_

1. 소개

Divide & Conquer(D&C) 혹은 분할 정복이라 불리는 문제 해결 기법은 최적해를 구할 때 유용하게 사용될 수 있는 기법 중 하나로, 주어진 문제를 두개 이상의 부분 문제들로 분할하고 각각을 해결한 후 이를 다시 합쳐 주어진 문제를 해결하는 방식이다.

다시 말해, 문제를 여러개의 해결 가능한 부분 문제들로 나누고 각각을 해결한 후 이 결과를 적절히 융합하여 원래 문제의 답을 구하는 방식을 반복하여 문제를 해결하는 방법이다. 이 방식을 사용하는 이유는 각각을 부분 문제로 분할하고 이를 각각 해결하는 방식이 전체를 한번에 해결하는 방식에 비해 효율적으로 작동하는 경우가 많기 때문이다.

2. 방법

일반적으로 분할 정복 알고리즘의 과정을 정리하자면 다음과 같다.

문제가 분할이 가능하다면 2개 이상의 부분 문제들로 분할 (Divide)
나뉜 문제가 추가적으로 분할이 가능할 경우 다시 분할, 그렇지 않을 경우 문제를 해결 (Conquer)
아래 단계에서 Conquer 과정을 통해 답을 구한 부분 문제들을 다시 합하여 원래 문제의 답을 구함

3. 예시

3.1. Merge Sort

Merge Sort 참고

3.2. 히스토그램에서 가장 큰 직사각형

이 문제는 주어진 히스토그램에서 얻을 구 있는 가장 큰 직사각형의 넓이를 구하는 문제다.

이 문제를 해결하기 위한 다양한 방법이 있지만, 분할 정복을 사용하여 풀 수도 있다. 주어진 히스토그램을 가운데에 위치한 직사각형들 사이를 기준으로 두 개의 부분으로 분할하면 히스토그램의 가장 큰 직사각형은 다음과 같이 세 유형 중 하나에 속하게 된다.

1) 분할 선 기준으로 왼쪽 히스토그램의 막대들만 사용하여 만들어진 직사각형
2) 분할 선 기준으로 오른쪽 히스토그램의 막대들을 사용하여 만들어진 직사각형
3) 분할 선을 지나는 직사각형

1번과 2번의 경우는 재귀함수를 통해 구해 주면 되기 때문에 3번 경우만 고려해 주면 문제를 해결할 수 있게 된다. 그리고 이 과정은 그리디 알고리즘을 통해 해결할 수 있다.

가운데 지점을 기준으로 양 쪽으로 막대를 하나씩 추가하면서 직사각형들을 만들면서 각 직사각형의 크기를 구해주게 되며, 막대를 추가할 때는 왼쪽과 오른쪽의 두 막대 중에서 더 높이가 높은 쪽의 막대를 추가하는 것 만으로도 가장 높이가 높은 직사각형을 구할 수 있다.

이 문제의 시간복잡도를 분석하면 각 단계에서 \(O(n)\)의 시간이 걸리게 되고 각 단계 마다 전체 히스토그램의 너비가 절반으로 감소하므로 \(\log n\)의 단계를 거치게 된다. 따라서 \(O(n \log n)\)의 시간복잡도로 문제를 해결할 수 있다.

3.3. 가장 가까운 두 점 구하기

이 문제는 좌표평면 상에 주어진 n개의 점들 사이에서 가장 가까운 두 점 사이의 거리를 구해야 하는 문제다.

일반적으로 이 문제는 모든 점 쌍들 간의 거리를 계산하는 방식으로 \( O(n^2) \)의 시간 복잡도로 문제를 해결할 수 있다. 그러나 분할 정복을 이용하면 \(O(n \log n)\)의 시간복잡도로 이 문제를 해결 할 수 있다.

가장 먼저 분할 정복을 이용하기 위해서 n개의 정점들을 x 좌표를 기준으로 정렬 해 준다. 이후 x좌표를 기준으로 점을 두 개의 그룹으로 분할 한 후, 각각의 그룹에 대해 가장 가까운 두 점 사이의 거리를 구하고 최솟값 d를 구한다. 이때 각 그룹에 있는 점 사이의 거리를 고려하지 않았으므로 이를 고려해 주어야 하는데, 두 그룹을 나누는 기준선에서 \(x\)좌표의 차이가 \(d\) 이상인 경우 최소 거리가 될 수 없으므로 제외한다. 그리고 이 점들을 \(y\)좌표를 기준으로 정렬하여, \(y\)좌표의 차이가 \(d\) 이하인 점들 간에 거리를 구해 준다. 이때, 각 점에 대해 \(y\)좌표의 차이가 \(d\) 이하인 점의 개수는 7개를 넘지 않으므로, \(O(n)\)만에 모든 점 쌍 사이의 최소 거리를 구할 수 있게 된다. 이 과정을 반복하여 답을 구할 수 있게 된다. 그리고 이 알고리즘의 시간 복잡도를 계산하면, \(O(n \log n)\)이 된다.

_