[알고리즘] 분할 정복 알고리즘(Divide-and-Conquer) - 합병 정렬(merge sort)

분할 정복 알고리즘이란?

주어진 문제의 입력을 분할하여 문제를 해결(정복)하는 방식의 알고리즘입니다.

• 분할한 입력에 대하여 동일한 알고리즘을 적용하여 해를 계산합니다.
• 이들의 해를 취합하여 원래 문제의 해를 얻습니다.

분할 알고리즘의 분할은 부분 문제와 부분 해로 나누어 집니다.

• 분할된 입력에 대한 문제를 부분 문제(subproblem)라고 합니다. -> 해 계산
• 부분 문제의 해를 부분 해라고 합니다.
• 부분 문제는 더 이상 분할 할 수 없을 때까지 분할합니다.

크기가 n인 입력을 3개로 분할하고, 각각 분할된 부분 문제의 크기가 n/2일 경우의 분할의 예입니다. 총 분할한 횟수가 k라고 한다면, 처음 입력의 크기가 n이고, 분할된 그 다음의 크기는 n/2, 그 다음은 n/(2^2), ... , n/(2^k-1), n/(2^k) 입니다.

n/(2^k) = 1 일 경우에 더 이상 분할 하지 못하므로, k = log_2(n)이라고 할 수 있습니다.

 

합병 정렬은 입력이 2개의 부분 문제로 분할되고, 부분 문제의 크기가 1/2로 감소하는 분할 정복 알고리즘입니다.

• n개의 숫자들을 n/2개씩 2개의 부분 문제로 분할합니다.
• 각각의 부분 문제를 순환으로 합병 정렬합니다.
• 2개의 정렬된 부분을 합병하여 정렬합니다.(정복)

합병(merge) 알고리즘은 다음과 같습니다.

public class Merge {
	public static void main(String[] args) {
		int[] A = { 6, 14, 18, 20, 29 };
		int[] B = { 1, 2, 15, 25, 30, 45 };
		
        // 정렬된 데이터를 담을 배열
		int[] C = new int[A.length + B.length - 2];
		
        // A, B, C의 시작 인덱스
		int i = 0, j = 0, k = 0;
		
        // i또는 j가 A또는 B배열의 길이보다 작을 때까지 진행
		while(i <= A.length - 1 && j <= B.length - 1) {
			if(A[i] <= B[j]) {
				C[k++] = A[i++];
			} else {
				C[k++] = B[j++];
			}
		}
		
        // B 배열이 남을 경우
		if(i > A.length) {
			for(int l = j ; l < B.length ; l++) {
				C[k++] = B[l];
			}
		}
		
        // A 배열이 남을 경우
		if(j > B.length) {
			for(int l = i ; l < A.length ; l++) {
				C[k++] = A[l];
			}
		}
		
		for(int l : C) {
			System.out.print(l + " ");
		}
        // 출력결과 : 1 2 6 14 15 18 20 25 29 
	}
}

 

합병 알고리즘을 이용하여 아래 분할 정복에 대한 합병 정렬 알고리즘을 코드로 나타내보겠습니다.

public class MergeSort {
	static int[] sorted;
	public static void main(String[] args) {
		int[] A = { 37, 10, 22, 30, 35, 13, 25, 24 };
		
		int p = 0, q = A.length - 1;
		
		sorted = new int[A.length];
		
		mergeSort(A, p, q);
		
		for(int i = 0 ; i < q ; i++) {
			System.out.print(sorted[i] + " ");
		}
	}
	
    // Divide-and-Conquer에서의 Merge Sort
	static void mergeSort(int[] A, int left, int right) {
		if(left < right) {
			int mid = (left + right) / 2; // Divide
			mergeSort(A, left, mid); // Conquer
			mergeSort(A, mid + 1, right); // Conquer
			merge(A, left, mid, right); // Merge
		}
	}
	
    // Merge Sort
	static void merge(int[] A, int left, int mid, int right) {
		int i = left, j = mid + 1, k = left;
		while(i <= mid && j <= right) {
			if(A[i] <= A[j]) {
				sorted[k++] = A[i++];
			} else {
				sorted[k++] = A[j++];
			}
		}
		
		if(i > mid) {
			for(int l = j ; l <= right ; l++) {
				sorted[k++] = A[l];
			}
		} else {
			for(int l = i ; l <= mid ; l++) {
				sorted[k++] = A[l];
			}
		}
		
		for(int l = left ; l <= right ; l++) {
			A[l] = sorted[l];
		}
	}
}

 

시간 복잡도

• 분할하는 부분 (Divide)
   - 배열의 중간 인덱스 계산과 2회의 순환 호출이므로 O(1)  시간이 소요됩니다.
• 합병의 수행 시간 (Merge)
  - 입력의 크기에 비례합니다.
  - 2개의 정렬된 배열 A와 B의 크기가 각각 m과 n이라면, 최대 비교 횟수 = (m + n - 1) 입니다.
  - 합병의 시간 복잡도 = O(m + n) -> O(n)

• 합병 정렬에서 수행되는 총 비교 횟수
  - 각각의 합병에 대해서 몇 번의 비교가 수행되었는지를 계산하여 이들을 모두 합한 수 입니다.
• 층별 비교횟수
  - 각 층을 살펴보면 모든 숫자(즉, n = 8 개의 숫자)가 합병에 참여합니다.
  - 합병은 입력 크기에 비례하므로 각 층에서 수행된 비교 횟수는 O(n)입니다.
• 층수의 계산
  - 층수를 세어보면, 8개의 숫자를 반으로, 반의 반으로 반의 반의 반으로 나눕니다.
  - 이 과정을 통하여 세 층이 만들어집니다.
• 입력 크기가 n일 때는 몇 개의 층이 만들어질까요?
  - n을 계속하여 1/2로 나누다가, 더 이상 나눌 수 없는 크기인 1일 될 때 분할을 중단합니다.
  - 따라서 k번 1/2로 분할했으면 k개의 층이 생기는 것이고, k는 2^k = n 으로부터 k = log_2(n) 임을 알 수 있습니다.
• 합병 정렬의 시간 복잡도 = (층수) * O(n) = log_2(n) * O(n) = O(nlog(n))

 

합병 정렬의 단점

• 합병 정렬의 공간 복잡도 : O(n)
  - 입력을 위한 메모리 공간 (입력 배열)외에 추가로 입력과 같은 크기의 공간 (임시 배열)이 별도로 필요합니다. (코드에서는 C, sorted 배열을 의미 합니다.)
  - 2개의 정렬된 부분을 하나로 합병하기 위해, 합병된 결과를 저장할 곳이 필요하기 때문입니다.