---
title: "그리디: 가장 빨리 끝나는 구간 선택을 교환 논증으로 증명하기"
slug: "java-greedy"
category: "CS"
topic: "cs"
subtopic: "algorithms"
tags: ["Java","Greedy","Interval Scheduling","Exchange Argument","Counterexample"]
status: "published"
created: "2026-08-06"
updated: "2026-08-06"
summary: "활동 선택 문제에서 종료 시간이 가장 이른 선택이 최적인 이유를 교환 논증으로 증명하고, 동전 반례로 지역 최선의 적용 한계와 Java 정렬·메모리 비용을 확인한다."
kind: "Deep Dive"
evidence: "MIT 6.046J greedy 강의 자료·Princeton Algorithms 자료·Java SE 21 Comparator/Arrays API를 대조하고 GreedyDemo를 OpenJDK 21.0.11에서 실행"
series: "Java Essential Algorithms"
---

그리디는 “지금 좋아 보이는 것을 고른다”가 아니다. 현재 선택을 포함하는 최적해로 다른 최적해를 **교환해도 손해가 없다는 증명**이 있어야 한다. 증명 없는 그리디는 heuristic이며, 정답 보장이 필요한 API에서는 이름을 구분해야 한다.

## 1. 문제 계약: 최대 개수의 겹치지 않는 interval

각 interval은 `[start,end)`로 해석한다. 이전 interval의 end와 다음 start가 같으면 양립한다. 목표는 동시에 겹치지 않게 선택 가능한 interval **개수**를 최대로 만드는 것이다. duration 합이나 priority 합 최대화가 아니다.

입력 list를 변경하지 않고 copy를 종료 시간 오름차순, 동률이면 시작 시간 오름차순으로 정렬한다. 잘못된 `start>end`와 null id는 거절한다. 빈 입력의 답은 빈 list다.

## 2. 왜 가장 빨리 끝나는 것을 고르는가

예제 interval은 A `[1,4)`, B `[3,5)`, C `[0,6)`, D `[5,7)`, E `[8,9)`, F `[5,9)`다.

| 정렬 후보 | 마지막 end | 선택 여부 | 이유 | 선택 결과 |
| --- | ---: | --- | --- | --- |
| A `[1,4)` | $-\infty$ | 선택 | 가장 빨리 종료 | A |
| B `[3,5)` | 4 | 제외 | 3 < 4 | A |
| C `[0,6)` | 4 | 제외 | 0 < 4 | A |
| D `[5,7)` | 4 | 선택 | 5 >= 4 | A,D |
| E `[8,9)` | 7 | 선택 | 8 >= 7 | A,D,E |
| F `[5,9)` | 9 | 제외 | 5 < 9 | A,D,E |

**불변식:** scan 시점에 selected는 처리한 prefix에서 양립 가능하고, 마지막 종료 시간이 가장 이른 형태의 최대 개수 선택으로 교환 가능하다.

## 3. 교환 논증

가장 빨리 끝나는 interval을 $g$라 하고 어떤 최적해의 첫 interval을 $o$라 하자. 정의상 `end(g) <= end(o)`다. 최적해에서 o를 g로 바꾸면 뒤의 interval들은 o 이후에 시작했으므로 더 늦지 않게 끝나는 g와도 양립한다. 선택 개수는 줄지 않는다.

따라서 g를 포함하는 최적해가 존재한다. g와 겹치는 interval을 제거한 나머지 문제에 같은 논리를 반복하면 algorithm 전체가 최적이다. 이 증명은 목적이 “개수 최대화”일 때만 성립한다. weight가 붙은 interval scheduling은 DP가 필요하다.

## 실행 재현

아래 코드는 설명용 조각이 아니라 `main`에 정상·빈 입력·중복·경계·실패 계약을 함께 넣은 완전한 Java 21 프로그램이다.

```java
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public final class GreedyDemo {
    record Interval(String id, int start, int end) {
        Interval {
            if (id == null || start > end) throw new IllegalArgumentException("invalid interval");
        }
    }

    static List<Interval> maximumCompatible(List<Interval> input) {
        if (input == null) throw new IllegalArgumentException("input must not be null");
        List<Interval> sorted = new ArrayList<>(input);
        sorted.sort(Comparator.comparingInt(Interval::end).thenComparingInt(Interval::start));
        List<Interval> selected = new ArrayList<>();
        int lastEnd = Integer.MIN_VALUE;
        for (Interval interval : sorted) {
            if (interval.start() >= lastEnd) {
                selected.add(interval);
                lastEnd = interval.end();
            }
        }
        return List.copyOf(selected);
    }

    static int greedyCoinCount(int[] descendingCoins, int amount) {
        int count = 0;
        for (int coin : descendingCoins) {
            count += amount / coin;
            amount %= coin;
        }
        return amount == 0 ? count : -1;
    }

    static void check(boolean condition, String message) {
        if (!condition) throw new AssertionError(message);
    }

    public static void main(String[] args) {
        List<Interval> selected = maximumCompatible(List.of(
                new Interval("A", 1, 4), new Interval("B", 3, 5),
                new Interval("C", 0, 6), new Interval("D", 5, 7),
                new Interval("E", 8, 9), new Interval("F", 5, 9)));
        check(selected.stream().map(Interval::id).toList().equals(List.of("A", "D", "E")), "optimal schedule");
        check(maximumCompatible(List.of()).isEmpty(), "empty");
        check(greedyCoinCount(new int[] {4, 3, 1}, 6) == 3, "greedy counterexample: 4+1+1");
        System.out.println("selected=[A, D, E], non-canonical coin greedy(6)=3 (optimum=2)");
    }
}
```

