Emong's Factory

[알고리즘]Divide and Conquer (분할 후 정복)

Divide and Conquer(분할 후 정복) 방법은 어떠한 문제를 작은 단위로 나누고 그것이 해결하기에 충분히 작으면 그것을 풀고, 아니면 더 작은 단위로 나누어 알고리즘을 풀어나가는 방식을 의미한다. Divide and Conquer라 하면 재귀(Recursive) 방식으로 알고리즘을 풀어나간다. Divide and Conquer로 풀 수 있는 문제의 예는 Binary Search, Merge Sort, Quick Sort 등등이 있다. Divide and Conquer로 문제를 풀기에 적당하지 않는 경우 1) 문제를 smaller instance로 나누었는데도 size가 기존과 비슷 2) 문제를 n등분하였는데도 size가 n/c 일 경우 이럴 때는 알고리즘을 잘못 구성하게 되면 complexit..