[알고리즘] 분할정복 - 이분 탐색, 합병 정렬, 퀵 정렬

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

 

문제의 입력사례를 두 개 이상 작은 입력사례로 분할한다. 계속 분할 하다가 바로 답을 얻을 수 있으면 원래 문제의 답은 얻은 답들을 통합해 구하는 알고리즘

 

하향식(top - down) 문제풀이 방식이다. 상위 입력사례의 해답은 하위의 작은 입력사례들의 해답을 가지고 구한다.

재귀함수의 작동원리가 이런데, 문제 풀이 중심으로 재귀함수를 작성한다.

 

이분 탐색(binary search)

 

재귀함수의 재귀 호출은 분할정복의 하향식 문제풀이 방식과 원리가 같다.

 

1. [분할(divide)] 배열을 정 가운데 원소를 기준으로 반으로 분할한다(divide). $x$가 가운데 원소보다 작으면 왼쪽 배열을 선택, $x$가 가운데 원소보다 크면 오른쪽 배열을 선택한다.

 

2. [정복(conquer)] 선택한 한 쪽 배열을 정복한다. 즉, 선택한 한 쪽 배열에 $x$가 있는지 재귀로 이분탐색한다.

 

3. [취합(combine)] 선택한 한 쪽 배열에서 얻은 답이 최종 답이다.

 

 

이분탐색 알고리즘은 해답을 구하고, 결과를 취합할 필요가 없기 때문에 가장 간단한 분할정복 알고리즘에 속한다.

 

 

$x$가 32이고 다음과 같은 배열이 있다고 가정하자.

 

 

1.[분할] 배열을 분할한다. $x>23$이기 때문에 오른쪽 배열에서 검색한다.

 

2.[정복] 오른쪽 배열에 $x$가 있는지 결정한다.(오른쪽 배열을 재귀적으로 정복한다).

 

예, $x$는 오른쪽 배열에 있습니다.

 

3.[취합] 오른쪽 배열에서 얻은 답으로 전체 배열에 대한 답을 구한다.

 

예, $x$는 오른쪽 배열에 있습니다. 

 

이분탐색 작동 사례

 

최악 시간복잡도 분석(이분탐색 재귀)

배열을 검색하는 알고리즘에서 가장 비용이 많이 드는 연산은 보통 검색 키와 배열 원소를 비교하는 연산이다.

 

단위 연산 : $x$와 $S[mid]$의 비교

입력 크기 : 배열 원소의 개수, $n$

 

최악의 경우가 $x$가 배열의 어떤 원소보다도 큰 경우이다. $n$이 16이면, $mid = \lfloor (1+16) /2\rfloor = 8 $이다. $x$가 배열의 모든 원소보다 크므로 오른쪽 8개의 원소가 재귀호출의 입력이고, 다음으로는 오른쪽 끝 4개의 원소가 입력되는 식으로 진행된다. 결국 재현식(recurrence)는 다음과 같이 나타난다.

 

$n$이 2의 거듭제곱인 경우

 

$$\begin{cases}W(n) = W(\frac{n}{2}) + 1 & n>1, \, n = 2^k (k \in \mathbb{N})\\ W(1) = 1\end{cases}$$

 

여기서 $n$이 2의 거듭제곱이라는 제한을 없애면 다음과 같이 된다.

 

$$W(n) = \lfloor \mathrm{lg} \, n \rfloor +1 $$

 

합병정렬(Merge sort) 

 

쌍방 합병 (two-way merging) : 정렬된 배열 두개를 정렬된 배열 두 개를 정렬상태를 유지하면서 하나로 합치는 것.

 

예를 들어, 8개의 원소로 이루어진 배열이 있는데 이 배열을 4개의 원소로 이루어진 배열로 나눈 후 정렬한 뒤, 쌍방 합병해 정렬된 배열을 만들 수 있다. 이런 식으로 계속 분할해 나가면 원소가 하나인 배열이 될 텐데, 이 원소가 하나인 배열은 그 자체로 정렬된 배열이다. 이것을 합병정렬(Mergesort)이라고 한다.

 

1. 분할 : 배열을 반으로 분할한다. 분할한 배열의 원소는 각각 $n/2$개이다.

 

2. 정복 : 분할한 배열을 각각 따로 정렬한다(배열에 원소가 2개 이상이면 합병정렬을 재귀호출해 정렬한다.)

 

3. 취합 : 정렬한 두 배열을 합병해 정렬한다.

 

 

다음 배열을 위의 절차에 따라 합병정렬을 시켜보자.

 

 

20  13  12  45  32  15  24  4

