그리디 (Greedy Algorithm)
- 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지만을 쫒아
최종적인 해달에 도달하는 알고리즘
- 극단적으로 문제에 접근한다는 점에서 정렬(Sort) 기반이 함께 사용되는 경우가 많음
🌝 장단점
- 근사치 추적에 홣용 -> 반드시 최적의 해를 구할 수 있는 것은 아님
🌝 정당성 증명
1. 탐욕적 선택 속성 (greedy choice property)
- 이전의 선택이 이후에 영향을 주지 않음
2. 최적 부분 구조 (optimal substructure)
- 부분 문제의 최적결과가 전체에도 그대로 적용될 수 있어야 함
🌝 문제 해결 방법
1. 선택 절차 (Selection Procedure)
- 현재 상태에서 가장 최선이라고 생각되는 해를 선택
2. 적절성 검사 (Feasibility Check)
- 현재 선택한 해가 전체 문제의 조건을 만족하는지 검사
3. 해답 검사 (Solution Check)
- 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사 후, 해결하지 못한다면 선택 절차로 돌아가 반복
