[알고리즘] 탐욕(Greedy) 알고리즘

탐욕 알고리즘(Greedy algorithm)

탐욕 알고리즘은 문제를 해결할 때마다 그 순간 가장 최적인(가장 좋아 보이는) 선택을 하는 알고리즘 전략
전체적인 최적의 해를 보장하진 않지만 계산량을 줄이면서 근삿값 또는 국소 최적해(local optimum)를 빠르게 구할 수 있음

 

탐욕 알고리즘의 핵심 원칙

1. Greedy Choice Property (탐욕 선택 속성)
   매 순간 가장 좋아 보이는 선택이 전역 최적해(global optimum)를 만든다.
2. Optimal Substructure (최적 부분 구조)
   전체 문제의 최적 해결책은 하위 문제의 최적 해결책으로 구성된다.

---

예제 1: 동전 문제 (Coin Change Problem)

문제 설명

4720원을 500원, 100원, 50원, 1원 동전으로 가장 적은 수로 지불하시오.

• 가장 큰 동전부터 최대한 많이 사용하는 것이 그리디 전략
• 단 이 전략은 모든 경우에 항상 정답이 되는 건 아님

 

import java.util.*;

public class GreedyCoin {

    public static Map<Integer, Integer> minCoinCount(int amount, List<Integer> coinList) {
        Collections.sort(coinList, Collections.reverseOrder());

        Map<Integer, Integer> result = new LinkedHashMap<>();

        for (int coin : coinList) {
            int count = amount / coin;
            amount -= count * coin;
            result.put(coin, count);
        }

        return result;
    }

    public static void main(String[] args) {
        List<Integer> coinList = Arrays.asList(500, 100, 50, 1);
        int amount = 4720;

        Map<Integer, Integer> coinUsage = minCoinCount(amount, coinList);
        int totalCoins = coinUsage.values().stream().mapToInt(i -> i).sum();

        System.out.println("총 동전 수: " + totalCoins);
        System.out.println("세부 사용:");
        for (Map.Entry<Integer, Integer> entry : coinUsage.entrySet()) {
            System.out.println(entry.getKey() + "원: " + entry.getValue() + "개");
        }
    }
}

출력 예시

총 동전 수: 31
세부 사용:
500원: 9개
100원: 2개
50원: 0개
1원: 20개

---

예제 2: 부분 배낭 문제 (Fractional Knapsack)

문제 설명

각 물건은 `(무게 w, 가치 v)`로 구성된다.
물건을 쪼갤 수 있다면 무게 대비 가치가 높은 순서로 배낭에 담는 것이 탐욕적 전략.

 

• 무게 제한이 k인 배낭에 최대 가치를 가지도록 물건을 넣는 문제
  • 각 물건은 무게(w)와 가치(v)로 표현될 수 있음
  • 물건은 쪼갤 수 있으므로 물건의 일부분이 배낭에 넣어질 수 있음 → 그래서 Fractional Knapsack Problem으로 부름
  • Fractional Knapsack Problem의 반대로 물건을 쪼개서 넣을 수 없는 배낭 문제도 존재함(0/1 Knapsack Problem)

 

 

import java.util.*;

public class FractionalKnapsack {

    static class Item {
        int weight;
        int value;

        Item(int weight, int value) {
            this.weight = weight;
            this.value = value;
        }

        double ratio() {
            return (double) value / weight;
        }
    }

    public static double getMaxValue(List<Item> items, int capacity) {
        items.sort((a, b) -> Double.compare(b.ratio(), a.ratio()));

        double totalValue = 0.0;

        for (Item item : items) {
            if (capacity >= item.weight) {
                capacity -= item.weight;
                totalValue += item.value;
                System.out.println("담은 물건: " + item.weight + "kg / " + item.value + "원 (100%)");
            } else {
                double fraction = (double) capacity / item.weight;
                totalValue += item.value * fraction;
                System.out.println("담은 물건: " + item.weight + "kg / " + item.value + "원 (" + (int)(fraction * 100) + "%)");
                break;
            }
        }

        return totalValue;
    }

    public static void main(String[] args) {
        List<Item> items = Arrays.asList(
            new Item(10, 10),
            new Item(15, 12),
            new Item(20, 10),
            new Item(25, 8),
            new Item(30, 5)
        );

        int capacity = 30;
        double maxValue = getMaxValue(items, capacity);

        System.out.println("총 얻은 가치: " + maxValue);
    }
}

 

출력 예시

담은 물건: 10kg / 10원 (100%)
담은 물건: 15kg / 12원 (100%)
담은 물건: 20kg / 10원 (25%)
총 얻은 가치: 24.5

---

탐욕 알고리즘의 한계

• 항상 최적해(optimal solution)를 보장하지 않음
• 직전 단계만 고려하므로 전체 구조를 보지 못해 실패할 수 있음

 

잘못된 예시

예시

• '시작' 노드에서 시작해서 가장 작은 값을 찾아 leaf node까지 가는 경로를 찾을 시에,
  • Greedy 알고리즘 적용시 시작 → 7 → 12 를 선택하게 되므로 7 + 12 = 19가 됨 
  • 하지만 실제 가장 작은 값은 시작 → 10 → 5 이며 10 + 5 = 15 가 답

 

탐욕 알고리즘 요약

항목	설명
전략	매 단계에서 가장 좋아 보이는 해를 선택
시간 복잡도	일반적으로 O(n log n) 또는 O(n) (정렬이 포함되는 경우)
활용 예시	동전 거스름돈, 부분 배낭, 활동 선택 문제, 허프만 코딩 등
단점	전역 최적 보장 불가, 일부 문제는 DP로 해결해야 함