그리디 알고리즘(Greedy Algorithm)

그리디가 뭐에요

그리디 알고리즘이란 말 그대로 욕심을 부리면서 답을 찾는 알고리즘을 말합니다. 그때 그때 상황에서의 최적해로 답을 정하는 방식입니다. 이 방식으로 풀리는 문제는 많지 않지만, 이 방식이 통하는 문제가 존재하기에 꼭 알아둬야 합니다. 그리디 알고리즘으로 해결하는 문제들은 대부분 그리디로 풀린다고 증명을 하기 보다는, 직관을 많이 요하고 Proof by AC가 많습니다. 문제를 읽다가 어떻게 하면 될 것 같다는 생각이 들면 반례를 찾아보고, 없으면 빠르게 구현하면 됩니다.

예시 1

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

11047번: 동전 0

풀이

$A_i$가 무조건 $A_{i-1}$의 배수이므로 $A_i$원을 낼 때 $i$ 번째 동전을 선택하지 않고 $i-1$번째 동전을 여러개 쓰는게 더 효율적인 경우가 없다는 것을 알 수 있습니다. 그러므로 가장 값어치가 큰 동전부터 선택하면됩니다.

($A_i$가 $A_{i-1}$의 배수라는 조건이 없다면 이 방법으로 해결되지 않습니다. 반례는 동전의 값어치가 6원, 5원, 3원, 1원이고, 8원을 만드려고 할 때 그리디하게 선택하면 6원 1개, 1원 2개가 선택되지만, 실제로 답은 5원 1개, 3원 1개를 선택하는게 더 이득입니다.)

소스코드

#include <bits/stdc++.h>
using namespace std;

int n,k,ans,a[10];

int main(void) {
	ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=n;i>=1;i--) {
        ans+=k/a[i];
        k=k%a[i];
    }
    cout<<ans;
    return 0;
}

예시 2

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

11399번: ATM

풀이

줄이 $i$번째의 사람이 돈을 인출하는데 걸리는 시간이 $A_i$라고 한다면 답은 $A_1 \times N + A_2 \times (N-1) \ldots A_N$이 됩니다. 그러므로 $A$가 오름차순 정렬된 경우가 가장 최적입니다.

소스코드

#include <bits/stdc++.h>
using namespace std;

int n,ans,p[1010];

int main(void) {
    cin>>n;
    for(int i=1;i<=n;i++) cin>>p[i];
    sort(p+1,p+n+1);
    for(int i=1;i<=n;i++) {
        ans+=p[i]*(n-i+1);  
    }
    cout<<ans;
    return 0;
}

Ex. 3

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

2437번: 저울

풀이

추의 무게들을 모두 정렬한 배열이 $A_i$라고 합시다. 지금까지 $1~x$의 무게를 만들 수 있었는데 무게가 $y$인 추가 생긴다고 하면 $1 ~ x+y$까지의 무게를 만들 수 있습니다. 그러나 $y>x$인 경우에는 $x+1$을 절대로 만들 수 없습니다. $A_i$를 쭉 보면서 $A_i$가 현재까지 만들 수 있었던 최대 무게보다 크다면 답은 그 값+1이 되고, 그렇지 않다면 그 값에 $A_i$를 더해주면 됩니다.

소스코드

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

Ex. 4

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

11034번: 캥거루 세마리2

풀이

처음에는 A가 B와 C 사이로 점프하거나 C가 A와 B 사이로 점프할 수 있습니다. 전자의 경우 최대 C-B-1번 점프할 수 있고, 후자의 경우 최대 B-A-1번 점프할 수 있습니다. 따라서 답은 max(B-A, C-B)+1이 됩니다.

소스코드

#include <bits/stdc++.h>
using namespace std;

int a,b,c;

int main(void) {
    while(scanf("%d",&a)!=EOF) {
        scanf("%d %d",&b,&c);
        printf("%d\n",max(b-a,c-b)-1);
    }
    return 0;
}

Exchange Argument

Exchange Argument 기법은 어떤 임의의 두 인접한 원소를 봤을 때, 순서를 특정 기준으로 정하는 것이 최적일 때, 해당 기준으로 전체를 정렬하면 된다는 주장입니다.

그게 뭔소리여

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

14908번: 구두 수선공

구두를 수선하는 순서가 가장 빠른 것부터 $k_1, k_2, \ldots, k_N$이라고 하면 답은 \(\sum_{i=1}^{N} {(\sum_{j=1}^{i-1} {T_{k_i}} \times S_i})\)가 됩니다.

수선할 구두가 a와 b만 있다고 가정해봅시다.

그러면 a와 b를 (a->b)의 순서로 놓는 방법과 (b->a)로 놓는 방법이 있는데, 전자의 경우 답이 $T_a \times S_b$가 될 것이고, 후자의 경우 답이 $T_b \times S_a$입니다. 즉, a의 순서< b의 순서가 되려면 \(\dfrac{T_a}{S_a}<\dfrac{T_b}{S_b}\)를 만족해야 합니다.

답은 왠지 $\dfrac{T_i}{S_i}$를 기준으로 정렬해서 일을 처리하면 될 것 같습니다. 증명해봅시다.

pf) 귀류법을 사용합니다.

$\dfrac{T_i}{S_i}$를 기준으로 정렬한 순서를 S라고 하고, 답은 S'(≠S)이라고 가정해봅시다.

그러면 S'에서 인접한 두 원소 $k_i$와 $k_{i+1}$ 중 \(\dfrac{T_{k_i}}{S_{k_i}} > \dfrac{T_{k_{i+1}}}{S_{k_{i+1}}}\)인 i가 존재합니다. 이 때 $k_i$와 $k_{i+1}$을 바꾸면 답이 더 최적이 됩니다.(가정에 모순)

따라서 $\dfrac{T_i}{S_i}$를 기준으로 정렬하면 답이 됩니다.