그리디 알고리즘(greedy)

그리디 알고리즘이란?

 

 

욕심쟁이라는 이름에 걸맞게 항상 눈 앞에 있는 가장 큰 이익을 구하는 방법으로 각 단계에서 가장 최선의 선택을 하는 기법이다. 완전 탐색으로 풀기 어려운 문제를 그리디 알고리즘으로 풀면 매우 쉽게 풀 수 있는 매우 강력하면서도 어려운 알고리즘이다. 완전 탐색으론 풀기 어려운 시간 복잡도를 그리디 알고리즘으로 접근하면 보통 $O(N)$ 정도의 시간복잡도로 해결이 가능하게 된다. 하지만 각 단계의 최선의 선택이 최적의 해가 아닐 수 있으므로 그리디 알고리즘을 통해 해결 가능한 문제에만 그리디 알고리즘을 사용하여 풀 수 있다.

 

 

예를 들어 동전 문제를 보면

 

1)  1, 2, 5, 10원, 50원, 100원짜리 동전으로 370원을 만들려면 동전을 몇 개를 사용해야 할까?(단 동전의 개수는 매우 많다)

 

100원짜리 3개, 50원짜리 1개, 10원짜리 2개로 나타내는 것이 동전 6개로 가장 적게 사용한다.

 

 

즉 가장 단위가 큰 동전부터 사용하는 그리디 알고리즘을 사용했다.

 

 

이를 코드로 구현하면 다음과 같다

 

 

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int n, ans=0;
    cin >> n;
    
    vector<int> coin={100, 50, 10, 5, 2, 1};
    
    for(int i=0; i<coin.size(); i++){
        ans+=(n/coin[i]);
        n%=coin[i];
    }
    cout << ans << "\n";
    return 0;
}

 

 

그러나 동전의 구성을 조금 바꿔보자.

 

 

1, 5, 6원짜리 동전이 있을 때 22원을 만들려고 할 때는 6원짜리 동전 3개, 1원짜리 동전 4개로 7개다.

 

 

하지만 5원짜리 동전 4개, 1원짜리 동전 2개, 총 6개로도 표현할 수 있다.

 

 

맨 처음에 그리디 알고리즘이 성립한 이유는 다른 동전들이 가장 큰 단위의 동전의 약수였기 때문이다. 즉 작은 동전들을 큰 동전으로 대체할 수 있었기 때문에 그리디 알고리즘이 성립하였다.

 

 

하지만 두 번째 경우에는 1, 5, 6원이므로 5는 6의 약수가 아니다. 따라서 이 같은 경우는 그리디 알고리즘이 성립하지 않는다.

 

 

 

 

그리디 알고리즘을 사용하는 문제에서 그리디를 써야하는지 잘 모르겠는 경우가 많은데

 

 

그리디 알고리즘을 할 때는 '가장 ~한 순서대로'라는 말이 자주 나온다.

 

 

따라서 주어진 자료를 문제에 맞게 정렬하는 방법을 익혀야한다.

 

회의실 배정 문제

 

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

1931번: 회의실 배정

 

회의의 시작시간과 끝나는 시간이 주어진다. 이 때 회의들을 끝나는 시간을 기준으로 정렬한 다음, 끝나는 시간이 짧은 회의부터 선택하면서 가능한 회의의 개수를 구하면 풀 수 있다.

 

위 방법이 성립하는 이유

끝나는 시간을 기준으로 정렬하는 이유를 설명하자면

 

이미 이 문제에 대한 해를 구했다고 가정하고, 그 해의 집합을 $S$라고 가정하자.

 

만약 회의가 끝나는 시간이 가장 빠른 회의가 $S$에 포함되어 있지 않다면, $S$에서 끝나는 시간이 가장 빠른 원소를 빼고, 끝나는 시간이 가장 빠른 회의를 $S$에 넣어도 된다.(그래도 원소의 개수, 즉 해의 개수는 변하지 않기 때문이다.)

 

