SJ_Koding

(독백체 글)오랜만에 알고리즘 연습을 하려고 한다. 배낭 문제는 DP를 입문할때 반드시 거치는 문제인데 제대로 연습해보고자 다시 한 번 풀었다.DP가 어려운 이유는 점화식을 세우는 것이 대단히 어렵다고 느낀다. 배낭문제를 처음 접하면 이 역시 점화식을 세우기 쉽지 않고 어떻게 접근해야하는지도 막막하다.https://www.acmicpc.net/problem/12865간단히 말하면 100개 이내의 물건은 각각 무게와 가치를 가지고 있고. 이를 K kg이내로 물건들을 최대로 담을 수 있을 때, 물건을 어떻게 담아야 최고의 가치를 얻을 수 있는지를 묻는다. 문제 이해 자체는 어렵지 않다.당연히 모든 경우의 수를 탐색하는 완전 탐색을 생각해 낼 수 있지만 물건들을 담냐 or 안담냐로 물건마다 2개의 경우의 수가..