[Algorithm] 그리디 알고리즘 (Greedy Algorithm)

그리디 알고리즘 (Greedy Algorithm) : 미래에 어떤 결과가 나올지는 고려하지 않은 채 현재 단계에서 가장 최적의 경우를 구하는 알고리즘. 동적 프로그래밍과 같이 각 단계에 나올 경우를 하나씩 고려해주기 때문에 동적 프로그래밍과 유사한 점이 있다.

매 단계마다 진행하는 경우는 최적이지만, 모든 경우의 수를 구했을 때 도출 되는 결과가 최적이라는 보장은 없다. 대표적인 문제가 분할가능 배낭문제 (Fractional Knapsack Problem) 이다.

Fractional Knapsack Problem (분할가능 배낭 문제)

"W 무게 만큼 담을 수 있는 배낭에 물건을 담으려고 한다. 물건들은 각각 W (무게)와 P (가격)에 대한 정보를 가지고 있다. 이 때, 가격의 총합이 최대가 되게 물건을 담아라. 단, 무게가 초과되면 물건을 쪼개어 일부분만 담을 수 있다."


가령 배낭이 담을 수 있는 최대 무게가 5kg이며, 각 물건에 대한 정보가 아래와 같다고 가정해보자.

	W	P
b1	2	800
b2	1	500
b3	7	1400
b4	3	3000

물건을 쪼갤 수 있다면 당연히 무게 대비 가성비가 좋은걸 많이 넣는게 최대가 될 것이다.

즉 b1 = 800 / 2 = 400, b2 = 500 / 1, b3 = 1400 / 7 = 200, b4 = 3000 / 3 = 1000이며, 이를 내림차순으로 정렬한다면 b4 -> b2 -> b1 -> b3  순으로 담는게 최대값이 될 것이며, 따라서 b4를 3kg만큼, b2를 2kg만큼 담도록 한다.

이처럼 크기순으로 정렬하여 뒤에 일은 생각하지 말고 일단 가장 크게만 만들어주면 되는 것이 그리디 알고리즘이다. 아래 문제로 감을 더 익혀보자.




11047. 동전 0


문제

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


풀이

앞에서 설명한 것처럼 그리디 알고리즘으로 풀어주면 된다. 동전의 수가 최소가 되려면 일단 가치가 가장 큰 것부터 최대한 사용하면 되는 것이다. 가치가 가장 큰 걸 다 쓰면 그 다음으로 큰 걸 쓰고... 이 과정을 반복하여 가치가 0이 되게끔 해주면 된다.


소스코드

//
//  Coin0.cpp
//  test
//
//  Created by 신기열 on 24/05/2019.
//  Copyright © 2019 신기열. All rights reserved.
//

#include <stdio.h>
#include <iostream> 

using namespace std;

int main(){
    
    int n, value, cnt = 0;
    cin >> n >> value;
    
    int val[n];
    
    for(int i = 0; i < n; i++){
        int v;
        cin >> v;
        val[i] = v;
    }
    

    for(int i = n - 1; i >= 0; i--){
        
        int j = 0;
        while(value - val[i] * (j + 1) >= 0){
            j++;
        }
        value = value - val[i] * j;
        cnt += j;
        
        if(value <= 0) break;
    }
    
    cout << cnt;
    
    return 0;
}

소스코드 : https://github.com/betterafter/BaekJoon/blob/master/Greedy/Coin0.cpp






11399. ATM


문제

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


풀이

역시 다를 바 없다. time 배열에 시간에 대한 정보를 저장하고 크기순으로 정렬해주고, sum 배열에 자신이 기다린 시간 + 돈을 뽑는데 걸리는 시간을 저장해준 후, 최종적으로 sum 배열 내에 있는 값들을 전부 더해서 출력해주면 된다.


소스코드

//
//  ATM.cpp
//  test
//
//  Created by 신기열 on 24/05/2019.
//  Copyright © 2019 신기열. All rights reserved.
//

#include <stdio.h>
#include <algorithm>
#include <iostream>

using namespace std;

int main(){
    
    int n, sum[1001] = { 0, }, res = 0;
    cin >> n;
    
    int time[n];
    
    for(int i = 0; i < n; i++){
        int p;
        cin >> p;
        time[i] = p;
    }
    
    sort(time, time + n);

    
    for(int i = 0; i < n; i++){
        for(int j = 0; j <= i; j++){
            sum[i] += time[j];
        }
    }
    
    for(int i = 0; i < n; i++){
        res += sum[i];
    }
    
    cout << res;
    
    return 0;
    
}

소스코드 : https://github.com/betterafter/BaekJoon/blob/master/Greedy/ATM.cpp