그리디 알고리즘 언제 쓰나, DP와 고르는 판단표와 반례 찾기 체크리스트

정렬 한 번에 반복문 한 번으로 끝나는 그리디 코드를 냈는데 "틀렸습니다"가 뜨면, 코드보다 그 문제가 그리디로 풀리는 문제인지부터 의심해야 해요. 결론부터 말하면 고르는 개수를 최대화하거나 최소화하는 문제이고, "최적해의 첫 선택을 그리디의 선택으로 바꿔도 손해가 없다"는 문장을 한 줄로 쓸 수 있으면 그리디, 점수·가치의 합을 따지거나 수량 제한이 붙으면 DP로 가는 게 안전해요. 그 한 줄을 쓸 수 있어도 작은 입력 전수 대조 테스트는 꼭 돌리고요.

이 글은 원리 설명 대신 고를 때와 제출·배포할 때 필요한 숫자만 다뤄요. 정렬 기준별로 실제로 얼마나 자주 틀리는지, 무작위 테스트를 몇 번 돌려야 반례가 잡히는지, 동전 체계가 그리디로 되는지 어디까지 검사하면 되는지를 Apple M1·파이썬 3.14.8로 직접 계산했어요(2026-10-27). 절대 시간은 기기마다 다르니 배수로 읽어 주세요.

그리디 알고리즘 언제 쓰나, 문제 유형별 판단표

그리디가 되는지는 문제 이름이 아니라 목표(개수냐 합이냐)와 제약(수량·마감·음수)이 정해요.

핵심은 세 번째 줄이에요. 위키백과 활동 선택 문제(Activity selection problem) 항목도 가중치 버전에는 그리디 해법이 없다고 적고 DP를 제시해요. "개수"를 "합"으로 바꾸는 순간 정렬 기준을 어떻게 바꾸든 답이 보장되지 않아요.

그림의 3번에서 말하는 "교환 문장"은 Jeff Erickson 의 『Algorithms』 4장 Greedy Algorithms (PDF)가 정리한 증명 틀을 실무용으로 줄인 거예요. 그리디 답과 다른 최적해가 있다고 놓고, 둘이 처음 갈라지는 선택을 그리디 쪽으로 바꿔도 해가 유효하고 나빠지지 않음을 보이면 돼요. "왜 나빠지지 않는가"를 한 문장으로 못 쓰면 4번 테스트를 아무리 통과해도 믿지 않는 게 좋아요.

그리디 반례 찾기, 무작위 테스트는 몇 번 돌려야 하나

증명이 어려울 때 가장 싼 확인법은 작은 입력에서 완전 탐색(또는 검증된 DP)과 답을 비교하는 거예요. 문제는 틀린 그리디가 얼마나 자주 틀리느냐에 따라 필요한 테스트 수가 수십 번에서 수만 번까지 벌어진다는 점이에요.

구간 n개를 무작위로 만들고(시작 0~3n, 길이 1~6), 최대 개수 문제에서 틀린 기준 세 가지가 정답과 다른 비율을 n마다 2만 번씩 셌어요. 정답은 끝 시각 순 그리디(증명된 방법)로 냈어요.

읽는 법은 이래요. 시작 시각 순은 n=8에서도 7번에 1번꼴로 틀리니 테스트 몇십 번이면 잡혀요. 반면 충돌 적은 순은 n=8에서 0.02%, 즉 5,000번에 1번이에요. n=5로만 테스트했다면 2만 번을 돌려도 반례가 하나도 안 나왔어요. 그래서 전수 대조는 이렇게 짜요.

• n을 키워 가며 돌려요. 오답률은 n이 커질수록 올라가요. 단, 완전 탐색이 감당하는 크기까지만이에요.
• 값 범위를 좁게 잡아야 경계·동점 버그가 드러나요.
• 반례가 나오면 가장 작은 반례를 남겨요. 작아야 사람이 읽고 원인을 찾아요.

부분집합 2ⁿ개를 비트마스크로 다 보는 완전 탐색 검사기가 버티는 크기예요.

n=12~14에서 수만 번이 현실적인 한계예요. 그보다 큰 입력이 필요하면 완전 탐색 대신 O(n²) DP 같은 "느리지만 확실한" 정답기를 따로 만들어 대조해요. 아래는 정답기와 후보 그리디를 받아 가장 작은 반례를 돌려주는 틀이에요.

