🦖 탐욕법

현재 상황에서 가장 좋은 것을 고르는 알고리즘

문제를 해결하는 과정에서 그 순간마다 최적이라고 생각되는 결정을 하는 방식으로 최종 해답에 도달하는 방식이다.

동적프로그래밍을 간단한 문제해결에 사용하면 지나치게 많은 일을 한다는 것을 착안하여 고안되었다.

순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 수집해서 최정적인 해답을 만들었다고 해서 최적이라는 보장은 없다.

---

🌳 탐욕 알고리즘 문제해결 방법

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

---

🌳 탐욕 알고리즘을 적용할 문제의 조건

1. 탐욕스런 선택 조건(greedy choice property)

앞의 선택이 이후의 선택에 영향을 주지 않는다.

2. 최적 부분 구조 조건(optimal substructure)

문제에 대한 최적해가 부분문제에 대해서도 역시 최적해라는 것으로 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적문제 해결방법으로 구성된다.

---

🍀 관련 문제

1. 프로그래머스_체육복

---

📑 References

이미지출처
https://velog.io/@contea95/탐욕법그리디-알고리즘
https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%83%90%EC%9A%95%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-greedy-algorithm/