12강 / 20강

탐욕 알고리즘 — 지금 제일 좋아 보이는 걸 고른다

쿠폰 자동 적용은 왜 가끔 손님에게 손해일까

손님 장바구니가 52,000원입니다. 쓸 수 있는 쿠폰이 세 장 있어요.

A — 10,000원 할인 (3만 원 이상)
B — 15% 할인, 최대 12,000원 (5만 원 이상)
C — 5,000원 할인 (제한 없음)

쿠폰은 한 장만 쓸 수 있습니다. 어떤 걸 자동으로 적용해 줘야 할까요?

당연히 가장 많이 깎이는 것이죠. B = 52,000 × 15% = 7,800원… 앗, A가 더 낫네요. 이렇게 지금 이 순간 가장 이득인 것을 고르는 방식을 탐욕 알고리즘(greedy algorithm)이라고 합니다.

고등학생지금 제일 좋아 보이는 걸 고른다

탐욕 알고리즘은 이름 그대로입니다.

앞을 안 보고 지금 최선을 고른다

거스름돈으로 보면

1,300원을 거슬러 줍니다. 동전은 500·100·50·10원.

가장 큰 것부터 → 500원 2개 (남은 300)
→ 100원 3개 (남은 0)
끝. 총 5개

앞뒤 안 재고 큰 것부터 — 그런데 답이 맞다

그런데 늘 맞지는 않습니다

만약 동전이 1원, 3원, 4원 뿐이라면? 6원을 거슬러 줘 봅시다.

방법	동전	개수
탐욕	4 + 1 + 1	3개
최선	3 + 3	2개

탐욕이 최선이 아닐 수 있다

그래서 쿠폰 자동 적용이 손해일 수 있습니다

부제가 그 이야기예요. 할인이 큰 쿠폰부터 적용하면 전체로는 손해일 수 있습니다.

7강의 쿠폰 적용 순서 이야기와 같은 문제죠.

쿠폰 한 장이면 탐욕이 항상 정답입니다.

Python 브라우저에서 실행

장바구니 = 52000

쿠폰들 = [
    {"이름": "A · 1만원 할인",      "정액": 10000, "율": 0,    "최대": 0,     "최소주문": 30000},
    {"이름": "B · 15% (최대 1.2만)", "정액": 0,     "율": 0.15, "최대": 12000, "최소주문": 50000},
    {"이름": "C · 5천원 할인",       "정액": 5000,  "율": 0,    "최대": 0,     "최소주문": 0},
]

def 할인액(쿠폰, 금액):
    if 금액 < 쿠폰["최소주문"]:
        return 0
    if 쿠폰["정액"]:
        return 쿠폰["정액"]
    return min(int(금액 * 쿠폰["율"]), 쿠폰["최대"])

# 탐욕 — 가장 많이 깎이는 것 하나
최선 = max(쿠폰들, key=lambda c: 할인액(c, 장바구니))
for c in 쿠폰들:
    print(f"  {c['이름']:<20} {할인액(c, 장바구니):>7,}원")
print()
print(f"🎟️ 자동 적용: {최선['이름']}  →  {할인액(최선, 장바구니):,}원 할인")
print(f"   결제 금액: {장바구니 - 할인액(최선, 장바구니):,}원")

고등학생탐욕이 잘 통하는 문제들

note 가 언제 탐욕이 통하는지를 정리합니다.

"지금 최선을 골라도 나중에 손해가 없다" 가 보장될 때

잘 통하는 예

문제	탐욕 규칙
거스름돈 (우리 동전)	큰 것부터
회의실 배정	일찍 끝나는 것부터
최소 신장 트리	가벼운 간선부터

회의실 배정이 재미있습니다

회의 여러 개 중 겹치지 않게 최대한 많이 넣으려면?

규칙	결과
일찍 시작하는 것부터	안 된다 — 긴 회의가 자리를 먹는다
일찍 끝나는 것부터	항상 최적 ✔

규칙을 어떻게 정하느냐가 전부다

같은 탐욕인데 기준 하나로 맞고 틀립니다. 그래서 "탐욕을 쓴다" 보다 "어떤 기준으로" 가 중요해요.

왜 일찍 끝나는 게 맞나

일찍 끝나면 남는 시간이 가장 많으니까요. 뒤에 더 많이 넣을 수 있습니다.

지금 고른 것이 미래를 가장 덜 방해하면 탐욕이 통한다

그런데 탐욕이 지는 순간

쿠폰을 여러 장 쓸 수 있게 정책을 바꿨습니다. 단, 총 할인 한도는 20,000원. 그리고 각 쿠폰에는 사용 조건이 붙어 있어요.

이제 "가장 큰 것부터"가 정답이 아닐 수 있습니다.

가장 큰 것 하나를 잡느라 더 좋은 조합을 놓치는 전형적인 사례.

Python 브라우저에서 실행

# 배낭 문제의 축소판 — 무게 한도 안에서 가치를 최대로
한도 = 20000

쿠폰 = [
    {"이름": "A", "차감": 12000, "혜택": 12000},
    {"이름": "B", "차감":  9000, "혜택": 10000},
    {"이름": "C", "차감": 11000, "혜택": 11000},
]

# 탐욕 — 혜택이 큰 것부터
남은, 탐욕결과, 탐욕혜택 = 한도, [], 0
for c in sorted(쿠폰, key=lambda c: -c["혜택"]):
    if c["차감"] <= 남은:
        남은 -= c["차감"]; 탐욕결과.append(c["이름"]); 탐욕혜택 += c["혜택"]

