분할 정복 알고리즘이란 주어진 문제의 입력을 분할하여 문제를 해결하는 방식의 알고리즘이다.

분할 정복 알고리즘의 분류

분할되는 부분문제의 수와 부분문제의 크기에 따라서 다음과 같이 분류할 수 있다.

• 문제가 a개로 분할되고, 부분문제의 크기가 1/b로 감소하는 알고리즘
  • a = b = 2인 경우, 합병 정렬, 최근접 점의 쌍 찾기, 공제선 문제
  • a=3, b=2인 경우, 큰 정수의 곱셈
  • a=4, b=2인 경우, 큰 정수의 곱셈
  • a=7, b=2인 경우, 스트라센의 행렬 곱셈 알고리즘
• 문제가 2개로 분할되고, 부분문제의 크기가 일정하지 않은 크기로 감소하는 알고리즘: 퀵 정렬
• 문제가 2개로 분할되나, 그중에 1개의 부분문제는 고려할 필요 없으며, 부분문제의 크기가 일정하지 않은 크기로 감소하는 알고리즘: 선택 문제 알고리즘
• 부분 문제의 크기가 1,2개씩 감소하는 알고리즘: 삽입 정렬, 피보나치 수의 계산 등

합병 정렬

합병 정렬은 입력이 2개의 부분문제로 분할되고, 부분문제의 크기가 1/2로 감소하는 분할 정복 알고리즘이다.

합병(merge)이란 2개의 각각 정렬된 숫자들을 1개의 정렬된 숫자들로 합치는 것이다.

아래 그림은 입력 크기 n=8인 배열 A=[37,10,22,30,35,13,25,24]에 대하여 MergeSort 알고리즘이 수행되는 과정을 보이고 있다. 원 속의 숫자들은 알고리즘이 수행된 순서를 나타낸다.

합병 정렬의 시간복잡도를 위 그림을 통해 알아보자.

분할하는 부분은 배열의 중간 인덱스 계산과 2번의 순환 호출을 하는 것이므로 O(1) 시간이 걸린다.

반면에 합병을 하는 수행 시간은 입력의 크기에 비례한다. 즉, 2개의 정렬된 배열 A와 B의 크기가 각각 n과 m이라면, 최대 비교 횟수는 (n+m-1)이다. 이유는 합병하는데 2개의 숫자를 1번 비교할 때마다, 하나의 ‘승자’(즉, 작은 숫자)가 탄생하고, 승자는 합병된 배열 C에 저장되기 때문이다. 따라서 배열 C에는 결국 배열 A와 B의 모든 (n+m)개의 숫자들이 저장되나, 가장 마지막에 저장되는 숫자는 비교할 숫자가 없으므로 최대 비교 횟수는(n+m-1)이다. 즉, 합병의 시간복잡도는 O(m+n)이다.

그림의 중간을 보면 모든 숫자(즉, n=8개의 숫자)가 합병에 참여한다. 합병의 수행시간은 합병되는 입력 크기에 비례하므로 각 층에서 수행된 비교 횟수는 O(n)이다. 8개 숫자를 반으로, 반의 반으로, 반의 반의 반으로 나누었다. 그렇게 해서 3개의 층이 만들어진 것이다.

그렇다면 입력이 n개일 때는 n을 계속하여 1/2로 나누다가, 더 이상 나눌 수 없는 크기인 1이 될 때 분할을 중단한다. 따라서 k번 1/2로 분할했으면 k개의 층이 생기는 것이고, k는 $log_{2}n$임을 알 수 있다.

결과적으로 합병 정렬의 시간복잡도는 (층수)*O(n) = O(nlogn)이다.

퀵 정렬

퀵 정렬은 분할 정복 알고리즘으로 분류되나, 사실 수행 과정을 살펴보면 정복 후 분할하는 알고리즘이다. 퀵 정렬 알고리즘은 문제를 2개의 부분문제로 분할하는데, 각 부분문제의 크기가 일정하지 않은 형태의 분할 정복 알고리즘이다.

퀵 정렬의 아이디어는 **피봇(pivot)**이라 일컫는 배열의 원소(숫자)를 기준으로 피봇보다 작은 숫자들은 왼편으로, 피봇보다 큰 숫자들은 오른편에 위치하도록 분할하고, 피봇을 그 사이에 놓는 것이다. 퀵 정렬은 분할된 부분문제들에 대하여서도 위와 동일한 과정을 순환적으로 수행하여 정렬한다.

단, 주의할 점은 피봇은 분할된 왼편이나 오른편 부분에 포함되지 않는다.

퀵 정렬 알고리즘의 수행과정

피봇 A[6]=8이라고 가정하면, 먼저 피봇을 가장 왼쪽으로 이동시킨다.

그 다음에는 피봇보다 큰 수와 피봇보다 작은 수를 다음과 같이 각각 교환한다.

