분할 정복법(Divide & Conquer)과 합병 정렬(Merge Sort)

분할 정복법(Divide & Conquer)이란

---

분할 정복법은 주어진 문제를 작은 단위로 분할(Divide)하여 작은 단위부터 정복(Conquer)하는 방식입니다.

 

일반적으로 재귀식을 사용해 큰 문제를 최대한 작게 쪼개고, 이 부분들을 하나씩 해결해 나갑니다.

 

순차적 방법보다 비교적 성능이 좋으며 대표적으로 O(n log n)의 성능을 갖는 합병정렬과 퀵정렬이 있습니다.

 

 

 

분할 정복법 설계전략

---

분할 정복법의 설계전략은 3단계의 하향식(top-down) 해법을 사용합니다.

 

1. 분할

해결하기 쉽게 큰 문제를 여러 개의 작은 부분으로 분할합니다.

2. 정복

분할된 문제들을 각각 해결(정복)하여 부분 해를 구합니다.

3. 통합

필요하다면 부분 해를 통합하여 전체 해를 구합니다.

 

---

이러한 방식으로 이루어지는 분할 정복은 다음과 같은 장점과 단점을 지닙니다.

장점

어려운 문제를 작은 단위로 쪼개가며 해결할 수 있다는 메리트가 있습니다.

문제를 나눠가며 해결하기 때문에 병렬 처리에 큰 강점을 지닙니다.

단점

재귀 호출을 이용하기 때문에 문제의 규모가 커진다면,

스택 오버플로우가 발생하거나 과도하게 메모리를 잡아먹을 수 있습니다.

 

 

 

합병 정렬

---

합병 정렬은 분할-정복-통합 3단계가 명확하게 구분되는 분할 정복의 대표적인 알고리즘입니다.

 

성능은 O(n log n)의 성능을 보여줍니다.

 

이는 더이상 나눌 수 없을 때 까지 n을 1/2로 나눈다면 log n 만큼의 시간이 필요하고,

합병 연산마다 정렬하기 위해 자료별로 한 번의 연산이 필요하기 때문에 각각 n의 연산이 필요합니다.

 

그렇기때문에 O(n log n)의 시간 복잡도를 가지게 됩니다.

 

코드

public class MergeSortEx {
	public static int[] list = new int[8];
	public static int[] tmp = new int[8]; // 정렬한 결과 저장
	
	public static void mergeSort(int start, int end) {
		if(start < end) { // 리스트의 자료를 하나가 될 때까지 분할
			int mid = (start+end) / 2;
			mergeSort(start, mid); // 왼쪽 리스트 분할
			mergeSort(mid+1, end); // 오른쪽 리스트 분할
			merge(start, mid, end); // 정렬 및 통합
		}
	}
	
	public static void merge(int start, int mid, int end) {
		int left = start;
		int right = mid + 1;
		int point = start;
		
		while(left <= mid && right <= end) {
			if(list[left] <= list[right]) {
				// 왼쪽 자료가 더 작거나 같으면 tmp에 삽입
				tmp[point++] = list[left++];
			} else {
				// 오른쪽 자료가 더 작으면 tmp에 삽입
				tmp[point++] = list[right++];
			}
		}
		// 왼쪽 리스트의 자료를 모두 삽입했다면 오른쪽 리스트의 나머지 자료 모두 삽입
		while(right <= end) {
			tmp[point++] = list[right++];
		}
		
		// 오른쪽 리스트의 자료를 모두 삽입했다면 왼쪽 리스트의 나머지 자료 모두 삽입
		while(left <= mid) {
			tmp[point++] = list[left++];
		}
		
		// 정렬 결과를 원본 리스트에 복사
		for(int i=start;i<=end;i++) {
			list[i] = tmp[i];
		}
		
		System.out.println(Arrays.toString(tmp));
		
	}
	
	public static void main(String[] args) {
		for(int i=0;i<8;i++) {
			list[i] = (int)(Math.random()*100)+1;
		}
		mergeSort(0, list.length-1);
		
		System.out.println(Arrays.toString(list));
	}
}

 

출력 결과를 보면 자료의 정렬 진행 과정을 확인할 수 있습니다.