[Java] 탐욕 알고리즘 (Greedy)

Greed Algorithm(탐욕 알고리즘)은 선택의 순간마다 최적의 상황을 찾고, 해답에 도달하는 방법이다. 

1. 선택절차 :(Selection Procedure) : 현재 상태에서의 최적의 해답을 선택
2. 적절성 검사 (Feasibility Check) : 해답이 문제의 조건을 만족하는지 검사 그렇지 않다면 선택절차로 복귀
3. 해답 검사 (Solution Check) : 원래의 문제가 해결됬는지 검사하고, 그렇지 않다면 선택절차로 복귀

 

탐욕 알고리즘이 필요한 상황 

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

 

마시멜로 실험
마시멜로를 1개 주어주고 1분을 기다리면 1개 더 주는 실험

이때 탐욕 알고리즘을 사용하면 즉시 1개를 받게 된다.
왜냐하면 현재에 최선의 선택을 하기 때문 따라서 상황에 맞게 사용해야 한다.