Divide and Conquer: 분할 정복 - 이분탐색, 합병정렬

 

개념

문제의 입력 사례를 두 개 이상의 작은 케이스로 분할한 후 분할한 입력의 답을 바로 구할 수 있다면 원래 문제의 답은 분할로 얻은 답들을 통해 구할 수 있는 방식. 상위 입력 사례의 해답을 하위 입력 사례 해답을 이용해 구하기 때문에 하향식(top-down) 풀이 방식에 속한다.

 

분할 정복의 흐름

예시

1) 이분탐색

10

12

15

16

18

20

25

27

42

43

이분탐색을 사용하려면 배열이 이미 정렬된 상태여야 한다. 위와 같은 배열에서 27이 배열 안에 있는지 확인한다고 가정하자.

 

① [분할] 가운데에 위치한 원소를 기준으로 배열을 나누고 찾는 값이 가운데 원소보다 작으면 왼쪽 배열, 크면 오른쪽 배열을 선택

② [정복] ①에서 선택한 부분에 찾고자 하는 값이 있는지 재귀적으로 이분 검색

③ [병합] ②에서 얻은 답으로 전체에 대한 답 도출

 

cf. 재귀를 분할 정복으로 구현할 경우 고려해야 할 사항

- 분할한 사례의 답으로부터 전체 입력 사례의 답을 구하는 방법 고안하기

- 종료 조건 정하기

- 종료 조건을 만족할 경우 답을 구하는 방식 정하기

 

 

재귀로 구현한 이분탐색(C언어)

int binarySearch(int arr[], int low, int high, int target) {
	// 배열의 인덱스 값
	int mid;

	if (low > high) {
		return 0;
	}
	else {
		mid = (low + high) / 2;

		if (arr[mid] == target) {
			return mid;
		}
		else if (arr[mid] < target) {
			return binarySearch(arr, mid + 1, high, target);
		}
		else {
			return binarySearch(arr, low, mid - 1, target);
		}
	}
}

 

 

2) 합병정렬(merge sort)

하나의 배열을 두 개의 배열로 나누어 정렬 상태를 유지하면서 합쳐 순서대로 정렬된 한 개의 최종적인 배열을 얻는 절차이다. 배열의 길이가 1이 될 때까지 분할을 반복하며, N개의 원소를 가진 배열의 합병정렬 과정은 아래와 같다.

 

① [분할] 배열을 반으로 분할(분할된 배열의 원소는 각각 N/2개)

② [정복] 분할한 배열을 각각 따로 정렬(배열의 원소가 2개 이상이면 합병정렬을 재귀 호출하여 정렬)

③ [병합] 정렬한 두 배열을 합치기

 

 

합병정렬 구현(C언어)

// 정렬된 상태의 부분 배열을 합병하는 함수
void merge(int array[], int left, int right) {
	int i, j, k;
	int mid = (left + right) / 2;

	i = left;
	j = mid + 1;
	k = left;

	// 이웃한 원소끼리 비교하며 배열 정렬 및 삽입
	while (i <= mid && j <= right) {
		if (array[i] <= array[j]) {
			res[k] = array[i];
			i++;
		}
		else {
			res[k] = array[j];
			j++;
		}
		k++;
	}

	// 남아있는 값들을 일괄 복사
	if (i > mid) {
		for (int l = j; l <= right; l++) {
			res[k] = array[l];
			k++;
		}
	}
	else {
		for (int l = i; l <= mid; l++) {
			res[k] = array[l];
			k++;
		}
	}

	// 임시 배열에 들어있는 값들을 원래 배열로 복사
	for (int l = left; l <= right; l++) {
		array[l] = res[l];
	}
}

void mergeSort(int arr[], int l, int r) {
	int mid;

	if (l < r) {
		mid = (l + r) / 2;			// 하나의 배열을 두개로 균등 분할

		mergeSort(arr, l, mid);		// 중간 인덱스 기준 좌측 배열
		mergeSort(arr, mid + 1, r);	// 중간 인덱스 기준 우측 배열

		merge(arr, l, r);			// 정렬된 부분 배열들을 합병
	}
}

 

합병정렬 코드 실행 결과