[알고리즘] 그리디 (탐욕법) 알고리즘

정의

그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자" 라는 모토를 가지는 알고리즘 설계 기법이다.

단, 그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 그걸 종합적으로 봤을 땐 최적이라는 보장은 절대 없다는 것을 명심해야 한다. 

사용되는 예시

• AI에 있어서 결정 트리 학습법(Decision Tree Learning)

• 활동 선택 문제(Activity selection problem)

• 거스름돈 문제

• 최소 신장 트리 (Minimum spanning tree)

• 제약조건이 많은 대부분의 문제

• 다익스트라 알고리즘

• 허프만 코드

• 크러스컬 알고리즘