탐욕 알고리즘 (Greedy)

도입

“지금 당장 가장 좋아 보이는 선택”을 반복해 답을 만드는 알고리즘 전략이다

알고리즘을 공부하다 보면 브루트포스, 백트래킹, 동적 계획법(DP), 분할 정복과 함께 자주 등장하는 개념이 바로 Greedy입니다.

한국어로는 보통 탐욕 알고리즘이라고 부릅니다.

이름만 보면 무조건 성급하게 고르는 단순한 방식처럼 느껴질 수 있지만, 실제로는 문제의 구조가 맞을 때 매우 빠르고 강력한 해법이 됩니다. 특히 정렬, 우선순위, 선택 기준이 분명한 최적화 문제에서 자주 쓰이며, 코딩 테스트와 실무 최적화 문제 모두에서 중요하게 다뤄집니다.

정의

매 순간 지역적으로 최선인 선택을 하면서 전체 해답을 구성하는 방식이다

Greedy 알고리즘은 문제를 해결할 때 매 단계마다 현재 시점에서 가장 이득이 커 보이는 선택을 합니다. 그리고 그 선택을 되돌리지 않거나 거의 되돌리지 않은 채, 다음 단계로 넘어가 같은 기준을 반복 적용합니다.

중요한 점은, Greedy가 단순히 “좋아 보이는 걸 고른다”로 끝나는 것이 아니라 그 선택이 결국 전체 최적해로 이어질 수 있어야 한다는 것입니다. 이 조건이 맞지 않으면 Greedy는 빠르지만 틀린 답을 내는 전략이 됩니다.

핵심 요약

• Greedy는 현재 시점의 최선을 선택한다.
• 선택을 누적해 최종 답을 만든다.
• 모든 문제에 통하지는 않으며, 문제 구조가 맞을 때만 정답이 된다.

한 줄 정리

Greedy = 지금 가장 좋아 보이는 선택을 반복하는 전략이지만, 그 선택이 전체 최적해로 이어진다는 근거가 있어야 합니다.

필요성

복잡한 최적화 문제를 빠르고 단순하게 풀 수 있게 해주는 강력한 도구다

어떤 문제는 모든 경우를 다 살펴보면 너무 오래 걸립니다. 브루트포스는 정확하지만 느리고, DP는 강력하지만 상태 정의와 점화식 설계가 복잡할 수 있습니다. 이런 상황에서 문제의 구조만 맞는다면 Greedy는 훨씬 단순한 구현으로 매우 빠른 성능을 제공합니다.

Greedy가 중요한 이유

• 빠르다: 정렬 후 선형 탐색 정도로 끝나는 경우가 많다.
• 구현이 단순하다: 상태 전이보다 선택 규칙 중심으로 생각할 수 있다.
• 실전에서 자주 나온다: 코딩 테스트, 일정 배정, 최소 비용 문제 등에서 반복적으로 등장한다.
• 최적화 감각을 키워준다: 어떤 기준이 전체 답에 영향을 주는지 분석하는 훈련이 된다.

핵심 원리

탐욕적 선택 속성과 최적 부분 구조를 함께 만족해야 한다

1. 탐욕적 선택 속성(Greedy Choice Property)

현재 단계에서 가장 좋아 보이는 선택을 해도, 이후의 최적 선택들과 모순되지 않아야 합니다. 즉, 지금의 최선이 전체 최선의 일부가 될 수 있어야 합니다.

2. 최적 부분 구조(Optimal Substructure)

큰 문제의 최적해가 작은 부분 문제의 최적해로부터 구성될 수 있어야 합니다. 현재 선택 이후 남은 문제 역시 같은 방식으로 최적으로 해결 가능해야 합니다.

중요

최적 부분 구조가 있다고 해서 무조건 Greedy가 되는 것은 아닙니다. DP도 최적 부분 구조를 이용합니다. Greedy가 되려면 여기에 더해 현재의 최선 선택이 항상 안전하다는 근거가 필요합니다.

동작 방식

