[Algorithms] Divide and Conquer

Divide and Conquer(분할 후 정복) 방법은 
어떠한 문제를 작은 단위로 나누고 그것이 해결하기에 충분히 작으면 그것을 풀고,
아니면 더 작은 단위로 쪼개어 알고리즘을 풀어나가는 방식을 의미한다.

대체적으로 확신할 수는 없지만 Divide and Conquer라 하면 재귀(Recursive) 방식으로 알고리즘을 풀어나간다.
그래서 Divide and Conquer를 Top-down approach라고 한다.
(Dynamic Programming은 이와는 반대로 Bottom-Up approach이다)

Divide and Conquer로 풀 수 있는 문제의 예는
Binary Search, Merge Sort, Quick Sort 등등이 있다.

Divide and Conquer로 문제를 풀기에 적당하지 않는 경우는
1) 문제를 smaller instance로 나누었는데도 size가 기존과 비슷하거나
2) 문제를 n등분하였는데도 size가 n/c 일 때 이다.

이럴 때는 다른 Approach로 알고리즘 구성하여야 한다.
대부분(내가 알고있는) Divide and Conquer는 재귀를 사용하기 때문에
알고리즘을 잘못 구성하게 되면 complexity가 어마어마해진다. 

따라서 적절한 형태로 구성해야 할 것이다.

Review 시
Merge sort의 complexity 분석 
Quick sort의 complexity(worst, average) 분석
Recurrence relation 풀기
정도는 증명해보고 풀어보자.