[알고리즘] 탐욕 알고리즘

1. 탐욕 알고리즘(greedy algorithm)

• 매순간 최적인 답을 선택하는 과정을 반복해 결과를 도출
  → 정당성 분석, 최적의 해를 구할 수 있는지 검토하는 것이 중요
• 만족하는 적합한 해를 찾는 방법
  → 최적의 해를 찾는 방법은 아님
• 동적 프로그래밍 중 지나치게 많은 일을 한다는 것에 착안해 고안된 알고리즘

 

2. 탐욕 알고리즘의 한계

최적의 해에 가까운 값을 구하는 방법으로 근사치 추정에 활용한다.

예를들어 '시작' 노드에서 시작해서 가장 작은 값을 찾아 leaf node 까지 가는 경로를 찾을 때

• Greedy 알고리즘 적용시 시작 -> 7 -> 12 를 선택하게 되므로 7 + 12 = 19 가 됨
• 하지만 실제 가장 작은 값은 시작 -> 10 -> 5 이며, 10 + 5 = 15 가 답

 

참고) https://www.zerocho.com/category/Algorithm/post/584ba5c9580277001862f188

https://www.zerocho.com/category/Algorithm/post/584ba5c9580277001862f188

 

참고) https://hongjw1938.tistory.com/172

알고리즘 - 그리디 알고리즘(Greedy Algorithm)