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

1. 알고리즘 설명

그리디 - 지금 가장 최적인 답을 근시안적으로 택하는 알고리즘 = 관찰을 통해 탐색 범위를 줄이는 알고리즘



이상적인 풀이 흐름

1. 관찰을 통해 탐색 범위를 줄이는 방법을 고안한다.

2. 탐색 범위를 줄여도 올바른 결과를 낸다는 사실을 수학적으로 증명한다.

3. 구현해서 문제를 통과한다.

 

절망적인 풀이 흐름

1. 관찰을 통해 탐색 범위를 줄이는 잘못된 방법을 고안한다.

2. 탐색 범위를 줄여도 올바른 결과를 낸다는 사실을 수학적으로 증명한다.

3. 믿음을 가지고 구현했는데 계속 틀린다.

 

코딩테스트에서의 추천 전략

 

거의 똑같은 문제를 풀어봤거나 간단한 문제여서 나의 그리디 풀이를 100% 확신한다

-> 짜서 제출해보고 틀리면 빠르게 손절

 

100% 확신은 없지만 맞는 것 같은 그리디 풀이를 찾았다

-> 일단은 넘어가고 다른 문제를 풀게 없거나 종료가 20-40분 남은 시점에 코딩 시작

 

---

2. 연습 문제1 - 동전 0

BOJ 11047번: 동전 0 문제

11047번: 동전 0

dp로 풀이 가능.

D[i] = 가치의 합을 i로 만들 때 필요한 동전 개수의 최솟값 이라고 정의했을 때, D[i] = min(D[i-A1], D[i-A2], ... D[i-AN]) + 1이 된다. 마지막에 사용한 동전이 A1인지, A2인지, ... , AN인지를 가지고 식을 세울 수 있는거고 이렇게 풀이를 하면 O(NK)에 답을 구할 수 있다. 그런데 이 문제에서는 K가 최대 1억, N이 최대 10이어서 O(NK)는 시간 초과가 발생한다.

 

이 문제는 그리디로 풀 수 있다.

 

"동전 개수를 최소화하려면 500원 동전을 최대한 많이 써야 한다"는 명제를 증명하고자 한다. 이걸 증명하려면 보조 정리를 이용하면 좋은데, 첫 번째 보조 정리는 "동전을 최소로 소모하면서 물건값을 지불하려면 10/100원 동전은 4개 이하, 50원 동전은 1개 이하로 사용해야 한다." 이다. 이건 귀류법으로 증명가능하다.

 

귀류법 - 명제가 거짓이라고 가정할 때 모순이 발생함을 보이는 증명법

귀류법으로 생각해서 10/100원 동전을 5개 이상 사용하거나 50원 동전을 2개 이상 사용해서 동전을 최소로 소모할 수 있다고 가정하자. 그런데 10/100원 동전이 5개 이상이면 이걸 50/500원 동전으로 대체하고, 50원 동전이 2개 이상이면 100원 동전으로 대체했을 때 동전의 개수가 더 줄어든다. 모순이 발생해서 보조 정리 1이 참임을 알 수 있다.

 

동전을 최소로 소모하면서 물건값을 지불하려면 500원 동전을 최대한 많이 써야 한다는건 보조 정리 1로부터 유도가 되는데, 보조 정리 1에 따라 10/100원 동전은 4개 이하, 50원 동전을 1개 이하로 사용되어야 한다.

 

그러면 10, 50, 100원 동전으로는 물건값을 최대 490원만 감당할 수 있고, 500원을 다 사용하지 않을 경우 10, 50, 100원 동전으로 물건값을 500원 이상 감당해야 하기 때문에 귀류법으로 정리를 증명할 수 있다. 마찬가지로 500원 동전을 최대한 많이 사용한 이후에는 100원 동전을, 그 이후에는 50원을, 마지막으로 10원을 최대한 많이 사용해야 한다.

 

#include <bits/stdc++.h>
using namespace std;
int coin[15];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int n,k, cnt = 0;
    cin >> n >> k;
    for (int i = 0;i<n;i++){
        cin >> coin[i];
    }

    for (int i =n-1;i>=0;i--){
        while (k - coin[i]>=0){
            k -= coin[i];
            cnt++;
        }
    }
    cout << cnt;
    return 0;
}

 

---

3. 연습 문제2 - 회의실배정

BOJ 1931번: 회의실배정

1931번: 회의실 배정

task scheduling problem 문제다.

문제를 해결하는 방법을 생각해보면 O(2^N)개의 모든 가능한 배정 방법을 확인하는 풀이도 떠올릴 수 있고 DP를 써서 O(N^2)으로 풀이할 수도 있다. DP로 문제를 풀려고 하면 회의를 정렬해두고 나보다 먼저 끝나는 회의에 대응되는 DP 값에서 1을 더하는 방식으로 식을 정의하면 된다. 그러면 각 칸을 채울 때 이전의 모든 회의를 모두 살펴봐야 하니 시간복잡도는 O(N^2)에 해결할 수 있습니다. 하지만 아직 시간복잡도가 너무 크다.

 

그리디적인 측면으로 가능한 회의 중에서 가장 먼저 끝나는 회의를 선택하면 된다.

 