마지막으로 피봇을 A[4]로 옮기기 위해 A[0]과 교환한다. 피봇을 A[4]로 이동하는 이유는 피봇(즉, 8)보다 작으면서 가장 오른쪽에 있는 숫자(즉, 2)가 A[4]에 있기 때문이다.

그 후로는 피봇을 기준으로 분할하여 더이상 피봇을 정의할 수 없을때까지 반복한다.

퀵 정렬의 성능은 피봇 선택이 좌우한다. 피봇으로 가장 작은 숫자 또는 가장 큰 숫자가 선택되면, 한 부분으로 치우치는 분할을 야기한다.

퀵 정렬의 총 비교 횟수는 O(n)*(층수) = O(n)*O($log_{2}n$)이다. 그러므로 퀵 정렬의 최선 경우 시간복잡도는

O($nlog_{2}n$)이다.

피봇을 항상 랜덤하게 선택한다고 가정하면, 퀵 정렬의 평균 경우 시간복잡도를 계산할 수 있다. 이때의 시간복잡도 역시 최선 경우와 동일하게 O($nlog_{2}n$)이다.

피봇 선정 방법

퀵 정렬의 불균형한 분할을 완화시키기 위해서, 일반적으로 다음과 같은 피봇 선정 방법이 사용된다.

• 랜덤하게 선정하는 방법
• 3 숫자의 중앙값으로 선정하는 방법: 가장 왼쪽 숫자, 중간 숫자, 가장 오른쪽 숫자 중에서 중앙값으로 피봇을 정한다.
• 중앙값들 중의 중앙값: 입력을 3등분하여 각 부분에서 3 숫자의 중앙값을 찾아서 3개의 중앙값에서 중앙값을 피봇으로 삼는다.

입력의 크기가 매우 클 때, 퀵 정렬의 성능을 더 향상시키기 위해서, 삽입 정렬이 동시에 사용되기도 한다. 입력의 크기가 작을 때에는 퀵 정렬이 삽입 정렬보다 빠르지만은 않다. 따라서 부분 문제의 크기가 작아지면, 더 이상의 분할을 중단하고 삽입 정렬을 사용하는 것이다.

퀵정렬은 커다란 크기의 입력에 대해서 가장 좋은 성능을 보이는 정렬 알고리즘이다. 퀵 정렬은 실질적으로 어느 정렬 알고리즘보다 좋은 성능을 보인다.

선택 문제

선택 문제는 n개의 숫자들 중에서 k번째로 작은 숫자를 찾는 문제이다.

해결 방법은 다음과 같다

• 최소 숫자를 k번 찾는다. 단, 최소 숫자를 찾은 뒤에는 입력에서 그 숫자를 제거한다.
• 숫자들을 오름차순으로 정렬한 후, k번째 숫자를 찾는다.

위의 알고리즘들은 최악의 경우 O(kn)과 O(nlogn)의 수행 시간이 걸린다. 여기서 O(nlogn)은 정렬의 시간복잡도이다. 이보다 효율적인 해결을 위해, 분할 정복 개념을 활용할 수 있다.

피봇을 선택하여 왼쪽(작은 그룹), 오른쪽(큰 그룹)로 나눴다고 했을 때 각 그룹의 크기를 알면, k번째 작은 숫자가 어느 그룹에 있는지를 알 수 있고, 그 다음에는 그 그룹에서 몇 번째로 작은 숫자를 찾아야 하는지를 또한 알 수 있다.

작은 그룹에 k번째 작은 숫자가 속한 경우: k번째 작은 숫자를 작은 그룹에서 찾는다.

큰 그룹에 k번째 작은 숫자가 있는 경우: k-작은그룹크기-1 번째로 작은 숫자를 큰 그룹에서 찾아야한다.

선택 문제 알고리즘은 문제가 2개의 부분문제로 분할되나, 그중에 1개의 부분문제는 고려할 필요 없으며, 부분문제의 크기가 일정하지 않은 크기로 감소하는 형태의 분할 정복 알고리즘이다.

선택 알고리즘은 분할 정복 알고리즘이기도 하지만 랜덤 알고리즘이기도 하다. 왜냐하면 선택 알고리즘의 처음에 피봇을 랜덤하게 정하기 때문이다.

피봇을 랜덤하게 정했을 때 good 분할이 될 확률이 1/2이므로 평균 2회 연속해서 랜덤하게 피봇을 정하면 good 분할을 할 수 있다. 즉, 매 2회 호출마다 good 분할이 되므로, good 분할만 연속하여 이루어졌을 때만의 시간복잡도를 구하여, 그 값에 2를 곱하면 평균 경우 시간복잡도를 얻을 수 있다.

