[Algorithm] 그리디 알고리즘(Greedy Algorithm)
그리디 알고리즘(Greedy Algorithm) 이란?
그리디 알고리즘은 각 단계에서 가장 최선이라고 여겨지는 선택을 하는 방식으로 문제를 해결하는 알고리즘입니다.
마치 눈앞의 이익만 좇는 탐욕스러운 사람처럼, 매 순간 가장 좋아 보이는 것을 선택하다 보면 최종적으로도 좋은 해답에 도달할 것이라는 가정에 기반합니다. 하지만, 모든 문제에 대해 항상 최적의 해를 보장하지는 않습니다. 즉, 지역 최적해(local optimum) 에는 도달할 수 있지만, 전역 최적해(global optimum) 를 보장하지는 않습니다.
간단한 예를 들어보겠습니다. 여러분이 거스름돈을 최소한의 동전 개수로 주어야 한다고 가정해 봅시다. 예를 들어, 거슬러 줄 금액이 470원이고, 동전 종류가 500원, 100원, 50원, 10원이라고 할 때, 그리디 알고리즘은 다음과 같이 작동합니다.
- 가장 큰 동전인 500원을 확인합니다. 470원보다 크므로 선택하지 않습니다.
- 다음으로 큰 동전인 100원을 확인합니다. 470원보다 작으므로 선택합니다. (470 - 100 = 370원)
- 다시 100원을 확인합니다. 370원보다 작으므로 선택합니다. (370 - 100 = 270원)
- 같은 방식으로 100원을 두 번 더 선택합니다. (270 - 100 = 170원, 170 - 100 = 70원)
- 50원을 선택합니다. (70 - 50 = 20원)
- 10원을 두 번 선택합니다. (20 - 10 = 10원, 10 - 10 = 0원)
결과적으로 100원 4개, 50원 1개, 10원 2개, 총 7개의 동전으로 거스름돈을 줄 수 있습니다. 이 예시에서는 그리디 알고리즘이 최적의 해를 찾았습니다. 하지만, 동전의 종류가 달라진다면 항상 최적의 해를 보장하지는 않습니다.
(출처 : https://en.wikipedia.org/wiki/Greedy_algorithm)
그리디 알고리즘의 특징
- 탐욕적인 선택: 각 단계에서 가장 최선이라고 여겨지는 선택을 합니다.
- 부분 문제의 최적 해: 부분 문제의 최적 해를 구하여 전체 문제의 해를 구합니다.
- 최적 부분 구조 (Optimal Substructure): 부분 문제의 최적 해가 전체 문제의 최적 해를 구성하는 경우에 그리디 알고리즘을 적용할 수 있습니다.
- 매트로이드 (Matroid): 특정 조건(매트로이드 구조)을 만족하는 문제에 대해서는 그리디 알고리즘이 항상 최적의 해를 보장합니다.
그리디 알고리즘의 적용 조건
모든 최적화 문제에 그리디 알고리즘을 적용할 수 있는 것은 아닙니다. 그리디 알고리즘이 효과적인 문제는 다음과 같은 조건을 만족해야 합니다.
- 탐욕적 선택 조건 (Greedy Choice Property): 각 단계에서의 탐욕적인 선택이 최종 해답의 최적성을 보장해야 합니다.
- 최적 부분 구조 조건 (Optimal Substructure Property): 문제의 최적 해가 부분 문제의 최적 해로 구성되어야 합니다.
장단점
장점
- 구현이 간단하고 직관적입니다. 문제를 해결하는 과정이 단순하고 명확하기 때문에, 코드를 작성하고 이해하기 쉽습니다.
- 계산 속도가 빠릅니다. 각 단계에서 최선의 선택을 하기 때문에, 전체 탐색 공간을 탐색하는 다른 알고리즘(예: 동적 프로그래밍)에 비해 계산 속도가 훨씬 빠릅니다.
- 일부 문제에 대해서는 최적의 해를 보장합니다. 특히, 매트로이드(Matroid) 구조를 가진 문제나, 탐욕적 선택 속성(Greedy Choice Property)과 최적 부분 구조 속성(Optimal Substructure Property)을 만족하는 문제에 대해서는 항상 최적의 해를 찾을 수 있습니다.
단점
- 모든 문제에 대해 최적의 해를 보장하지 않습니다. 그리디 알고리즘은 각 단계에서 지역적인 최적해(local optimum)를 선택하기 때문에, 최종적으로 전역적인 최적해(global optimum)에 도달하지 못할 수 있습니다. 즉, 눈앞의 이익만 좇다가 전체적인 관점에서 손해를 볼 수 있습니다.
- 탐욕적 선택의 정당성 증명이 필요합니다. 특정 문제에 그리디 알고리즘을 적용하기 위해서는, 각 단계에서의 탐욕적인 선택이 최종 해답의 최적성을 보장한다는 것을 수학적으로 증명해야 합니다. 이러한 증명 없이 그리디 알고리즘을 적용하면, 최적이 아닌 해를 얻을 수 있습니다.
- 문제의 특성을 잘 파악해야 합니다. 모든 문제가 탐욕적 선택 속성과 최적 부분 구조 속성을 만족하는 것은 아닙니다. 따라서, 문제의 특성을 분석하여 그리디 알고리즘의 적용 가능성을 신중하게 판단해야 합니다.
- 반례(Counterexample)를 고려해야 합니다. 특정 문제에 그리디 알고리즘을 적용하기 전에, 그리디 알고리즘이 최적의 해를 찾지 못하는 반례가 존재하는지 고려해야 합니다. 반례가 존재한다면, 그리디 알고리즘을 적용해서는 안 됩니다.
그리디 알고리즘 적용 시 고려 사항:
- 문제의 목표를 명확히 정의해야 합니다. 무엇을 최소화하거나 최대화해야 하는지 명확히 정의해야, 탐욕적인 선택의 기준을 정할 수 있습니다.
- 탐욕적인 선택의 기준을 명확히 정의해야 합니다. 각 단계에서 어떤 기준으로 선택을 할 것인지 명확히 정의해야 합니다.
- 탐욕적 선택이 전체 해답의 최적성을 보장하는지 검증해야 합니다. 수학적 증명이나 반례 검토를 통해 이를 확인해야 합니다.
- 다른 알고리즘과의 비교를 고려해야 합니다. 그리디 알고리즘이 항상 최적의 해를 보장하는 것은 아니므로, 동적 프로그래밍, 분할 정복 등 다른 알고리즘과의 비교를 통해 더 나은 해결 방법을 찾을 수 있는지 고려해야 합니다.
예제
[거스름돈 문제 (Coin Change Problem)]
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int change = 470;
vector<int> coins = {500, 100, 50, 10};
int count = 0;
// 내림차순 정렬 (큰 동전부터 확인하기 위함)
sort(coins.rbegin(), coins.rend());
for (int coin : coins) {
while (change >= coin) {
change -= coin;
count++;
}
}
cout << "최소 동전 개수: " << count << endl;
return 0;
}
[회의실 배정 문제 (Activity Selection Problem)]
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Activity {
int start;
int finish;
};
bool compareActivities(Activity a, Activity b) {
return a.finish < b.finish;
}
int main() {
vector<Activity> activities = {
{1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 9}, {5, 9}, {6, 11}, {8, 12}
};
// 종료 시간 기준으로 정렬
sort(activities.begin(), activities.end(), compareActivities);
int count = 1;
int lastFinishTime = activities[0].finish;
for (int i = 1; i < activities.size(); i++) {
if (activities[i].start >= lastFinishTime) {
count++;
lastFinishTime = activities[i].finish;
}
}
cout << "최대 선택 가능한 회의 개수: " << count << endl;
return 0;
}