알고리즘
[알고리즘] 배낭 문제(0-1 Knapsack Problem)
먼저, 많은 알고리즘 중 배낭 문제를 꼽은 이유는 다음과 같다... 최근에 응시한 코테에 나왔는데 풀지 못했다. 문제를 보자마자 배낭 문제라는 것을 알았고, 심지어 DP 문제라는 것도 알았다. 하지만 1차원 배열을 써야 하는지, 2차원 배열을 써야하는지 상세한 풀이 방법이 생각나지 않았다.대충, 점화식의 형태도 기억이 났지만, 결과적으로는 풀지 못했다. 그래서 다시 한 번 공부를 하면서, 다음 번에는 꼭 한 번에 풀 수 있도록 하고자 한다. 🔍 배낭 문제란?배낭 문제는 유한한 용량을 가진 배낭과 여러 개의 물건들이 주어졌을 때, 배낭에 담을 수 있는 물건들의 조합을 찾아 그 가치의 합이 최대가 되도록 하는 문제이다. 각 물건은 고유한 가치와 무게를 가지며, 물건을 쪼개서 넣을 수 없다는 제약(0-1 ..
