(TIL) 20210610

2021. 6. 10. 10:36카테고리 없음

반응형

📕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(자기 선언)


  • 日日新又日新
  • 순간에 최선을

 

📕여담


 

반응형