목록2023/11/17 (1)
Rootable의 개발일기
냅색(Knapsack) 알고리즘
📌 냅색(Knapsack) 문제란 어떤 가치를 가진 물건이 여러 개 있을 때, 특정 조건을 만족하는 조합을 구하는 문제로 작은 문제의 결과로 큰 문제의 결과를 해결하는 다이나믹 프로그래밍의 대표적인 문제 여기서는 물건의 가치를 쪼갤 수 없는 0-1 Knapsack 문제를 설명한다. 📌 점화식 다이나믹 문제를 해결하기 위해서는 먼저 점화식을 세워야 한다. 아래 그림을 보자 빈 상자에 20kg을 담을 수 있다. 해당 무게만큼 담을 때, 담은 공의 가격이 가장 높은 케이스를 찾는 것이다. 즉, 특정 조건 내에서 가장 가치합이 높은 조합을 찾는 것이다. 🔎 타뷸레이션 & 메모이제이션 타뷸레이션 : 작은 문제의 정답을 이용하여 큰 문제를 해결하는 방법 메모이제이션 : 이미 계산된 값을 다시 계산해야 할 때, 이미..
알고리즘
2023. 11. 17. 21:14