그리디, 빠르게 고르지만 신중해야 하는 이유

그리디 알고리즘

이번에는 코딩테스트에서 자주 나오는 그리디 알고리즘에 대해 공부했다.

그리디는 이름부터 조금 낯설었다.
영어로 Greedy는 “탐욕스러운”이라는 뜻인데, 알고리즘에서는 매 순간 가장 좋아 보이는 선택을 하는 방법을 의미한다.

처음에는 “그냥 제일 큰 값이나 제일 작은 값을 고르면 되는 건가?”라고 생각했는데, 공부해보니 그렇게 단순하게만 볼 문제는 아니었다.
그리디에서 중요한 것은 지금 선택한 것이 나중에도 손해가 되지 않는지 확인하는 것이다.

---

그리디 알고리즘이란?

그리디 알고리즘은 현재 상황에서 가장 좋아 보이는 선택을 반복해서 답을 구하는 방식이다.

쉽게 말하면 이런 느낌이다.

지금 가장 좋아 보이는 선택을 한다.
그 선택을 반복한다.
최종적으로 답을 구한다.

예를 들어 거스름돈을 줄 때를 생각해볼 수 있다.

760원을 거슬러줘야 하고, 동전이 다음과 같이 있다고 하자.

500원, 100원, 50원, 10원

가장 적은 동전 개수로 거슬러주려면 보통 큰 동전부터 사용하면 된다.

760원
→ 500원 1개 사용, 남은 금액 260원
→ 100원 2개 사용, 남은 금액 60원
→ 50원 1개 사용, 남은 금액 10원
→ 10원 1개 사용, 남은 금액 0원

정리하면 다음과 같다.

동전개수

500원	1개
100원	2개
50원	1개
10원	1개
총합	5개

이 경우에는 매번 가장 큰 동전을 고르는 선택이 최적의 결과로 이어진다.
이런 방식이 그리디 알고리즘이다.

---

그리디의 핵심은 “지금 이 선택을 해도 괜찮은가?”이다

그리디는 현재 상황에서 가장 좋아 보이는 것을 고른다.
하지만 여기서 주의해야 할 점이 있다.

지금 가장 좋아 보이는 선택이 항상 전체 정답을 보장하지는 않는다.

예를 들어 동전이 이렇게 있다고 해보자.

500원, 400원, 100원

800원을 거슬러줘야 한다면, 가장 큰 동전부터 고르는 그리디 방식은 이렇게 된다.

500원 선택
남은 금액 300원
100원 3개 선택
총 4개

하지만 실제로는 이렇게 하는 것이 더 좋다.

400원 + 400원 = 총 2개

이 예시를 보면, 무조건 가장 큰 것을 고르는 방식이 항상 정답은 아니라는 것을 알 수 있다.

그래서 그리디 문제에서는 단순히 “큰 것부터 고르자”가 아니라,
그 선택이 전체적으로도 최선이 되는지를 생각해야 한다.

---

그리디가 잘 맞는 문제 유형

그리디는 보통 최댓값, 최솟값, 최소 개수, 최대 개수 같은 문제에서 자주 등장한다.

문제 유형그리디 접근 예시

거스름돈	가장 큰 동전부터 사용
회의실 배정	가장 빨리 끝나는 회의부터 선택
체육복	빌려줄 수 있는 학생에게 바로 빌려주기
구명보트	가장 무거운 사람과 가장 가벼운 사람을 함께 태울 수 있는지 확인
큰 수 만들기	앞자리부터 큰 숫자가 오도록 선택
단속카메라	차량이 나가는 지점 기준으로 카메라 설치

문제에서 이런 표현이 나오면 그리디를 의심해볼 수 있다.

최소 개수
최대 개수
가장 적은 비용
가장 큰 값
가장 빨리 끝나는 것
현재 선택을 반복하는 구조

다만 이런 표현이 있다고 해서 무조건 그리디는 아니다.
현재 선택이 정말 전체 최적해로 이어지는지 확인해야 한다.

---

그리디와 완전탐색의 차이

완전탐색은 가능한 모든 경우를 다 확인한다.

모든 경우를 다 해보고 가장 좋은 답을 찾는다.

