[알고리즘] 41. 그리디 알고리즘 기초

[알고리즘] 41. 그리디 알고리즘 기초

지난 글에서는 차분 배열(Difference Array)에 대해 정리했습니다. 이번 글에서는 알고리즘 문제에서 자주 등장하는 풀이 방식인 그리디 알고리즘(Greedy Algorithm)에 대해 알아보겠습니다.

그리디는 매 순간 가장 좋아 보이는 선택을 하는 알고리즘입니다. 말 그대로 욕심쟁이처럼 현재 상황에서 가장 이득이 되는 선택을 반복해서 정답을 만들어갑니다.

그리디 알고리즘은 매 순간 가장 좋아 보이는 선택을 하면서 전체 정답을 구하는 알고리즘입니다.

---

1. 그리디 알고리즘이란?

그리디 알고리즘은 현재 단계에서 가장 좋아 보이는 선택을 하는 방식입니다. 미래의 모든 경우를 다 계산하지 않고, 지금 당장 가장 유리한 선택을 합니다.

예를 들어 거스름돈을 줄 때 가장 큰 동전부터 사용하는 상황을 생각해보겠습니다.

거스름돈: 760원
사용 가능한 동전: 500원, 100원, 50원, 10원

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

이 방식은 매번 사용할 수 있는 가장 큰 동전을 선택합니다. 현재 가장 큰 동전을 고르는 선택을 반복해서 거스름돈을 만듭니다.

그리디는 지금 가장 좋아 보이는 선택을 반복하는 방식입니다.

---

2. 그리디가 필요한 상황

그리디는 모든 경우를 다 확인하지 않아도 되는 문제에서 사용할 수 있습니다. 특히 정렬 후 가장 작은 값이나 가장 큰 값부터 선택하는 문제가 많습니다.

• 가장 큰 값부터 선택해야 할 때
• 가장 작은 값부터 선택해야 할 때
• 현재 선택이 이후 선택에 큰 영향을 주지 않을 때
• 정렬 후 앞에서부터 처리하면 되는 문제
• 최소 개수, 최대 개수, 최소 비용, 최대 이익을 구하는 문제
• 매 순간의 최선 선택이 전체 최선으로 이어지는 문제

문제에서 “최대한 많이”, “최소 개수”, “가장 적은 비용”, “가장 큰 이익” 같은 표현이 보이면 그리디를 의심해볼 수 있습니다.

---

3. 그리디의 핵심 조건

그리디는 단순해 보이지만 모든 문제에 사용할 수 있는 것은 아닙니다. 현재 최선의 선택이 전체 정답으로 이어져야 합니다.

그리디가 통하려면 보통 아래 조건을 만족해야 합니다.

조건	의미
탐욕 선택 속성	현재의 최선 선택이 전체 최적해로 이어질 수 있음
최적 부분 구조	부분 문제의 최적해가 전체 문제의 최적해를 구성함

입문 단계에서는 용어를 완벽히 외우기보다, “지금 가장 좋은 선택을 해도 나중에 손해가 없는가?”를 먼저 생각하면 됩니다.

그리디는 현재 선택이 나중에 후회 없는 선택이어야 사용할 수 있습니다.

---

4. 그리디와 완전탐색의 차이

완전탐색은 가능한 모든 경우를 확인합니다. 반면 그리디는 매 순간 가장 좋아 보이는 선택만 합니다.

구분	완전탐색	그리디
풀이 방식	모든 경우를 확인	현재 최선만 선택
장점	정답을 놓칠 가능성이 적음	빠르고 구현이 간단한 경우가 많음
단점	경우의 수가 많으면 느림	항상 정답을 보장하지는 않음
핵심	모든 후보 확인	선택 기준의 정당성

그리디는 빠르지만, 선택 기준이 틀리면 정답도 틀립니다. 따라서 왜 그 선택이 맞는지 생각하는 과정이 중요합니다.

---

5. 거스름돈 문제

그리디의 대표 예시는 거스름돈 문제입니다. 가장 큰 동전부터 최대한 많이 사용하면 동전 개수를 줄일 수 있습니다.

거스름돈: 1260원
동전: 500원, 100원, 50원, 10원

큰 동전부터 사용하면 다음과 같습니다.

동전	사용 개수	남은 금액
500원	2개	260원
100원	2개	60원
50원	1개	10원
10원	1개	0원

총 동전 개수는 6개입니다.

거스름돈 문제는 가장 큰 단위부터 선택하는 그리디의 기본 예제입니다.

---

6. 거스름돈 Java 코드

거스름돈 문제를 Java 코드로 작성하면 다음과 같습니다.

int money = 1260;
int[] coins = {500, 100, 50, 10};

