탐욕법(그리디) 알고리즘

탐욕법(그리디) 알고리즘

 

정의

현제 상황에서 가장 좋은 것 (최선의 선택)을 고르는 알고리즘

 

• 동적 프로그래밍을 간단한 문제 해결에 사용하면 지나치게 많은 일을 한다는 것을 착안하여 고안됨
• 최선의 결과를 선택해 나가지만, 최종 결과가 가장 좋은 결과라는 보장은 없다.

 

최선의 선택이란?

현제 상황에서 선택할 수 있는 것들 중 가장 좋은 것.

 

 

그리디 알고리즘 조건

1. 탐욕스러운 선택 조건
   탐욕적인 선택은 항상 안전하다는 것이 보장되어야 한다.
   '안전하다'란 이 선택으로 인해 전체 문제의 최적해를 반드시 도출 할 수 있어야 한다는 것이다.
   ➡그리디 문제가 나왔을 때, '이 조건이 만족하는 가?'를 생각해 충족하면 그리디 알고리즘을 사용한다.
   
   
2. 최적 부분 구조 조건
   문제에 대한 최종 해결 방법이 부분 문제에 대해서 최적의 해결 방법이다라는 조건이다.
   ➡전체 문제에는 여러 단계가 존재하고, 여러 단계내의 하나 하나의 단계에 대해 최적해가 도출되어야 한다.

 

 

🔰그리디 알고리즘에서 고려해야하는 상황에서 값들이 서로 영향을 주면 안되는 것을 염두해야 한다.