1. 문제 2. 접근 방법 '알고리즘' 하면 빠질 수 없는 문제, '다이나믹 프로그래밍' 하면 빠질 수 없는 문제! 그 유명한 배낭 문제 (Knapsack Problem) 되시겠다. 나는 이 문제를 처음 접했을 때, 그러니까 대학교 3학년 시절에는 당연하게도 모든 경우의 수를 대입하는 무식한 방법을 택할 수 밖에 없었다. 그도 그럴 것이, 당시에는 DP의 개념도 몰랐었을 뿐더러 마땅한 해결책이 떠오르지 않았기 때문이다. 이렇게 문제를 풀었을 때는 각 물건 당 넣을지 안넣을지의 경우가 가능하므로, O(2^n) 이라는 어마어마한 시간 복잡도가 나오게 된다. 만약 물건이 100개라면 2의 100승이니까... 얼마나 무자비한 계산인지는 상상에 맡기겠다. 자! 그렇다면 본격적으로 다이나믹 프로그래밍의 개념을 적용..