지금까지 이 블로그를 운영하면서 생각해보면은 나는 DP류의 문제도 꽤 경험을 했다. 언제부터인지 모르겠지만 예전에 SK 코딩테스트에서 1번부터 DP문제를 때려맞고 너무 무기력하게 아무것도 못한 내 모습을 보면서 DP의 중요성을 내심 느꼈었던거같다. 코딩테스트 문제중에서도 가장 어려운 분류에 속하는 문제이고 솔직히 출제자에 마음에 따라서 어떻게든 어렵게 낼수있는 유형의 타입이다. 가령 예를들면 DP는 DFS 및 BFS와 섞어서 낼수도있고 가장 흔하게는 Greedy한 솔루션을 강제하면서 DP를 낼수도 있는것이다.
이번에 풀어본 문제는 DP 중에서도 가장 교과서 같은 문제에 가까운 Knapsack Problem 을 한국어로 번역한것이다. 그런데 그냥 번역하지 무슨 한 달 후면 국가의 부름을 받는 준서와 행군을 언급하는거보면 정말 K-군대의 부심을 다시금 느낄수있다. 난 이제 전역을 했고 군대를 안가도 된다는 사실에 다시한번 감사함을 느끼고있다.
먼저 처음에 문제를 접했을때 이 전에 풀었던 DP Tabulation 솔루션을 기억하면서 풀어보았다.
테스트 케이스까지는 통과했지만 정말 어림도 없었다. 내가 이런 기본적인 문제에 굳이 틀린답을 공개하는 이유는 Tabulation 방식으로 DP를 푸는거에 익숙치 않은 내 모습을 자아성찰 하고 싶어서이다. 항상 Memoization 방식으로 풀었던 나기에 아직까지 어려웠던거같다. 유투브 강의를 봐볼까 하고 생각했지만 그냥 내가 제일 좋아하는 얍문 솔루션 글을 읽고 한번에 이해를 했다. 왜 내 답이 틀렸는지, 1차원 DP 벡터를 이용한 솔루션 방법과 2차원 DP 벡터를 이용하는 솔루션의 차이점 또한 알수 있을거같다.
DP류의 문제는 정말 글과 설명만으로는 이해하기 힘든거같다. 나는 실제로 구종만의 책도 읽고 Knapsack 이라는 문제 또한 예전부터 많이 봤음에도 잘 몰랐다. 그렇기 때문에서인지 이렇게 직접 적어보니깐 훨씬 더 많은 이해가 됐고 최대한의 설명을 주석 안에 포함시켰다. 혹시라도 이해가 안된다면 더 좋은 설명을 적은 위에 링크를 클릭해서 보는게 훨씬 빠를거같다.
배운점:
1. 2차원 DP 활용
2. DP 의 기본중 기본인 Knapsack Problem 의 Tabulation 솔루션
