정의
그리디 알고리즘은 탐욕 알고리즘 또는 욕심쟁이 알고리즘이라고도 불리는데요. "미래를 생각하지 않고 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"를 모토로 하여, 각 단계에서 최선의 선택을 한 것이 전체적으로도 최선이길 바라는 알고리즘
사용처
- 탐욕 선택 속성(greedy choice property)
- 최적 부분 구조(optimal substructure)
한번의 선택이 다음 선택에는 전혀 무관한 값이어야 하며 매 순간의 최적해가 문제에 대한 최적해여야 한다는 의미이다.
단점
- 100% 최적해를 보장해주지 않는다.
: 예시로 매 순간 최적을 따라가면 1-1-1-100라는 순서로 가는데, 중간에 1-1-10-10으로 움직이는 것이 더 빠를 수 있기 때문에
주로 사용 되는 문제들
- AI에 있어서 결정 트리 학습법(Decision Tree Learning)
- 활동 선택 문제(Activity selection problem)
- 거스름돈 문제
- 최소 신장 트리(Minimum spanning tree)
- 제약조건이 많은 대부분의 문제
- 다익스트라 알고리즘
- 허프만 코드
- 크러스컬 알고리즘