“선택 기준 정의 → 정렬 또는 우선순위 구성 → 순차 선택” 흐름으로 자주 구현된다

Greedy 문제는 겉보기에는 다양하지만 실제 구현 패턴은 꽤 비슷합니다. 보통 어떤 기준으로 “지금 가장 좋은 선택”인지 정한 뒤, 정렬이나 우선순위 큐를 통해 후보를 정리하고, 조건을 만족하는 항목을 차례대로 선택합니다.

1. 선택 기준 정의: 무엇이 “가장 좋은 선택”인지 정한다.
2. 정렬 또는 우선순위 구성: 선택 기준에 맞게 후보를 정리한다.
3. 하나씩 선택: 현재 조건에서 가능한 최선의 후보를 고른다.
4. 상태 갱신: 남은 자원, 시간, 구간, 비용 등을 갱신한다.
5. 반복: 더 이상 선택할 수 없을 때까지 같은 규칙을 적용한다.

대표 예시

동전 문제, 회의실 배정, 최소 신장 트리 같은 고전 문제가 Greedy의 전형적인 예다

1. 거스름돈 문제

예를 들어 동전 단위가 500원, 100원, 50원, 10원이라면 가장 큰 동전부터 최대한 사용하는 방식으로 최소 동전 개수를 구할 수 있습니다. 이 경우에는 큰 단위 동전을 먼저 쓰는 것이 전체 최적해로 이어집니다.

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

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

2. 회의실 배정 문제

끝나는 시간이 가장 빠른 회의를 먼저 선택하면, 이후에 더 많은 회의를 배치할 가능성이 커집니다. 그래서 보통 종료 시간 오름차순 정렬이 핵심 선택 기준이 됩니다.

3. Kruskal 알고리즘

최소 신장 트리(MST)를 구할 때는 가중치가 낮은 간선부터 선택하되, 사이클이 생기지 않게 관리합니다. “가장 싼 간선부터 고른다”는 점에서 대표적인 Greedy 알고리즘입니다.

4. Huffman Coding

가장 빈도가 낮은 두 노드를 합치는 과정을 반복해 평균 코드 길이를 최소화합니다. 이 또한 지역적으로 가장 손해가 적은 선택을 반복하는 Greedy 사례입니다.

통하지 않는 경우

선택 기준이 틀리거나 문제 구조가 맞지 않으면 쉽게 오답이 된다

Greedy의 가장 큰 함정은 “그럴듯해 보여도 항상 맞는 것은 아니다”는 점입니다. 특히 현재 이득이 큰 선택이 나중에 더 큰 손해를 부를 수 있는 문제에서는 Greedy가 실패합니다.

상황	문제점
현재 선택이 미래 선택을 심하게 제한하는 경우	지금의 최선이 전체 최선을 망칠 수 있다
선택 기준이 직관적일 뿐 증명되지 않은 경우	반례가 존재할 가능성이 높다
부분 문제의 최적해가 전체 최적해로 이어지지 않는 경우	DP나 완전 탐색이 필요할 수 있다

대표 반례: 동전 단위가 일반적이지 않은 경우

동전이 500, 100, 50, 10처럼 규칙적이면 Greedy가 잘 맞지만, 예를 들어 동전이 4원, 3원, 1원이고 목표가 6원이라면 큰 동전부터 고르면 4 + 1 + 1 = 3개가 됩니다. 하지만 최적해는 3 + 3 = 2개입니다.

핵심

Greedy는 “빠른 알고리즘”이기 전에 “증명이 필요한 알고리즘”입니다. 감으로 기준을 잡으면 틀릴 가능성이 큽니다.

DP와 차이

한 번의 선택을 믿고 가고, DP는 여러 가능성을 저장하며 비교한다

항목	Greedy	DP
선택 방식	현재 최선 하나를 선택	가능한 상태를 저장하며 비교
속도	보통 더 빠름	상태 수에 따라 커질 수 있음
구현 난이도	기준만 맞으면 단순	점화식 설계가 필요
정답 보장	성립 조건이 맞을 때만	상태 설계가 맞으면 보장 가능