1. 배열의 분할

 

20  13  12  45, 32  15  24  4

 

2. 분할한 배열을 따로 정렬 

 

12  13  20  45, 4  15  24  32

 

3. 정렬한 배열을 합병

 

4  12  13  15  20  24  32  45

 

 

 

합병정렬 작동 사례

 

두개의 배열 A, B가 합병하는 예

$k$	$A$	$B$	$S$(결과)
1	12 13 20 45	4 15 24 32	4
2	12 13 20 45	4 15 24 32	4 12
3	12 13 20 45	4 15 24 32	4 12 13
4	12 13 20 45	4 15 24 32	4 12 13 15
5	12 13 20 45	4 15 24 32	4 12 13 15 20
6	12 13 20 45	4 15 24 32	4 12 13 15 20 24
7	12 13 20 45	4 15 24 32	4 12 13 15 20 24 32
-	12 13 20 45	4 15 24 32	4 12 13 15 20 24 32 45

 

 

합병(Merge)의 최악 시간복잡도 분석

 

단위연산 : $A[i]$와 $B[j]$의 비교

입력크기 : 두 입력 배열의 원소 개수, $h$와 $m$

 

최악의 경우는 $i = h+1$이고 $j=m$인 상태에서 루프를 빠져나가는 경우이다.

 

따라서, 

$$W(h,m) = h+m-1$$

 

합병정렬(Merge sort)의 최악 시간복잡도 분석

 

단위연산 : merge에서 일어나는 비교연산

입력크기 : 배열 S의 아이템 수, $n$

 

총 비교 횟수는 $U, \,V$를 정렬하는데 걸리는 시간과, merge를 실행하는 비교연산의 횟수의 합이다.

 

따라서,

 

$$W(n) = W(h) + W(m) + h+m-1$$

 

만약 $n$이 2의 거듭제곱이면, 

 

$$\begin{eqnarray} W(n) &=& W( \frac{n}{2}) + W( \frac{n}{2} ) + n -1 \\ & = & 2W(\frac{n}{2}) + n -1 \end{eqnarray} $$

 

입력크기가 1이면 종료조건을 만족하므로 합병이 없다. 고로 $W(1) = 0 $이다. 결과적으로 재현식은 다음과 같다.

 

$$ \begin{eqnarray} W(n) & = & 2W( \frac{n}{2} ) + n -1 \,( n > 1 , n = 2^k (k \in \mathbb{N})) \\ W(1)& = & 0 \end{eqnarray} $$

 

이 재현식의 해는 다음과 같다.

 

$$W(n) = 2W( \frac{n}{2} ) - (n-1) \in \Theta (n \lg n )$$

 

이렇게 재현식의 해를 구할 때, 편하게 구하려면 Master Theorem을 알아야한다. 

 

https://kimmessi.tistory.com/155?category=871925 

[알고리즘] 마스터 정리, 보조 마스터 정리 (Master Theorem)

 

제자리 정렬 (in-place sort)를 이용한 합병정렬(Merge sort)

 

제자리 정렬 : 정렬하는데 필요한 장소 이외의 추가적인 저장장소를 이용하지 않는 정렬 알고리즘.

 

이때, 위의 합병정렬 알고리즘은 제자리 정렬이 아니다.

그 이유는 정렬하는데 배열을 추가적으로 사용하기 때문이다. 예를 들어 맨 처음 배열의 원소 개수가 $n$이라하면, 재귀 호출 할 때, 두 배열의 원소 개수의 합은 $n$이고, 두 번째는 $n/2$이고, 세 번째는 $n/4$이다. 이렇게 $n$이 충분히 크다고 가정하면 추가적으로 만들어지는 배열 원소의 총 개수는 

$n(1+ 1/2 + 1/4 + \cdots) = 2n$이다.

 

하지만 $n$개의 원소를 가진 배열 하나만 추가적으로 있어도 합병 정렬이 작동하도록 할 수 있다.

 

반응형

빠른정렬 (Quick sort)

 

퀵정렬이라고 불리는 빠른 정렬은 배열을 둘로 분할하고, 분할한 배열을 각각 재귀 호출로 정렬하여 합병하므로 합병정렬과 비슷하다. 그러나 빠른 정렬은 배열을 분할하는 방식이 합병 정렬과는 다르다. 빠른 정렬에서는 기준원소(pivot)을 선정해 기준원소보다 작은 원소는 모두 왼쪽 배열로, 기준원소보다 크거나 같은 원소는 모두 오른쪽으로 가도록 분할한다. 여기서, 기준원소 선정은 매우 중요하다. 

 

