[Algorithm Part 3] 2. Divide-and-Conquer

이번 글에서는, 알고리즘 설계 시 사용되는 접근법들 중 하나인 divide-and-conquer에 대해 살펴볼 것이다.

---

Divide-and-Conquer

Definition

divide-and-conquer는 instance를 작은 instance(s)로 쪼개 푼 것을 기반으로, original instance를 푼다.

Approach

divide-and-conquer 알고리즘은 다음 3단계 절차를 기반으로 설계돼야 한다.

1. (문제의) instance를 (같은 문제의) 작은 instance(s)로 쪼갠다.(즉, 정렬 instance를 작은 정렬 instance로 쪼갠다.)
2. 작은 instance(s)를 푼다. (이때, 작은 instance를 더 쪼갤 수 있다면, 재귀를 통해 푼다.)
3. 작은 instance(s)의 solution(s)을 기반으로 original instance의 solution을 구한다.

이 접근법은 top-down 방식이다. top-level instance의 solution이 작은 instance(s)의 solution에 의해 구해지기 때문이다.

 

재귀 알고리즘 설계 시, 

1. 작은 instance(s)의 solution(s)를 기반으로 original instance의 solution을 구하는 방법을 설계해야 한다.
2. terminal condition을 설정해야 한다. 즉, 어느 instance가 terminal condition인지 설정해줘야 한다.
3. (instance가) terminal condition인 경우, solution 설정을 해줘야 한다.

이제부터, divide-and-conquer에 대한 이해도를 높이기 위해, 이 접근법을 활용한 유명 알고리즘에 대해 살펴볼 것이다.

---

1. Binary Search

Problem

전형적인 탐색 문제다. 즉, 크기가 n인 정렬 배열 S에 탐색키 x가 있는지 확인하는 문제다.

Algorithm 

만약 배열의 중간 item(=S[mid])과 x가 같다면, 중간 index(=mid) 반환. 그렇지 않다면,

1. 배열을 반으로 쪼개, 작은 배열 2개(S[:mid]와 S[mid+1:])를 만든다.
2. 작은 배열에서 탐색키 $x$가 있는지 확인하는 문제를 푼다. (만약, 작은 배열을 더 쪼갤 수 있다면, 재귀를 통해 풀어라)
   
   1. x가 S[mid]보다 크다면, S[:mid] 선택
   2. x가 S[mid]보다 작다면, S[mid+1:] 선택
3. 작은 배열의 solution으로 original 배열의 solution을 구한다.

위 알고리즘은 꼬리 재귀(=재귀호출 이후에는 로직이 없는 경우)을 사용했다.

때문에, 꼬리 재귀(=tail-recursion) 버전에서 반복(=iteration) 버전으로 알고리즘을 수정할 수 있다.

이는, 재귀 호출로 생기는 메모리 사용량을 없애, 메모리 사용량을 획기적으로 줄일 수 있다.

Performance

base operation: x와 S[mid]간의 비교 연산

input size: n(=size of array)

worst-case time complexity:

$$\begin{matrix}W(n) &=& W\left(\frac{2}{n}\right) + 1 \\ &=&  \lg n + 1 \\ &\in& \Theta(\lg n) \end{matrix}$$

---

2. Mergesort

Problem

정렬 문제다. 즉, 크기가 n인 배열 S을 정렬하는 문제다.

Algorithm 

1. 배열을 반으로 쪼개, 작은 배열 2개(S[:mid]와 S[mid+1:])를 만든다.
2. 작은 배열 2개를 각각 정렬한다. (만약, 작은 배열을 더 쪼갤 수 있다면, 재귀를 통해 정렬한다.)
3. 정렬된 작은 배열 2개(U, V)를 합병하여, original 배열을 정렬합니다.

위 알고리즘은 in-place sort 알고리즘이다. 즉, 정렬을 하기 위해 추가 배열이 필요한 알고리즘이다.

배열을 반으로 쪼갤 때, 작은 배열 2개를 생성하는 방식은 크기가 $n(1 + 1/2 + 1/4 + \cdots) = 2n$인 배열을 추가 생성하며,

작은 배열 2개를 합병할 때, 복사본 배열을 생성하는 방식은 크기가 $n$인 배열을 추가 생성한다.

Performance

base operation: x와 S[mid]간의 비교 연산

input size: n(=size of array)

worst-case time complexity:

$$\begin{matrix}W(n) &=& 2W\left(\frac{n}{2}\right) + n - 1 \\ &=& n\lg n \\ &\in& \Theta(n\lg n)\end{matrix}$$

---

Determining Thresholds

재귀 알고리즘은 재귀 호출로 상당한 overhead가 생긴다.

때문에, mergesort에서 배열 크기가 1이 될 때까지 재귀 호출을 하는 것보다,

중간 재귀 호출을 중단하고, 삽입 정렬을 사용하는 것이 더 빠르다.

그럼 언제 재귀 호출을 중단해야 하는지 즉, optimal threshold value 구하는 방법에 대해 살펴보겠다.

 

optimal threshold value는 1). 재귀 알고리즘(=merge-sort), 2). 대체 알고리즘(insertion-sort) 그리고 3). 컴퓨팅 자원에 따라 달라진다.

 

A 컴퓨터에서의 merge-sort의 time complexity는 $W(n) = 2W\left(\frac{n}{2}\right) + 32\mu n = 32n \lg n \mu n$이며,

insertion-sort의 time complexity는 $W(n) = \frac{n(n-1)}{2} \mu n$이다.

이때, 대부분 $\frac{n(n-1)}{2} \mu n < 32n \lg n \mu n \rightarrow n < 591$을 통해 optimal threshold value를 구한다. 하지만, 이는 잘못된 방법이다. 이 수식이 의미하는 바는 "n<591일 때, insertion-sort가 merge-sort 빠르다는 것을 의미한다." 즉, $n < 591$은 threshold value지 optimal threshold value는 아니다.

 

자세히 말하자면, merge-sort를 사용한 후 insertion-sort를 사용할 때와 모두 insertion-sort를 사용할 때를 비교해 optimal threshold value를 구하는게 맞다.

---

When Not to Use Divide-and-Conquer

1. 크기가 n인 instance가 2개 이상의 크기가 n인 작은 instances로 나뉘는 경우 (dynamic programming)

2. 크기가 n인 instance가 n개의 크기가 n/c인 작은 instances로 나뉘는 경우