건빵의 블로그

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로 문제를 풀기에 적당..