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

📕 개요

그리디 알고리즘은 '욕심쟁이 알고리즘'이라는 별칭을 가지고 있습니다.
이는 '지금 이 순간 최적의 답을 선택하여, 전체 문제를 해결하자!'라는 아이디어로부터 출발합니다.
 
간단한 예시를 들어보겠습니다.
서울에서 부산으로 가고자 하는데,
무조건 대전, 대구를 경유해서 가야 한다고 가정해 보겠습니다.
 
어떻게 해야 가장 빠르게 부산에 도착할 수 있을까요?
 
서울 ~ 대전까지 가장 빠르게 도달하는 시간
+
대전 ~ 대구까지 가장 빠르게 도달하는 시간
+
대구 ~ 부산까지 가장 빠르게 도달하는 시간
=
서울 ~ 부산까지 가장 빠르게 도달하는 시간
일 겁니다.
 
그때그때 최적의 답을 선택하고, 그것을 모아서 전체 문제에 대한 해답을 찾고자 합니다.
그러나, 그리디 알고리즘이 항상 최적의 결과를 도출하는 것은 아닙니다.
 
그리디 알고리즘이 최적의 결과를 도출할 수 있는 문제는 한정되어 있습니다.

 
📘 어떤 상황에서 사용하는 것이 좋을까?

1. 최적 부분 구조 조건
부분 문제의 최적의 답이 전체 문제의 최적의 답이 되어야만 합니다.
서울 ~ 부산의 최적 시간은 구하는 문제는
서울~대전, 대전~대구라는 부분 문제의 대한 최적의 답으로 해결할 수 있습니다.
 
2. 탐욕스러운 선택 조건
앞의 선택이 이후의 선택에 영향을 주지 않아야 합니다.
다음 도시로 가기 위해서 버스, 기차를 타는 방법이 있다고 가정합니다.
 
버스, 기차를 타는 횟수가 제한되어 있지 않다면, 그 순간 가장 빠른 교통을 이용하면 되겠죠.
하지만, 타는 횟수나 돈이 제한되어 있다면? 이전의 결과가 이후의 결정에 영향을 미치기 때문에
이 경우엔 그리디 알고리즘으로 해결할 수 없습니다.
 
그리디 알고리즘은 항상 최적의 답을 도출하는 것은 아니기 때문에, 어떤 문제 상황에서 사용할 것인지
신중하게 판단해야 합니다.

 
📗 동전문제

---

[문제]
거스름 돈으로 사용할 수 있는 동전은 [10, 50, 100, 500] 원 이 존재하고,
k원을 거슬러 줘야 할 때, 거슬러 줘야 한 동전의 최소 개수를 구하여라
 
[입력]
1610
 
[출력]
 5

[설명]
500 *3 + 100 *1 + 10 *1
-> 5

---

1. 조건 확인 
먼저 해당 문제가 그리디 알고리즘의 조건에 부합하는지 확인해 봅시다.
 
  1) 최적 부분 구조 조건
  가장 큰 단위의 돈부터 부분 문제를 해결해 나가면 최적의 답으로 연결할 수 있습니다.
  
  2) 탐욕스러운 선택 조건
  동전이 무한 개이고, 모든 동전은 자신보다 작은 동전의 배수이기 때문에, 이전 결과가 다음 결과에
  영향을 미치지 않습니다.
 
2. 아이디어
k = 1610이라고 할 때, 가장 큰 단위의 돈부터 생각해서, 문제를 해결합니다.
 
500원으로 거슬러 줄 수 있는 최소 동전 개수
+
100원으로 거슬러 줄 수 있는 최소 동전 개수
+
50원으로 거슬러 줄 수 있는 최소 동전 개수
+
10원으로 거슬러 줄 수 있는 최소 동전 개수
 
이 부분 문제들의 최적해는 전체 문제의 최적해가 될 수 있습니다.
 
3. 코드 및 결과

#include <iostream>
using namespace std;

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

int main()
{
	int k;
	cin >> k;

	int rst = 0;

	for (int i = 3; i >= 0; i--)
	{
		rst += k / coin[i];
		k = k % coin[i];
	}

	cout << rst << endl;
}

 
뺄셈 방법으로 해를 구해도 되지만, 나누기와 모듈러 연산을 사용하면 더 빠르게 답을 구해낼 수 있습니다.
 
(참고: 나누기, 나머지도 결국 뺄셈 기를 이용하지만, 그냥 뺄셈을 통해 값을 구하는 것보다 훨씬 적은 뺄셈이 발생합니다.)

 

