알고리즘 - 분할정복법 (Divide and Conquer)
분할정복법 (Divide and Conquer)이란?분할정복법은 주어진 문제를 작은 사례로 나누고(Divide) 각각의 작은 문제들을 해결하여 정복 (Conquer)하는 방법이다. 분할정복법은 문제의 사례를 2개 이상의 더 작은 사례로 나눈다. 이 작은 사례는 주로 원래 문제에서 따온다. 나눈 작은 사례의 해답을 바로 얻을 수 있으면 해를 구하고 아니면 더 작은 사례로 나눈다. 해를 구할 수 있을 만큼 충분히 더 작은 사례로 나누어 해결하는 방법이다. 분할 정복법은 하향식(top-down) 접근 방법으로 최상위 사례의 해답은 아래로 내려가면서 작은 사례에 대한 해답을 구함으로써 구한다. 분할정복법의 설계전략 1. 문제 사례를 하나 이상의 작은 사례로 분할(Divide)한다. 2. 작은 사례들을 각각 정복..
