그리디 알고리즘

그리디 알고리즘

그리디 알고리즘이란 지금 주어진 단계에서 가장 최선의 선택을 하는 기법이다. 이렇게 각 단계에서 최선의 결과를 선택한 결과 값이 전체적으로도 최선이기를 바라는 알고리즘이다. 일반적인 그리디 알고리즘 풀이 방법을 적어보자면 아래와 같은 흐름을 따른다.

1. 관찰을 통해 탐색 범위를 줄이는 방법을 고안한다.
2. 탐색 범위를 줄여도 올바른 답을 낸다는 것을 수학적으로 증명한다.
3. 알고리즘을 구현한다.

그리디 알고리즘은 모든 경우에서 통하는 알고리즘은 아니다. 현재에 약간 손해보더라도 전체적으로 봤을 때는 이득인 경우에 통하지 않는데, 예를 들자면 유명한 마시멜로 이야기와 같이 지금 당장은 마시멜로를 1개를 받을 수 있지만 조금 기다리는 경우 2개를 받을 수 있는 경우 그리디 알고리즘으로 풀면 틀린 경우가 된다. 그렇기 때문에 그리디 알고리즘으로 문제를 풀 때는 위의 2번 과정과 같이 입증하는 과정을 거쳐야한다.

2-1. boj 11047 동전 0

그리디 알고리즘을 활용하여 풀 수 있는 문제여서 적용하여 풀어보았다. DP를 활용한 풀이도 생각할 수 있는 문제이지만, DP를 활용할 경우 O(NK)의 시간복잡도로 시간초과가 나와 그리디를 활용해야만 하는 문제였다. 위의 풀이 흐름에 따라 풀어보았다.

1. 직관적으로 높은 금액의 동전을 최대한 많이 사용할 수록 동전 갯수가 적어질 거라고 생각했다.
2. 위 생각을 증명해보았다.
   • 간단하게 하기 위해 동전의 가치가 10, 50, 100, 500원 뿐이라고 한다.
   • '동전을 최소로 소모하여 값을 지불하기 위해서는 500원은 최대한, 100원은 4개 이하, 50원은 1개 이하, 10원은 4개 이하로 사용해야한다' 를 증명해보자.
   • 증명을 편히 하기 위해 먼저 '동전을 최소로 소모하여 값을 지불할 때, 100원은 4개 이하, 50원은 1개 이하, 10원은 4개 이하로 사용해야한다' 를 증명해보겠다. 귀류법으로 생각하여 10/100원 동전을 5개 이상, 50원 동전을 2개 이상 사용하여 최소로 동전을 소모할 수 있다고 가정해보자. 10/100원이 5개 이상, 50원이 2개 이상이면 각각 50/500원, 100원으로 대체하여 동전의 갯수를 줄일 수 있으므로 가정이 모순된다. 그러므로 100원 4개 이하, 50원 1개 이하, 10원 4개 이하로 사용해야하는 것은 참이다.
   • 이제 500원을 최대한 사용해야한다는 것을 증명해야하는데 앞서 증명한 '동전을 최소로 소모하여 값을 지불할 때, 100원은 4개 이하, 50원은 1개 이하, 10원은 4개 이하로 사용해야한다' 를 이용하면 쉽게 증명된다. 귀류법으로 생각하여, 500원을 최소한으로 사용하여 동전을 최소로 소모하여 값을 지불할 수 있다고 가정해보자. 앞에서 증명한 내용에 따라 10/50/100원으로 지불할 수 있는 돈은 490원이 최대이다. 500원을 사용하지 않을 경우 10/50/100원으로 500원 이상을 지불해야하므로 가정이 모순되므로 500원을 최대한으로 사용해야하는 것은 참이다.
   • 문제의 조건에 따라 동전의 가치가 배수 관계이므로 언제나 성립한다.
3. 구현한다.

#include <iostream>
using namespace std;
 
int N;  
int K;  
int A[10];
 
int main(void)  
{  
ios_base::sync_with_stdio(0);  
cin.tie(0);
 
int ans = 0;
cin >> N >> K;
for (int i = 0; i < N; i++) cin >> A[i];
for (int i = N - 1; i >= 0; i--)
{
    ans += K / A[i];
    K %= A[i];
}
 
cout << ans;
 
return 0;
}

2-2. boj 1931 회의실 배정

1. 현재 시간을 t라고 할 때, t이상의 회의들 중에 가장 먼저 끝나는 회의를 선택하는 것이 최선이라고 생각했다.
2. 증명까지는 하지 못했고, 그림을 그려보고 당장 손해이지만 나중에는 이득인 경우가 있나 확인해보았다.
3. 입력 받은 회의의 시간들을 끝나는 시간이 빠른 순으로, 끝나는 시간이 같을 때는 시작하는 시간이 빠른 순으로 정렬한 후에 가장 먼저 끝나는 회의를 찾는 방식으로 구현했다.

#include <iostream>
#include <utility>
#include <algorithm>
using namespace std;
 
int N;
int ans = 0;
int t = 0;
pair <int, int> p[100005];
 
bool compare(const pair<int, int>& p1, const pair<int, int>& p2)
{
    if (p1.second < p2.second) return true;
    else if (p1.second == p2.second) return p1.first <= p2.first;
    else return false;
}
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> N;
    for (int i = 0; i < N; i++) cin >> p[i].first >> p[i].second;
    sort(p, p + N, compare);
 
    for (int i = 0; i < N; i++)
    {
        if (t > p[i].first) continue;
        ans++;
        t = p[i].second;
    }
 
    cout << ans;
 
    return 0;
}