맨 앞의 원소를 기준원소로 선정했을 때의 예를 보자.

 

 

 

1. 기준원소보다 작은 원소는 모두 왼쪽으로, 큰 원소는 모두 오른쪽으로 가도록 분할한다.

 

 

 

2. 왼쪽, 오른쪽 배열을 각각 따로 정렬한다.

 

 

빠른 정렬은 분할한 배열을 각각 재귀 호출하여 정렬한다. 원소가 하나뿐인 배열로 분할될 때까지 재귀호출을 계속한다.

원소가 하나밖에 없는 배열은 정렬할 필요없다.

 

예시 알고리즘 작동 사례

 

분할(partition)

 

partition 알고리즘은 배열의 원소를 하나씩 차례로 점검한다. 기준원소보다 작은 원소는 배열의 왼쪽으로 옮긴다.

 

여기서 i,j 인덱스를 사용하는데 왼쪽으로 원소를 옮길 때, j에 1을 더해주고 배열의 i,j 각각에 해당하는 원소를 서로 바꿔준다. 그렇게 끝까지 반복 후, 마지막에 j 인덱스에 해당하는 원소와 기준 원소를 바꿔준다.

 

분할의 일정 시간복잡도 분석

단위연산 : $S[i]$와 $pivotitem$의 비교

입력크기 : $n = high - low + 1$ (부분배열 원소의 개수)

첫째 원소를 제외한 원소를 모두 비교하므로

 

$$T(n) = n-1$$

 

여기서 $n$은 부분배열의 크기를 나타낸다.

빠른정렬의 최악 시간복잡도 분석

단위연산 : partition에서 $S[i]$와 $pivotitem$의 비교

입력크기 : $n$(배열 $S$ 원소의 개수)

 

정렬된 배열을 정렬하는 경우에 최악의 경우가 발생한다. 이미 정렬된 사례들로 재현식을 세우면 다음과 같다.

 

$$T(n) = T(0) + T(n-1) + n-1$$

 

$$\begin{eqnarray} T(n) &=& T(n-1) + n -1 \,\,, n>0 \\ T(0) &=& 0 \end{eqnarray} $$

 

위의 재현식의 해는,

 

$$T(n) = \frac{n(n-1)}{2} $$

 

위의 경우가 최악의 사례인지 귀납법을 이용해 증명해보자. 

 

$$ W(n) \leq \frac{n(n-1)}{2} $$

 

1. $n=0$일 때

 

$$W(0) =0 \leq \frac{0(0-1)}{2} $$

 

2. $0 \leq k < n $이 성립하는 모든 $k$에 대해서 다음 부등식이 성립한다고 가정하자.

 

$$ W(k) \leq \frac{k(k-1)}{2} $$

 

3. 다음 부등식이 성립함을 보이자.

 

$$ W(n) \leq \frac{n(n-1)}{2} $$

 

$pivotpoint$의 값을 $p$라고 하자. 그러면 다음과 같은 식을 얻는다.

 

$$ \begin{eqnarray} W(n) & \leq & W(p-1) + W(n-p) + n-1 \\ & \leq & \frac{(p-1)(p-2)}{2} + \frac{(n-p)(n-p-1)}{2} +n-1 \end{eqnarray}$$

 

위의 식을 풀면 $1 \leq p \leq n$인 모든 $p$에 대해서 마지막 식은 다음과 같다.

 

$$ \leq \frac{n(n-1)}{2} $$

 

따라서 최악 시간복잡도 증명이 완료되었다.

 

$$W(n) = \frac{n(n-1)}{2} \in \Theta(n^2) $$ 

 

빠른정렬의 평균 시간복잡도 분석

 

무작위로 기준원소를 지정한다고 하자, 그럼 1 에서부터 $n$사이의 임의의 수가 기준원소가 될 것이고 어떤 수가 되든지 확률은 모두 같다. 그러므로 재현식은 다음과 같다.

 

$$A(n) = \sum ^n _{p=1} \frac{1}{n} [ A(p-1) + A(n-p)] +n-1 $$

 

여기서, $\frac{1}{n}$은 기준원소가 $p$번째 원소일 확률이다.

 

위의 재현식을 풀면, 평균 시간복잡도가 나오는데 다음과 같다.

 

$$ \begin{eqnarray} A(n) & \approx & (n+1)2 \ln n = (n+1) 2 (\ln 2)(\lg n ) \\ & \approx & 1.38(n+1) \lg n \in \Theta(n \lg n ) \end{eqnarray} $$

 

따라서 빠른정렬의 평균 시간복잡도는 합병정렬의 시간복잡도와 차수가 같다.