이 가정하에 계속 반복한다면 분할 후 큰 부분의 최대 크기는 (3/4)i제곱/n보다 항상 작으므로 입력 크기가 n에서부터 3/4배로 연속적으로 감소되고, 입력 크기가 1일 때에는 더 이상 분할할 수 없게 된다. 그러므로 선택 알고리즘의 평균 경우 시간복잡도는 다음과 같다.

Selection 알고리즘의 평균 경우 시간복잡도는 2*O(n) = O(n)이다. 여기서 2를 곱한 이유는 평균 2번 만에 good 분할이 되기 때문이다.

선택 알고리즘은 정렬을 하지 않고 k번째 작은 수를 선형 시간에 찾을 수 있게 해준다.

최근접 점의 쌍 찾기

최근접 점의 쌍을 찾는 문제는 2차원 평면상의 n개의 점이 입력으로 주어질 때, 거리가 가장 가까운 한 쌍의 점을 찾는 문제이다.

위 그림에서 동그라미 내의 두 점이 최근접 점의 쌍이다. 최근접 점의 쌍을 찾는 가장 간단한 방법은 모든 점에 대하여 각각의 두 점 사이의 거리를 계산하여 가장 가까운 점의 쌍을 찾는 것이다. 그러면 거리를 계산하여야 할 쌍은 총 몇 개인가?

답은 조합이다. 즉, nC2 = n(n-1)/2 = O($n^2$)이고, 한 쌍의 거리 계산은 두 점 간의 거리 공식을 이용하면 O(1) 시간이 걸리므로, 이 방법의 시간복잡도는 O($n^2$)이다.

O($n^2$)보다 효율적인 방법은 분할 정복을 이용하는 것이다. n개의 점을 1/2로 분할하여 각각의 부분문제에서 최근접 점의 쌍을 찾고, 2개의 부분해 중에서 짧은 거리를 가진 점의 쌍을 일단 찾는다. 그러나 2개의 부분해를 취합할 때에는 반드시 다음과 같은 경우를 고려해야 한다.

그림을 보면 왼쪽 부분문제의 최근접 쌍의 거리가 10이고, 오른쪽 부분문제의 최근접 쌍의 거리가 15인데, 왼쪽 부분문제의 가장 오른쪽 점과 오른쪽 부분문제의 가장 왼쪽 점 사이의 거리가 7인 경우를 보여주고 있다. 따라서 2개의 부분문제의 해를 취합할 때 단순히 10과 15 중에서 짧은 거리인 10을 최근접 거리라고 할 수 없는 것이다. 그러므로 아래 그림과 같이 각각 거리가 10 이내의 중간 영역 안에 있는 점들 중에 최근접 점의 쌍이 있는지도 확인해보아야 한다.

최근접 점의 쌍을 찾는 알고리즘은 문제가 2개의 부분문제로 분할되고, 부분문제의 크기가 1/2로 감소하는 전형적인 분할 정복 형태의 알고리즘이다.

최근접 점 쌍 찾기 알고리즘의 시간복잡도를 알아보자.

입력 S에 n개의 점이 있다고 가정하고, 알고리즘을 단계별로 살펴보자. 알고리즘의 전처리 과정으로 S의 점을 $x$좌표로 정렬하는데, 이 과정은 O($nlogn)$의 시간이 소요된다.

최근접 점 쌍 찾기 알고리즘의 분할 과정은 합병 정렬의 분할 과정과 동일하지만, 합병 정렬에서는 합병 과정에서 O(n) 시간이 걸리고, 최근접 점 쌍 찾기 알고리즘에서는 해를 취합하여 올라가는 과정에서 O($nlogn$) 시간이 걸린다.

해를 취합하여 올라가는 과정인 line 56에서 O(nlogn) 시간이 걸린다. 여기서 line 56이란 중간 영역에서 최근접 점 쌍을 찾고 전에 분할한 영역에서 구한 두 최근접 점 쌍 중 최솟값을 구하는 과정이다. 그림에서 k층까지 분할된 후, 층별로 line 5~6이 수행되는 (취합) 과정을 보여준다. 여기서 층 수인 k는 $log_{2}n$보다는 작다. 왜냐하면 점의 수가 3 또는 2일 때 분할을 중단하기 때문이다. 이때 각 층의 수행 시간은 O(nlogn)이다. 여기에 층 수인 logn을 곱하면

O($nlog^2n$)이 된다.

분할 정복을 적용하는 데 있어서 주의할 점

분할 정복이 부적절한 경우는 입력이 분할될 때마다 분할된 부분문제의 입력 크기의 합이 분할되기 전의 입력 크기보다 매우 커지는 경우이다.

예시: 피보나치 수열

또한 분할 정복 알고리즘으로 해결하려고 할 때의 주의해야 하는 또 하나의 요소는 취합(정복) 과정이다. 입력을 분할만 한다고 해서 효율적인 알고리즘이 만들어지는 것은 아니다. 보통 기하 문제들의 특성상 취합 과정이 문제 해결에 잘 부합되기 때문이다.