[Algorithm] 그리디 알고리즘

그리디 알고리즘은 한국어로 탐욕 알고리즘 이라고도 하며 결정해야 하는 순간 가장 좋다고 생각하는 것을 선택하면서 답을 찾아가는 알고리즘을 말합니다.

이 방식의 한계점은 그 순간에는 최적일지도 모르지만 최종적으로는 답이 아닐 수 있는 경우가 많기 때문에 그리디 알고리즘을 사용한 경우, 최적이라는 걸 입증하는게 쉽지 않습니다. 그래도 입증만 한다면 구현하는건 다른 알고리즘에 비해 쉬운 편입니다.

문제를 풀면서 이해해보도록 하겠습니다.

BAEKJOON 동전 0

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

11047번: 동전 0

#include <iostream>

using namespace std;

int main(int argc, const char * argv[]) {
    
    int coin[10];
    int coinNum = 0;
    
    int N,K;
    cin >> N >> K;
    
    for (int i=0;i<N;i++){
        cin >> coin[i];
    }
    
    for (int i=N-1;i>=0;i--){
        int temp = K / coin[i];
        coinNum += temp;
        K -= coin[i] * temp;
    }
    
    cout << coinNum << "\n";
   
    return 0;
}

화폐의 가치가 큰 동전부터 순회하면서 그 순간 최적의 수, 최대한 동전을 많이 사용하도록 합니다. 여기서 다음과 같은 그리디 알고리즘을 사용할 수 있는 이유는 아래와 같은 문장 때문입니다.

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

동전의 가치가 서로 배수관계에 있기 때문에 가능합니다. 만약 다음과 같은 언급이 없었으면 반례가 존재합니다.

3 1200
1
100
400
500

그리디 알고리즘 을 사용한다면 500원 짜리 두 개를 사용한 후 100원 짜리 두 개를 더 사용하여 4개 동전을 사용하는 반면, 400원 동전을 통해 3개만에 만들 수 있습니다.

이처럼 그리디 알고리즘은 사용할 수 있음을 증명만 한다면 쉽지만 조금만 조건이 바뀌더라도 예외사항이 많이 존재하기 때문에 쉬지만은 않은 알고리즘 입니다.