```bash
javac --release 21 GreedyDemo.java
java GreedyDemo
```

직접 실행한 출력은 다음과 같다.

```text
selected=[A, D, E], non-canonical coin greedy(6)=3 (optimum=2)
```

컴파일러와 런타임은 `javac 21.0.11`, OpenJDK `21.0.11`을 사용했다. `assert` 옵션에 의존하지 않고 실패 시 `AssertionError`를 던지므로 위 명령 그대로 검증된다.


## 4. 동전 문제 최소 반례로 한계를 본다

동전 `[4,3,1]`로 6을 만들 때 가장 큰 동전부터 고르면 `4+1+1`, 3개다. 최적은 `3+3`, 2개다. 지역에서 금액을 가장 많이 줄이는 선택을 최적해로 교환할 근거가 없다.

일부 canonical coin system에서는 큰 동전 우선이 맞지만, 임의 denomination에 일반화할 수 없다. 구현 예제가 특정 화폐에서 통과했다는 사실은 증명이 아니다.

## 5. 시간·공간 복잡도

정렬이 $O(n\log n)$, 한 번 scan이 $O(n)$이므로 전체는 $O(n\log n)$이다. 이미 종료 시간으로 정렬돼 있다는 계약이면 scan만 $O(n)$이다. copy list와 selected output이 $O(n)$ reference 공간을 쓴다. output 자체를 보조 공간에서 분리하면 정렬 copy $O(n)$, 결과 $O(k)$다.

Java `ArrayList<>(input)`은 backing array를 새로 만들고 reference를 복사한다. interval record는 재사용하므로 객체를 깊은 복사하지 않는다. comparator chain은 primitive `comparingInt`를 사용해 key boxing을 피한다.

## 6. JVM과 정렬 계약

input/copy/selected list와 backing arrays, Interval records는 heap에 있다. loop locals는 frame 관점이다. object list 정렬은 comparator 호출이 많으므로 comparator 안에서 parsing/I/O/allocation을 하지 않는다. 동률 규칙이 결과 결정성에 영향을 주므로 `thenComparingInt`를 명시했다.

동일 end/start/id 중 어떤 것을 반환해야 하는지 business contract가 더 엄격하면 최종 tie-breaker를 추가한다. 최대 개수만 같다고 결과가 운영적으로 같은 것은 아니다.

## 7. DP·brute force·heuristic과 비교

| 문제 | 선택 | 근거 |
| --- | --- | --- |
| unweighted interval count | earliest-finish greedy | exchange argument |
| weighted interval value | DP + predecessor search | local 교환 불가 |
| 임의 coin 최소 개수 | DP/shortest path | 큰 coin 반례 |
| NP-hard 근사 | heuristic/approximation | 보장 비율을 별도 증명 |

그리디와 DP는 반대가 아니다. 동일 문제에서 greedy-choice property가 증명되면 상태를 저장하지 않고 선택할 수 있고, 그렇지 않지만 optimal substructure가 있으면 DP로 더 많은 상태를 비교한다.

## 8. 실제 도메인 적용

단일 회의실 예약 수 최대화, maintenance slot 선택, non-overlapping batch window에 적용할 수 있다. 그러나 실제 scheduler에는 priority, cancellation, setup time, 여러 resource가 있어 문제 계약이 달라진다. 관측 지표는 accepted count, utilization, starvation, reschedule rate, objective gap이다. business weight를 무시한 “최대 건수”가 고객 가치 최대와 같다고 가정하지 않는다.

## 9. 이건 피한다

- **지역 최선이면 전체 최선이라 선언한다.** 교환 논증이나 cut property가 없으면 오답이다. 최소 반례를 찾고 DP/brute force와 작은 입력에서 대조한다.
- **목적 함수를 바꿔도 같은 greedy를 쓴다.** 개수 최대와 가치 최대는 다르다. weighted interval은 DP를 검토한다.
- **입력 정렬 비용을 빼고 $O(n)$이라 쓴다.** 사전 정렬 계약이 없다면 전체는 $O(n\log n)$이다.
- **동률 규칙을 생략한다.** 최대 개수는 같아도 결과가 실행마다 흔들릴 수 있다. deterministic tie-breaker를 둔다.
- **실패해도 근사라고 얼버무린다.** approximation ratio 증명 없는 heuristic이다. 보장 수준을 정확히 표기한다.

## Reference

- MIT OpenCourseWare, [6.046J Design and Analysis of Algorithms — Greedy Algorithms lecture notes](https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2015/pages/lecture-notes/)
- Oracle, [Comparator — Java SE 21 API](https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/Comparator.html)
- Oracle, [List — Java SE 21 API](https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/List.html)
- Robert Sedgewick, Kevin Wayne, [Algorithms, 4th Edition](https://algs4.cs.princeton.edu/home/)
- Oracle, [The Java Virtual Machine Specification, Java SE 21 — Heap and Frames](https://docs.oracle.com/javase/specs/jvms/se21/html/jvms-2.html#jvms-2.5)