이 방법은 $S$의 모든 원소에 적용하면 끝나는 시간이 빠른 회의들이 $S$에 포함되게 된다.

 

 

예제입력에서 주어진 회의들을 정렬하면

 

 

(1 4), (3 5), (0 6), (5 7), (3 8), (5 9), (6 10), (8 11), (8 12), (2 13), (12 14) 가 되고

 

 

1번째 회의를 선택하면 다음 회의로는 시작시간이 4이상인 회의들을 선택할 수 있고

 

4번째 회의를 선택하면 다음 회의로는 시작시간이 7이상인 회의들을 선택할 수 있고

 

8번째 회의를 선택하면 다음 회의로는 시작시간이 11이상인 회의들을 선택할 수 있고

 

11번째 회의를 선택하면 최대 4개의 회의를 선택할 수 있다.

 

 

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int n;
struct info{
    int s, e;
};
vector<info> v;

bool cmp(const info &a, const info &b)
{
    return a.e==b.e ? a.s<b.s : a.e<b.e;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i=1; i<=n; i++){
        int s, e; cin >> s >> e;
        v.push_back({s, e});
    }
    sort(v.begin(), v.end(), cmp);
    int ans=0, en=0;
    for(int i=0; i<n; i++){
        if(v[i].s>=en){ en=v[i].e; ans++; }
    }
    cout << ans << "\n";
    return 0;
}

 

 

 

BOJ 13904 과제

과제가 $N$개 주어져 있고 각 과제마다 날짜와 점수가 있는데 날짜가 넘어가면 그 과제는 할 수 없게 되고 가능한 최대 점수를 찾는 문제이다.

가장 중요한 요소인 점수를 기준으로 과제를 정렬한다.

그리고 점수가 큰 과제부터 수행할 수 있으면 수행한다. 수행할 수 없으면 근처에 비어있는 날짜에 넣는다.

 

예제를 보면(앞이 날짜, 뒤가 점수이다.)

4 60

4 40

1 20

2 50

3 30

4 10

6 5

이렇게 되어 있고 이를 점수를 기준으로 내림차순으로 정렬하면

4 60

2 50

4 40

3 30

1 20

4 10

6 5

가 된다.

 

1번째 과제 4 60은 할 수 있다.

2번째 과제 2 50또한 할 수 있다.

3번째 과제 4 40은 1번째 과제와 날짜가 겹치므로 비어있는 3일에 한다.

4번째 과제 3 30은 3일에 하려고 보니 3번과 겹치고, 2일에 하려고 보니 2번과 겹친다. 따라서 1일에 한다.

5번째 과제 1 20은 할 수 없다.

6번째 과제 4 10은 4일에 하려고 보니 1번과 겹치고 3일에 하려고 보니 3번과 겹치고 2일에 하려고 하니 4번과 겹치고 1일에 하려고하니 5번과 겹치므로 못한다.

7번째 과제 6 5는 6일에 할 수 있다.

 

∴ 60 + 50 + 40 + 30 + 5 = 185

 

 

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int n;
struct info{
    int day, score;
};
vector<info> v;

bool cmp(const info &a, const info &b)
{
    return a.score==b.score ? a.day<b.day : a.score>b.score;
}

bool chk[1001];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i=1; i<=n; i++){
        int a, b; cin >> a >> b;
        v.push_back({a, b});
    }
    int ans=0;
    sort(v.begin(), v.end(), cmp);
    for(int i=0; i<n; i++){
        if(!chk[v[i].day]){
            ans+=v[i].score;
            chk[v[i].day]=1;
        }
        else{
            for(int j=v[i].day-1; j>=1; j--){
                if(!chk[j]){
                    chk[j]=1;
                    ans+=v[i].score; break;
                }
            }
        }
    }
    cout << ans << "\n";
    return 0;
}