📕Facts(한 것)

📕Findings(배운 것)

knapsack problem(배낭문제) 을 다이나믹 프로그래밍을 통해 구현했다.

보통 knapsack problem은 그리디 알고리즘을 통해 나오는 문제들이 많지만

큰 무게가 작은 무게의 배수가 아니거나, 그 수량이 1개로 한정되어 있을때는 그리디 알고리즘 적용이 불가능하다.

그렇기 때문에 recursion + memoization 방식인 DP로 푸는게 적합하다.

이 문제를 DP로 풀 경우, 시간복잡도는 O(N*W) (w는 weight)이다.

Floyd 알고리즘의 기본적인 개념을 이러하다

"If V(k)is a node on an optimal path from Vi to Vj then the sub-paths Vi to Vk and Vk to Vj are also optimal paths"

결국, 얼마나 적은 비용으로 목표 노드에 도달할 수 있는가에 대한 알고리즘이기 때문에

어떻게 최적의 노드를 선택하느냐가 이 알고리즘의 핵심이다.

Floyd 알고리즘에서는 최적의 노드를 선택하는 방법을 자신과 목적지를 제외한 모든 노드를 거쳐서 목적지에 도달하는 비용을 누산하고

그 중 최솟값을 최종 비용으로 선택한다.

그래프의 경우 방향성이 없기 때문에 쉽게 구현이 가능하지만

트리의 경우 양방향이더라도, 방향의 가중치가 다른 경우가 있기 때문에 구현하기 까다롭다.