<알기쉬운 알고리즘> Chapter3 - 분할 정복 알고리즘

분할 정복 (Divide-And-Conquer)알고리즘이란 주어진 문제의 입력을 분할하여 문제를 해결(정복)하는 방식의 알고리즘 이다. 분할 된 입력에 대하여 동일한 알고리즘을 적용하여 해를 계산하며, 이들의 해를 취합하여 원래 문제의 해를 얻는다. 

여기서 분할된 입력에 대한 문제를 부분문제(subproblem) 이라고 하고, 부분 문제의 해를 부분해 라고 한다. 부분 문제는 더이상 분할 할 수 없을 때까지 계속 분할 한다. 

 

분할 정복 알고리즘의 분류 

문제가 a개로 분할 되고, 부분문제의 크기가 1/b로 감소하는 알고리즘 

                 (1) a=b=2인 경우, 합병 정렬, 최근접 점의 쌍 찾기, 공제선 문제 

                 (2) a=3,b=2인 경우, 큰 정수의 곱셈 

                 (3) a=4, b=2인 경우, 큰 정수의 곱셈 

                 (4) a=7, b=2인 경우, 스트라센의 행렬 곱셈 알고리즘 

문제가 2개로 분할 되고, 부분 문제의 크기가 일정하지 않은 크기로 감소하는 알고리즘 : 퀵정렬

문제가 2개로 분할 되나, 그 중에 1개의 부분문제는 고려할 필요 없으며, 부분문제의 크기가 1/2로 감소하는 알고리즘 : 이진탐색

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

부분문제의 크기가 1,2개씩 감소하는 알고리즘 : 삽입정렬, 피보나치 수열의 계산 

 

 

 

 

3.1 합병정렬(Merge Sort)

입력이 2개의 부분문제로 분할 되고, 부분문제의 크기가 1/2로 감소하는 분할 정복 알고리즘 . n개의 숫자들을 n/2개씩 2개의 부분문제로 분할 하고, 각각의 부분문제를 재귀적으로 합병 정렬한 후, 2개의 정렬된 부분을 합병하여 정렬(정복)한다. 즉, 합병 과정이 (문제를) 정복하는 것이다. 

 

 

MergeSort(A,p,q)
입력 : A[p]~A[q]
출력 : A[p]~A[q]
1 if(p>q){    //책에 잘못나온것 같다 if(q>p){  로 생각하자      // 배열의 원소의 수가 2개 이상이면 
2	k=|(p+q)/2|				 // k=반 으로 나누기 위한 중간 원소의 인덱스 
3    MergeSort(A,p,k) 		 // 앞부분 재귀호출 
4    MergeSort(A,k+1,q) 		 // 뒷부분 재귀호출 
5    A[p]~A[q]dhk A[k+1]~A[q] 를 합병한다. 
6}

 

 

line1에서는 정렬할 부분의 원소의 수가 2개 이상일 때만 다음 단계가 수행되도록 한다. 만일 p=q(즉 , 원소의 수가 1) 이면, 그 자체로 정렬된 것이므로 line 2~5가 수행되지 않은 채 이전 호출 했던 곳으로 리턴한다. 

line2에서는 정렬할 부분의 원소들을 1/2로 나누기 위해, k=|(p+q)/2| 를 계산한다. 단, 원소의 수가 홀수인 경우 k는 소수점 이하를 버린 정수이다. 

line 3~4에서는 MergeSort(A,p,k)와 MergeSort(A,k+1,q) 를 재귀호출하여 각각 정렬한다. 

line 5에서는 line 3~4에서 각각 정렬된 부분을 합병한다. 합병 과정의 마지막에는 임시배열에 있는 합병된 원소들을 배열 A로 복사한다. 즉, 임시배열 B[p]~B[q]를 A[p]~A[q]로 복사한다. 

 

 

합병정렬의 시간복잡도는 층수* O(n) = logn*O(n) = O(nlogn)

합병정렬의 공간복잡도는 O(n) 

