알고리즘
[알고리즘] 배낭 문제에서 넣은 물건을 찾는 방법
배낭 문제가 뭔지 잘 모른다면 이 글을 읽고 오자! 🔍 배낭 문제에서 넣은 물건을 어떻게 찾을까?보통 배낭 문제에서는 어떤 물건을 넣었는지 보다는 가치의 최댓값을 물어보기 때문에, 해당 방식을 무조건 알지 않아도 된다고 생각한다.하지만 내가 풀지 못했던 코딩테스트 문제에서는 내 생각에는 넣은 물건을 알아야 문제를 풀 수 있었다. 따라서 배낭 문제에서 넣은 물건을 찾는 방법에 대해 추가로 글을 작성하게 됐다. ▶️ 넣은 물건을 찾는 방법바로 선택된 물건을 역추적 하면 된다.설명을 위해 이전 포스팅에서 사용한 그림을 그대로 가져왔다.아래 예제의 경우에는 마지막 값인 가치의 최댓값이 14이다.즉, 선택된 물건을 찾기 위해서는 14를 만든 물건을 역추적 하면 된다. 무게가 7일 때, 최댓값이 14이므로, ..
