탐욕 알고리즘(Greedy algorithm)
그리디 알고리즘
탐욕 알고리즘, 다른말로 그리디 알고리즘이란 각 분기마다 현 상황에서 최적의 선택을 고르는 알고리즘을 말합니다. 완전 탐색 알고리즘과 비슷하지만 모든 선택지를 고려하여 그 중 최적해를 찾는 방법이 아닌 지금 당장 가장 좋은 방법만을 선택하는 것입니다.
그리디 알고리즘의 사용
그리디 알고리즘은 많은 경우 최적해를 찾지 못합니다. 그러나 2가지의 경우에서는 그리디 알고리즘을 사용하는 것이 좋은 방법일 수 있습니다.
- 탐욕법을 사용하도 항상 최적해를 구할 수 있는 문제를 만난 경우, 탐욕법은 다른 알고리즘에 비해 수행 시간이 월등히 빠르기 때문에 유용
- 시간이나 공간적 제약으로 인해 다른 방법으로 최적해를 찾기 어려운 경우 최적해 대신 근사해를 찾는 것으로 타협하는 경우
