탐욕법 (Greedy)

탐욕법은 각 단계마다 지역적으로 최적인 선택을 하면서, 결국 전역 최적해를 찾는 방식의 알고리즘입니다.

조금 더 쉽게 말하자면,

각 단계에서 지금 "가장 좋아보이는" 선택을 하는 것을 반복해서, 결국 전체적으로 가장 좋은 선택이 되도록 하는 알고리즘을 말합니다.

 

하지만 이 방식을 모든 문제에서 쓸 수 있는 것은 아닙니다.

간단한 예를 들어봅시다.

 

다음과 같은 그래프가 있습니다.

우리는 1번 정점에 있고, 4번 정점까지 최단거리를 구하려고 합니다. 그리디하게 접근해봅시다.

현재 1번 정점에서 거리 5인 2번정점으로 가는 것 보다는, 거리가 2인 3번 정점으로 가는 것이, 현재 "가장 좋아보이는 선택"입니다.

하지만 실제 최단 거리는 그렇지 않음을 쉽게 알 수 있습니다.

 

따라서 탐욕법을 이용해 문제를 풀고자 한다면, 먼저 이 문제가 탐욕적으로 풀릴 수 있는 문제인지를 증명해야 합니다.

다시 말하자면, 지역적으로 최적인 선택이 전역으로도 최적인지 증명한 후에 탐욕법을 이용한 문제 풀이를 진행해야 합니다.

그렇기 때문에 탐욕법을 이용한 문제는 풀이가 단순한 대신, 이런 성질을 증명하는 것이 어려운 경우가 많습니다.

 

탐욕법으로 풀 수 있는 문제들은 굉장히 한정되어 있지만, 탐욕법은 일단 지역적으로 최적해를 찾아주기 때문에, 전역 최적해를 찾기 어려운 경우에 "적당한" 근사해를 구하는데에는 좋은 알고리즘입니다.

 

그럼 탐욕법으로 풀 수 있는 문제들의 예를 몇가지 살펴보도록 합시다.

 

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

11047번: 동전 0

\(N\)종류의 동전이 있습니다. 이 동전들을 적절히 사용해 합이 \(K\)원이 되도록 하려고 하는데, 필요한 동전 개수의 최소값을 구해야 합니다.

 

탐욕적으로 접근해봅시다. 동전 개수를 최소화 하려면, 가장 가치가 높은 동전부터 차례로 가져가면 되지 않을까요?

실제로 이 방법으로 동전을 가져가는 것이 답입니다.

 

\(A_i\)이 \(A_{i-1}\)의 배수이기 때문에, \(A_i\)원을 만드는데 더 가치가 작은 동전 여러개를 사용하는것 보다는 \(A_i\)원짜리 동전 하나를 사용하는게 무조건 이득임을 쉽게 증명할 수 있습니다.

 

#include <iostream>
using namespace std;
 
int n, k;
int a[10];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> a[i];
 
    int ans = 0;
    for (int i = n - 1; i >= 0; i--) // 가장 가치가 높은 동전부터 본다.
    {
        ans += k / a[i]; // a[i]를 최대한 사용한다.
        k %= a[i];
    }
 
    cout << ans;
}

---

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

1931번: 회의실배정

\(N\)개의 회의의 시작시간과 끝나는 시간이 주어집니다.

한 개의 회의실에서 서로 겹치지 않으면서 진행할 수 있는 회의의 최대 수를 구해야 합니다.

 

역시 탐욕법으로 접근해봅시다. 회의를 최대한 많이 하려면, 가장 빨리 끝나는 회의를 반복해서 고르면 될 것 같습니다.

 

회의들을 끝나는 순서가 빠른순으로 정렬 한 다음, 지금까지의 회의와 겹치지 않으면서 가장 빨리 끝나는 회의를 반복해서 골라 회의를 배정합시다. 더 이상 배정할 수 있는 회의가 없을 때, 지금까지 배정한 회의의 수가 답입니다.

 

