그리디
- 무조건 현재 상황에서 가장 좋은 선택만을 하는 알고리즘 기법
- 항상 최적해를 보장하지는 않음
그리디 알고리즘 특징
- 단계적 선택: 문제 해결 과정에서 매 단계마다 가장 최적의 선택을 함
- 지역적 최적해: 각 단계에서 최적 선택을 통해 해결을 시도함 but 이게 전체 문제의 최적해를 보장하지는 않음
- 비가역적 선택 : 이전 단계의 선택은 이후 단계에 영향을 미치지 않음
알고리즘 장점
- 직관적이고 이해하기 쉬워서 구현 간단함
- 최적의 선택만 함 → 즉 계산 속도가 빠름
- 많은 문제에서? 적절한 해를 빠르게 제공하는 편임
알고리즘 단점
- 항상 최적해를 보장하지는 않음 → 그리디로 풀 수 없는 문제가 존재함
- 문제 자체가 그리디 특성을 가져야 함
알고리즘 적용 예시