그리디 알고리즘

정의

최적의 해를 구하는데 사용하는 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식
'각 단계에서 최적이라고 생각되는 것'을 선택하는 방식

특징

그리디 알고리즘은 100% 최적해를 보장해주지 않는다.
-> 적당히 괜찮은 방법을 찾을 때 유용
-> 빠르게 찾을 수 있음

-> 가중치?가 있는 경우 그리디 적용가능

성립조건

1. 탐욕 선택 속성(Greedy Choice Property)
   각 단계에서 최선의 선택을 했을 때 전체 문제에 대한 최적의 해를 구할 수 있는 경우

2. 최적 부분 구조(Optimal Substructure)
   전체 문제의 최적해가 부분 문제의 최적해로 구성될 수 있는 경우
   -> 작은 부분 문제로 나누어 부분 문제에서 최적의 해를 구한 다음 조합하는 것

위 두가지 조건을 만족하지 못하면 그리디는 최적의 해를 보장하지 못한다.

문제 해결 단계

1. 선택 절차(Selection Procedure): 현재 상태에서 최적의 해답 선택
2. 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사
3. 해답 검사(Solution Check): 기존 문제가 해결되었는지 검사하고, 해결되지 않았다면 위의 과정 반복

예시

다익스트라 알고리즘
허프만 코드
크루스칼 알고리즘
제약 조건이 많은 대부분의 문제

예시 문제

https://jellili.tistory.com/23

참고 자료

정의
정의
전체
단계