동적 프로그래밍2 [DP] Knapsack Problem (0-1 Knapsack) References Algorithms (Sanjoy Dasgupta) Contents Knapsack Problem (배낭 문제) with repetition without repetition Knapsack Problem 배낭 문제(knapsack problem)는 간단하게 다음과 같습니다. 한 여행가의 배낭에 담을 수 있는 무게의 최댓값(W)이 정해져 있습니다. 담을 수 있는 항목은 총 n개가 있는데, 이들의 무게는 \(w_1, \cdots, w_n\)이고, 그 항목의 가치는 \(v_1, \cdots, v_n\) 일 때, 가치의 합이 최대가 되도록 배낭에 담을 항목을 고르는 방법은 무엇일까요? 예를 들어, W = 10일 때를 생각해보도록 하겠습니다. 이 문제는 두 종류의 버전이 존재합니다. 만약 각.. 2022. 4. 14. 동적 프로그래밍 (Dynamic Programming) References Algorithms (Sanjoy Dasgupta) Contents DAG에서의 최단 경로 Longest Increasing Subsequence (LIS; 최장 증가 부분 수열) Edit Distance (편집 거리) DAG에서의 최단 경로 DAG(Directed Acyclic Graph), 즉, 유향 비순환 그래프에서의 최단 경로 알고리즘에는 다익스트라(Dijkstra) 알고리즘, 벨만-포드(Bellman-Ford) 알고리즘 등이 있습니다. 이 알고리즘을 통해서 최단 경로 문제는 쉽게 해결될 수 있다는 것을 알 수 있습니다. 이는 동적 프로그래밍의 핵심적인 부분이기 때문에, 동적 프로그래밍에 대해 시작하기 전에 한 번 요약해보도록 하겠습니다. 각 최단 경로 알고리즘에 대해서는 다른.. 2022. 4. 13. 이전 1 다음
