분할 정복 ( Divide and conquer Algorithm )

1. 개요

[그림 1] 분할 정복법 ( Divide and conquer )

 알고리즘 방법론중 하나인 분할정복 ( Divide and conqeur ) 알고리즘은 하나의 문제를 작은 문제로 분할하여 문제를 해결하는 방법이다. 분할 정복 알고리즘은 보통 재귀함수 ( Recursive function )을 이용해서 구현하는 것이 일반적이나 빠른 실행이나 부문제 해결 순서 선택을 위해 재귀호출을 사용하지 않고 스택(Stack), 큐(Queue) 등의 자료구조를 이용하여 분발 정복법을 구현하는 것도 가능하다.

분할 정복의 설계전략으로는

1. 분할 (Divide) : 해결할 문제를 여러 개의 작은 부분으로 나눈다.

2. 정복 (Conquer) : 나눈 작은 문제를 각각 해결한다.

3. 통합 (Combine) : 해결된 해답을 모은다 (필요할 경우)

---

2. 퀵 정렬 ( Quick Sort )

[그림 2] 퀵 정렬 (Quick Sort) 과정

 퀵정렬은 축(pivot)값을 중심으로 연속적으로 분할하며 정렬하는 기법으로 pivot 값을 중심으로 왼쪽은 pivot보다 작은 값으로 오른쪽은 pivot보다 큰 값으로 배열시키는 것이다. 속도는 평균적으로  O(n log n)번의 비교를 수행한다.

퀵 정렬의 구현 방법은 아래와 같다.

1. 배열의 가장 우측의 값은 Pivot 으로 설정한다. ( ex ) 10 )

2. 한 구간 안에서 다음을 반복적으로 수행한다.

2-1. 구간의 좌측으로부터 Pivot 값보다 큰 값이 있는 가를 i 를 증가시키며 검사

2-2. 구간의 우측으로부터 Pivot 값보다 작은 값이 있는 가를 j 를 감소 시키며 검사한다.

2-3. i<j 이면 i의 자리값과 j의 자리에 있는 값은 서로 Swap 한다

3. i>=j 이면 한 구간에 대한 교환이 완료된 것이므로 i의 자리값과 Pivot의 값을 서로 Swap 해준다.

(Pivot값을 중심으로 좌측에는 Pivot보다 작은 값들이 위치하게 되고 우측에는 Pivot보다 큰 값들이 위치하게 된다)

4. 이러한 과정을 Pivot값을 중심으로 나누어 좌측과 우측 두 구간에 대하여 똑같이 반복한다. (구간의 크기가 1이 될 때까지)

int main() { int dataList[] = { 38,27,43,3,9,82,10 }; int size = sizeof(dataList) / sizeof(dataList[0]); printf(" size = %d \n", size); quickSort(dataList, size); printf("\n\n[퀵 정렬 후 출력]\n"); output(dataList, size); return 0; } /////////////////////////////////////////////////// void quickSort(int *ary, int size) { int pivot, temp; int i, j; if (size <= 1)return; // 구간값이 1이하이면 sort가 완료된 것이므로 return pivot = ary[size - 1]; // 구간의 가장 우측값을 pivot으로 정함 i = 0; j = size - 1; while (1) { if (i >= j) break; for (;i< size-1; ++i) if (ary[i] > pivot) break; for (; j>=0; --j) if (ary[j] < pivot) break; if (i < j) { temp = ary[i]; ary[i] = ary[j]; ary[j] = temp; } } temp = ary[i]; ary[i] = ary[size-1]; ary[size - 1] = temp; quickSort(ary, i); // 좌측 소구간에 대한 퀵 정렬 재귀 호출 quickSort(ary + i + 1, size - i - 1); // 우측 소구간에 대한 퀵 정렬 재귀 호출 }

다음 코드는 [그림 2]의 배열을 퀵 정렬한 코드이다.

우선, Pivot값을 10으로 설정한다. 10보다 큰 값을 i 10보다 작은 값을 j 라 하고 구간안에서 탐색을 시작한다.

( [38] [27] [43] [3] [9] [82] [10] )

i j

처음엔 i는 38 (0번방) 일 것이고 j는 9 (4번방) 일 것이다. i보다 j가 크므로 서로 swap한다.

( [9] [27] [43] [3] [38] [82] [10] )

i j

다음은 i는 다음번 원소 27 (1번방) 일 것이고 j는 3 (3번방)일 것이고 여전히 i보다 j가 크므로 서로 swap한다.

( [9] [3] [43] [27] [38] [82] [10] )

j i

다음은 i는 다음번 원소 43 (2번방)일 것이고 j는 3 (1번방)일 것이고, i 가 j보다 크므로 반복문을 탈출하여 i값과 Pivot값을 바꿔주며 첫번째 교환이 끝나게되고 Pivot값 = 10 (2번방) 을 중심으로 왼쪽에는 작은값들 오른쪽에는 큰 값들이 위치하게 된다.

( [9] [3] [10] [27] [38] [82] [43] )

PIVOT

재귀호출을 통하여 왼쪽구간과 오른쪽구간을 위 과정과 똑같이 해주고나면 정렬이 완료된다.

---

3. 이분검색 ( Binary Search )

