그리디 알고리즘

1. 그리디 알고리즘 (Greedy Algorithm)

매 순간 가장 최선(최적)이라고 판단되는 선택을 하고,

그 선택이 전체적으로도 최선이 되도록 하는 알고리즘.

💡 사용 조건

• "지금 당장 좋은 선택이, 미래에도 나쁜 결과를 만들지 않는 경우"
• *"국지적 최적해 → 전체 최적해"**가 보장될 수 있어야 함

🧠 적용 예시

1. 동전 거스름돈 문제 (단위가 잘 구성돼 있을 때)

2. 회의실 배정 문제 (빨리 끝나는 회의부터 잡기)

3. 최소 신장 트리(MST): 크루스칼, 프림 알고리즘

4. 이 문제 (숫자 게임 최대 승점)

   → "이길 수 있을 때는 최소한으로 이기고, 못 이기면 포기"

🕒 시간 복잡도

• 대부분 정렬이 선행되므로 O(N log N)
• 이후에는 한 번 순회 → O(N)

✅ 언제 쓰면 좋은가?

• "매 단계에서 결정이 미래의 상황에 영향을 안 미칠 때"
• "최적해 조건이 증명돼 있을 때"
• 선형적 선택만으로도 목표에 도달 가능한 구조

---

그리디 알고리즘 예제: 회의실 배정 문제

🔹 문제 설명

N개의 회의가 있을 때, 회의 시간이 겹치지 않도록 하면서

최대한 많은 회의를 배정하라.

각 회의는 시작 시간과 종료 시간으로 주어진다.

(회의가 끝나는 시간이 빠를수록 유리)

🔸 Java 코드

java
복사편집
import java.util.*;

class Meeting implements Comparable<Meeting> {
    int start, end;

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

    @Override
    public int compareTo(Meeting o) {
        if (this.end == o.end) return this.start - o.start;
        return this.end - o.end;
    }
}

public class GreedyMeeting {
    public static void main(String[] args) {
        List<Meeting> meetings = Arrays.asList(
            new Meeting(1, 4),
            new Meeting(3, 5),
            new Meeting(0, 6),
            new Meeting(5, 7),
            new Meeting(3, 8),
            new Meeting(5, 9),
            new Meeting(6, 10),
            new Meeting(8, 11),
            new Meeting(8, 12),
            new Meeting(2, 13),
            new Meeting(12, 14)
        );

        Collections.sort(meetings); // 종료시간 기준 정렬

        int count = 0;
        int endTime = 0;

        for (Meeting m : meetings) {
            if (m.start >= endTime) {
                endTime = m.end;
                count++;
            }
        }

        System.out.println("최대 회의 수: " + count);
    }
}

🔹 결과

최대 회의 수: 4