import random

def stress(candidate, oracle, make_case, sizes, trials=20000, seed=0):
    rng = random.Random(seed)
    for n in sizes:                       # 작은 n부터 키워 가며
        for _ in range(trials):
            case = make_case(rng, n)
            want, got = oracle(case), candidate(case)
            if want != got:
                return n, case, want, got  # 찾은 것 중 가장 작은 크기의 반례
    return None

거스름돈 그리디 조건, 검사는 큰 두 단위의 합까지

동전 문제는 특별히 쉬운 판정법이 있어요. 큰 단위부터 고르는 그리디가 모든 금액에서 최적이면 그 체계를 정준(canonical)이라고 하는데, Kozen·Zaks 의 논문 Optimal Bounds for the Change-Making Problem (PDF)은 정준이 아닐 때 가장 작은 반례가 c₃+1보다 크고 가장 큰 두 단위의 합(cₘ + cₘ₋₁)보다 작다는 것을 보였어요(1이 포함된 체계 기준). 그러니 그 합보다 작은 금액만 DP와 대조하면 판정이 끝나요.

def is_canonical(coins):
    cs = sorted(coins)                    # cs[0] == 1 이어야 해요
    limit = cs[-1] + cs[-2]
    best = [0] + [float("inf")] * limit
    for x in range(1, limit):
        best[x] = min(best[x - c] + 1 for c in cs if c <= x)
        g, rest = 0, x
        for c in reversed(cs):
            g, rest = g + rest // c, rest % c
        if g != best[x]:
            return False, x               # 가장 작은 반례 금액
    return True, None

직접 돌린 결과예요. 원 단위 체계는 가장 작은 단위로 나눠 1부터 시작하게 바꿔서 넣었어요.

위키백과 거스름돈 문제(Change-making problem) 항목도 니켈이 없는 미국 동전으로 40센트를 만들 때 그리디 7개, 최적 4개라는 예를 들고, 정준 여부를 다항 시간에 판별할 수 있다고 적어요.

단위가 셋({1, c, d})이면 계산도 필요 없어요. 같은 논문의 정리 8에 따르면 d = q·c + r 로 나눴을 때 0 < r < c − q 이면 정준이 아니에요. {1, 3, 4} 는 4 = 1·3 + 1 이라 q=1, r=1 이고 0 < 1 < 2 이니 정준이 아니죠. 1 < c < d ≤ 100 인 4,851개 체계를 이 식과 DP 대조로 각각 판정한 결과는 모두 같았고, 정준인 것은 1,086개(22.4%)뿐이었어요. 아무 단위나 고르면 그리디가 통할 확률이 낮다는 뜻이라, 문제에서 단위가 입력으로 주어지면 기본값을 DP로 두는 게 맞아요.

수량 제한이 붙으면 정준 체계도 깨져요

자판기·ATM처럼 단위별 남은 개수가 정해져 있으면 정준 체계여도 그리디가 실패할 수 있어요. 미국 동전에서 25센트 1개, 10센트 3개만 있을 때 30센트를 내면 그리디는 25를 먼저 집고 나머지 5를 못 만들어 "거슬러 줄 수 없음"이 돼요. 10센트 3개면 되는데도요.

단위별 개수를 0~4개, 금액을 1~120으로 무작위로 2만 번 만들어 "만들 수 있는 경우"만 셌더니, 미국 동전 체계는 7,146번 중 130번(1.82%) 그리디가 틀렸어요. 각 단위가 바로 아래 단위의 배수인 한국 동전 비율(1·5·10·50)에서는 6,681번 중 0번이었고요. 이건 이 범위 무작위 시험 결과일 뿐 증명이 아니에요. 돈이 걸린 시스템이면 수량 제한 DP를 정답기로 두고 재고 조합을 따로 검증하세요.

가중치가 붙으면 그리디는 얼마나 틀리나

"개수"가 "합"으로 바뀐 변형에서 흔히 시도하는 그리디를 정답 DP와 비교했어요. 가중치 구간은 구간 12개(점수 1~20), 0/1 배낭은 물건 10개·용량 40으로 각 1만 번이에요. 막대는 정답과 달랐던 비율이고, 달라도 정답 대비 몇 %를 얻었는지가 평균 달성률이에요.