현재 시간이 t라고 할 때 시작 시간이 t 이상인 모든 회의 중에서 가장 먼저 끝나는 회의를 택하는 것이 최적해란걸 보이자. 명제를 거짓이라고 가정하면 지금 이 상황에서 회의 A 말고 다른 회의 B를 택했을 때 더 많은 회의를 배정할 수 있는 경우가 있다는 것이다. 회의 B를 회의 A로 변경해도 스케쥴에는 아무런 문제가 없다. 회의 A는 남아있는 회의 중에서 가장 먼저 끝나는 회의이니 당연히 회의 A가 회의 B보다 먼저 끝나기 때문이다. 그러면 회의 A 말고 회의 B를 선택했을 때 더 많은 회의를 배정할 수 있다고 했는데 해당 스케쥴에서 회의 B를 A로 변경하는 방법을 생각해보면 회의 A를 택했을 때 적어도 회의 B를 택했을 때 만큼의 회의는 진행할 수 있다. 이런 모순으로 인해 명제가 참임을 증명한다.

 

#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> v;
vector<pair<int, int>> ans;

// bool cmp(pair<int, int> v1, pair<int,int> v2){
//     if (v1.second == v2.second){
//         return v1.first < v1.first;
//     }else{
//         return v1.second < v2.second;
//     }
// }

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int n;
    cin >> n;

    for (int i =0;i<n;i++){
        int start, end;
        cin >> start >> end;
        v.push_back({end, start});
    }

    sort(v.begin(), v.end());
    int end = 0;
    int cnt = 0;

    for (int i = 0;i<n;i++){
        if (v[i].second >= end){
            end = v[i].first;
            cnt++;
            ans.push_back({v[i].first, v[i].second});
        }
    }
    // for (int i = 0;i<ans.size();i++){
    //     cout << ans[i].first<<" "<<ans[i].second<<"\n";
    // }
    cout << cnt;
    return 0;
}

 

---

4. 연습 문제3 - 로프

BOJ 2217번: 로프

2217번: 로프

이 문제에서도 시간복잡도를 고려하지 않는다면 2^N개의 모든 로프 조합을 따져보는 방법으로 풀이가 가능하겠지만 N이 최대 10만이나 되는 이상 불가능하다.

 

예를 들어 로프를 3개 사용하기로 정했다면 어떤 로프를 선택하는게 가장 좋을까? 직관적으로 생각하면 3개 중에서 최대 중량이 가장 낮은 로프의 중량을 가장 크게 만들어야 하니 가장 최대 중량이 큰 3개를 선택하는게 당연하다.

 

수학적으로 증명을 하고자 한다면 귀류법을 이용해서 최대 중량 순으로 선택하지 않았을 때 최대 중량이 가장 낮은 로프의 중량은 가장 최대 중량이 큰 로프들을 선택했을 때보다 클 수 없다는 식으로 보일 수 있다. 그냥 로프의 최대 중량을 정렬한 후 로프를 k개 고른다면 w[n-k] * k를 계산해주면 된다.

#include <bits/stdc++.h>
using namespace std;
int rope[100002];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;

    for (int i = 0;i<n;i++){
        cin >> rope[i];
    }
    sort(rope, rope+n,greater<>());
    int ans = 0;
    for (int i = 0;i<n;i++){
        ans = max(ans, rope[i]*(i+1));
    }
    cout << ans;
    return 0;
}

---

5. 연습 문제4 - 보물

BOJ 1026번: 보물 

1026번: 보물

문제의 예시로 설명을 해보면 1, 1, 1, 6, 0을 정렬하면 0, 1, 1, 1, 6이니 작은 수부터 차례로 B에서 가장 큰 8부터 대응시키는 방법이다.

이게 맞는 이유는 재배열 부등식이라는걸로 설명이 가능하다.

 

재배열 부등식 - 배열 A의 수와 배열 B의 수를 재배열해서 짝지어 곱한 후 합을 구할 때 큰 원소를 큰 원소와 매칭시켜주면 결과가 최대가 되고, 큰 원소를 작은 원소와 매칭시켜주면 결과가 최소가 된다는 부등식

#include <bits/stdc++.h>
using namespace std;
int a[52], b[52];
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    for (int i=0;i<n;i++){
        cin >> a[i];
    }
    for (int i=0;i<n;i++){
        cin >> b[i];
    }
    sort(a, a+n);
    sort(b, b+n);
    int ans = 0;
    for (int i = 0;i<n;i++){
        ans += a[i] * b[n-i-1];
    }
    cout << ans;
    
}

---

6. 잘못된 그리디

BOJ 12865번: 평범한 배낭

12865번: 평범한 배낭

 0-1 knapsack 문제이고 유명한 DP 문제로 풀 수 있는데 그리디로 풀게 되면 최적해를 구할 수 없다.

 

BOJ 1477번: 휴게소 세우기 

1477번: 휴게소 세우기

그리디 풀이의 반례도 쉽게 생각할 수 있는데 현재 휴게소가 한 개도 없고 휴게소를 2개 더 지을 예정이라고 하면 그리디 풀이는 500과 250에 휴게소를 짓겠지만 사실 333, 666 지점에 짓는게 더 효율적이다.

이 문제는 parametric search라고 해서 아직 우리가 배우지 않은 알고리즘을 써서 풀 수 있는 문제다.

 

 

---

참고자료

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

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