실전에서는 어떤 문제가 Greedy로 풀리는지 먼저 의심해 보고, 근거가 약하면 DP나 다른 방식으로 전환하는 판단이 중요합니다.

문제 접근법

“무엇을 기준으로 먼저 고를 것인가”를 찾는 과정이 핵심이다

1. 목표를 명확히 본다: 최소 비용인지, 최대 개수인지, 최대 가치인지 확인한다.
2. 선택 기준 후보를 세운다: 가장 큰 값, 가장 작은 값, 가장 빨리 끝나는 값 등 기준을 생각한다.
3. 정렬 가능성을 본다: 기준에 따라 정렬하면 쉽게 풀릴 수 있는지 확인한다.
4. 반례를 만든다: 지금 정한 기준이 항상 맞는지 작은 예제로 깨본다.
5. 증명 또는 직관 근거를 확보한다: 왜 이 선택이 안전한지 설명할 수 있어야 한다.

코딩 테스트 팁

Greedy 문제는 보통 정렬, 우선순위 큐, 누적 선택과 함께 출제됩니다. “일단 정렬해 보면 기준이 보인다”는 경우가 많습니다.

장점과 단점

매우 효율적이지만, 선택 기준이 틀리면 빠르게 틀린 답으로 간다

장점 ✅

• 시간 복잡도가 좋은 경우가 많다
• 구현이 간결하다
• 정렬 + 반복으로 끝나는 패턴이 많다
• 최적화 문제를 빠르게 해결할 수 있다

단점 ❌

• 항상 정답을 보장하지 않는다
• 문제 성립 조건을 증명해야 한다
• 직관적인 기준이 반례에 무너질 수 있다
• 잘못 적용하면 오답인데도 구현은 간단해서 착각하기 쉽다

실전 패턴

선택 기준에 따라 정렬형, 우선순위 큐형, 구간 선택형으로 자주 나타난다

• 정렬형: 끝나는 시간, 시작 시간, 비용, 무게 등 기준으로 정렬 후 순차 선택
• 최소/최대 우선순위 큐형: 현재 가장 유리한 값을 계속 꺼내는 방식
• 구간 선택형: 겹치지 않는 구간 최대 선택, 최소 커버 문제 등
• 가중치 선택형: 값 대비 비용, 작은 비용 우선, 큰 가치 우선 등
• 그래프 선택형: MST, 최단 경로 일부 문제 등에서 국소 최적 선택을 반복

디버깅

풀이가 틀릴 때는 정렬 기준, 반례, 선택 안전성을 먼저 점검해야 한다

1

정렬 기준이 정말 문제 목표와 일치하는지 확인한다.

2

작은 반례를 만들어 현재 선택 기준이 깨지지 않는지 본다.

3

“왜 이 선택이 안전한가”를 문장으로 설명할 수 있는지 확인한다.

4

선택이 미래의 가능성을 지나치게 제한하지 않는지 점검한다.

5

증명이 약하면 DP, 이분 탐색, 완전 탐색 등 다른 접근으로 전환한다.

요약

매우 효율적인 전략이지만, 정답이 되려면 “지금의 최선이 전체의 최선으로 이어진다”는 근거가 필요하다

• ✅ Greedy는 현재 시점의 최선 선택을 반복하는 알고리즘 전략이다.
• ✅ 빠르고 구현이 간단하지만, 모든 최적화 문제에 맞는 것은 아니다.
• ✅ 탐욕적 선택 속성과 최적 부분 구조가 함께 성립해야 한다.
• ✅ 정렬, 우선순위 큐, 구간 선택 문제에서 자주 등장한다.
• ✅ 반례를 만들고 선택 기준의 안전성을 검증하는 습관이 중요하다.

RELATED POST

DP와 Greedy의 차이: 어떤 문제에서 무엇을 선택해야 할까?
회의실 배정 문제로 배우는 탐욕 알고리즘의 핵심
정렬 + Greedy 패턴 정리: 코딩 테스트 빈출 유형 모음