(대부분의 정렬 알고리즘들은 입력을 위한 메모리공간과 O(1)크기의 메모리 공간만을 사용하면서 성렬을 수행한다. 

O(1) 크기의 메모리공간이란 입력 크기 n과 상관없는 크기의 공간-변수, 인덱스 등-을 의미한다. 

 

합병 정렬은 외부정렬의 기본이 되는 정렬 알고리즘이다. 연결 리스트에 있는 데이터를 정렬할 때에도 퀵 정렬이나 힙 정렬보다 훨씬 효율적이다. 

 

 

 

 

3.2 퀵정렬(Quick Sort) 

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

 

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

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

 

QuickSort(A,left,right)
입력 : 배열 A[left]~A[right]
출력 : 정렬된 배열 A[left]~A[right]
1 if(left<right){
2	피봇을 A[left]~A[right]중에서 선택하고, 피봇을 A[left]와 자리를 바꾼후, 
    피봇과 배열의 각 원소를 비교하여 피봇보다 작은 숫자들은 A[left]~A[p-1]로 옮기고,
    피봇보다 큰 숫자들은 A[p+1]~A[right]로 옮기며, 피봇은 A[p]에 놓는다. 
3 QuickSort(A,left,p-1) // 피봇보다 작은 그룹
4 QuickSort(A,p+1,right) // 피봇모다 큰 그룹
}

퀵정렬의 성능은 피봇 선택이 좌우한다. 

 

최선의 경우란 어떤 분할일까? 항상 1/2씩 분할한다면 최선의 경우가 될 것이다. 피봇이 입력을 2등분으로 분할 하는 경우는 입력의 중앙값이 피봇으로 선택될 때이다. 

 

퀵정렬의 시간복잡도

 

 

피봇 선정방법  - 랜덤하게 선정하는 방법 , 3 숫자의 중앙값으로 선정하는 방법 

 

입력의 크기가 매우 클 때, 퀵 정렬의 성능을 더 향상시키기 위해서, 삽입 정렬이 동시에 사용되기도 한다. 

입력의 크기가 작을 때에는 퀵 정렬이 삽입 정렬보다 빠르지많은 않다. 왜냐하면 퀵 정렬은 재귀 호출로 수행되기 때문이다. 

퀵정렬은 커다란 크기의 입력에 대해서 가장 좋은 성능을 보이는 정렬 알고리즘 이다. 

 

 

3.3 선택문제 (Selection)

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

<간단한 방법>

1) 최초 숫자를 k번 찾는다. 단 최소 숫자를 찾은 뒤에는 입력에서 그 숫자를 제거한다.

2) 숫자들을 오름차순으로 정렬한후, k번째 숫자를 찾는다.

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

 

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

 

Selection(A,left,right,k)
입력 : A[left]~A[right]와 k, (단, 1<=k<=|A|, |A|=right-left+1)
출력 : A[left]~A[right] 에서 k 번째 작은 원소 
1 피봇을  A[left]~A[right] 에서 랜덤하게 선택하고 피봇과  A[left] 자리를 바꾼후, 
  피봇과 배열의 각 원소를 비교하여 피봇 보다 작은 숫자는  A[left]~A[p-1] 로 옮기고, 
  피봇보다 큰 숫자는 A[p+1]~A[right] 로 옮기며 피봇은  A[p] 에 놓는다. 
2 S=(p-1)-left+1   						// S=small group 의 크기 
3 if(k<=S) Selection(A,left,p-1,k)		// Small group 에서 찾기 
4 else if(k=S+1) return A[p]			// 피봇 =k 번째 작은 숫자 
5 else Seleciton(A, p+1 right, k-S-1)	// large group 에서 찾기 
 // k-S-1 에서 1은 피봇에 해당한다. 

 

line 1은 피봇을 랜덤하게 선택하는 것을 제외하고는 퀵 정렬 알고리즘의 line2와 동일하다. 

line2 에서는 입력을 두 그룹으로 분할 한 후, A[p]가 피봇이 있는 곳이기 때문에 Small group의 크기를 알 수 있다. 

즉, Small group 의 가장 오른쪽 원소의 인덱스가 (p-1) 이므로, Small group 의 크기 S 는 (p-1)-left+1 이다. 

line3 은 k번째 작은 수가 Small group 에 속한 경우이므로 Selection(A,left,p-1,k)를 호출한다. 

line4 는 k번째 작은 수가 피봇 A[p]와 같은 경우 이므로 해를 찾은 것이다. 

line5 에서는 k 번째 작은 수가 Large group에 속한 경우이므로 Selection(A,p+1,right,k-S-1)을 호출한다. 이때에는 (k-S-1)번째 작은 수를 Large group 에서 찾아야 한다. 왜냐하면 피봇이 k 번째 작은 수 보다 작고, S 는 Small group 의 크기이기 때문이다. 

 

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

선택 알고리즘은 정렬을 하지 않고 k번째 작은 수를 선형시간에 찾을 수 있게 해준다. 따라서 선택 알고리즘은 데이터 분석을 위한 중앙값을 찾는데 활용된다. 

 

 

3.4 최근접 점의 쌍 찾기 - 다시 봐야함. 

 

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

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

 

피보나치 수 계산을 위한 O(n) 시간 알고리즘 
FibNumber(n)
F[0]=0
F[1]=1
for i=2 to n
	F[i]=F[i-1]+F[i-2]