개수 문제의 정답 기준(끝 시각 순)이 합 문제에서는 가장 많이 틀려요. 점수를 아예 안 보니까요. 반면 점수 높은 순이나 가치 밀도 순은 자주 틀려도 평균 94~98%는 얻어요. 코딩 테스트에서는 1%만 모자라도 오답이지만, 실무에서 "대충 좋은 배치"를 빨리 내야 하는 경우라면 근사로 쓸 여지가 있다는 뜻이에요.

처리 시간과 한계, 구간 10만 개에서 직접 재기

정렬이 들어가면 그리디의 속도 이점은 생각보다 작아요. 무작위 구간 10만 개로 세 방법을 세 번씩 재 가장 빠른 값을 적었어요.

최대 개수 그리디와 가중치 DP의 차이는 약 3배예요. 둘 다 O(n log n)이라 정렬이 대부분을 차지하고, DP는 구간마다 이분 탐색 한 번이 더 붙을 뿐이에요. 회의실 힙은 동시에 열린 방이 많을수록 느려져요. n=100만이면 파이썬은 셋 다 1초를 넘겨요. 정렬 키를 튜플 대신 미리 만든 키로 바꾸는 요령은 파이썬·자바 정렬 성능 판단표에 따로 정리해 뒀어요.

거스름돈 쪽은 차이가 커요. 단위 6개(1·5·10·50·100·500) DP는 금액 1만에 0.014초, 10만에 0.14초, 100만에 1.6초로 금액에 비례해 늘었어요. 그리디는 금액과 상관없이 한 번에 약 2.4마이크로초였고요. 금액이 10⁹처럼 크면 O(단위 수 × 금액) DP는 아예 불가능해서, 정준 체계임을 위 방법으로 먼저 확인하고 그리디를 쓰는 것이 유일한 길이에요.

운영에서 자주 나는 문제와 확인 순서, 체크리스트

그리디 코드가 틀렸다고 나올 때 실제 원인은 판단 실수보다 사소한 구현 쪽이 더 흔해요. 아래 순서로 보면 대부분 위쪽에서 걸려요.

1. 경계 부등호: 문제가 "끝나는 시각에 바로 다음 회의를 시작할 수 있다"고 하면 s >= last_end, 아니면 s > last_end 예요.
2. 동점 정렬: 끝 시각이 같을 때 순서는 개수에 영향이 없지만, 길이 0 구간(s == e)이 허용되면 시작 시각 오름차순 보조 키가 필요해요. 파이썬 정렬은 공식 Sorting Techniques 문서대로 안정 정렬이라 보조 키를 안 주면 입력 순서가 그대로 남아요.
3. 문제 변형 확인: 점수, 단위별 수량, 마감 시각, 음수 값 중 하나라도 붙었으면 이전에 통하던 그리디를 그대로 쓰지 말고 교환 문장부터 다시 써요.
4. 전수 대조: 위 stress 틀로 n을 키워 가며 돌려요. 2만 번에 안 잡혀도 증명이 없으면 통과로 치지 않아요.
5. 시간 초과: "고른 것 전부와 겹치는지" 검사하는 코드는 O(n²)이에요. 끝 시각 순으로 정렬했다면 마지막 끝 시각 하나만 비교하면 되고, 최소 방 수는 파이썬 heapq 공식 문서의 heapreplace 로 꺼내기·넣기를 한 번에 해요.

실무 서비스에서 그리디를 쓸 때

예약·배차·작업 배정 같은 서비스 코드에서는 그리디가 맞는지보다 입력 가정이 계속 맞는지가 더 자주 문제가 돼요. 처음엔 "회의 개수 최대"였던 요구가 "중요한 회의 우선"으로 바뀌면 가중치 문제가 되는데, 코드는 그대로 남는 경우가 많아요. 그리디 함수 위에 "가정: 가중치 없음, 반열린 구간, 수량 무제한" 같은 전제를 주석으로 적고, 그 전제를 깨는 입력이 들어오면 예외를 내게 하면 조용히 틀린 결과가 나가는 일을 막을 수 있어요.

도입 전에 따질 것