int count = 0;

for (int coin : coins) {
    count += money / coin;
    money %= coin;
}

System.out.println(count);

출력 결과는 다음과 같습니다.

6

money / coin은 해당 동전을 몇 개 사용할 수 있는지 구합니다. money % coin은 그 동전을 사용하고 남은 금액입니다.

사용 개수: money / coin
남은 금액: money % coin

---

7. 그리디가 항상 맞지는 않습니다

그리디는 강력하지만 항상 정답을 보장하지는 않습니다. 동전 문제도 동전 단위에 따라 그리디가 틀릴 수 있습니다.

예를 들어 동전이 아래처럼 있다고 하겠습니다.

동전: 500원, 400원, 100원
거스름돈: 800원

가장 큰 동전부터 선택하면 다음과 같습니다.

500원 1개
100원 3개

총 4개

하지만 실제 최적해는 400원 2개입니다.

400원 2개

총 2개

이 예시처럼 매 순간 가장 큰 동전을 선택하는 방식이 항상 최적은 아닙니다. 따라서 그리디를 사용할 때는 선택 기준이 항상 맞는지 확인해야 합니다.

그리디 문제에서는 “이 선택이 항상 최선인가?”를 의심해야 합니다.

---

8. 정렬과 그리디

그리디 문제는 정렬과 함께 나오는 경우가 많습니다. 정렬을 통해 선택 기준을 명확히 만든 뒤, 앞에서부터 또는 뒤에서부터 선택합니다.

• 작은 값부터 선택하기
• 큰 값부터 선택하기
• 끝나는 시간이 빠른 것부터 선택하기
• 비용이 낮은 것부터 선택하기
• 이익이 큰 것부터 선택하기

예를 들어 회의실 배정 문제에서는 회의가 끝나는 시간이 빠른 순서로 정렬한 뒤 선택합니다. 빨리 끝나는 회의를 먼저 선택해야 뒤에 더 많은 회의를 배치할 수 있기 때문입니다.

그리디 문제에서는 어떤 기준으로 정렬할지가 매우 중요합니다.

---

9. 회의실 배정 문제 아이디어

회의실 배정 문제는 그리디의 대표 유형입니다. 여러 회의의 시작 시간과 끝 시간이 주어졌을 때, 겹치지 않게 최대한 많은 회의를 선택하는 문제입니다.

회의 목록:
회의 A: 1시 시작, 4시 종료
회의 B: 2시 시작, 3시 종료
회의 C: 3시 시작, 5시 종료
회의 D: 5시 시작, 6시 종료

가장 좋은 선택 기준은 끝나는 시간이 빠른 회의부터 선택하는 것입니다. 일찍 끝나는 회의를 고르면 남은 시간에 더 많은 회의를 넣을 수 있습니다.

끝나는 시간 기준 정렬
→ 가능한 회의를 앞에서부터 선택
→ 현재 선택한 회의의 끝 시간 이후에 시작하는 회의만 선택

---

10. 회의실 배정 Java 예시

회의실 배정 문제의 기본 코드는 다음과 같습니다.

import java.util.Arrays;

int[][] meetings = {
    {1, 4},
    {2, 3},
    {3, 5},
    {5, 6}
};

Arrays.sort(meetings, (a, b) -> {
    if (a[1] != b[1]) {
        return a[1] - b[1];
    }

    return a[0] - b[0];
});

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);

출력 결과는 다음과 같습니다.

3

끝나는 시간이 빠른 회의부터 확인하면서, 현재 회의가 이전 회의의 종료 시간 이후에 시작하면 선택합니다.

회의실 배정은 끝나는 시간이 빠른 순서로 정렬하는 것이 핵심입니다.

---

11. 그리디 문제 풀이 순서

그리디 문제는 아래 순서로 접근하면 좋습니다.

1. 무엇을 최소화하거나 최대화해야 하는지 확인한다.
2. 매 순간 어떤 선택을 할 수 있는지 정리한다.
3. 가장 좋아 보이는 선택 기준을 세운다.
4. 그 기준이 항상 맞는지 예외를 생각한다.
5. 정렬이 필요한지 확인한다.
6. 선택한 값을 누적하며 정답을 만든다.

그리디에서는 코드보다 선택 기준이 더 중요합니다. 선택 기준이 틀리면 코드를 잘 작성해도 정답이 될 수 없습니다.

그리디는 구현보다 기준 설정이 더 중요한 알고리즘입니다.

---

12. 그리디가 맞는지 확인하는 방법

그리디 풀이가 맞는지 확인하려면 반례를 찾아보는 것이 중요합니다.

아래 질문을 스스로 해보면 좋습니다.

