[코딩테스트] 그리디 알고리즘

1. 그리디 알고리즘이란? 

 : 탐욕법이라고도 함

 : 현재 상황에서 당장 가장 좋아 보이는 상황만을 선택하는 알고리즘

 : 최적의 해를 구하기 위한 근사적인 방법 but 이러한 근사적인 방법은 최적의 해를 놓칠 수도 있다.

 => 코테에서는 탐욕 방법으로 최적의 해가 보장되는 문제가 출제되므로 걱정할 필요는 없다고 한다. 

 

2. 그리디 알고리즘 접근 방법

 1) 방법 고안하기

 2) 정당성 확인하기 

 

3. 그리디 알고리즘 접근 방법 예시

 ex) 거스름돈 문제 :손님에게 500 , 100, 50, 10원으로 주어진 값에 대해 거스름돈을 주어야 할 때 동전 갯수를 최솟값으로 하는 법

 1) 그 후 500원으로 최대한 거슬러줌

 2) 그 후 100원으로 최대한 거슬러줌

 3) 그 후 50원으로 최대한 거슬러줌

 4) 그 후 10원으로 최대한 거슬러줌

 

 

이런 식으로 당장 할 수 있는 최선의 방법을 선택해서 그 시점에서 할 수 있는 최선의 선택을 하는 것이 포인트다.