탐욕 알고리즘(Greedy Algorithm) 개념 및 예제

탐욕 알고리즘(Greedy Algorithm)은 문제 해결 과정에서 현재 상황에서 가장 최적인 선택을 반복함으로써 전체적인 해답을 구하는 방식입니다. 이러한 방식은 대개 최적해를 보장하지 않지만, 특정한 조건 하에서는 최적해를 보장할 수 있습니다. 탐욕 알고리즘은 빠르고 구현이 비교적 간단하기 때문에 다양한 문제에서 사용됩니다.

탐욕 알고리즘이 성공적으로 문제를 해결하기 위해서는 문제 자체가 탐욕적 선택 속성(Greedy Choice Property) 과 최적 부분 구조(Opitmal Substructure) 를 가져야 합니다. 간단히 말해, 탐욕적 선택 속성은 각 단계에서의 최적 선택이 전체 문제에 대한 최적 해결로 이어져야 함을 의미하며, 최적 부분 구조는 부분 문제의 최적해가 전체 문제의 최적해에 기여한다는 것을 의미합니다.

탐욕 알고리즘은 다음과 같은 단계로 문제를 해결합니다:

1. 현재 상태에서 가장 최적인 선택을 합니다.
2. 선택에 따라 상태가 변경됩니다.
3. 모든 선택이 완료될 때까지 반복합니다.

대표적인 탐욕 알고리즘의 예로는 활동 선택 문제(Activity Selection Problem), 동전 교환 문제(Coin Change Problem), 크루스칼 알고리즘(Kruskal's Algorithm) 등이 있습니다. 이번 포스트에서는 탐욕 알고리즘의 개념을 설명하고, 가장 간단한 동전 교환 문제를 예제로 사용하여 탐욕 알고리즘을 Java와 C로 구현해 보겠습니다.

동전 교환 문제 예제

문제 설명

동전 교환 문제는 주어진 금액을 최소한의 동전으로 거슬러 주는 문제입니다. 예를 들어, 1원, 5원, 10원, 50원, 100원 동전이 있을 때 126원을 최소한의 동전으로 교환하려면 어떻게 해야 할까요?

탐욕 알고리즘은 각 단계에서 가장 큰 단위의 동전을 선택하는 방식으로 문제를 해결합니다. 이러한 방식으로 각 단계를 선택하면 전체 금액을 최소한의 동전으로 거슬러 줄 수 있습니다.

Java 구현

import java.util.HashMap;
import java.util.Map;

public class CoinChange {
    public static void main(String[] args) {
        int[] coins = {100, 50, 10, 5, 1};
        int amount = 126;
        Map<Integer, Integer> result = getMinCoins(coins, amount);

        System.out.println("동전 교환 결과:");
        for (Map.Entry<Integer, Integer> entry : result.entrySet()) {
            if (entry.getValue() > 0) {
                System.out.println(entry.getKey() + "원 동전: " + entry.getValue() + "개");
            }
        }
    }

    public static Map<Integer, Integer> getMinCoins(int[] coins, int amount) {
        Map<Integer, Integer> coinCount = new HashMap<>();

        for (int coin : coins) {
            int count = amount / coin;
            amount %= coin;
            coinCount.put(coin, count);
        }

        return coinCount;
    }
}

위의 Java 코드는 주어진 금액을 최소한의 동전으로 거슬러 주기 위해 가장 큰 단위의 동전부터 차례로 선택합니다. getMinCoins 함수는 각 동전의 개수를 계산하여 HashMap에 저장하고 이를 반환합니다.

C 구현

#include <stdio.h>

void getMinCoins(int coins[], int size, int amount) {
    printf("동전 교환 결과:\n");
    for (int i = 0; i < size; i++) {
        int count = amount / coins[i];
        amount %= coins[i];
        if (count > 0) {
            printf("%d원 동전: %d개\n", coins[i], count);
        }
    }
}

int main() {
    int coins[] = {100, 50, 10, 5, 1};
    int amount = 126;
    int size = sizeof(coins) / sizeof(coins[0]);

    getMinCoins(coins, size, amount);
    return 0;
}

위의 C 코드는 Java 구현과 유사하게, 주어진 금액을 최소한의 동전으로 교환하기 위해 가장 큰 단위의 동전부터 선택합니다. getMinCoins 함수는 각 동전의 개수를 계산하여 출력합니다.

탐욕 알고리즘의 한계

탐욕 알고리즘은 문제를 빠르게 해결할 수 있지만 항상 최적해를 보장하지는 않습니다. 동전 교환 문제의 경우, 동전 단위가 1원, 5원, 10원, 50원, 100원과 같이 잘 정의되어 있을 때는 탐욕 알고리즘으로 최적해를 얻을 수 있지만, 예를 들어 동전 단위가 1원, 7원, 10원인 경우 14원을 거슬러 줄 때 탐욕 알고리즘은 10원 + 1원 + 1원 + 1원 + 1원을 선택하여 최적해(7원 2개)와 다른 결과를 도출할 수 있습니다.

탐욕 알고리즘의 성능은 문제의 특성에 크게 의존하므로, 항상 탐욕적인 접근 방식이 최적해를 보장하는 것은 아닙니다. 탐욕 알고리즘을 사용할 때는 문제에 탐욕적 선택 속성과 최적 부분 구조가 있는지를 고려해야 합니다.

결론

탐욕 알고리즘은 각 단계에서 가장 최적인 선택을 하여 문제를 해결하는 방식입니다. 이 방식은 간단하고 빠르게 문제를 해결할 수 있어 다양한 문제에서 유용하게 사용됩니다. 이번 포스트에서는 동전 교환 문제를 Java와 C 언어로 구현해 보았습니다. 동전 교환 문제는 탐욕 알고리즘을 사용하여 최적해를 얻을 수 있는 대표적인 예제입니다.

하지만 탐욕 알고리즘은 항상 최적해를 보장하지 않기 때문에, 문제의 특성을 충분히 분석한 후 적절히 적용해야 합니다. 탐욕 알고리즘이 잘 적용될 수 있는 문제에 한해서는 단순하고 효율적인 해결책을 제공할 수 있습니다.

탐욕 알고리즘의 기본적인 아이디어를 잘 이해하고 다양한 예제를 통해 익혀 나가면서 더욱 복잡한 문제에도 적용해 보세요.