# 완전 탐색 — 모든 조합을 다 해 본다
from itertools import combinations
최적결과, 최적혜택 = [], 0
for r in range(1, len(쿠폰) + 1):
    for 조합 in combinations(쿠폰, r):
        if sum(c["차감"] for c in 조합) <= 한도:
            v = sum(c["혜택"] for c in 조합)
            if v > 최적혜택:
                최적혜택, 최적결과 = v, [c["이름"] for c in 조합]

print(f"탐욕    : {탐욕결과}  →  {탐욕혜택:,}원")
print(f"완전탐색: {최적결과}  →  {최적혜택:,}원")
print()
print("🚨 탐욕이 졌습니다!" if 탐욕혜택 < 최적혜택 else "탐욕도 최적입니다.")
print("   A(12,000) 하나를 잡느라 B+C(21,000)를 놓쳤어요.")

🎮 쿠폰 조합기

쿠폰을 직접 만들고 한도를 조절하면서 탐욕과 완전 탐색의 결과를 나란히 비교해 보세요. 탐욕이 지는 경우를 만들어 보는 것이 이번 실습의 목표입니다. 계산 횟수도 함께 표시되니, 완전 탐색의 비용도 확인하세요.

고등학생그럼 항상 완전 탐색을 쓰면 되지 않나요

note 가 자연스러운 질문에 답합니다. 모든 경우를 다 해 보면 항상 최선을 찾잖아요?

맞다. 그런데 2ⁿ 으로 폭발한다

얼마나 폭발하나

쿠폰 개수	경우의 수	시간 (초당 100만 개)
10	1,024	순식간
20	100만	1초
30	10억	17분
50	1,000조	36년

쿠폰 50장이면 컴퓨터로도 불가능하다

비유 — 옷 조합 다 입어 보기

옷 30벌 중 입을지 말지 를 다 시험해 본다면? 10억 가지입니다. 평생 못 합니다.

경우의 수가 두 배씩 늘면 금방 감당이 안 된다

그래서 세 가지 길이 있습니다

방법	얻는 것	잃는 것
탐욕	빠르다	최선이 아닐 수 있다
완전 탐색	항상 최선	느리다
동적 계획법 (13강)	최선 + 빠름	조건이 맞아야 한다

13강이 세 번째 길이다

완전 탐색의 중복 계산을 없애면 같은 답을 훨씬 빨리 얻을 수 있어요.

실무에서의 현실적인 타협

실제 쇼핑몰은 이렇게 합니다.

상황	선택	이유
쿠폰 1장만 사용 가능	탐욕	탐욕이 곧 최적. 계산 즉시.
쿠폰 여러 장, 개수 적음(≤15)	완전 탐색 또는 DP	정확한 최적을 보장
쿠폰 종류가 아주 많음	탐욕 + 정책 제한	"중복 사용 최대 2장" 같은 규칙으로 n을 줄임
배송 박스 포장	탐욕(큰 것부터)	최적은 어렵지만 실용적으로 충분

"정책을 단순하게 만들어 알고리즘 문제를 없앤다"는 것도 시스템 관리자의 훌륭한 해결책입니다.

탐욕의 성공 여부는 '문제의 구조'에 달려 있습니다.

Python 브라우저에서 실행

# 거스름돈 — 탐욕이 항상 최적인 유명한 예 (한국 화폐 기준)
def 거스름돈(금액):
    화폐 = [50000, 10000, 5000, 1000, 500, 100, 50, 10]
    결과 = []
    for 단위 in 화폐:                # 큰 것부터 — 탐욕
        개수 = 금액 // 단위
        if 개수:
            결과.append((단위, 개수))
            금액 -= 단위 * 개수
    return 결과

for 금액 in (87650, 13400, 990):
    print(f"{금액:>7,}원 거스름돈:", end=" ")
    print(", ".join(f"{단위:,}원×{개수}" for 단위, 개수 in 거스름돈(금액)))

print()
print("💡 만약 화폐 단위가 [1, 3, 4]원이고 6원을 거슬러야 한다면?")
print("   탐욕: 4 + 1 + 1 = 동전 3개")
print("   최적: 3 + 3     = 동전 2개  ← 탐욕이 집니다!")
print("   한국 화폐는 운 좋게 탐욕이 항상 최적인 구조예요.")

고등학생탐욕을 쓸지 정하는 법

실무에서 어떻게 판단할까요?

작은 경우로 반례를 찾아 본다

방법

탐욕 규칙을 정한다
작은 예를 여러 개 만든다
탐욕 답과 완전 탐색 답을 비교한다
다르면 → 탐욕이 안 통한다

위젯에서 한 것이 바로 이 검증이다

왜 작은 예로 하나

완전 탐색이 작을 때만 가능하니까요. 쿠폰 10장이면 1,024가지 — 순식간입니다.

거기서 반례가 나오면 큰 경우에도 안 통합니다.

반례 하나면 충분히 반박된다

수학의 그것과 같습니다

"모든 n 에 대해 성립한다" 를 반박하려면 안 되는 n 하나만 찾으면 되죠.

반대로 증명하려면 훨씬 어렵습니다 — 모든 경우를 다뤄야 하니까요.

반박은 쉽고 증명은 어렵다

실무에서의 타협

증명이 어려우면 많이 시험해 보고 씁니다. 그리고 "최선이 아닐 수 있다" 를 적어 둡니다.

쿠폰 자동 적용이 그래요 — 대체로 좋지만 가끔 손해일 수 있다고요.

완벽하지 않아도 알고 쓰면 문제없다

🤔 확인 문제

탐욕 알고리즘의 정의로 가장 알맞은 것은?

🤔 확인 문제

쿠폰 25장 중 조합을 완전 탐색하면 몇 가지 경우를 봐야 할까요?

🤔 확인 문제

화폐 단위가 [1, 3, 4]원일 때 6원을 거슬러 주려 합니다. 탐욕(큰 것부터)의 결과는?