4. 분할정복(1)
4. 분할정복 Divide : 문제를 같지만 더 작은 단위로 나눈다. Conquer : 분할된 작은 문제들을 해결한다. Combine : 작은 문제에 대한 해결책을 본래의 문제로 조합하여 대입한다. Recursive case : 분할된 소문제들이 재귀적으로 풀 만큼 충분히 크면 Recursive case라고 부른다. 소문제들을 풀다보면 원래 문제와 동일하지 않을 때도 있는데, 이 떄는 Combine 단계의 일부이다. Recurrences 재귀식을 푸는 세 가지 방법 : 점근적인 Θ 또는 O 상한을 얻는 방법 Substitution method : 수학적 귀납법을 통해 추측을 증명 ...