• 목표가 개수인가 합인가: 합이면 그리디는 근사일 뿐이에요. 위 실험처럼 평균 94~98%여도 최악의 경우는 훨씬 나쁠 수 있어요(끝 시각 순은 평균 83.5%).
• 입력이 주는 단위가 고정인가: 동전·지폐처럼 단위가 코드에 박혀 있으면 정준 검사를 한 번 하고 테스트로 남겨요. 단위가 설정값이나 입력이면 DP가 기본이에요.
• 크기가 DP를 허용하나: 금액·용량이 10⁶ 이하면 DP가 파이썬으로도 1~2초 안이에요. 그보다 크면 그리디가 맞다는 증명이 필수예요.
• 정답기를 유지할 수 있나: 그리디를 배포하면 완전 탐색이나 DP 정답기를 테스트 코드에 같이 둬요.

비슷한 판단은 이분 탐색 판단표와 BFS DFS 판단표에도 정리해 뒀어요.

자주 묻는 질문

그리디와 DP 중 무엇을 먼저 시도해야 하나요?

문제가 "합"을 묻거나 수량 제한이 있으면 DP부터 시도해요. "개수"를 묻고 교환 문장을 한 줄로 쓸 수 있을 때만 그리디를 먼저 짜고, 작은 입력에서 DP나 완전 탐색과 대조한 뒤 제출해요.

무작위 테스트를 2만 번 통과하면 그리디가 맞다고 봐도 되나요?

아니에요. 충돌 적은 순 기준은 구간 5개로 2만 번 돌렸을 때 한 번도 틀리지 않았지만, 구간 32개에서는 0.66% 틀렸어요. 테스트는 반례를 찾는 도구이지 정답을 보장하지 않아요. 증명 문장이 함께 있어야 해요.

우리 서비스의 동전·쿠폰 단위가 그리디로 되는지 어떻게 확인하나요?

가장 작은 단위가 1이 되게 나눈 뒤, 가장 큰 두 단위의 합보다 작은 모든 금액을 DP와 비교하면 돼요. 그 범위에 반례가 없으면 모든 금액에서 그리디가 최적이에요(Kozen·Zaks). 단위가 셋이면 d = q·c + r 로 나눠 0 < r < c − q 인지만 보면 돼요.

한국 동전은 그리디로 거슬러 줘도 되나요?

10·50·100·500원은 정준 체계라 개수 제한이 없으면 그리디가 항상 최소 개수예요. 지폐 1천·5천·1만·5만 원도 같아요. 다만 자판기·키오스크처럼 남은 개수가 정해져 있으면 무작위 시험에서 반례는 없었어도 증명은 아니니, 재고를 반영한 DP로 확인하는 편이 안전해요.

가중치가 있는 회의 선택은 어떻게 푸나요?

끝 시각으로 정렬한 뒤, 각 회의마다 이분 탐색으로 "겹치지 않는 가장 늦은 직전 회의"를 찾고 dp[i] = max(dp[i−1], dp[직전] + 점수)로 채워요. O(n log n)이고 파이썬으로 10만 개에 약 0.28초였어요. 점수 높은 순 그리디는 무작위 입력의 31.4%에서 틀렸어요.

끝 시각 순 그리디가 시간 초과가 나요.

겹침 검사를 고른 회의 전체와 하고 있지 않은지 보세요. 끝 시각 순이면 마지막에 고른 회의의 끝 시각 하나만 비교하면 돼요. 그래도 느리면 정렬 키와 입력 읽기를 줄여요. 구간 100만 개면 파이썬은 정렬만으로 2초 가까이 걸려요.

정리

• 개수를 최대화·최소화하고 교환 문장을 한 줄로 쓸 수 있으면 그리디, 점수 합·수량 제한·임의 단위면 DP가 기본이에요.
• 틀린 그리디 중에는 0.1%도 안 틀리는 기준이 있어요. 작은 입력부터 n을 키워 가며 전수 대조하고, 테스트 통과를 증명으로 치지 마세요.
• 동전 체계는 가장 큰 두 단위의 합 미만만 검사하면 그리디 가능 여부가 판정돼요. 한국 동전·지폐는 통과하지만 수량 제한이 붙으면 다시 따져요.
• 정렬이 비용 대부분이라 그리디와 이분 탐색 DP의 시간 차이는 약 3배예요. 그리디는 빠르기보다 단순해서 고르는 거예요.

더 깊이 읽기

이 글은 실무에서 판단할 때 필요한 것 위주로 정리했어요. 같은 주제의 내부 동작 원리는 devboi 기술 블로그의 그리디 알고리즘 정당성 원리 — 교환 논법·회의실 배정·동전 반례에서 도식과 코드로 단계별로 풀었어요.