[C++]그리디 알고리즘(Greedy Algorithm)

 개념

 

그리디 알고리즘은 말 그대로그리디 알고리즘은 각 단계에서 지금 당장 가장 좋아 보이는 선택을 하는 알고리즘이다. 매 순간 최선의 선택을 통해 전체적인 최적해를 찾는 방법으로 사용됩니다.

이렇게 지금 당장 좋아보이는 선택만 하다 보니 항상 최적의 선택을 할순 없다.

 

예제(동전 0)

그리디 알고리즘은 항상 최적해를 찾는 것을 보장하지 않기 때문에 어떤 경우에는 최적해가 아닌 해를 반환할 수 있다. 이를 설명하기 위해 거스름돈 문제를 약간 변형한 예제를 살펴보자.

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

 

 문제

가게에서 물건을 샀을 때, 손님이 지불한 금액보다 적은 동전의 개수로 거스름돈을 주려고 한다. 어떻게 하면 손님에게 줄 동전의 개수를 최소화할 수 있을까?

 

 입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

 출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

 

알고리즘 순서

1. 동전의 종류를 내림차순으로 정렬한다. (가장 큰 동전부터 사용하기 위함)

2. 가장 큰 동전부터 손님에게 줄 수 있는 최대한의 동전을 선택한다.

3. 남은 거스름돈이 0이 될 때까지 반복한다.

 

 

 전체 코드

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

int main() 
{
	int n, k, input, minTotal, answer = 0;
	vector<int> coins;
	cin >> n >> k;

	for(int i = 0; i < n; i++)
	{
		cin >> input;
		coins.push_back(input);
	}

	sort(coins.begin(), coins.end(), greater<>());

	for (int i = 0; i < n; i++) 
	{
		answer += k / coins[i];
		k %= coins[i];
	}

	cout << answer;
}

만약 동전종류가 8, 6, 5, 1원이 있고 손님이 11원을 지불했다고 하자.

     그리디 알고리즘 적용시 : 8원 동전 2개, 1원 동전 3개, 총 5개

     실제 최적의 해 : 6원 동전 1개, 5원 동전 1개, 총 2개

 

최적의 해는 5원 동전 1개와 6원 동전 1개를 사용하는 것인데, 그리디 알고리즘은 더 큰 동전을 선택하게 되어 최적해를 찾지 못한다. 이는 그리디 알고리즘이 항상 최적해를 찾지는 못한다는 특성을 보여준다.

 

따라서 그리디 알고리즘이 항상 최적해를 찾지는 못하며, 문제에 따라서는 다른 알고리즘이 필요할 수 있다.

 

결론

그리디 알고리즘은 직관적이고 간단하여 많은 문제에 적용할 수 있다. 그러나 항상 최적해를 보장하지는 않으며, 각 단계에서의 최적해가 전체적인 최적해를 보장하지 않을 수 있다. 문제의 특성을 고려하여 적절한 상황에서 사용하는 것이 중요하다.