Greedy

✍️ 정의

• 각 단계마다 가장 좋은 것만 선택하여 해답을 구한다.
• 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중에서 최선의 선택지라고 가정하는 알고리즘이다.
• 지금 선택이 앞으로 남은 선택에 어떤 영향을 끼치질 고려하지 않는다.
• 탐욕법을 적용하기 위해서 지역적으로 최적이면서 전역적으로 최적이어야 한다.
• 단계마다 하는 선택이 지역적으로는 최선이지만, 모든 단계를 거쳐 최종적으로 나온 해답이 최적이란 보장은 없다.

---

🔎 적용 조건

1. greedy choice property
   • 앞의 선택이 이후 선택에 영향을 주지 않는다.
   • 각 단계에서 가장 좋은 것을 선택하는 행위가 최적해로 가는 길이다.
2. optimal substructure
   • 문제의 최적해가 부분 문제에서도 최적해이다.
   • 전체 문제 안에 여러 단계가 있고, 모든 여러 단계에서 최적해가 도출되어야 한다.

---

📌 그리디 알고리즘 핵심 이론

그리디 알고리즘은 다음과 같은 3단계를 반복하면서 문제를 해결한다.

1. 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다.
2. 적절성 검사 : 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다.
3. 해 검사 : 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 만약 전체 문제를 해결하지 못하면 1로 돌아가 같은 과정을 반복한다.