[그림 3] 이분탐색 (Binary Search) 과정

 이분검색 (Binary Search)는 배열의 구간을 반 씩 나누어 검색해 나가는 기법으로 이것또한 분할정복법이다. 처음부터 끝까지 순서대로 찾는 일반적인 순차검색기법에 비해 검색속도가 빠른 것이 장점이지만, 데이터가 미리 정렬이 되어 있어야 하는 단점(?)이 있다. 따라서 경우에 따라서는 쓰기 곤란한 경우가 있다. 시간복잡도 O(logn) 이며, 약 43억개의 원소가 있다고 가정하면 최악의 탐색 깊이 ( 값이 없는 경우 ) 가 딱 32회이다. 그러나 일반적인 순차탐색의 경우 최악의 경우는 43억...이다. 그만큼 순차검색에 

비해 속도가 빠르다.

이분검색의 알고리즘은 다음과 같다.

1. while ( 검색구간의 크기 > 0 )

1.1 구간의 중간값을 구한다.

1.2 구간의 중간값이 key 값과 같으면 찾은 것이므로 index 리턴

1.3 key값이 중간값 보다 크면 오른쪽구간을 선택하고 1로 돌아감

1.4 key값이 중간값 보다 작으면 왼쪽구간을 선택하고 1로 돌아감

2. 구간의 크기가 0이면 찾지 못한 것.

int main() { int ary[12] = { 1,4,4,7,7,8,11,19,21,23,24,30 }; int size; int key; int index; int res; size = sizeof(ary) / sizeof(ary[0]); quickSort(ary, size); output(ary, size); while (1) { printf("검색할 숫자를 입력 (문자입력시 종료) :"); res = scanf("%d", &key); if (res != 1) { break; } if ((index = nrbinarySearch(ary, 0, size - 1, key)) != -1) printf(" %d는 %d번방 데이터입니다.\n", key, index); else printf("%d는 존재하지 않습니다.\n", key); } return 0; } ///////////////////////////////////////////////////////////////// void main int nrbinarySearch(int *ary, int leftIndex, int rightIndex, int key) { int mid = (rightIndex + leftIndex) / 2; //중간값 printf("ary[mid]=%d\n", ary[mid]); if (rightIndex < leftIndex)return -1; if (ary[mid] == key) return mid; else if (ary[mid] < key) // 검색할값이 더 크면 return nrbinarySearch(ary, mid + 1, rightIndex, key); else if (ary[mid] > key) return nrbinarySearch(ary, 0, mid - 1, key); }

다음은 [그림 3]을 이분탐색으로 재귀호출로 구현한 코드이다. 기본 부분(Base Part)는 당연히 첫째는 찾고자하는 key값과 구간의 중간값이 같은경우 이고 두번째는 왼쪽인덱스가 오른쪽인덱스보다 커지는 구간 즉, 구간의 크기가 0이되는 순간이다.구간의 크기가 0이 될 때동안 key값과 동일한 값을 찾지 못했으므로 함수를 종결시킨다.

( [1] [4] [4] [7] [7] [8] [11] [19] [21] [23] [24] [30] )

[그림 3]의 경우 중간값은 rightIndex = 11 + leftIndex = 0 / 2 => 5 이므로 5번방 원소 "8"이 될것이고 8은 찾고자하는 값 19와 같지 않고 key값이 중간값보다 크므로 오른쪽구간을 선택한다.

( [11] [19] [21] [23] [24] [30] )

오른쪽 구간에서의 중간값은 rightIndex = 11 + leftIndex = 6 / 2 => 8 이므로 8번방 원소 "21"이 될것이고 21은 찾고자하는 값 19와 같지 않고 key값이 중간값보다 작으므로 왼쪽구간을 선택한다.

( [1] [4] [4] [7] [7] [8] )

(그림에서는 생략) 왼쪽구간에서의 중간값은 rightIndex = 7 + leftIndex = 0 / 2 => 3 이므로 7번방 원소 "7"이 될것이고 7은 찾고자하는값 19와 같지 않고 key값이 중간값보다 크므로 오른쪽구간을 선택한다.

( [7] [8] [11] [19] )

오른쪽 구간에서의 중간값은 rightIndex = 7 + leftIndex = 4 / 2 => 5 이므로 5번방 원소 "8"이 될것이고 8은 찾고자하는값 19와 같지 않고 key값이 중간값보다 크므로 오른쪽구간을 선택한다.

( [11] [19] )

오른쪽 구간에서의 중간값은 rightIndex = 7 + leftIndex = 6 / 2 => 6 이므로 6번방 원소 "11"이 될것이고 11은 찾고자하는 값 19와 같지않고 key값이 중간값보다 크므로 오른쪽구간을 선택한다.

( [19] )

오른쪽 구간에서의 중간값은 rightIndex = 7 + leftIndex = 7 / 2 => 7 이므로 7번방 원소 "19"가 될것이고 찾고자 하는 값과 맞으므로 함수를 끝낸다.

---

3-2 ) 이분검색 비재귀

/*--------------------------------------------------------------------- 함수명 및 기능 : binarySearch() - 이분 검색 함수 전달인자: ary - 검색할 데이터 배열의 시작주소 leftIndex - 검색 구간의 좌측 인덱스 rightIndex - 검색 구간의 우측 인덱스 key - 검색할 데이터 리턴값: 검색 성공 시 - 찾은 숫자의 index / 검색 실패 시 - -1 리턴 --------------------------------------------------------------------*/ int binarySearch(int *ary, int leftIndex, int rightIndex, int key) { int midIndex; // 중간위치값의 인덱스 while (rightIndex >= leftIndex) while (1) { midIndex = (leftIndex + rightIndex) / 2; if (key == ary[midIndex]) return midIndex; // 찾은 데이터의 index값을 리턴 else if (key < ary[midIndex]) rightIndex = midIndex - 1; else leftIndex = midIndex + 1; if (rightIndex < leftIndex) break; } return -1; // 못찾았으면 -1 리턴 }