Greedy Algorithm (그리디 알고리즘)

현재 사황에서 지금 당장 좋은 것만 고르는 방법

매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서 고려하지 않는다.

 

1. Example. 거스름돈

(1) 문제

거스름돈으로 사용한 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다.

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

 

(2) 문제 해설

그리디 알고리즘을 이용해 풀어 보자.

가장 큰 화폐 단위부터 돈을 거슬러 주는 것이다.

가장 먼저 500원으로 거슬러 줄 수 있을 만큼 거슬러 준다. 그다음 100원, 50원, 10원짜리 동전을 차례대로 거슬러 줄 수 있을 만큼 거슬러 주면 최소의 동전 개수로 모두 거슬러 줄 수 있다.

(3) 소스 코드

public class greedy {
    static int n = 1260;
    static int[] coin_types = {500, 100, 50, 10};
    public static void main(String[] args) {
        int count = 0;
        for (int i = 0; i <coin_types.length; i++) {
            count += (n/coin_types[i]);
            n %= coin_types[i];
        }
        System.out.println(count);
    }
}

 

2. 그리디 알고리즘의 정당성

그리디 알고리즘의 해가 항상 최적의 해가 아니다.

그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토해야 한다. 

위의 Example 거스름돈 문제가 그리디 알고리즘으로 해결할 수 있는 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.

예를 들어 N = 800원이고 화폐단위가 500원, 400원, 100원인 경우 그리디 알고리즘으로는 500 1개, 100원 3개이지만 최적의 해는 400원 2개를 거슬러 주는 것이다. 

대부분의 그리디 알고리즘 문제에서는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 컴토할 수 있어야 답을 도출할 수 있다.