동적 계획법(DP)이란?

DP의 핵심 이론 복잡한 문제를 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 문제의 답을 구현하는 방식입니다. DP의 원리와 구현 방식 큰 문제를 작은 문제로 나눌 수 있어야한다.

작은 문제들은 반복되어 사용되며 문제들의 결과값은 항상 같아야한다. 해결된 문제들은 DP테이블에 저장해두고 재사용 할 때 DP테이블의 값을 이용한다.

(메모이제이션 기법) Top-Down 방식과 Bottom-Up 방식으로 구현이 가능한다. 동적 계획법의 대표적인 예시인 피보나치 수열에 대해 알아보겠습니다.

출처 : http://monthly.chosun.com/client/news/viw.asp?ctcd=&nNewsNumb=201611100041 피보나치 수열은 토끼의 번식, 꽃잎의 개수, 나무가지의 분기 등 자연계 에서 볼 수 있습니다.

만약 5번째 피보나치 수가 몇인가를 구하고 싶다면 (4번째 피보나치 수 + 3번째 피보나치 수)로 나타낼 수 있습니다. 이러한 관계로 점화식을 세우면 다...