탐욕 알고리즘(Greedy Algorithm)이란?

'욕심쟁이 알고리즘'이라고도 한다.

매 순간, 눈앞에 있는 것들 중 가장 좋은 것을 가져가는 욕심쟁이처럼,

매 단계에서 최적의 선택을 함으로써, 최종적으로도 최적의 선택을 할 수 있게 하는 알고리즘 설계 기법이다.

기술적으로 표현하면 "각 단계에서 국소 최적해(locally optimal solution)를 찾음으로써 최종적으로는 전역 최적해(globally optimal solution)를 구한다"는 것이다.

구조

구조를 따로 설명할게 없을 정도로 간단하다.

매 선택의 순간, 현재 상황만을 고려해서 가장 좋은 선택을 하면 된다.

살다 보면 해답을 찾을 수 없는 문제도 만난다.
해결 수 있더라도 해결하는 데 드는 비용이 비현실 적으로 커서 사실상 해답을 찾는게 불가능한 문제들도 있다.

위에서 말한 그런 문제, 완벽한 답을 찾는게 불가능한 그런 문제를 컴퓨터과학에서는 컴퓨터과학에서는 NP-완전(NP-Complete) 문제라고 한다.
구체적으로는 지수시간(O(2^n))으로 푸는 해결방법 밖에 없는, 최적 알고리즘이 존재하지 않는 문제들을 말한다.

NP-완전인지 파악하는 쉽거나 완벽한 방법은 없고, 보통 아래에 해당 하면 NP-완전 문제 일것이라고 본다.

데이터가 규모가 작을 때는 빠른데, 커지면 갑자기 느려지는 경우
모든 가능한 경우를 다 따져서 답을 구해야되는 문제들
알려진 NP-완전문제의 유형에 해당하는 경우
- 외판원문제 (가능한 모든 경로중 최선의 경로 선택)
- 집합커버링문제 (가능한 부분집합 중 최선의 집합 선택)
- 시간표 문제
- ...(추가 예정)

완벽한 해답을 찾는 것이 불가능한 상황에서는 "불가능한 최선보다는 가능한 차선을!"이라는 마음으로
완벽한 답(최적해)를 찾으려는 노력을 멈추고, 정답과 가까운 적당한 답을 찾는 것이 최선일 수 있다.

이런 근사값을 구하는 알고리즘을 근사 알고리즘(Approximation Algorithm)이라 한다.

근사 알고리즘은 '얼마나 빠른가'와 '최적해에 얼마나 가까운가'로 성능을 평가하는데,
탐욕 알고리즘은 아주 간단하고 빠르게 해법을 구할 수 있으므로 근사 알고리즘으로서 좋은 선택지가 될 수 있다.

판단에 앞서 모든 경우의 수를 파악할 수 없을 때는,
당장 그 순간에 최선으로 보이는 것을 선택하는것이 궁극적으로 최선의 결정에 가까운 선택이 될 수 있다는 것이다.