정의

• 그리디 알고리즘은 매 선택에서 현재 시점에서 가장 최적인 답을 선택하여 최적해를 도출하는 알고리즘
• 일반적으로 전체적인 최적해를 보장하지는 않지만, 특정한 경우에 대해서는 정확한 답을 보장

특징

탐욕 선택 속성

• 부분 문제를 해결할 때 매 순간 가장 최적인 선택을 하면 전체적으로도 최적해를 얻을 수 있는 성질을 가짐
• 과거의 선택이 이후의 선택에 영향을 미치지 않으며, 지역적으로 최적해를 선택하는 것이 전체 최적해를 보장하는 경우가 많음

최적 부분 구조

• 문제의 최적해가 부분 문제들의 최적해로 이루어진 경우 적용할 수 있음
• 즉, 부분 문제를 해결한 결과가 전체 문제의 최적해를 구성하는 속성을 가져야 함

근사 알고리즘

• 정확한 최적해를 구하기 어려운 경우, 최적해에 근사한 결과를 빠르게 도출하는데 유용
• 대표적으로 외판원 문제(TSP), 배낭 문제 등에 사용됨

예시

• 동전 거스름돈 문제
• 회의실 배정 문제
• 활동 선택 문제
• 최소 신장 트리(MST)
• 다익스트라 알고리즘

관련 문제(백준)