(TIL) 20210610

📕Facts(한 것) 알고리즘 복습(DP, Floyd) 프로그래머스 문제 풀기 수업듣기 학교 과제 📕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..

2021.06.10