[알고리즘] 그리디 - 백준 11047: 동전 0, 1931: 회의실 배정, 2217: 로프, 12865: 평범한 배낭

[실전 알고리즘] 0x11강 - 그리디

바킹독님의 블로그를 바탕으로 정리한 글입니다.

---

그리디 알고리즘은 탐욕적으로 지금 상태에서 가장 최적인 답을 선택하는 알고리즘이다.

이를 다르게 말하면 관찰을 통해 탐색 범위를 줄이는 알고리즘이다.

• 조금 더 쉽게 풀어보자면 현재 상태를 관찰해서 원래라면 O(N^2) 만큼 탐색해야 하는걸 O(N) 정도로 줄이는 것이다.
• 예를 들어 merge sort를 생각해보자. 병합 과정의 한 step을 생각해보면, 정렬된 결과 배열에 들어갈 하나의 원소를 선택해야 한다.
• 이 과정에서 현재 칸에 들어가는 원소는 병합 대상 배열들을 모두 순회해서 결정하는 것이 아닌, 배열의 가장 앞 원소만 보고 더 작은 원소를 선택하면 된다.
• greedy하게 탐색 범위를 줄이는 것이다.

그리디 알고리즘은 이상적으로 다음과 같은 과정을 통해 푸는 것이 가장 좋다.

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

그런데 수학적으로 증명은 굉장히 어렵고 practical에서는 사용할 수 없다.

그렇다면 수학적 증명 과정만 스킵하고 나름 근거를 가진 뒤 구현해서 제출해보는 방법이 있다.

 

조금 절망적인 상황을 생각해보면 그 근거가 사실은 틀렸고 보통 이런 잘못된 근거는 굉장히 오랜 시간을 써야 잘못된 부분을 찾아낼 수 있다. 그래서 차라리 다음과 같은 방법을 사용해보자.

1. 이전에 그리디로 풀어본 문제이거나 간단한 문제여서 100% 그리디로 확신한다. 
   • 빠르게 구현해서 제출해보고 틀리면 빠르게 손절
2. 100% 확신은 아닌데 뭔가 그리디로 풀면 될 것 같다.
   • 일단 넘어가고 다른 문제부터 풀기. 마지막에 시간이 애매하게 남으면 한 번 풀어보기.

사실 그리디 유형은 코딩테스트에 자주 등장하지는 않고 그리디로 착각해서 잘못된 풀이를 계속 시도하는 경우가 더 잦다.그래서 위의 방식들이 추천되는 것이다.

---

연습 문제 1. 11047: 동전 0

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

 

N 종류의 동전을 가지고 가치의 합을 K로 만드는데 필요한 동전의 최솟값을 구하면 된다.

N은 최대 10, K는 최대 1억이다.

 

문제를 바로 봤을 때 떠오르는 풀이는 다음과 같았다.

1. DP
   • dp[k] = 가치의 합을 k로 만들 때 필요한 동전 개수의 최솟값
   • dp[k] = min(dp[k - Ai]) + 1( i = 1~N), Ai는 i번째 동전
   • 위의 풀이는 하나의 dp[k]를 구하는데 O(N), 총 k번 구해야하므로 O(NK)
   • NK는 10억번의 연산이 일어나는데 10억은 보통 1초안에 연산할 수 없다.
2. 그리디
   • 제일 큰 동전부터 합을 계산하고 K와의 차액만큼 다음 동전에 대해 계산
   • 직관적으로 답을 구할 수 있을 것 같고 문제도 없어보인다.
   • 비교적 간단한 문제이기에 100% 확신을 가질 수 있었고 바로 구현해보자.

