그리디 알고리즘 - 동전 개수의 최솟값 구하기

그리디 알고리즘이란?

그리디 알고리즘은 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중에서 최선의 선택지라고 가정하는 알고리즘이다. 이 말은 즉, 이름에서도 알 수 있듯 현재 상황에서 당장 좋은 것을 고르는 방식이다.

 

→ 순간마다 하는 선택은 그 순간에 대해 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 해서 그것이 최적이라는 보장은 없다. 하지만 그리디 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서, 전역적으로도 최적인 문제들이니 걱정하지 않아도 된다.

 

그리디 알고리즘의 핵심 이론

그리디 알고리즘을 접할 때 일반적으로 아래 3단계를 반복하면서 문제를 해결한다.

 

<그리디 알고리즘 수행 과정>

1. 해 선택: 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다.

2. 적절성 검사: 현재 선택한 해가 전체 문제의 제약 조건에서 벗어나지 않는지 검사한다. 

3. 해 검사: 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 전체 문제를 해결하지 못한다면 1번으로 돌아가 같은 과정을 반복한다.

 

그러면 이제 그리디 알고리즘의 대표적인 문제를 살펴보자

<문제>

백준 - 11047: 동전 개수의 최솟값 구하기

https://www.acmicpc.net/problem/11047

11047번: 동전 0

 

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

 

<문제 해결>

이 문제는 거창한 알고리즘을 사용하는 것 없이 반복문과 조건문을 이용해 풀 수 있는 문제이다.

1. 동전을 최소로 사용하여 동전 개수의 최솟값을 구하기 위해서는 가장 가격이 큰 동전부터 접근하면 된다. 

2. 목표 금액을 동전 종류로 나누었을 때 몫을 이용하면서 문제를 풀면 해결된다.

 

<슈도 코드>

n = 동전 수 
m = 목표 금액
num = 동전 종류
cnt = 필요한 동전 개수
moc = 목표 금액을 동전 종류로 나누었을 때 몫

cin >> n >> m

for(i = 0; i < n; i++){
	cin >> num
    v[i] = num
}

for(i = n-1; i >= 0; i--){
	moc = m / v[i]
	if(m / v[i] == 0){
    	continue
    }
    else if(moc > 0){
    	m = m - moc * v[i]
        cnt = cnt + moc
    }
}

cout << cnt

 

<전체 코드>

#include <iostream>
#include <vector>
using namespace std;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m, num; 
	int moc = 0, cnt = 0;

	cin >> n >> m;

	vector <int> v(n);

	for (int i = 0; i < n; i++) {
		cin >> num;
		v[i] = num;
	}

	for (int i = n - 1; i >= 0; i--) {
		moc = m / v[i];
		if (moc == 0) {
			continue;
		}
		else if (moc > 0) {
			m = m - moc * v[i];
			cnt = cnt + moc;
		}
	}

	cout << cnt;
}