대학생 때부터 나를 괴롭혔던 DP.. DP 뿌리를 뽑아버리자!! 아주 전형적인 DP의 대표적인 문제 0 - 1 냅색 문제이다. 문제 물건 A, B, C, D가 있고 각각의 value와 weight가 정의되어 있다. 가방에 최대로 넣을 수 있는 무게제한이 주어질 때 무게제한 안에서 최대한의 value로 물건을 가방에 담는 문제이다 다음과 같이 문제가 주어졌다고 하자. 무식하게 생각해볼까? 그냥 편하게 툭 생각해볼 수 있는 것은 Brute Force 방법이다. 각각의 물건을 담는다(T)와 담지 않는다(F)로 나뉠 수 있고 time complexity는 2^n 이다. 우리는 이것보다는 더 효율적으로 답을 구해내야만 한다..! DP를 적용할 수 있는 문제인지 여부는 다음을 판단해보면 된다. 더 작은 문제(sub..