반면 그리디는 모든 경우를 확인하지 않는다.
현재 상황에서 가장 좋아 보이는 선택을 하고, 그 선택을 반복한다.

구분완전탐색그리디

방식	모든 경우 확인	현재 최선의 선택
장점	정답을 찾을 가능성이 높음	빠르게 풀 수 있음
단점	경우의 수가 많으면 느림	항상 정답을 보장하지 않음
핵심 질문	모든 경우를 확인할 수 있는가?	지금 선택해도 나중에 손해가 없는가?

완전탐색은 안전하지만 느릴 수 있고,
그리디는 빠르지만 잘못된 선택 기준을 잡으면 틀릴 수 있다.

---

그리디 문제는 정렬과 함께 자주 나온다

그리디 문제를 풀다 보면 정렬이 같이 나오는 경우가 많다.

왜냐하면 “무엇을 먼저 선택할 것인가”를 정해야 하기 때문이다.

예를 들어 회의실 배정 문제를 생각해보자.

회의가 여러 개 있고, 겹치지 않게 최대한 많은 회의를 선택해야 한다면 어떤 기준으로 골라야 할까?

처음에는 빨리 시작하는 회의부터 고르면 될 것 같지만, 실제로는 빨리 끝나는 회의를 먼저 고르는 것이 중요하다.

빨리 끝나는 회의를 선택해야 뒤에 더 많은 회의를 넣을 수 있기 때문이다.

많은 회의를 선택하고 싶다
→ 회의가 빨리 끝날수록 남은 시간이 많다
→ 종료 시간이 빠른 회의부터 선택한다

이처럼 그리디 문제에서는 정렬 기준을 잘 잡는 것이 중요하다.

---

예시: 회의실 배정 문제

다음과 같은 회의들이 있다고 하자.

회의시작 시간종료 시간

A	1	4
B	3	5
C	0	6
D	5	7
E	8	9

최대한 많은 회의를 선택하려면 종료 시간이 빠른 순서대로 정렬한 뒤,
현재 회의가 이전 회의의 종료 시간 이후에 시작한다면 선택하면 된다.

풀이 흐름은 다음과 같다.

1. 종료 시간이 빠른 순서로 정렬한다.
2. 이전에 선택한 회의의 종료 시간을 저장한다.
3. 현재 회의의 시작 시간이 이전 종료 시간보다 크거나 같으면 선택한다.
4. 선택했다면 종료 시간을 갱신한다.

Java 코드로 쓰면 다음과 같다.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[][] meetings = {
            {1, 4},
            {3, 5},
            {0, 6},
            {5, 7},
            {8, 9}
        };

        Arrays.sort(meetings, (a, b) -> Integer.compare(a[1], b[1]));

        int count = 0;
        int endTime = 0;

        for (int[] meeting : meetings) {
            int start = meeting[0];
            int end = meeting[1];

            if (start >= endTime) {
                count++;
                endTime = end;
            }
        }

        System.out.println(count);
    }
}

여기서 핵심은 이 부분이다.

Arrays.sort(meetings, (a, b) -> Integer.compare(a[1], b[1]));

회의를 시작 시간 기준이 아니라 종료 시간 기준으로 정렬한다.
이 선택 기준이 그리디 풀이의 핵심이다.

---

그리디 문제에서 자주 하는 실수

그리디 문제를 풀 때 가장 조심해야 할 점은 선택 기준을 잘못 잡는 것이다.

1. 무조건 큰 것부터 고르는 실수

그리디라고 해서 항상 큰 값을 고르는 것은 아니다.

문제에 따라 선택 기준은 달라진다.

가장 큰 값
가장 작은 값
가장 빨리 끝나는 값
가장 손해가 적은 값

즉, “무엇이 가장 좋은 선택인가”를 문제에 맞게 다시 정의해야 한다.

---

2. 정렬 기준을 잘못 잡는 실수

회의실 배정 문제에서 시작 시간 기준으로 정렬하면 틀릴 수 있다.
이 문제에서는 종료 시간 기준으로 정렬해야 한다.

그리디 문제는 정렬 기준 하나가 풀이 전체를 결정하는 경우가 많다.

---

3. 반례를 확인하지 않는 실수

그리디는 반례 하나만 있어도 틀린 풀이가 된다.

