그리디 알고리즘

그리디 알고리즘 = 현재 상황에서 지금 당장 좋은 것만 고르는 방법.

 

코테에서는 그리디 문제를 풀기 위해 최소한의 아이디어가 필요하다. 그리고 이러한 아이디어가 타당성이 있는지 검토를 해야한다. 코테에서의 그리디 문제는 그리디 알고리즘을 통해 얻은 해가 가장 최적이기 때문에 출제자의 의도를 파악하고 그리디하게 문제를 풀자.

 

대표적으로 거스름돈 문제를 보자.

 

거스름돈 문제 (500, 100, 50, 10)

해법 : 가장 큰 화폐 단위부터 돈을 거슬러 준다. 

1. 동전들 중 큰 단위가 항상 작은 단위의 배수이다.

2. 작은 단위의 동전로 아무리 조합을 해도 큰 단위를 포함했을 때보다 최적인 상태를 만들 수 없다. 

따라서 그리디하게 생각하고 이를 뒷받침해줄 근거를 찾는것이 중요하다.

 

# include <bits/stdc++.h>
using namespace std;

int n = 1650
int cnt;

int coins[4] = {500,100,50,10};

int main(void){
	for (int i = 0;i<4:i++){
		cnt += n / coins[i];
		n %= coins[i];
	}
	cout <<cnt<'\n'
}