📒탐욕법(Greedy Algorithm)

✍탐욕법(Greedy Algorithm) 이란?

현재 상황에서 가장 좋은 경우의 수를 선택하는 알고리즘. 단, 최종적인 결과 도출에 최적해를 보장해주지 않는다.

✍특징

📌조건

1. 탐욕적 선택이 안전하다.
   • 전체 문제의 최적해를 도출할 수 있다.(Greedy를 사용해 최적해가 나오는 경우에만 사용)
2. 최적 부분 구조 조건
   • 최종 해결 방법이 부분 문제에 대해서 또한 최적이 해결 방법이다. 각 단계의 최적해가 도출되어야 한다.
3. 값들이 서로에게 영향을 주면 안된다.

📌사용 경우

• 최대/최소를 구하는 경우의 수를 구하는 경우 자주 사용한다.
• 정렬을 한 뒤 그것을 사용해 문제를 해결하려는 경우가 많다.