그리디 알고리즘 (Greedy Algorigthm)

그리디 알고리즘이란?

 

현재 상황에서 지금 당장 좋은 것만 고르는 방법

-매 순간 좋아 보이는 것만 선택한다.

-현재의  선택이 나중에 미칠 영향에 대해 고려하지 않을 때여야 한다.

 

따로 구현방법이 있거나 그러진 않음

 

[예제 1] 거스름돈

Q .  손님에게 거슬러야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수? (동전은 500원, 100원, 50원, 10원이 있다)

A .  가장 큰 화폐 단위부터 돈을 거슬러 줘야 함

 

이 문제가 그리디 알고리즘을 이용할 수 있는 이유

=> 가장 큰 단위가 작은 단위의 배수이므로 다른 방법으로 해가 나올 수 없다.

     만약 500,100,50,10원 단위가 아니라 500,400,50,10원 단위였으면 다를 수도 있다.

     2800원을 생각해보자. 500원 5개와 100원 3개를 통해 8개의 동전을 사용하지만,

     500원 4개와 400원 2개를 통해 6개의 동전 밖에 사용하지 않는다.

 

#include <iostream>
using namespace std;

int n;//손님에게 받은 돈
int coin[4] = { 500, 100, 50, 10 };
int ans; //거스름돈의 개수
int main() {
    cin >> n;
    for (int i = 0; i < 4; i++) {
        ans += (n / coin[i]);
        n %= coin[i];
    }
    cout << ans;
}

 

[예제 2] 1이 될 때까지

Q . 어떠한 수가 1이 될 때까지 2가지 연산이 가능하다. 2가지 연산을 하여 1이 되는 최소의 연산의 수는 ?

     ⓐ N에서 1을 뺀다.

     ⓑ N에서 K로 나눈다.

A1 . 반대로 생각하여 1부터 시작해 1을 더하거나 K를 곱하여 N이 되는 최소의 연산의 수를 구하면 된다.

A2 . N이 K의 배수가 되도록 효율적으로 한 번에 빼는 방식으로 작성 가능

 

이 문제가 그리디 알고리즘을 이용할 수 있는 이유

=> N에서 1을 빼는 것보다 K로 나누는 것이 더 빨리 1을 만들 수 있다는 것이 보장되기 때문이다.

 

#include <iostream>
using namespace std;

int n, k, ans;
int main() {
	cin >> n >> k;

	int num = 1;
	while (true) {
		if (num == n) break;
		if (num * k <= n) {
			num *= k;
			ans++;
		}
		else {
			num++;
			ans++;
		}
	}
	cout << ans;
}