자료구조 · 알고리즘 기초집LESSON 21

그리디 알고리즘: 지금의 최선이 전체 해가 되는 조건

난이도초급 → 중급 입문

예상 시간40분

선수지식이전 강의

21강. 그리디 알고리즘: 지금의 최선이 전체 해가 되는 조건

1. 이번 강의에서 해결할 문제

서로 시간이 겹치는 이벤트 중 가장 많은 이벤트에 참여하려면 당장 보상이 큰 이벤트를 고르는 직관이 전체 최적해를 보장하지 않습니다.

2. 학습 목표

3. 핵심 개념

그리디는 매 단계에서 되돌리지 않고 지역적으로 가장 좋아 보이는 선택을 합니다. 정답이 되려면 그 선택을 포함하는 최적해가 항상 존재함을 보여야 합니다. 활동 선택에서는 가장 빨리 끝나는 이벤트를 고르면 남은 시간 구간을 가장 크게 보존합니다. 보상 합 최대화처럼 목표가 바뀌면 같은 규칙은 실패할 수 있습니다.

4. 단계별 실습

1. 예제 파일 작성

실행 환경: 코드 편집기

실행 위치: C:\dev\game-ranking-algorithms

실행 전 확인: 같은 이름의 파일이 있다면 덮어쓰기 전에 Git diff로 변경 범위를 확인합니다. 선택한 LTS JDK의 java -version과 javac -version이 모두 실행되어야 합니다.

대상 파일: src/GreedyEvents.java

src/GreedyEvents.java
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class GreedyEvents {
    record Event(String name, int start, int end) {}

    static List<Event> selectMost(List<Event> events) {
        List<Event> sorted = new ArrayList<>(events);
        sorted.sort(Comparator.comparingInt(Event::end).thenComparingInt(Event::start));
        List<Event> selected = new ArrayList<>();
        int lastEnd = Integer.MIN_VALUE;
        for (Event event : sorted) {
            if (event.start() >= lastEnd) {
                selected.add(event);
                lastEnd = event.end();
            }
        }
        return selected;
    }

    public static void main(String[] args) {
        List<Event> events = List.of(new Event("A", 1, 4), new Event("B", 3, 5),
                new Event("C", 4, 7), new Event("D", 7, 8));
        System.out.println(selectMost(events));
    }
}

2. PowerShell에서 컴파일·실행

실행 환경: Windows PowerShell

실행 위치: C:\dev\game-ranking-algorithms

실행 전 확인: src/GreedyEvents.java가 저장되었고 out 폴더에는 삭제해도 되는 컴파일 결과만 있는지 확인합니다.

대상: src/GreedyEvents.java와 out 아래 생성되는 class 파일

Windows PowerShell
Set-Location C:\dev\game-ranking-algorithms
New-Item -ItemType Directory -Force .\out | Out-Null
javac -Xlint:all -d .\out .\src\GreedyEvents.java
java -cp .\out GreedyEvents

예상 결과: 종료가 빠르고 겹치지 않는 A, C, D 세 이벤트가 출력됩니다.

실행 시간은 PC의 CPU·메모리, JDK 버전, JVM 워밍업, 백그라운드 작업과 입력 분포에 따라 달라질 수 있습니다. 측정값은 같은 조건에서 여러 번 비교하고 Big-O 분석과 함께 해석합니다.

5. 코드와 알고리즘이 동작하는 이유

가장 빨리 끝나는 이벤트 대신 다른 첫 이벤트가 있는 최적해도 첫 선택을 더 빠른 이벤트로 교환하면 이후 선택 가능성을 줄이지 않습니다. 정렬 O(n log n), 한 번 선택 O(n), 결과 O(n) 공간입니다.

6. 자주 하는 실수와 해결법

7. 직접 실습

8. 이해 점검 질문 3개

9. 핵심 요약

MINI QUIZ