탐욕 알고리즘 (Greedy)

미래의 결과를 고려하지 않고 각 단계에서 현재 상황에서 가장 좋아 보이는 선택을 하는 알고리즘.

장단점

• 장점: 구현이 간단하고 실행 속도가 빠름. 대규모 문제에 적용 가능
• 단점: 항상 전역 최적해를 보장하지 않음

예시) 10원, 50원, 70원, 100원 동전으로 140원 만들기

• Greedy: 100×1 + 10×4 = 5개
• 최적: 70×2 = 2개

적용 조건

• 각 단계의 최적 선택이 전체 문제의 최적 해로 이어질 때 (탐욕 선택 속성)
• 문제의 최적해가 부분 문제의 최적해를 포함할 때 (최적 부분 구조)

응용

• 최소 신장 트리
• 다익스트라 최단 경로 알고리즘
• 활동 선택 문제
• 분할 가능 배낭 문제
• 동전 거스름돈 문제 (특정 화폐 단위일 경우)