정의
각 단계에서 그 순간에 가장 최적이라고 생각되는 선택을 하는 방식
장점
•
구현이 간단하고 빠른 속도를 가진다
•
최적의 결과를 보장하는 특정한 상황에서는 매우 효과적인 알고리즘으로 작용
단점
•
항상 최적의 결과를 보장하지는 않는다.
적용 가능한 문제의 속성
1.
탐욕적 선택 속성(Greedy Choice Property)
a.
현재의 선택이 이후의 선택과는 독립적이고, 현재의 선택이 최종 해답에 영향을 주는 속성
b.
각 단계에서의 최적의 해가 전체 문제에서의 최적의 해로 이어진다는 것을 보장
2.
최적 부분 구조(Oprimal Substructure)
a.
큰 문제의 해결 방법이 작은 문제의 최적 해결 방법들로부터 구해 질 수 있어야 한다.
b.
문제를 분할했을 때 각 부분 문제의 최적 해결 방법을 통해 전체 문제의 최적 해결 방법을 찾을 수 있어야 한다.
예시
1.
거스름돈 문제
a.
가장 큰 단위의 동전부터 최대한 많이 주면 가장 적은 동전의 개수를 도출
2.
작업 스케줄링 문제
a.
가장 먼저 끝나는 작업부터 선택하는 방식
b.
최대한 많은 작업을 스케줄링 가능
3.
최소 신장 트리 문제
4.
다익스트라 알고리즘
5.
하프만 코딩
1.
여행자 문제(TSP)와 같은 경우에는 탐욕법이 최적의 해를 보장하지 않는다.