반응형
📕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 then the sub-paths Vi to Vk and Vk to Vj are also optimal paths"
결국, 얼마나 적은 비용으로 목표 노드에 도달할 수 있는가에 대한 알고리즘이기 때문에
어떻게 최적의 노드를 선택하느냐가 이 알고리즘의 핵심이다.
Floyd 알고리즘에서는 최적의 노드를 선택하는 방법을 자신과 목적지를 제외한 모든 노드를 거쳐서 목적지에 도달하는 비용을 누산하고
그 중 최솟값을 최종 비용으로 선택한다.
그래프의 경우 방향성이 없기 때문에 쉽게 구현이 가능하지만
트리의 경우 양방향이더라도, 방향의 가중치가 다른 경우가 있기 때문에 구현하기 까다롭다.
📕Feeling(느낀 점)
📕Affirmation(자기 선언)
- 日日新又日新
- 순간에 최선을
📕여담
반응형
