[알고리즘 & 문제 해결 패턴] 탐욕 알고리즘(Greedy) 원리 및 활용 사례

[알고리즘] 탐욕 알고리즘(Greedy) 원리 및 활용 사례

1. 탐욕 알고리즘(Greedy)이란?

탐욕 알고리즘(Greedy Algorithm)은

**각 단계에서 최적이라고 판단되는 선택을 반복하여 최종 해답을 찾는 방식**의 알고리즘입니다.

일반적으로 전체 최적해를 구하는 것이 아닌,

각 단계에서 가장 좋은 선택을 했을 때 최적해를 구할 수 있는 경우에 효과적입니다.

2. 탐욕 알고리즘의 특징

• ✔ **지역 최적해(Local Optimal Choice)를 선택하여 전체 최적해(Global Optimal Solution)를 찾음**
• ✔ 항상 최적해를 보장하지는 않지만, **근사 최적해(Approximate Solution)**를 빠르게 구할 수 있음
• ✔ DP(Dynamic Programming)와 다르게, **과거의 선택을 저장하지 않음**

3. 탐욕 알고리즘이 적용 가능한 조건

조건	설명
탐욕 선택 속성(Greedy Choice Property)	각 단계에서 최적의 선택이 전체 최적해를 보장할 수 있어야 함
최적 부분 구조(Optimal Substructure)	문제를 작은 부분 문제로 나누었을 때, 각 부분 문제의 최적해가 전체 문제의 최적해를 구성해야 함

4. 탐욕 알고리즘 예제: 동전 거스름돈 문제

가장 적은 수의 동전으로 거스름돈을 줄 때, 탐욕적 선택을 적용해볼 수 있습니다.

🔹 **비효율적인 방식 (완전 탐색)**

import java.util.*;

public class CoinChangeBruteForce {
    public static int minCoins(int amount, int[] coins) {
        Arrays.sort(coins); // 동전 정렬
        int count = 0;
        for (int i = coins.length - 1; i >= 0; i--) {
            while (amount >= coins[i]) {
                amount -= coins[i];
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[] coins = {1, 5, 10, 50, 100, 500};
        int amount = 1260;
        System.out.println("최소 동전 개수: " + minCoins(amount, coins)); // 출력: 6
    }
}

 

✅ **문제점:**

- 항상 최적해를 보장하는 것은 아님

- 일부 화폐 단위에서는 그리디 방식이 최적해를 찾지 못할 수도 있음

5. 탐욕 알고리즘 예제: 활동 선택 문제(Activity Selection)

여러 개의 회의가 있을 때, 겹치지 않도록 최대한 많은 회의를 배정하는 문제입니다.

🔹 **탐욕적 선택 방식 (시작 시간 기준 정렬 후 선택)**

import java.util.*;

class Meeting {
    int start, end;
    public Meeting(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

public class ActivitySelection {
    public static int maxMeetings(List meetings) {
        meetings.sort(Comparator.comparingInt(m -> m.end)); // 종료 시간 기준 정렬
        int count = 0, lastEnd = 0;

        for (Meeting meeting : meetings) {
            if (meeting.start >= lastEnd) {
                count++;
                lastEnd = meeting.end;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        List meetings = Arrays.asList(new Meeting(1, 3), new Meeting(2, 5), new Meeting(3, 9), new Meeting(6, 8));
        System.out.println("최대 회의 개수: " + maxMeetings(meetings)); // 출력: 2
    }
}

 

✅ **핵심 로직:**

- 종료 시간이 가장 빠른 회의를 먼저 선택

- 다음 회의의 시작 시간이 현재 회의의 종료 시간 이후라면 선택

6. 탐욕 알고리즘이 효과적인 문제 유형

문제 유형	설명	예제
최소 동전 거스름돈	최소한의 동전으로 특정 금액을 거슬러 주기	coinChange()
활동 선택 문제	회의 일정 중 가장 많은 회의 배정	activitySelection()
크루스칼 알고리즘	최소 신장 트리(MST) 구하기	kruskalMST()
다익스트라 알고리즘	최단 경로 찾기	dijkstra()

📌 정리

• ✔ 탐욕 알고리즘은 **각 단계에서 최선의 선택을 반복**하여 해를 구하는 방식
• ✔ 항상 최적해를 보장하지는 않지만, **빠른 근사해(Approximate Solution) 구할 때 유용**
• ✔ 대표적인 문제: **거스름돈 문제, 회의 배정 문제, 최소 신장 트리(MST), 최단 경로(Dijkstra)**
• ✔ **탐욕적 접근이 항상 최적해를 보장하는지 확인하는 것이 중요**

---

🔗 다른 알고리즘 관련 글도 함께 확인해보세요!

다이나믹 프로그래밍(DP) 개념과 대표 문제 풀이