[알고리즘] 탐욕(그리디) 알고리즘(Greedy algorithm)

탐욕 알고리즘이라고도 불리는 그리디 알고리즘이 있다.

그리디 알고리즘은 항상 각 단계에 있어서 가장 좋을 거라 생각되는 선택을 한다. 다시 말해 이 선택이 전체적으로 최적해로 안내하게 될 거라는 바람을 가지고 부분적으로 최적인 선택을 한다.

 

그리디 알고리즘의 접근 과정

• selection procedure: 현재 상태에서 가장 greedy한 선택으로 해를 결정
• feasibility check: 결정한 해의 적절성 검사
• solution check: 해의 최적성 검사

https://ko.wikipedia.org/wiki/%ED%83%90%EC%9A%95_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

탐욕 알고리즘 - 위키백과, 우리 모두의 백과사전

---

예제

 

그리디 알고리즘의 예

그리디 알고리즘에서의 대표적인 예로는 최적의 동전 개수를 구하는 문제다.

예를 들어 N원을 20원, 10원, 5원, 1원으로 구성된 최소의 동전 개수를 구해보자

예 1

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

int main() {
	int money = 0;
	vector<pair<int, int>> coin{ {20, 0}, {10, 0},  {5, 0},  {1, 0} };
	cin >> money;

	for (int i = 0; i < coin.size(); i++) {
		coin[i].second = (money / coin[i].first);
		money %= coin[i].first;
	}

	cout << "quarter(20센트) 개수 : " << coin[0].second << endl;
	cout << "dime(10센트)    개수 : " << coin[1].second << endl;
	cout << "nickel(5센트)   개수 : " << coin[2].second << endl;
	cout << "penny(1센트)    개수 : " << coin[3].second << endl;

	return 0;
}

이 코드를 실행하면 money의 값을 넣었을 때 우리가 최소의 동전 개수를 구할 수 있게 된다.

다음 코드도 보자

 

예 2

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

int main() {
	int money = 0;
	vector<pair<int, int>> coin{ {500, 0}, {450, 0},  {100, 0},  {1, 0} };
	cin >> money;

	for (int i = 0; i < coin.size(); i++) {
		coin[i].second = (money / coin[i].first);
		money %= coin[i].first;
	}

	cout << "500원 개수 : " << coin[0].second << endl;
	cout << "450원 개수 : " << coin[1].second << endl;
	cout << "100원 개수 : " << coin[2].second << endl;
	cout << "1원   개수 : " << coin[3].second << endl;

	return 0;
}

 

이 코드에서 money에 900원을 넣게 되면 500원 1개 100원 4개가 나온다.

하지만 우리가 알 수 있는 것은 450원 2개를 사용하면 전자보다 최소의 개수가 나온다는 것을 알 수 있다.

예 2를 보게 되면 그리디 알고리즘이 통하지 않는 예가 있다는 것을 알 수 있다.

다음 코드를 보자

 

예 3

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

int main() {
	int money = 0;
	vector<pair<int, int>> coin{ {25, 0}, {10, 0},  {5, 0},  {1, 0} };
	cin >> money;

	for (int i = 0; i < coin.size(); i++) {
		coin[i].second = (money / coin[i].first);
		money %= coin[i].first;
	}

	cout << "quarter(25센트) 개수 : " << coin[0].second << endl;
	cout << "dime(10센트)    개수 : " << coin[1].second << endl;
	cout << "nickel(5센트)   개수 : " << coin[2].second << endl;
	cout << "penny(1센트)    개수 : " << coin[3].second << endl;

	return 0;
}

 

첫 번째 코드에서 20센트를 25센트로 바꿨다.

하지만 예 3은 예 2와 달리 그리디 알고리즘이 통한다. 예 2를 보고 우리는 큰 동전이 작은 동전의 배수가 아니면 그리디 알고리즘의 정당성(그리디 알고리즘이 최적의 해를 못 구해줌)이 떨어진다는 사실을 알고 있게 됐다.

하지만 25센트는 10센트의 배수가 아니다 하지만 왜 예 2와 달리 그리디 알고리즘이 통했을까?

---

 

그리디 알고리즘이 작동하는 이유는 25센트가 10센트의 배수가 아니더라도, 다른 동전들과의 관계를 통해 최적의 해를 찾을 수 있기 때문이다.

 

25센트는 10센트의 배수가 아니지만, 10센트로 만들 수 있는 최소 값은 10센트이므로 25센트 동전을 사용하는 것이 그리디적으로 최선의 선택이다.

 

이러한 경우에 그리디 알고리즘이 작동하는 이유는, 주어진 동전의 단위 사이에 서로 배수 혹은 배수 관계가 성립하고 있어서, 더 큰 단위의 동전을 사용하는 것이 항상 최적의 해를 찾는데 도움이 되기 때문이다.

 

즉 예 2에선 500원과 400원은 배수의 관계가 성립이 된다고 보기 어렵다. 그래서 그리디 알고리즘이 작동하지 않았던 걸 알 수 있다.

 

참고: Introduction to Algorithms (개정판)