그리디 알고리즘

그리디 알고리즘은 '탐욕법'이라고도 불리는데 여기에선 그리디 알고리즘으로 사용하겠습니다.

그리디 알고리즘은 해를 구하는 과정에서 각 단계마다 '가장 최선'의 최적해를 선택해 나가면서 결과적으로 전체적인 최적의 해를 구하려는 알고리즘입니다.

하지만 각 단계마다 최적의 해를 구한다고해서 전체의 최적해를 만들지 못할 수도 있습니다. 즉 전체적인 최적의 해를 보장하지 않는다는 말입니다.

예를들어, S에서 시작해서 E에 도착할때까지의 수의 합이 가장 높은 노선을 구해봅시다.

S에서 시작해서 E까지의 노선중에서 수의 합이 가장 높은 노선은 S - 3 - 8 - E 이고 합은 11이라는것을 바로 알 수 있을 것입니다.

하지만 그리디 알고리즘을 적용해보면

S - 5 - 3 - E 라는 결과가 나왔습니다. 각 노선을 선택할 때마다 가장 높은 수를 선택했지만 최적해인 11에 미치지 못하는 8이 되었습니다. 따라서 그리디 알고리즘은 현재에서 가장 최선의 값을 선택하지만 그것이 항상 최적의 값을 보장하지 않는 알고리즘입니다.

그리디 알고리즘 예제

대표적인 문제로는 거스름돈 문제가 있습니다. 거스름돈에 사용되는 동전의 개수를 최소로 하는 문제입니다.

    public static void main(String[] args) {

        Integer[] coins = {100, 50, 10, 500}; // 동전
        int money = 780; // 거스름돈
        int count = 0; // 동전 사용 개수

        // 사용할 동전을 액수가 큰 순서대로 정렬
        Arrays.sort(coins, Comparator.reverseOrder());

        // 차례대로 거스름돈에서 차감
        for (int coin : coins) {
            count += money / coin;
            money %= coin;
        }

        // 결과 출력
        if (money == 0) {
            System.out.println("결과 count = " + count);
        }

    }