그리디

• 무조건 현재 상황에서 가장 좋은 선택만을 하는 알고리즘 기법
• 항상 최적해를 보장하지는 않음

그리디 알고리즘 특징

• 단계적 선택: 문제 해결 과정에서 매 단계마다 가장 최적의 선택을 함
• 지역적 최적해: 각 단계에서 최적 선택을 통해 해결을 시도함 but 이게 전체 문제의 최적해를 보장하지는 않음
• 비가역적 선택 : 이전 단계의 선택은 이후 단계에 영향을 미치지 않음

알고리즘 장점

• 직관적이고 이해하기 쉬워서 구현 간단함
• 최적의 선택만 함 → 즉 계산 속도가 빠름
• 많은 문제에서? 적절한 해를 빠르게 제공하는 편임

알고리즘 단점

• 항상 최적해를 보장하지는 않음 → 그리디로 풀 수 없는 문제가 존재함
• 문제 자체가 그리디 특성을 가져야 함

알고리즘 적용 예시

• 동전 거슬러주기 문제 #최소 개수의 동전