그리디 알고리즘

그리디 알고리즘에 대해

 

그리디 알고리즘 유형은 국내 알고리즘 교재에서 단어 그대로 번역하여 탐욕법으로 소개됩니다.

현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미합니다.

그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로

문제에서 '가장 큰 순서대로', 가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해줍니다.

대체로 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로

그리디 알고리즘 문제는 자주 정렬 알고리즘과 짝을 이뤄 출제됩니다.

 

지금 살펴볼 거스름돈 문제는 그리디 알고리즘을 대표하는 문제입니다.

 

 

그리디 알고리즘 문제 풀이

 

1번 - 거스름돈

문제 :

당신은 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한이 존재한다고 가정한다.

손님에게 거슬러 줘야 할 돈이 N원일 때, 거슬러줘야 할 동전의 최소 개수를 구하라.

단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

 

해설 :

이 문제는 그리디 알고리즘을 이용해 풀 수 있는 대표적인 문제로 간단한 아이디어만 떠올릴 수 있으면 문제를 해결할 수 있습니다. 그것은 바로 '가장 큰 회폐 단위부터' 돈을 거슬러 주는 것입니다.

 

소스 코드 :

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n;
    vector<int> v = {500, 100, 50, 10};
    int coin;
    int count = 0;
    cin >> n;
    
    for(int i=0; i<v.size(); i++) {
        count = count + (n / v[i]);
        n = n % v[i];
    }
    cout << count;
    
    return 0;
}

 

 

2번 - 큰 수의 법칙

문제 :

다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만든다.

단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없다.

ex) 2, 4, 5, 4, 6 으로 이루어진 배열이 있을 때 M이 8이고, K가 3이면

6 + 6 + 6 + 5 + 6 + 6 + 6 + 5 인 46이 된다.

 

첫째 줄에 자연수 N(배열의 크기), M, K가 주어진다.

둘째 줄에 N개의 자연수가 주어진다. 각각의 자연수는 10000 이하의 수로 주어진다.

 

입력 예시 )

5 8 3

2 4 5 4 6

 

출력 예시 )

46

 

내 소스 코드 :

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n, m, k;
    vector<int> v;
    vector<int> vv;
    int num;
    int sum = 0;
    cin >> n >> m >> k;
    
    for(int i=0; i<n; i++) {
        cin >> num;
        v.push_back(num);
    }
    sort(v.begin(), v.end(), greater<>());
    
    vv.assign(m, v[0]);
    // 6 6 6 5 6 6 6 5
    for(int i=1; i<=vv.size(); i++) {
        if (i % (k+1) == 0) {
            vv[i-1] = v[1];
        }
    }
    for(int i=0; i<vv.size(); i++) {
        sum += vv[i];
    }
    cout << sum;
    
    return 0;
}

 

하지만 제가 작성한 코드의 경우, M이 10000이하가 아니라 100억 이상 같이 커진다면 시간 초과 판정을 받습니다.

따라서 더 효율적인 코드를 짜는 방법을 알아야합니다.

 

반복되는 수열에 대해서 파악하고 코드를 작성해야 합니다.

 

M=11, K=3 이라 6+6+6+5 + 6+6+6+5 + 6+6+6 이렇게 반복됩니다.

6 + 6 + 6 + 5 단위로 생각해봅시다.

반복되는 수열의 길이 = K + 1

수열이 반복되는 수 = M / (K + 1)

가장 큰 수가 등장하는 횟수 = (M / (K + 1)) * K + M % (K + 1)

두 번째로 큰 수가 등장하는 횟수 = M - (M / (K + 1)) * K  // 가장 큰 수가 등장하는 횟수 

 

이를 이용해서 새로 코드를 작성해봅시다!

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n, m, k;
    vector<int> v;
    int num;
    int count = 0;
    int sum = 0;
    cin >> n >> m >> k;
    
    for(int i=0; i<n; i++) {
        cin >> num;
        v.push_back(num);
    }
    sort(v.begin(), v.end(), greater<>());
    
    int first = v[0];
    int second = v[1];
    
    count = (m / (k + 1)) * k;
    count += m % (k + 1);
    
    sum += count * first;
    sum += (m-count) * second;
    
    cout << sum;

    return 0;
}

 

 

출처 (학습 자료) :

 

나동빈 - 저자의 이것이 코딩 테스트다 

http://www.yes24.com/Product/Goods/91433923