[Algorithm] 그리디(Greedy) 알고리즘

Idea

그리디(Greedy) 알고리즘은 현재 상황에서 가장 좋은 선택을 하는 방식으로 최적의 해답을 찾는 알고리즘이다. 각 단계에서 가장 좋다고 생각되는 선택을 함으로써 최종적인 해답에 도달하는 것이 목표이다. 따라서 그리디 알고리즘이 항상 최적의 해를 보장하지는 않지만, 특적 문제에서는 매우 효과적으로 작용한다.

https://besjournals.onlinelibrary.wiley.com/doi/10.1111/1365-2656.12963

첫 번째 그림과 같은 그래프가 있을 때, 거쳐가는 모든 값의 최댓값을 만든다고 한다면 정답은 Optimal 부분의 0 → 3 → 100 일 것이다. 하지만 그리디 알고리즘을 사용한다면 현재 위치에서의 최선의 선택을 하기 때문에 0의 위치에서는 3과 10 중에 10이 더 크므로 10으로 이동하고 10의 위치에서는 7과 8 중에 8이 더 크므로 8로 이동할 것이다. 즉, 그리디 알고리즘을 사용하면 0 → 10 → 8 Greedy 부분처럼 이동할 것이다.

 

위 예시에서 볼 수 있듯이 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다. 하지만 코딩테스트에서 '가장 큰 순서대로' 또는 '가장 작은 순서대로'와 같이 기준을 제시해준다면 그리디 알고리즘을 사용하는 것이 좋은 선택이 되는 상황이 있다고 한다.

 

다음은 그리디 알고리즘의 대표적인 예제 중 하나인 "동전 거스름돈 문제"를 Java로 구현한 코드이다.

10원, 50원, 100원, 500원의 동전이 있을 때, 1260원을 최소 개수의 동전으로 거슬러 주는 프로그램을 작성해라.

 

주어진 금액을 최소한의 동전 개수로 거슬러 주어야 하므로 동전을 내림차순으로 저장하고, 큰 동전부터 작은 동전 순서대로 동전 개수를 카운트하면 무조건 최적의 동전 개수가 나온다.

 

하지만 만약에 아래의 문제를 보자 

동전의 종류가 10원, 30원, 40원이 있을 때, 60원을 거슬러 준다고 해보자. 

그러면 처음에 40원을 거슬러주고, 20원이 남으니 10원 2개를 거슬러 줘서 총 3개의 동전을 사용할 것이다. 하지만 최적의 해는 30원 동전 2개를 거슬러 줘서 총 2개를 사용하는 것이다.

 

따라서 그리디 알고리즘이 항상 최적의 해를 찾지 못할 수 있음을 보여준다.

Code

그리디 알고리즘을 사용해도 항상 최적의 해를 반환하는 코드

import java.util.Arrays;

public class CoinChange {
    // 동전의 종류를 저장한 배열
    static int[] coins = {500, 100, 50, 10};

    // 그리디 알고리즘을 이용한 동전 거스름돈 계산 함수
    public static int getMinimumCoins(int amount) {
        int coinCount = 0;
        // 동전 배열을 순회하면서
        for (int coin : coins) {
            if (amount == 0) break;
            // 현재 동전으로 줄 수 있는 최대 개수를 계산
            coinCount += amount / coin;
            // 나머지 금액을 계산
            amount %= coin;
        }
        return coinCount;
    }

    public static void main(String[] args) {
        int amount = 1260; // 예시 금액
        int result = getMinimumCoins(amount);
        System.out.println("최소 동전 개수: " + result);
    }
}

그리디 알고리즘을 사용하면 최적의 해를 찾지 못할 수 있는 문제의 예시

import java.util.Arrays;

public class CoinChangeException {
    // 동전의 종류를 저장한 배열
    static int[] coins = {4, 3, 1};

    // 그리디 알고리즘을 이용한 동전 거스름돈 계산 함수
    public static int getMinimumCoins(int amount) {
        int coinCount = 0;
        for (int coin : coins) {
            if (amount == 0) break;
            coinCount += amount / coin;
            amount %= coin;
        }
        return coinCount;
    }

    public static void main(String[] args) {
        int amount = 6; // 예시 금액
        int result = getMinimumCoins(amount);
        System.out.println("그리디 알고리즘으로 계산한 최소 동전 개수: " + result);

        // 최적의 해답을 수동으로 확인
        int optimalCoins = 2; // 3원 2개로 6원을 거슬러 줄 수 있음
        System.out.println("최적의 해답: " + optimalCoins);
    }
}