• 현재 가장 좋은 선택이 나중에 손해가 되지는 않는가?
• 더 작은 선택을 먼저 해야 전체적으로 더 좋아지는 경우는 없는가?
• 정렬 기준을 바꿨을 때 더 좋은 답이 나오는가?
• 가장 큰 값부터 선택하는 것이 항상 맞는가?
• 가장 작은 값부터 선택하는 것이 항상 맞는가?

그리디 문제는 단순히 감으로 풀면 틀릴 수 있습니다. 작은 예시를 여러 개 만들어보면서 선택 기준이 깨지는 경우가 없는지 확인해야 합니다.

---

13. 그리디와 DP의 차이

그리디와 DP는 둘 다 최적의 답을 구할 때 사용됩니다. 하지만 접근 방식이 다릅니다.

구분	그리디	DP
선택 방식	현재 최선 선택	여러 경우를 저장하며 비교
과거 상태 저장	거의 저장하지 않음	이전 결과를 저장함
장점	빠르고 단순함	그리디가 안 되는 문제도 해결 가능
주의점	항상 정답을 보장하지 않음	점화식 설계가 필요함

현재 선택만으로 정답이 보장되면 그리디를 사용할 수 있습니다. 하지만 여러 선택지를 비교하며 최적값을 쌓아야 한다면 DP가 필요할 수 있습니다.

그리디가 안 되는 문제는 DP로 접근해야 하는 경우가 많습니다.

---

14. 그리디가 사용되는 대표 문제 유형

그리디는 아래와 같은 문제에서 자주 사용됩니다.

문제 유형	대표 선택 기준
거스름돈	큰 동전부터 선택
회의실 배정	끝나는 시간이 빠른 회의부터 선택
최소 비용	비용이 작은 것부터 선택
최대 이익	이익이 큰 것부터 선택
문자열 만들기	사전순으로 유리한 문자 선택
정렬 후 선택	조건에 맞는 순서대로 처리

그리디 문제는 정렬, 우선순위 큐, 투 포인터와 함께 섞여 나오는 경우도 많습니다. 그래서 선택 기준을 먼저 잡고, 필요한 자료구조를 함께 고르는 것이 좋습니다.

---

15. 그리디에서 자주 하는 실수

그리디 문제를 풀 때는 아래 실수를 조심해야 합니다.

• 현재 가장 좋아 보이는 선택이 항상 정답이라고 착각하는 경우
• 반례를 확인하지 않는 경우
• 정렬 기준을 잘못 잡는 경우
• 오름차순과 내림차순을 반대로 적용하는 경우
• 끝나는 시간 기준이어야 하는데 시작 시간 기준으로 정렬하는 경우
• 동전 단위가 그리디에 적합하지 않은데 큰 동전부터 선택하는 경우
• 그리디로 풀 수 없는 문제를 억지로 그리디로 푸는 경우

특히 그리디는 반례 하나만 있어도 틀린 풀이가 됩니다. 따라서 선택 기준을 세운 뒤 작은 테스트 케이스를 직접 만들어 확인하는 습관이 필요합니다.

그리디 풀이에서는 선택 기준이 틀리면 전체 풀이가 틀립니다.

---

16. 정리

이번 글에서는 그리디 알고리즘 기초에 대해 정리했습니다.

• 그리디는 매 순간 가장 좋아 보이는 선택을 하는 알고리즘이다.
• 현재의 최선 선택이 전체 최적해로 이어질 때 사용할 수 있다.
• 그리디는 빠르고 구현이 단순한 경우가 많다.
• 하지만 모든 문제에서 정답을 보장하지는 않는다.
• 거스름돈 문제는 그리디의 대표 예제이다.
• 회의실 배정 문제는 끝나는 시간이 빠른 순서로 정렬하는 것이 핵심이다.
• 그리디 문제는 정렬과 함께 나오는 경우가 많다.
• 선택 기준이 항상 맞는지 반례를 확인해야 한다.

그리디는 알고리즘 문제에서 매우 자주 등장하는 풀이 방식입니다. 하지만 단순히 “가장 큰 것부터”, “가장 작은 것부터” 고르면 된다고 외우면 위험합니다. 왜 그 선택이 항상 최적인지 판단하는 과정이 꼭 필요합니다.

그리디의 핵심은 매 순간의 선택 기준을 정확히 세우고, 그 선택이 전체 최적해로 이어지는지 확인하는 것입니다.

---

다음 글 예고

다음 글에서는 그리디 대표 문제를 정리하겠습니다.

거스름돈, 회의실 배정, 최소 비용 선택, 정렬 후 선택 문제를 예제로 보면서 그리디 선택 기준을 어떻게 잡는지 더 자세히 알아보겠습니다.