분할정복법

분할 정복법 분할정복법Divide and Conquer 은 주어진 문제를 작은 문제로 나눠서 해결하고, 각 나눠진 문제의 해들을 조합해서 최종해를 구하는 알고리즘 기법 입니다. 분할정복법의 단계를 나타내면 아래와 같습니다. 1. 문제를 부분문제로 나눕니다. 보통 더 이상 나눌수 없을때까지 나눕니다. 2. 나눈 문제들에 대해 각각 해를 구합니다. 3. 부분 문제들의 해를 조합해서 최종적으로 전체문제의 해를 구합니다. [그림] 분기한정법의 과정 모든 문제를 나눠서 해결한다고 성능이 개선되는 것은 아니고, 문제를 나눴을 때, 각 부분문제 들이 독립적으로 해결될 수 있는 경우에 효과적입니다. 문제를 나눴을때 독립적이지 않은 예는 동적 계획법으로 해결한 문제들 입니다. 예를 들면 LCS가 있습니다.(자세한 내용은 동적계획법을 설명하는부분을 참조해주세요) 점화식을 보면 이전에 구한 해를 활용해 현재해를 갱신해 나가는 방식이므로 각각의 해들은 이전해에 의존하고 있습니다. 따라서 부분해가 독립적이...

원문링크 : 분할정복법