[알고리즘] CHAP 1. Divide and Conquer (분할정복) - mergesort

이번 챕터에서는 divide and conquer에 대해 다뤄볼 예정이다. 목차는 다음과 같다.

• 분할정복 알고리즘?
• 예시 - merge sort

그럼 시작!

---

1. Divide-and-Conquer ?

분할정복은 본격적인 알고리즘 수업의 첫 시간에 배운 알고리즘이다. 그만큼 기초적인 부분이라고 할 수 있다. 

분할정복이란 하나의 문제를 작은 여러개의 문제로 쪼갠 후 재귀적으로 각 문제를 해결한 후 이를 다시 합쳐 원래 문제를 해결하는 방법이다. 이에 대한 접근은 다음과 같이 할 수 있다.

 

STEP 1) Divide

답을 얻을 수 있을 때까지 한 문제를 2개 이상의 작은 문제로 나눈다. 

 

STEP 2) Conquer

길이가 충분히 짧아지면 답을 바로 구할 수 있다.

 

STEP 3) Combine

작은 문제를 해결하면서 결합해 나간다.

 

이렇게 쪼개진 것을 결합하면서 문제를 풀어가는 접근을 Top-down approach라고 한다.

이 Divide-and-Conquer형식의 알고리즘은 여러 개가 있지만 대표적으로 mergesort, quicksort, master theorem이 있다. 

 

 

이번 게시물에서는 mergesort를 알아보자

---

2. Mergesort

얘는 자료구조론에서도 배웠던 알고리즘이다.  이 알고리즘은 분할정복 알고리즘 중 하나이기 때문에 분할정복으로 접근해보려한다.

 

# Design strategy

- Divide

배열을 2개의 서브배열로 나누어준다. (각각 n/2개씩 갖도록)

- Conquer

각 서브배열을 재귀를 사용해 해결한다

- Combine

나눈 서브배열을 하나로 합침으로써 문제를 해결한다

 

# Code

코드는 수도코드(Pseudo-Code)로 작성한다.

void merge(int h, int m, const keytype U[], const keytype V[], const keytype S[]) {
	// h는 subarr1, m은 subarr2의 길이
    index i = 1, j = 1, k = 1;
    while (i <= h && j <= m) {
    	if (U[i] < V[j]) { S[k] = U[i]; i++; }
        else { S[k] = V[j]; j++; }
        k++;
    }
    
    if (i > h) copy V[j] through V[m] to S[k] through S[h+m];
    else copy U[i] through U[h] to S[k] through S[h+m];
}

 

mergesort 과정

 

divide를 거치면서 매 과정을 stack에 저장해두었다가, merge를 거치며 꺼내어 병합한다.

---

# Worst-case Time Complexity

나눠진 두 개의 배열의 크기를 h, m이라고 할 때, i = h, j = m - 1이고 h + m = n이다. 따라서 worst case는 merge 했을 때 U의 원소와 V의 원소가 번갈아가며 병합되는 경우이다. 

 

h + m이 n과 같으므로, worst case는 W(h,m) = h + m - 1이고, W(h,m)은 W(n)으로 바꿀 수 있다.

재귀를 사용한다는 걸 이용하면 최종적으로 W(n) = W(n/2) + W(n/2) + n - 1이라고 쓸 수 있게 된다. (n - 1은 merge 횟수)

 

이를 풀게 되면,

W(n) = 2W(n/2) + n - 1     n > 1, n = 2^k

W(1) = 0 (원소가 1개면 비교할 필요 없음)

 

이므로, W(n) = θ (n lg n)이다.

 

 

# Space Complexity

결론적으로 mergesort는 In-place sort가 아니다!

 

In-place sort는 제자리정렬이라는 의미로, 추가 메모리공간을 사용하지 않는 알고리즘을 의미한다. mergesort는 여러 배열을 생성함으로써 추가적인 메모리를 사용하므로 제자리정렬이  아니게 된다.

 

mergesort의 공간복잡도를 알려면 추가 배열의 총 개수를 알아야 하고, 이는 n + n/2 + n/4 + ... = 2n이 된다. 

즉, 2n ∈ θ(n) 이다.

 

---

다음 게시물에서는 divide-and-conquer의 다른 예시인 quicksort에 대해 다루어 볼 예정이다!