냅색 알고리즘1 1/29 WIL 1. 알고리즘 관련 공부 이번 주는 공부했던 알고리즘 지식을 정리하려 한다. 냅색 알고리즘 (Knapsack Algorithm) 유명한 다이나믹 프로그래밍 문제 혹은 그리디 알고리즘 문제 중 하나이다. 두 가지 유형으로 나뉜다. Fractional Knapsack Algorithm: 주어진 자원을 쪼갤 수 있다는 가정 하에 그리디 알고리즘으로 최적의 조건이 구해진다. 주어진 조건(ex: 가격, 무게) 중 가장 크거나 작은 것부터 대입하여 최적 방식을 구한다.(그리디 알고리즘) 0 - 1 Knapsack Algorithm: 주어진 자원이 0 또는 1, 즉 존재하거나 존재하지 않는, 쪼갤 수 없는 상태면 DP를 사용해야한다. 보통 후자의 문제가 자주 나온다. 그래서 쪼갤 수 없는 보석이 나오면 제로원, 디피.. 2023. 1. 31. 이전 1 다음