#include <iostream>
#include <algorithm>
using namespace std;
 
struct meet
{
    int st, ed;
    bool operator<(meet& m)
    {
        if (ed != m.ed) return ed < m.ed; // 정렬하게 되면 끝나는 순서 순으로
        return st < m.st; // 끝나는 시간이 같다면 시작하는 순서 순으로
    }
};
 
int n;
meet mt[100001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> mt[i].st >> mt[i].ed;
 
    sort(mt, mt + n); // 위의 기준에 맞춰 정렬
 
    int ans = 0;
    int cur_ed = 0; // 현재 회의가 끝나는 시간
 
    for (int i = 0; i < n; i++)
    {
        if (mt[i].st < cur_ed) continue; // 회의 시간이 겹치는건 무시한다.
        
        cur_ed = mt[i].ed;
        ans++; // 겹치지 않으면 이 회의를 추가한다.
    }
 
    cout << ans;
}

---

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

1202번: 보석 도둑

\(N\)개의 보석이 있습니다. 각 보석은 무게 \(M_i\)와 가격 \(V_i\)를 가지고 있습니다.

이 보석들을 \(K\)개의 가방안에 넣어 가져가려고 하는데 가방에 담을 수 있는 최대 무게는 \(C_i\)로 정해져 있고, 각 가방에는 최대 1개의 보석만을 가져 갈 수 있습니다.

이 때 가져갈 수 있는 보석의 최대 가격을 구해야 합니다.

 

탐욕적으로 생각해보면, 가방에 보석이 1개밖에 안들어가므로 최대한 가격이 높은 보석부터 가방에 넣는게 이득임을 알 수 있습니다.

보석을 가격순으로 정렬한 다음, 넣을 수 있는 가방이 있다면 그 가방에 보석을 넣으면 됩니다.

 

만약 넣을 수 있는 가방이 여러개라면 어떻게 해야 할까요?

이것도 탐욕적으로 접근해봅시다. 그 중 담을 수 있는 최대 무게가 가장 작은 가방을 선택하는 것이 이득임을 쉽게 알 수 있습니다.

만약 위에서 설명한 가방에 담을 수 있는 최대 무게가 \(C_i\)인데, 만약 최대 무게가 \(C_j\)인 가방을 선택했다고 합시다.

그럼 무게 \(W\)가 \(C_i \lt W \le C_j\)인 보석이 나오면 원래는 가져갈 수 있었겠지만, 가져가지 못하게 됩니다. 이런 방식으로 위의 방법이 최적임도 증명할 수 있게 됩니다.

 

#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
 
struct jewel
{
    int m, v;
    bool operator<(jewel j)
    {
        if (v != j.v) return v > j.v; // 가치가 높은 순으로 정렬한다.
        return m < j.m;
    }
};
 
int n, k;
jewel j[300001];
 
multiset <int> bag;
// 필요없는 원소를 제거하면서 lower_bound를 빠르게 찾기 위해 multiset을 이용한다.
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        cin >> j[i].m >> j[i].v;
 
    for (int i = 0; i < k; i++)
    {
        int c; cin >> c;
        bag.insert(c);
    }
 
    sort(j, j + n);
 
    long long ans = 0;
    for (int i = 0; i < n; i++)
    {
        auto it = bag.lower_bound(j[i].m);
        // 현재 보석의 무게보다 같거나 큰 값 중 가장 작은 것을 찾는다.
 
        if (it == bag.end()) continue;
        // 없으면 가져가지 못한다.
 
        ans += j[i].v;
        bag.erase(it); // 사용한 가방은 multiset에서 삭제한다.
    }
 
    cout << ans;
}

---

제 그룹의 문제집에서 연습 문제들을 관리하고 있습니다.
문제집의 문제들을 보고 싶으시다면, 가입 신청을 해 주세요.

https://www.acmicpc.net/group/7712

ANZ1217

가입 신청하시면 최대한 빨리 승인해드리겠습니다!