[알고리즘] Greedy Algorithm(탐욕 알고리즘)

Greedy Algorithm[탐욕 알고리즘]이란?

각 단계에서 가장 최선의 선택지(가장 큰, 가장 작은 등)를 고르는 것.

Greedy 알고리즘은 구현이 쉽다는 장점이 있지만, 항상 최선의 답을 구하는 것은 아니다. 

 

Greedy Algorithm을 활용 가능한 문제

1) 거스름돈

x라는 금액의 거스름돈이 주어야할 때, 10,000원, 5,000원, 1,000원, 500원, 100원으로 가장 적은 갯수의 거스름 돈을 주어야하는 상황

 

#include <iostream>

using namespace std;

int main(){
    int x, cnt = 0;
    cin >> x;

    // 가장 큰 액수의 화폐부터 선택
    cnt += x / 10000;
    x = x % 10000;

    cnt += x / 5000;
    x = x % 5000;

    cnt += x / 1000;
    x = x % 1000;

    cnt += x / 500;
    x = x % 500;

    cnt += x / 100;

    cout << cnt;

}

 

2) Task Scheduling Problem

운영 체제에서 사용하는 방법으로 프로세스의 총  대기시간을 최소로 줄어야하는 상황

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

using namespace std;

int main(){
    int n; // process 개수
    vector <int> v; // prcess 당 burst time
    int wait = 0;

    cin >> n;

    for(int i = 0; i < n; i++){
        int tmp;
        cin >> tmp;
        v.push_back(tmp);
    }
    
    // burst time이 가장 적은 process부터 실행
    sort(v.begin(), v.end());

    for(int i = 0; i < n; i++){
        for(int j = 0; j < i; j++){
            wait += v[j];
        }
    }

    cout << wait;
}