그리디 알고리즘
- 탐욕 알고리즘, 욕심쟁이 알고리즘이라고도 불린다.
- Greedy는
최적해를 구하는 상황에서 사용할 수 있는 알고리즘이다. - Greedy는 매 순간의 최적해를 선택해가는 방식이지만, 최종적으로 최적해를 보장하지는 않는다.
- DP나 다른 알고리즘에 비해 수행 소요시간이 짧다.
적용
Greedy 알고리즘을 적용했을 때 최종적으로도 최적의 해를 보장하는 문제는 다음과 같은 조건을 만족한다.
- 탐욕스런 선택 조건
: 앞의 선택이 이후의 선택에 영향을 주지 않는다.- 최적 부분 구조 조건
: 문제에 대한 최적해가 부분 문제에 대해서도 역시 최적해다.
위 조건을 만족하지 않는 문제에 그리디 알고리즘을 사용하면 최적해를 구할 수 없다. 하지만 빠른 계산 속도를 활용하여 근사 최적해를 구할 수 있다. 이 때 결과값이 최적해에 근사한다는 것을 보장하려면 정당성 증명이 필요하다.