답이 아주 잘 나오네요

 
📕 그리디 알고리즘의 한계점 (vs 다이내믹 프로그래밍)

자 이제 동전문제에서 조건을 살짝 바꿔보겠습니다.
k = 1610 일 때, 동전의 단위가 [10, 50, 100, 500]에서 [10, 400, 700]
으로 바뀐다면 어떻게 될까요?
 
위와 똑같은 코드로 동전의 단위만 바꿔서 실행해 보겠습니다.

23이 나옵니다. 근데 이것이 최적의 해일까요?
 
아닙니다.
최적의 해는
400 * 4 + 10 * 1 -> 5입니다.
 
동전의 조건만 살짝 바꿨는데 왜 그리디 알고리즘이 통하지 않을까요?
바로 '탐욕스러운 선택 조건'이라는 전제를 위반했기 때문입니다.
 
[10, 50, 100, 500]의 동전은 큰 동전이 모든 작은 동전의 배수이기에
전 부분 문제의 해답이 다음 부분 문제의 해결에 영향을 미치지 않습니다.
 
[10, 400, 700]의 경우
700을 2번 고르면, 1610 - 1400 = 210이 남죠?
나머지 동전을 10원으로 처리할 수밖에 없습니다.
 
오히려, 400을 4번 고르는 것이 최적의 해가 될 수도 있다는 의미죠.
 
이것이 '그리디 알고리즘'의 한계입니다.
항상 최적의 답을 도출해 내는 알고리즘은 아니다.
 
해당 문제는 다른 문제 해결방법인 '동적계획법 (다이내믹 프로그래밍)'으로 해결할 수 있습니다.
'다이내믹 프로그래밍'에 대해서는 다음에 추가적으로 다룰 것이고
오늘은 간단하게 소개 및 코드 소개만 하고 넘어가겠습니다.
 
'그리디 알고리즘'은 그때그때 최적의 답을 골라서 가기에 항상 최적의 답을 찾지 못하는 것입니다.
그전 결과가 당시엔 최적이 아니었을지라도, 나중에 그것이 더 좋은 선택이었을 수도 있거든요.
 
다이나믹 프로그래밍은 모든 경우를 고려해서 찾아낸 값을 이전 결과와 비교하여 최적의 해를 찾아나갑니다.
(말만 들으면 시간이 많이 걸리는 알고리즘 같지만, O(n)이라는 매우 빠른 시간복잡도를 가지고 있습니다.)
 
자세한 내용은 '다이나믹 프로그래밍' 포스팅에서 다룰 것이고, 오늘은 위 문제를 해결하는 간단한 다이나믹 프로그래밍 코드만 소개하겠습니다.
 

#include <iostream>
#include <vector>
#define MAX 10000
using namespace std;

const int coin[3] = {10, 400, 700};

int main()
{
	int k;
	cin >> k;

	vector<int> dp(MAX, INT_MAX);
	//dp는 index원 에 도달하기 위한 최소 동전 개수를 value로 가집니다.
	//좋은 dp 예시인지는 모르겠지만, 일단 이런 식으로 코딩해봤습니다.
	//모든 값을 INT_MAX로 초기화 해줬습니다.

	dp[k] = 0;
	//dp[1610]을 만들기 위한 최소 동전은 0개

	for (int i = k; i >= 0; i -= 10)
	{
		//어짜피 모든 돈이 10의 배수로 10씩 빼줬습니다.

		for (int  j= 0; j < 3; j++)
		{
			int idx = i - coin[j];

			if (idx < 0) continue; //예외처리

			dp[idx] = min(dp[idx], dp[i] + 1);
		}
	}

	cout << dp[0] << endl;
	//0원 일 때 최소 동전 개수를 출력합니다.

}

 
📘 결론

그리디 알고리즘이 '100% 최적해'를 찾아내는 기법이 아니라고 설명했지만, 그럼에도 불구하고 상당히 좋은 알고리즘 기법입니다.
계산속도가 빠르기 때문에, 최적의 성능이 필요하지 않고 적당히 좋은 해가 필요할 경우에 상용할 수 있고, 조건만 맞는 다면 빠르게 최적의 결과를 찾아낼 수 있습니다.
 
결정 트리 학습, 최소 신장 트리, 다익스트라 알고리즘 등 에서 그리디 알고리즘를 활용하기도 하고, 코딩 테스트에서도 많이 사용하는 알고리즘이기 때문에 반드시 익혀보시길 바랍니다.
 
상당히 좋은 기법이고
후에 개발할 때 좋은 영감을 줄 수 있습니다.