/** 그리디 11047 동전 0 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int n, k;
int ans = 0;
int coins[15];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k;

    for (int i = 0; i < n; i++)
        cin >> coins[i];

    int cnt = n - 1;
    while (k != 0 && cnt >= 0)
    {
        if (coins[cnt] > k)
        {
            cnt--;
            continue;
        }
        ans += k / coins[cnt];
        k = k % coins[cnt];
        cnt--;
    }

    cout << ans << '\n';
}

 

간단하게 그리디로 풀 수 있었지만 비슷한 문제를 만났을 때 무조건 그리디로 확신해서는 안된다.

예를 들어 5의 배수로 동전의 단위가 정해지는 것이 아닌 경우, 1, 5, 9, 10원이 있을 때 19원은 위의 알고리즘대로면 10원을 먼저 사용하고 나머지 9에 대해 동전을 사용하게 된다. 9원 두 개가 최적임에도 이를 고려하지 않는 것이다.

 

이런식으로 사실 그리디는 코딩테스트에서 잘못 떠올리기 굉장히 쉽다. 유의하고 넘어가자.

---

연습 문제 2. 1931: 회의실 배정

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

 

한 개의 회의실이 있을 때 N개의 회의가 겹치지않는 최대 회의 수를 구하면 된다. N은 최대 10^5, 10만이다.

 

먼저 가장 간단하게 모든 경우의 수를 판단하면 당연히 구할 수 있겠지만 당연히 시간 초과이다.

DP도 떠오르는데

먼저 회의가 끝나는 시간을 기준으로 오름차순 정렬을 한 뒤

dp[i] = i번째 회의까지 진행했을 때 최대 회의 수로 두고 dp[i] = max(dp[j]) + 1(j<=i)로 구할 수 있다.

i번째 회의보다 빨리 끝나는 회의를 기준으로 dp 값에 1을 더하면 되는 것이다.

이 방법도 O(N^2)이 나와서 시간 초과이다.

 

그래도 DP 풀이에서 하나 건진게 i번째 회의보다 빨리 끝나는 회의를 기준으로 그 다음에 바로 회의를 시작하면 제일 좋다.

그런데 최대한 많이 회의를 해야하므로 끝나는 시간이 제일 빠른걸 greedy하게 선택하면 스케줄을 꽉꽉 채울 수 있다.

 

반례가 없을지 생각을 한 번 생각해보자.

• 가장 빨리 끝나지 않는 회의를 선택할 필요는 전혀 없다.
  1. 예를 들어 두 번째로 빨리 끝나는 회의를 선택했을 때 그 다음에 가능한 회의 집합을 C2라 하자. C1은 가장 빨리 끝나는 회의를 선택했을 때 그 다음에 가능한 회의 집합이다.
  2. C2는 C1에 포함되므로 가장 빨리 끝나는 회의를 선택하는게 일단 가장 좋다.

이정도면 반례는 없을 것 같고 구현도 쉬울 것 같으니 바로 들어가면 된다.

회의가 빨리 끝나는 시간을 기준으로 정렬한 뒤 선택해나가면 된다.

/** 그리디 1931 회의실 배정 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int n;
pair<int, int> c[100005]; // end time, start time
int ans = 0;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int e, s;
        cin >> s >> e;
        c[i] = {e, s};
    }

    sort(c, c + n);

    int cur = c[0].first;
    ans++;

    for (int i = 1; i < n; i++)
    {
        // i번째 회의의 start time이 현재 선택한 회의의 end time 보다 같거나 크면 바로 선택
        if (c[i].second < cur)
            continue;
        ans++;
        cur = c[i].first;
    }

    cout << ans << '\n';
}

---

연습 문제 3. 2217: 로프

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

 

N개의 로프를 가지고 들 수 있는 최대 중량을 계산하면 된다. 각 로프는 들 수 있는 중량이 다르다.

처음 문제를 봤을때는 그냥 모든 로프를 쓰면 안되나? 했었는데 극단적인 예시로 1000을 들 수 있는 로프 a와 1을 들 수 있는 로프 b를 생각해보자.

두 로프를 모두 사용하면 1은 너무 약해서 1밖에 못든다. 총 2를 들 수 있는 것이다.

 

위의 예시에서 얻을 수 있는 통찰은 너무 약한 로프는 사용하면 안된다. 즉, k개의 로프를 사용해야 한다. 

k는 O(n)으로 모두 돌면서 구하면 되고, k개의 로프를 어떻게 선택해야 할까?

직관적으로 생각해보면 그냥 제일 많이 들 수 있는 k개의 로프를 선택하면 된다. 계산은 로프를 내림차순으로 정렬한 뒤, rope[n-w]가 그 중 제일 약하므로 rope[n-w] * k를 계산하면 된다.

 

바로 구현해보자.

/** 그리디 2217 로프 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int rope[100010];
int n;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> rope[i];
    sort(rope, rope + n);

    int ans = 0;
    for (int k = 1; k <= n; k++)
        ans = max(ans, rope[n - k] * k);

    cout << ans << '\n';
}

 

처음 흐름만 잘 타면 그리디를 생각하는 것 까지도 쉽고 구현은 더 쉽다. 독특한 흐름이니 이 부분만 기억해두면 될 것 같다.

---

연습 문제 4. 12865: 평범한 배낭

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

 

0-1 knapsack 유형으로 분류되는 굉장히 유명한 문제이다.

간략하게 설명하자면 물건을 담거나 담지 않는 수 밖에 없는 2진 분류 문제이다.

 

그리디 챕터에 포함되어있으니 가장 쉽게 떠오르는 풀이는 무게 대비 가치가 가장 높은 물건을 담는 것이다.

바로 풀어보자!

---

---

---

---

사실 그리디로 풀면 안된다. 내부 단편화 문제가 존재하는데, 예시 1번으로 보자.

4 7
6 13
4 8
3 6
5 12

 

무게 6을 넣게되면 무게 1의 낭비가 발생한다. 이런 문제를 내부 단편화라 한다.

그래서 그리디로 풀면 안되고 다른 방식을 생각해봐야 한다.

 

DP가 바로 떠오르는데 dp[i] = i 무게에서 들 수 있는 최대 가치로 설정하고 점화식을 고민해보자.

 

dp[i] = max(dp[i], dp[i - w[j] + v[j]), w[j] <= i 인 동안 반복

이렇게 하면 된다. i 무게 가방에서 j번째 물건을 넣는 경우를 따져보는 것인데, 여기서 문제가 되는 부분이 중복이다.dp[3]에서 이미 2번째 물건을 선택했는데 dp[4]에서 2번째 물건을 또 선택할 수 있는 것이다.

 

중복을 해결하기 위해 우선 물건별로 dp값을 구해야 한다. j loop를 바깥쪽에 두고 j번째 물건을 넣을지 말지 정하는 것이다.

물건을 기준으로 루프를 먼저 돌게되어도 중복이 발생하는데, 예를 들어 dp[6]을 구할 때 dp[3] + v[3]이 최대가 되고 dp[3] = v[3]인 경우 여전히 중복이 발생하는 것이다.

 

이는 dp[i]를 뒤에서부터 구하는 방식으로 해결할 수 있다. j번째 물건을 쓸건데 딱 한 번 쓰도록 한다고 생각하면 이해가 쉽다. 

/** DP 12865 평범한 배낭 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int n, k;
int w[104];
int v[104];
int dp[100005];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k;

    for (int i = 0; i < n; i++)
        cin >> w[i] >> v[i];

    for (int j = 0; j < n; j++)
    { // 각 물건마다 한 번씩
        for (int i = k; i >= w[j]; i--)
        {

            dp[i] = max(dp[i], dp[i - w[j]] + v[j]);
        }
    }

    cout << dp[k] << '\n';
}