1. 분할 정복이란?
분할 정복은 이름에서 볼 수 있듯이 말 그대로 분할 정복입니다.
분할 정복의 접근법)
1. divides an instance of a problem into two or more smaller instances.
2. if they are too large to be sorved, they can be divided into still smaller instances
3. if solutions to them can be obtained readily, these smaller solutions can be combined into original solution
즉, 문제를 두 개 이상의 instance로 쪼갠다.
그래도 instance가 여전히 크면 또 쪼갠다.
만약 분할한 instance에 대해 답을 구할 수 있으면, 원래 문제의 답은 분할한 instance에서 구한 답을 통합하여 구할 수 있다.
생각보다 간단합니다.
문제를 풀 수 있을 때까지 계속해서 쪼개면 됩니다. 그게 끝이예요.
이런 방식을 Top-Down approach라고 합니다.
문제의 상위 instance들의 해답을 하위의 작은 instance들의 해답을 가지고 구하는겁니다.
쉽죠??
보통 분할 정복 문제는 이런 식으로 사고하고, 재귀를 통한 알고리즘을 구현합니다.
후에 재귀 알고리즘은 좀 더 효율적인 반복문 알고리즘으로 변하게 됩니다.
이 다음부터는 실제로 분할 정복 알고리즘을 소개하도록 하겠습니다.
감사합니다.
지적 환영합니다.