알고리즘

탐욕법(Greedy)이란?

2026.08.14

1. 탐욕법(Greedy)란 무엇인가?

문제를 해결하는 각 단계에서 현재 상황에서 가장 좋아 보이는 선택을 반복적으로 내려 전체 문제를 해결하는 기법이다.

핵심: "지금 당장 최선인 선택을 하고, 그 선택을 절대 번복하지 않는다!"
매 단계마다 부분 최적해를 선택하며, 이 선택들이 모여 전체 최적해가 되기를 기대한다.
DP처럼 여러 하위 문제의 결과를 저장·비교하지 않고, 한 번 결정하면 되돌아보지 않기 때문에 구현이 단순하고 속도가 빠르다.

2. 사용 조건

모든 문제에 그리디를 적용할 수 있는 것은 아니다.

아래 2가지 조건이 동시에 성립 할 때만 그리디 알고리즘이 최적해를 보장한다.

① 탐욕적 선택 속성

각 단계에서 당장 최선인 선택을 하더라도, 이후의 선택에 의해 그 결정이 틀렸음이 밝혀지지 않는 성질이다.

즉, 앞선 선택을 절대 번복하지 않아도 전체 최적해에 도달할 수 있어야 한다.

② 최적 부분 구조

큰 문제의 최적해가 작은 하위 문제들의 최적해를 조합하여 형성되는 구조다.

DP와 조건이 같아 보이지만, 그리디는 하위 문제의 최적해를 비교하지 않고 하나만 선택해 진행한다는 점이 다르다.

3. 대표 예시 — 거스름돈 문제

동전 [500, 100, 50, 10]원으로 n원을 거슬러 줄 때, 동전 개수를 최소화하는 문제다.

그리디 전략: 가장 큰 단위의 동전부터 최대한 많이 사용한다.

💻 예시 코드

const coins = [500, 100, 50, 10];

const minCoinCount = (change) => {
  let remaining = change;
  let count = 0;

  for (const coin of coins) {
    count += Math.floor(remaining / coin);
    remaining %= coin;
  }

  return count;
};

시간 복잡도: 동전 종류 수를 $K$ 라 하면 $O(K)$
주의: 이 그리디 전략은 동전 단위가 [500, 100, 50, 10]처럼 배수 관계일 때만 최적해를 보장한다. [500, 400, 100]처럼 배수 관계가 아니면 큰 동전 우선 선택이 항상 최적은 아니다. (예: 800원 → 그리디는 500+100+100+100 = 4개, 최적은 400+400 = 2개)

4. 대표 유형 ① — 활동 선택 문제

여러 활동의 [시작 시간, 종료 시간]이 주어질 때, 겹치지 않게 최대한 많은 활동을 선택하는 문제다.

그리디 전략: 종료 시간이 빠른 활동부터 선택한다.

왜 종료 시간 기준인가?

종료 시간이 가장 빠른 활동을 먼저 선택하면, 남는 시간이 가장 많아져 이후 선택할 수 있는 활동의 여지가 최대로 남는다.
시작 시간이나 소요 시간 기준으로 정렬하면 반례가 존재해 최적해를 보장하지 못한다.

💻 예시 코드

const selectActivities = (activities) => {
  // 종료 시간 기준 오름차순 정렬
  const sorted = [...activities].sort((a, b) => a[1] - b[1]);
  const selected = [];
  let lastEndTime = -Infinity;

  for (const [start, end] of sorted) {
    if (start >= lastEndTime) {
      selected.push([start, end]);
      lastEndTime = end;
    }
  }

  return selected;
};

정렬에 $O(N \log N)$ , 이후 순회에 $O(N)$ → 전체 시간 복잡도 $O(N \log N)$

5. 대표 유형 ② — 분할 가능 배낭 문제

무게 제한 capacity인 배낭에, 물건을 쪼개서 담을 수 있을 때 가치를 최대화하는 문제다.

그리디 전략: 무게당 가치(가치/무게)가 높은 물건부터 채운다.

💻 예시 코드

const fractionalKnapsack = (items, capacity) => {
  // items: [{ weight, value }, ...]
  const sorted = [...items].sort(
    (a, b) => b.value / b.weight - a.value / a.weight,
  );

  let remaining = capacity;
  let totalValue = 0;

  for (const { weight, value } of sorted) {
    if (remaining <= 0) break;

    const take = Math.min(weight, remaining);
    totalValue += (value / weight) * take;
    remaining -= take;
  }

  return totalValue;
};

물건을 쪼갤 수 없는 0/1 배낭 문제는 그리디로 최적해를 보장할 수 없어 DP로 풀어야 한다.

6. Greedy vs DP, 무엇이 다른가?

비교 항목	Greedy (탐욕법)	DP (동적 계획법)
선택 방식	매 단계 하나의 최선만 선택하고 확정	하위 문제들의 결과를 모두 저장·비교
선택 번복	하지 않음 (되돌아보지 않음)	필요 시 여러 경우를 모두 고려
적용 조건	탐욕적 선택 속성 + 최적 부분 구조	최적 부분 구조 + 중복되는 부분 문제
속도·공간	대체로 더 빠르고 메모리 사용 적음	테이블 저장이 필요해 상대적으로 무거움
최적해 보장	조건 성립 시에만 보장	조건 성립 시 항상 보장

7. Greedy가 실패하는 경우

탐욕적 선택 속성이 성립하지 않으면, 그리디는 부분 최적해에 갇혀 전체 최적해를 놓친다.

반례: 배수 관계가 아닌 동전 문제

동전 [1, 3, 4]원으로 6원을 거슬러 준다고 하자.

그리디 결과: $4 + 1 + 1 = 3$ 개
실제 최적해: $3 + 3 = 2$ 개

가장 큰 단위부터 채우는 전략이 이 경우에는 최적해를 보장하지 못한다. 이런 문제는 그리디 대신 DP로 모든 경우를 비교해야 한다.

그리디를 적용하기 전에는 항상 반례가 존재하지 않는지 증명하거나, 최소한 여러 케이스로 검증해 보는 습관이 필요하다.

8. 정리

키워드	Greedy
선택 방식	매 단계 최선의 선택을 즉시 확정
필요 조건	탐욕적 선택 속성 + 최적 부분 구조
대표 문제	거스름돈, 활동 선택, 배낭, MST
주의할 점	조건 미성립 시 반례로 최적해 실패

그리디는 조건만 만족하면 DP보다 간단하고 빠르게 문제를 풀 수 있는 강력한 도구다.
다만 "당장 최선의 선택이 항상 전체 최적해로 이어지는가?"를 먼저 증명하거나 검증하는 습관이, 그리디를 안전하게 사용하는 핵심이다.