[파이썬] 탐욕 알고리즘(Greedy Algorithm)

• 여러 경우 중 하나를 결정해야할 때마다 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서 최종 값을 구함

 

(예제 1) 지불해야 하는 값이 4,720원일 때 1원, 50원, 100원, 500원으로 동전의 수가 가장 적게 지불할 경우는?

 

(예제 2) 부분 배낭 문제(Fractional Knapsack Problem) - 무게 제한이 k인 배낭에 최대 가치를 가지도록 물건을 넣는 문제, 물건을 쪼개 일부분만 배낭에 넣을 수 있음

 

< 탐욕 알고리즘의 한계 >

• 탐욕 알고리즘은 매순간 판단에 의존하므로 반드시 최적의 해를 구할 수 있는 것은 아니다.
• 따라서 근사치 추정에 활용된다.

• '시작' 노드에서 leaf node까지 가장 작은 값을 찾는 경로
• 탐욕 알고리즘 적용시 : 시작 → 7 → 12 이므로 19
• 실제 가장 작은 값 : 시작 → 10 → 5