[알고리즘 기초] 02 알고리즘 설계(분할 정복)

1. 알고리즘 설계

1) 점진적 방법(Incremental design)

• 반복적(Iterative)
• ex) insertion sort

2) 분할정복(Divde and Conquer)

• 재귀적(Recursive), 재귀호출 방법으로 해결 -> Recurrence(점화식)
• ex) merge sort
• 주어진 문제를 풀기 위해 자기자신을 재귀적으로 여러번 호출함으로써 밀접하게 연관된 부분 문제를 다룸
• 즉, 문제의 범위를 더 작은 단위로 쪼개어 해결한 뒤 다시 합쳐 문제를 해결하는 방법

3) 분할정복 세 가지 단계

1. 분할(Divide) : 현재의 문제를 같은 문제를 다루는 다수의 부분문제로 분할
2. 정복(Conquer) : 부분문제를 재귀적으로 풀어서 정복, 충분히 작아지면 직접적인 방법으로 해결
3. 결합(Combine) : 부분문제의 해를 결합하여 원래 문제의 해가 되도록 만듦

---

2. 분할정복 알고리즘 분석

* 수행시간은 재귀방정식(Recurrence equation) 또는 점화식(Recurrence)로 설명할 수 있다.

먼저, $T(n)$을 입력크기가 $n$인 문제에 대한 수행시간으로 정함
 
Assume : (알고리즘의 수행시간에 관한 점화식은 세 단계로 만들어짐)
▶ 주어진 문제가 원래 문제의 $1 \over b$인 $a$개의 부분문제로 분할된다고 가정. (합병 정렬에서는 $a=b$)
▶ 이때, 크기가 $n \over b$인 부분문제에 $T$($n \over b$)시간이 걸린다면 $a$개의 문제를 해결하는데 $a\cdot$$T$($n \over b$)가 걸림
▶ 문제를 분할하는 데 $D(n)$시간, 부분문제 결합하여 원래 문제의 해를 만드는데 $C(n)$시간 걸림

$\therefore$ $T(n)$ $=$ $\cases{ \Theta(1) & $\text{if } n\le c$, 문제의 크기가 충분히 작아진 경우\cr aT(n/b) + D(n) +C(n)}$