[CodingTest]Greedy Algorithm(탐욕 알고리즘)

Greedy Algorithm 문제 해결 단계

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

---

Greedy Algorithm 적용 예시

---

거스름돈을 거슬러 주는 알고리즘

1. 선택 절차 - 현재 가장 가치가 높은 동전 우선 선택
2. 적절성 검사 - 거슬러 줄 금액을 초과하는지 검사. 초과하면 가장 마지막에 선택한 동전을 삭제, 1번으로 돌아가 한 단계 작은 동전 선택
3. 해답 검사 - 거슬러 줄 금액과 일치하는지 검사. 액수가 부족하면 1번 과정부터 다시 반복

해결 과정에서 매 순간, 최적이라 생각되는 해답(locally optimal solution)을 찾으며, 최종 문제의 해답(globally optimal solution)에 도달하는 문제 해결 방식

---

탐욕 알고리즘의 특징

• 탐욕적 선택 속성(Greedy Choice Property) - 앞의 선택이 이후의 선택에 영향을 주지 않음
• 최적 부분 구조(Optimal Substructure) - 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성

어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점, 근사 알고리즘으로 사용 가능