[바미] Dynamic programming - 0/1 Knapsack Problem 알고리즘 구현하기.
·
하루 알고리즘(JS)
Knapsack problem? Knapsack problem은 동적 계획법을 이용하여 효율적으로 해결할 수 있는데요. 이를 위해서는 다이나믹 프로그래밍의 개념을 이해해야 합니다. 다이나믹 프로그래밍(Dynamic Programming)은 복잡한 문제를 간단한 하위 문제로 나누어 해결하는 알고리즘인데 중복되는 하위 문제들을 한 번만 계산하여, 전체 문제를 해결하는 효율적인 방법을 제공합니다. Knapsack problem의 경우, 각 아이템을 배낭에 넣거나 넣지 않을 수 있으므로, 하위 문제는 아이템을 넣을지 말지에 따라 달라지죠. 따라서, 각 아이템마다 넣을지 말지에 대한 선택지를 가지고, 모든 가능한 선택지에 대해서 최대 가치를 계산해야 해요. 이 때, 각 선택지에 대한 최대 가치는 이전 선택지에 대..