Knapsack - DP 기본편(1)
Knapsack - DP 기본편(1) 1. DP란?DP(Dynamic Programming)는 뭘까?우리나라 말로는 동적계획법이라 한다.뭐 이름이 중요하진 않다.(이 이름도 연구비 잘 받으려면 간지가 필요해 이렇게 붙였다고 한다. 아무 의미가 없음 ㅡ,.ㅡ;; ) 아무튼 DP란, 수학적 귀납법을 이용한 문제풀이 기법이다.수학적 귀납법이란 다음과 같다.자연수에 관한 명제 P(n)P(n)이 모든 자연수(또는, 어떤 자연수보다 큰 모든 자연수)에 대하여 성립함을 보이는 증명법이다.[1] 증명은 두 부분으로 구성되는데, 첫 번째 부분은 최소원 n=n0n=n0에 대해 P(n0)P(n0)가 성립함을 보이는 부분이며, 두 번째 부분에서는 어떤 자연수 kk에 대해 P(k)P(k)가 성립한다는 가정 하에 P(k+1)..
