저자 Dasgupta의 Algorithms을 해석하면서 정리한 글입니다.

Part 2. Divide-and-conquer algorithms

분할정복 알고리즘은 문제를 더 이상 나눌 수 없을 때 까지 나누어서 각각 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘 입니다.

divide-and-conquer 문제 해결 전략

1. 한 문제를 같은 크기를 갖는 몇 개의 subproblem들로 나눕니다. (devide)
2. 하위 문제를 recursive하게 풀어줍니다. 즉 각각에 대해서 subproblem을 구합니다. (conquer)
3. 각 subproblem들에 대해 합치거나 더 가공하여 최종 답을 냅니다. (combine)

Reference

1. Algorithms - Dasgupta