[그리디] 당장 좋은 것만 선택하는 그리디

그리디 알고리즘(Greedy Algorithm)

 

• 현재 상황에서 지금 당장 좋은 것만 고른다.
• 정당성 분석이 중요하다.(단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토)
• 일반적인 상황에서 최적의 해를 보장할 수 없을 때가 많다.
• 하지만 코딩테스트에서는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서 , 이론을 추론할 수 있어야 풀리도록 출제가 된다.
• 정렬과 함꼐 주로 사용이 되며 '가장 큰', '가장 작은' 과 같은 기준을 문제에서 제시해 준다.

 

 

예시 문제) 거스름돈

해결 아이디어 : 최적의 해를 빠르게 구하기 위해서는 가장 큰 화폐 단위부터 돈을 거슬러 주면된다.

 

정당성 분석

가장 큰 화페 단위부터 돈을 거슬러 주는 것이 최적의 해를 보장하는 이유는 무엇일까?

=> 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른해가 나올수 없다 !!