그래서 풀이를 정한 뒤에는 이렇게 생각해봐야 한다.

이 방식이 항상 맞을까?
틀리는 예시는 없을까?

앞에서 본 동전 예시처럼, 지금 가장 좋아 보이는 선택이 나중에 손해가 될 수도 있다.

---

그리디와 DP의 차이

그리디와 DP는 둘 다 최적의 답을 찾는 문제에서 자주 나온다.
하지만 접근 방식은 다르다.

구분	그리디	DP
선택 방식	지금 가장 좋아 보이는 선택	이전 답을 저장해서 현재 답 계산
계산 방식	한 번 선택하면 보통 되돌리지 않음	작은 문제의 답을 재사용
핵심 질문	지금 선택이 전체 최적해로 이어지는가?	이전 답으로 현재 답을 만들 수 있는가?
예시	회의실 배정, 거스름돈	계단 오르기, 정수 삼각형

쉽게 정리하면 다음과 같다.

그리디 = 지금 제일 좋아 보이는 것을 고른다.
DP = 이전에 구한 답을 저장해서 다시 쓴다.

그리디는 선택을 반복하는 느낌이고,
DP는 값을 저장하면서 쌓아가는 느낌이다.

---

그리디 문제를 풀 때 체크할 것

앞으로 그리디 문제를 풀 때는 아래 순서로 생각해보면 좋을 것 같다.

순서확인할 것

1	무엇을 기준으로 선택할 것인가?
2	정렬이 필요한가?
3	지금 선택한 것이 나중에 손해가 되지 않는가?
4	이 선택이 항상 최적해를 만드는가?
5	반례는 없는가?

 

특히 마지막 질문이 중요하다.

반례가 없다면 그리디 가능성이 높다.
반례가 있다면 DP나 완전탐색을 고려해야 한다.

---

시간복잡도

그리디 문제는 정렬을 사용하는 경우가 많다.

정렬을 한다면 보통 시간복잡도는 다음과 같다.

O(N log N)

정렬 후 한 번 순회하면 O(N)이 추가된다.

따라서 전체 시간복잡도는 보통 다음과 같이 생각할 수 있다.

O(N log N) + O(N) = O(N log N)

정렬이 필요 없는 그리디 문제라면 한 번 순회로 끝나서 O(N)이 될 수도 있다.

 

경우	시간복잡도
정렬이 필요한 경우	O(N log N)
한 번 순회만 하는 경우	O(N)

---

내가 이해한 그리디 핵심

이번에 그리디를 공부하면서 가장 중요하게 느낀 점은 이것이다.

그리디는 빠르지만, 항상 맞는 것은 아니다.

지금 가장 좋아 보이는 선택을 반복하는 방식이지만,
그 선택이 전체 정답으로 이어져야만 사용할 수 있다.

그래서 그리디 문제를 풀 때는 단순히 “큰 것부터 고르면 되겠다”라고 생각하면 안 된다.

왜 이 선택이 최선인가?
이 선택 때문에 나중에 손해를 보지는 않는가?
반례는 없는가?

이 질문을 꼭 해야 한다.

---

마무리

그리디 알고리즘은 개념 자체는 어렵지 않다.

매 순간 가장 좋아 보이는 선택을 하는 방법이다.

 

하지만 실제 문제에서는 무엇이 가장 좋아 보이는 선택인지를 정하는 것이 어렵다.

거스름돈 문제에서는 큰 동전이 기준이 될 수 있고,
회의실 배정 문제에서는 빨리 끝나는 회의가 기준이 된다.

 

즉, 그리디 문제의 핵심은 선택 기준이다.

앞으로 그리디 문제를 풀 때는 먼저 이렇게 생각해야겠다.

1. 지금 무엇을 선택해야 하지?
2. 어떤 기준으로 정렬해야 하지?
3. 이 선택이 나중에도 손해가 되지 않을까?
4. 반례는 없을까?

 

그리디는 답을 빠르게 구할 수 있는 알고리즘이지만,
선택 기준이 틀리면 바로 오답이 될 수 있다.

 

그래서 그리디 문제를 풀 때는 빠르게 선택하는 것보다,
그 선택이 왜 맞는지를 설명할 수 있는지 먼저 확인해야겠다.