4.분할정복
4.3 점화식을 풀기 위한 치환
치환(Substitution)법 : 귀납 가정을 더 작은 문제에 적용할 때 추측한 해로 치환한다.
- 해의 모양을 추측한다.
- 상수들의 값을 찾아내기 위해 수학적 귀납법을 사용하고 그 해가 제대로 동작함을 보인다.
이 책에서는 결과로 나올 해의 모양을 추측하여 치환하는 것에 대한 설명이 많다.
하지만 실제로 양 변에서 공통된 모양을 추출하여 새로운 수열로 치환함으로서 풀 수 있는 점화식 이많다.
예시
치환(Substitution)법 : 귀납 가정을 더 작은 문제에 적용할 때 추측한 해로 치환한다.
이 책에서는 결과로 나올 해의 모양을 추측하여 치환하는 것에 대한 설명이 많다.
하지만 실제로 양 변에서 공통된 모양을 추출하여 새로운 수열로 치환함으로서 풀 수 있는 점화식 이많다.
예시
