눈앞의 이익이 정말 전체의 이익일까
그리디 알고리즘은 이름 그대로 "탐욕스럽게" 선택하는 방법입니다. 지금 이 순간 가장 좋아 보이는 선택을 하고, 그 선택을 되돌리지 않은 채 다음 단계로 넘어갑니다. 말만 들으면 매우 단순합니다. 가장 작은 것, 가장 큰 것, 가장 빨리 끝나는 것, 가장 적게 드는 것처럼 기준 하나를 정하고 계속 고르면 됩니다.
하지만 코딩 테스트에서 그리디가 까다로운 이유는 구현이 어려워서가 아닙니다. 그 기준이 정말 맞는지 설명하기 어렵기 때문입니다. 잘못된 기준으로도 예제는 통과할 수 있습니다. 심지어 꽤 많은 테스트도 통과할 수 있습니다. 그러나 숨어 있는 반례 하나가 나오면 바로 틀립니다.
그리디 문제를 풀 때는 다음 질문을 먼저 던져야 합니다.
"지금 최선으로 보이는 선택을 해도, 나중에 더 좋은 전체 해를 놓치지 않는가?"
이 질문에 자신 있게 대답할 수 있어야 합니다. 그리디는 감으로 푸는 알고리즘이 아니라, 선택 기준의 정당성을 세운 뒤 빠르게 구현하는 알고리즘입니다.
그리디가 통하는 문제의 두 가지 냄새
모든 최적화 문제에 그리디를 적용할 수 있는 것은 아닙니다. "최댓값을 구하라", "최솟값을 구하라"라는 말이 나온다고 해서 무조건 그리디는 아닙니다. 오히려 그런 문제 중 상당수는 다음 장에서 다룰 동적 계획법으로 풀어야 합니다.
그리디가 통하는 문제에는 대체로 두 가지 성질이 숨어 있습니다.
첫째, 한 번 한 선택을 나중에 바꿀 필요가 없어야 합니다. 어떤 선택을 했는데 이후 상황을 보고 "아까 다른 걸 골랐어야 했네"가 자주 발생한다면 그리디로는 위험합니다. 그리디는 되돌아가지 않는 방식이므로, 현재 선택이 미래 선택을 망치지 않는다는 확신이 필요합니다.
둘째, 부분 문제의 최적 선택이 전체 최적해와 잘 이어져야 합니다. 예를 들어 어떤 회의를 하나 선택한 뒤 남은 시간대에서 최대한 많은 회의를 고르는 문제가 다시 같은 형태로 남는다면 그리디를 의심해볼 수 있습니다. 선택 후에도 문제 구조가 깔끔하게 유지되는 것입니다.
실전에서는 이 성질을 엄밀한 수학 증명처럼 길게 쓰지는 않아도 됩니다. 하지만 머릿속으로는 반드시 검토해야 합니다. 특히 면접이나 라이브 코딩에서는 "왜 이 기준으로 정렬하나요?"라는 질문을 자주 받습니다. 이때 "그냥 그게 맞는 것 같아서요"라고 답하면 위험합니다.
정당성을 확인하는 가장 실용적인 방법
그리디의 정당성을 설명할 때 가장 많이 쓰는 방식은 교환 논증입니다. 이름은 어렵지만 생각은 단순합니다.
내가 선택한 그리디 선택이 있습니다. 그리고 어떤 최적해가 있습니다. 만약 그 최적해가 내 선택을 포함하지 않는다면, 최적해의 일부를 내 선택으로 바꾸어도 결과가 나빠지지 않음을 보입니다. 그러면 "내 선택을 포함하는 최적해도 존재한다"고 말할 수 있습니다. 이 과정을 반복하면 그리디 선택을 계속 쌓아도 최적해에 도달할 수 있습니다.
예를 들어 회의실 배정 문제를 생각해 봅시다. 한 회의실에서 가능한 한 많은 회의를 진행해야 합니다. 각 회의에는 시작 시간과 종료 시간이 있습니다. 이때 가장 널리 알려진 그리디 기준은 종료 시간이 빠른 회의부터 선택하는 것입니다.
왜 그럴까요? 첫 번째 회의를 고를 때 종료 시간이 빠른 회의를 선택하면, 뒤에 남는 시간이 가장 많아집니다. 어떤 최적해가 첫 회의로 다른 회의를 골랐다고 합시다. 그 회의보다 더 빨리 끝나는 회의로 바꾸면, 이후에 배치할 수 있던 회의들은 여전히 배치할 수 있습니다. 오히려 시간이 더 넉넉해질 뿐입니다. 따라서 종료 시간이 가장 빠른 회의를 선택해도 손해가 없습니다.
이처럼 그리디 기준은 단순히 "좋아 보인다"가 아니라 "다른 최적해의 선택과 바꿔도 나빠지지 않는다"로 설명할 수 있어야 합니다.
그리디 풀이의 기본 절차
그리디 문제는 대체로 구현보다 풀이 설계가 중요합니다. 다음 순서로 접근하면 실수가 줄어듭니다.
선택해야 하는 대상이 무엇인지 정합니다.
매 순간 비교할 기준을 정합니다.
그 기준으로 골라도 손해가 없는지 반례를 찾아봅니다.
필요하다면 정렬, 우선순위 큐, 스택 등을 결합합니다.
선택한 뒤 상태를 어떻게 갱신할지 구현합니다.
중요한 것은 3번입니다. 많은 사람이 2번에서 바로 구현으로 넘어갑니다. 그러면 예제 중심 풀이가 됩니다. 코딩 테스트에서 그리디를 안전하게 통과하려면, 구현 전에 반드시 작은 반례를 만들어보아야 합니다.
예를 들어 "가장 짧은 회의부터 선택하면 많이 고를 수 있지 않을까?"라는 기준을 떠올릴 수 있습니다. 얼핏 그럴듯합니다. 하지만 짧은 회의가 한가운데 끼어 있어서 양쪽의 많은 회의를 방해할 수 있습니다. 길이가 짧다는 사실보다 중요한 것은 얼마나 빨리 자리를 비워주느냐입니다. 그래서 회의실 배정에서는 길이가 아니라 종료 시간이 기준이 됩니다.
정렬과 만나는 순간 강해지는 그리디
그리디 문제에서 정렬은 거의 단짝처럼 등장합니다. 현재 최선의 선택을 반복하려면, 무엇이 먼저 고려되어야 하는지 순서를 정해야 하기 때문입니다. 정렬을 잘하면 문제의 복잡한 관계가 한 방향으로 흐르기 시작합니다.
정렬을 사용할 때는 단순히 "오름차순 정렬"이라고 생각하지 말고, 다음처럼 기준의 의미를 언어로 설명해야 합니다.
"먼저 끝나는 것을 고르면 남은 선택지가 최대한 넓어진다."
"가장 작은 요구 조건부터 처리하면 더 많은 사람을 만족시킬 수 있다."
"구간의 끝점을 기준으로 보면 한 번의 선택으로 최대한 많은 대상을 포함할 수 있다."
이런 문장으로 설명되지 않는 정렬 기준은 위험합니다. 정렬 기준이 문제의 최적 구조와 연결되어 있어야 합니다.
회의실 배정: 빨리 끝나는 회의가 왕이다
대표적인 그리디 문제인 회의실 배정을 자세히 보겠습니다. 목표는 서로 겹치지 않는 회의를 최대한 많이 선택하는 것입니다.
가장 먼저 떠오르는 기준은 여러 가지입니다. 빨리 시작하는 회의, 시간이 짧은 회의, 종료 시간이 빠른 회의. 이 중 정답으로 이어지는 기준은 종료 시간이 빠른 회의입니다.
풀이 흐름은 간단합니다. 회의들을 종료 시간 기준으로 정렬합니다. 종료 시간이 같다면 시작 시간이 빠른 순서로 두면 안정적입니다. 그다음 현재 마지막으로 선택한 회의의 종료 시간을 기억해 둡니다. 다음 회의의 시작 시간이 이 종료 시간 이상이면 선택할 수 있습니다.
meetings = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 13), (12, 14)]
meetings.sort(key=lambda x: (x[1], x[0]))
count = 0
end_time = 0
for start, end in meetings:
if start >= end_time:
count += 1
end_time = end
print(count)이 문제에서 핵심은 코드가 아니라 선택 기준입니다. "가장 빨리 시작하는 회의"를 선택하면 긴 회의 하나가 하루를 통째로 차지할 수 있습니다. "가장 짧은 회의"를 선택하면 짧지만 애매한 위치의 회의가 더 좋은 조합을 막을 수 있습니다. 반면 "가장 빨리 끝나는 회의"는 다음 회의들이 들어올 공간을 가장 넓게 남깁니다.
그리디 문제를 만났을 때 이렇게 여러 기준을 후보로 세워보고, 각 기준이 왜 맞거나 틀린지 비교하면 풀이가 훨씬 단단해집니다.
체육복 유형: 가까운 사람에게 빌려주는 선택
체육복 문제는 탐욕 기준이 조금 더 생활감 있게 드러나는 유형입니다. 어떤 학생은 체육복을 잃어버렸고, 어떤 학생은 여벌 체육복이 있습니다. 여벌이 있는 학생은 바로 앞 번호나 바로 뒷 번호 학생에게만 빌려줄 수 있습니다. 목표는 체육 수업을 들을 수 있는 학생 수를 최대화하는 것입니다.
이 문제에서 먼저 주의할 점은 한 학생이 동시에 잃어버리고 여벌을 가져올 수 있다는 것입니다. 이런 학생은 여벌을 자기 자신이 입어야 하므로 다른 사람에게 빌려줄 수 없습니다. 따라서 시작할 때 잃어버린 집합과 여벌 집합의 교집합을 제거해야 합니다.
그다음 작은 번호부터 보며 처리할 수 있습니다. 잃어버린 학생을 기준으로 왼쪽 학생에게 먼저 빌릴지, 오른쪽 학생에게 먼저 빌릴지 정해야 합니다. 일반적으로 번호 순서대로 잃어버린 학생을 처리하면서 왼쪽 여벌을 먼저 확인하면 안정적입니다. 왜냐하면 왼쪽 학생은 현재 학생을 지나치면 더 이상 뒤쪽 학생에게 영향을 주기 어렵기 때문입니다.
def solution(n, lost, reserve):
lost_set = set(lost)
reserve_set = set(reserve)
both = lost_set & reserve_set
lost_set -= both
reserve_set -= both
for student in sorted(lost_set):
if student - 1 in reserve_set:
reserve_set.remove(student - 1)
elif student + 1 in reserve_set:
reserve_set.remove(student + 1)
else:
n -= 1
return n이 문제는 작은 입력에서는 어떤 식으로 빌려줘도 맞아 보입니다. 하지만 실제로는 처리 순서가 중요합니다. 앞쪽 학생에게 빌려줄 수 있는 기회를 놓치면 나중에 복구할 수 없습니다. 그래서 그리디는 항상 "지금 선택하지 않으면 기회가 사라지는 대상"을 잘 찾아야 합니다.
여기서도 정당성은 간단히 설명할 수 있습니다. 번호가 작은 잃어버린 학생부터 처리할 때, 그 학생에게 체육복을 빌려줄 수 있는 후보는 왼쪽과 오른쪽뿐입니다. 왼쪽 후보는 현재 학생을 도와주지 않으면 이후 더 오른쪽 학생을 도울 가능성이 제한적입니다. 따라서 왼쪽을 먼저 사용하는 선택이 미래 선택지를 크게 해치지 않습니다.
단속 카메라 유형: 구간을 한 번에 찌르기
단속 카메라 유형은 여러 차량의 이동 구간이 주어지고, 모든 차량이 적어도 한 번 카메라를 만나도록 카메라 수를 최소화하는 문제입니다. 각 차량의 진입 지점과 진출 지점이 구간으로 주어집니다.
이 문제는 회의실 배정과 닮았습니다. 회의실 배정이 "겹치지 않게 많이 고르기"라면, 단속 카메라는 "겹치는 구간을 한 번의 선택으로 최대한 처리하기"입니다.
핵심 기준은 진출 지점이 빠른 차량부터 보는 것입니다. 가장 먼저 끝나는 구간의 끝에 카메라를 설치하면, 그 지점을 포함하는 모든 차량을 동시에 처리할 수 있습니다. 그리고 그 지점을 지나 이미 처리된 차량은 더 이상 고려하지 않습니다.
def solution(routes):
routes.sort(key=lambda x: x[1])
cameras = 0
camera_pos = -30001
for start, end in routes:
if start > camera_pos:
cameras += 1
camera_pos = end
return cameras왜 구간의 끝점에 카메라를 두는 것이 좋을까요? 가장 빨리 끝나는 구간을 반드시 찍어야 한다고 생각해 봅시다. 이 구간 안 어딘가에는 카메라가 있어야 합니다. 그런데 그 구간의 끝점에 카메라를 두면, 뒤에 이어지는 다른 구간들과 겹칠 가능성을 최대한 크게 유지할 수 있습니다. 더 왼쪽에 두는 것보다 손해 볼 이유가 없습니다.
이 유형에서는 "끝나는 지점 기준 정렬"이 자주 등장합니다. 회의실 배정에서는 끝나는 지점이 빠른 것을 선택해 다음 공간을 확보했고, 단속 카메라에서는 끝나는 지점에 선택을 배치해 현재 구간을 처리하면서 다음 구간과의 겹침 가능성을 남깁니다. 모양은 다르지만 기준의 철학은 비슷합니다.
동전 문제: 항상 큰 동전부터 쓰면 될까
동전 거스름돈 문제는 그리디의 대표 예시로 자주 소개됩니다. 예를 들어 500원, 100원, 50원, 10원 동전으로 1,260원을 거슬러줘야 한다면 가장 큰 동전부터 쓰면 됩니다. 500원 두 개, 100원 두 개, 50원 한 개, 10원 한 개로 총 6개입니다.
amount = 1260
coins = [500, 100, 50, 10]
count = 0
for coin in coins:
count += amount // coin
amount %= coin
print(count)하지만 여기서 아주 중요한 함정이 있습니다. 동전 문제는 언제나 그리디로 풀리지 않습니다.
예를 들어 동전 단위가 1원, 3원, 4원이고 6원을 만들어야 한다고 합시다. 가장 큰 동전부터 고르면 4원 하나를 고르고, 남은 2원은 1원 두 개로 채워 총 3개입니다. 하지만 최적해는 3원 두 개, 총 2개입니다. 큰 동전을 먼저 고르는 탐욕 기준이 틀린 것입니다.
이 차이는 동전 단위의 구조에서 나옵니다. 한국 화폐처럼 큰 단위가 작은 단위들과 잘 맞물려 있는 경우에는 큰 동전부터 고르는 방식이 자연스럽게 최적해로 이어집니다. 그러나 임의의 동전 단위가 주어지면 그렇지 않을 수 있습니다. 이런 경우에는 보통 동적 계획법으로 최소 동전 개수를 구해야 합니다.
따라서 코딩 테스트에서 동전 문제가 나오면 다음을 확인해야 합니다.
동전 단위가 익숙한 배수 구조인지 확인합니다.
문제에서 그리디가 가능하다는 조건이 주어졌는지 봅니다.
임의의 동전 단위라면 작은 반례를 만들어봅니다.
"가장 큰 것부터 고른다"는 기준은 강력하지만, 언제나 옳지는 않습니다. 그리디에서 가장 위험한 말은 "당연히"입니다.
배낭 문제: 쪼갤 수 있으면 그리디, 못 쪼개면 조심
배낭 문제도 그리디를 이야기할 때 자주 등장합니다. 물건마다 무게와 가치가 있고, 배낭에는 담을 수 있는 최대 무게가 있습니다. 목표는 가치의 합을 최대화하는 것입니다.
여기서 물건을 쪼갤 수 있다면 이야기가 쉬워집니다. 예를 들어 금가루, 설탕, 액체처럼 일부만 담을 수 있다면 단위 무게당 가치가 높은 것부터 담으면 됩니다. 1kg당 가치가 높은 물건을 먼저 채우는 것이 언제나 이득입니다. 남은 공간이 부족하면 그 물건의 일부만 담으면 됩니다.
하지만 물건을 쪼갤 수 없다면 상황이 완전히 달라집니다. 단위 무게당 가치가 가장 높은 물건을 먼저 골랐더니, 남은 공간이 애매하게 남아 더 좋은 조합을 놓칠 수 있습니다.
예를 들어 배낭 용량이 10이고 다음 물건들이 있다고 합시다.
| 물건 | 무게 | 가치 | 단위 가치 |
|---|---|---|---|
| A | 6 | 30 | 5 |
| B | 5 | 24 | 4.8 |
| C | 5 | 24 | 4.8 |
단위 가치만 보면 A가 가장 좋습니다. A를 담으면 무게 4가 남고 B나 C를 더 담을 수 없습니다. 총 가치는 30입니다. 하지만 B와 C를 함께 담으면 무게 10, 가치 48입니다. 이 경우 단위 가치 기준 그리디는 틀립니다.
이처럼 0/1 배낭 문제, 즉 물건을 통째로 담거나 아예 담지 않아야 하는 문제는 일반적으로 그리디가 아니라 동적 계획법으로 접근합니다. 반면 물건을 나눌 수 있는 분할 배낭 문제는 그리디가 통합니다.
문제에서 "일부만 선택할 수 있다", "나누어 담을 수 있다"라는 조건이 있으면 그리디 가능성을 강하게 의심해볼 수 있습니다. 반대로 "각 물건은 한 번만 선택 가능하다", "선택하거나 선택하지 않는다"라면 조심해야 합니다.
최소와 최대를 반복 선택할 때의 함정
그리디 문제는 종종 최소값이나 최대값을 반복해서 선택하는 모양으로 나타납니다. 가장 작은 비용을 합치기, 가장 큰 이익을 먼저 챙기기, 가장 적은 자원으로 처리하기 같은 형태입니다.
하지만 최소와 최대라는 단어에 속으면 안 됩니다. 반복 선택이 최적인지 확인하려면 "이번에 선택한 값이 이후 선택 구조를 어떻게 바꾸는가"를 봐야 합니다.
예를 들어 여러 카드 묶음을 하나로 합칠 때, 두 묶음을 합칠 때마다 두 묶음 크기의 합만큼 비용이 든다고 합시다. 전체 비용을 최소화하려면 매번 가장 작은 두 묶음을 합치는 것이 좋습니다. 작은 묶음을 빨리 합쳐야 이후 반복해서 더해지는 비용이 줄어들기 때문입니다. 이 유형은 우선순위 큐와 결합되어 자주 출제됩니다.
반면 "가장 큰 이익부터 선택하자"는 기준은 제약 조건에 따라 쉽게 깨집니다. 어떤 일을 선택하면 특정 시간 동안 다른 일을 못 한다든지, 선행 조건이 있다든지, 선택 가능한 시점이 다르다면 단순 최대값 기준은 위험합니다. 이때는 정렬 후 가능한 후보만 우선순위 큐에 넣거나, 아예 동적 계획법으로 바꾸어야 할 수 있습니다.
즉, 그리디는 단순히 최대·최소를 고르는 기술이 아닙니다. 반복 선택의 결과가 전체 구조에서 손해를 만들지 않는다는 확신이 필요합니다.
반례를 만드는 습관
그리디를 잘하려면 반례를 잘 만들어야 합니다. 반례는 내 풀이를 공격하는 작은 테스트입니다. 좋은 반례는 크지 않습니다. 오히려 원소 3개, 4개짜리 작은 입력에서 풀이의 약점이 가장 잘 드러납니다.
반례를 만들 때는 먼저 내가 세운 기준을 한 문장으로 적어봅니다.
"가장 빨리 시작하는 회의를 고른다."
"가장 짧은 회의를 고른다."
"가장 큰 동전을 먼저 쓴다."
"단위 가치가 높은 물건부터 담는다."
그다음 그 기준이 좋아 보이지만 실제로는 손해를 보는 상황을 상상합니다. 가장 빨리 시작하는 회의가 너무 길면 어떨까요? 가장 짧은 회의가 가운데에 끼어 양쪽 회의를 막으면 어떨까요? 가장 큰 동전 하나 때문에 더 적은 개수의 조합을 놓치면 어떨까요? 단위 가치가 높은 물건 하나가 배낭 공간을 애매하게 남기면 어떨까요?
이렇게 질문을 던지면 반례가 만들어집니다.
회의실 배정에서 "빨리 시작하는 회의" 기준의 반례를 봅시다.
회의 목록: (1, 10), (2, 3), (3, 4), (4, 5)빨리 시작하는 회의를 고르면 (1, 10) 하나만 선택합니다. 하지만 최적해는 (2, 3), (3, 4), (4, 5)로 세 개입니다.
이번에는 동전 문제에서 "큰 동전부터" 기준의 반례입니다.
동전: 1, 3, 4
금액: 6큰 동전부터 고르면 4 + 1 + 1로 세 개입니다. 최적해는 3 + 3으로 두 개입니다.
배낭 문제에서 "단위 가치가 높은 것부터" 기준의 반례도 다시 볼 수 있습니다.
용량: 10
물건: (무게 6, 가치 30), (무게 5, 가치 24), (무게 5, 가치 24)단위 가치 기준으로는 첫 번째 물건을 고르지만, 실제 최적해는 두 번째와 세 번째 물건을 함께 담는 것입니다.
반례를 찾는 과정은 시간을 잡아먹는 일이 아니라 시간을 아껴주는 일입니다. 잘못된 그리디를 구현하고 디버깅하는 데 30분을 쓰는 것보다, 처음에 3분 동안 반례를 찾는 편이 훨씬 낫습니다.
그리디와 정렬 문제를 구분하는 감각
코딩 테스트에서 그리디 문제는 종종 정렬 문제처럼 보입니다. 실제로 정렬만 잘하면 대부분의 구현이 끝나는 경우도 많습니다. 하지만 정렬 문제와 그리디 문제는 관점이 다릅니다.
정렬 문제는 데이터를 원하는 순서로 나열하는 것이 핵심입니다. 반면 그리디 문제는 정렬된 순서에서 무엇을 선택하고 무엇을 버릴지가 핵심입니다. 정렬은 도구이고, 선택 기준이 본질입니다.
예를 들어 회의실 배정에서는 종료 시간으로 정렬한 뒤 가능한 회의만 선택합니다. 단속 카메라에서는 진출 지점으로 정렬한 뒤 현재 카메라 위치로 처리되지 않는 구간에만 새 카메라를 둡니다. 체육복 문제에서는 번호 순서로 보면서 여벌을 사용할지 결정합니다.
정렬 후 모든 원소를 그대로 쓰면 단순 정렬·구현 문제에 가깝습니다. 정렬 후 조건에 따라 일부를 고르거나, 현재 상태를 갱신하며 최적 선택을 쌓아가면 그리디 문제일 가능성이 큽니다.
구현에서 자주 나는 실수
그리디는 아이디어가 맞아도 구현에서 미끄러지기 쉽습니다. 특히 경계 조건과 정렬 기준에서 실수가 많이 납니다.
첫째, 같은 값이 있을 때의 보조 정렬 기준을 확인해야 합니다. 회의실 배정에서 종료 시간이 같다면 시작 시간이 빠른 순서로 두는 것이 자연스럽습니다. 어떤 문제에서는 종료 시간이 같을 때 시작 시간이 늦은 것이 유리할 수도 있습니다. 보조 기준은 문제 조건에 맞게 정해야 합니다.
둘째, 겹침 조건의 등호를 조심해야 합니다. 회의가 끝나는 시간과 다음 회의가 시작하는 시간이 같을 때 가능한지 문제에서 확인해야 합니다. 가능하다면 start >= end_time이고, 불가능하다면 start > end_time입니다. 등호 하나가 정답을 바꿉니다.
셋째, 이미 처리된 대상을 다시 쓰지 않도록 해야 합니다. 체육복 문제에서 여벌을 빌려준 학생은 reserve 집합에서 제거해야 합니다. 단속 카메라 문제에서는 현재 카메라 위치로 처리되는 구간은 넘어가야 합니다.
넷째, 초기값을 입력 범위 밖으로 안전하게 잡아야 합니다. 카메라 위치처럼 아직 아무 선택도 하지 않은 상태를 표현할 때는 가능한 구간보다 작은 값을 쓰거나, 첫 번째 원소를 따로 처리하는 방식이 좋습니다.
작은 실수처럼 보이지만 그리디 문제에서는 이런 조건 하나가 선택 흐름 전체를 바꿉니다.
그리디 문제를 만났을 때의 사고 루틴
실전에서 그리디 후보 문제를 만나면 다음 루틴으로 생각해 보세요.
먼저 목표를 분명히 합니다. "개수를 최대화하는가?", "비용을 최소화하는가?", "모든 대상을 덮어야 하는가?", "제한된 자원으로 최대한 만족시켜야 하는가?"를 확인합니다.
다음으로 선택 단위를 정합니다. 회의 하나를 고르는지, 카메라 위치 하나를 정하는지, 동전 하나를 쓰는지, 사람 하나를 처리하는지 결정합니다.
그다음 가능한 탐욕 기준을 여러 개 떠올립니다. 가장 빨리 시작, 가장 빨리 끝남, 가장 짧음, 가장 큼, 가장 작음, 단위 효율이 높음 같은 후보를 나열합니다.
그리고 각 기준에 대해 반례를 만들어봅니다. 기준이 깨지는 작은 입력을 찾았다면 버립니다. 반례를 찾지 못했고 교환 논증이나 직관적 설명이 가능하다면 그 기준을 채택합니다.
마지막으로 정렬이나 자료구조를 붙입니다. 기준이 고정되면 구현은 비교적 단순해집니다. 정렬 한 번으로 충분한지, 매번 최소·최대를 꺼내야 하므로 우선순위 큐가 필요한지 판단합니다.
이 루틴에 익숙해지면 그리디 문제를 보고도 조급해지지 않습니다. 그리디는 빠르게 떠올리는 사람이 이기는 것이 아니라, 틀린 기준을 빠르게 버리는 사람이 이깁니다.
연습 문제를 풀 때 남겨야 할 기록
그리디 문제를 연습할 때는 정답 코드만 저장하지 말고 선택 기준을 함께 기록해야 합니다. 예를 들어 다음처럼 짧게 남기면 좋습니다.
문제: 회의실 배정
기준: 종료 시간이 빠른 회의부터 선택
이유: 빨리 끝날수록 남은 시간 구간이 넓어져 이후 선택을 방해하지 않음
반례로 버린 기준: 시작 시간이 빠른 회의, 길이가 짧은 회의이 기록은 나중에 비슷한 문제를 만났을 때 큰 힘이 됩니다. 코딩 테스트에서는 완전히 새로운 문제보다 익숙한 구조를 살짝 비튼 문제가 자주 나옵니다. 그때 "아, 이건 종료 시간 기준 구간 선택과 닮았네", "이건 큰 동전부터 고르면 위험한 임의 동전 문제네"처럼 빠르게 분류할 수 있습니다.
그리디는 유형 암기가 아니라 기준의 축적입니다. 기준을 외우는 것이 아니라, 왜 그 기준이 안전한지 함께 기억해야 합니다.
마무리: 그리디는 용감하지만 의심이 많아야 한다
그리디 알고리즘은 매력적입니다. 복잡한 계산 없이도 정렬 한 번, 반복문 한 번으로 최적해가 나오는 경우가 많습니다. 그래서 잘 맞으면 풀이가 매우 깔끔합니다. 하지만 그만큼 위험합니다. 틀린 기준도 그럴듯한 얼굴을 하고 나타나기 때문입니다.
그리디를 사용할 때는 두 가지 태도를 함께 가져야 합니다. 선택은 과감해야 하지만, 기준은 의심해야 합니다. 현재의 최선이 전체의 최선으로 이어진다는 설명이 있어야 합니다. 반례를 만들어보고, 교환해도 손해가 없는지 생각해보고, 문제 조건이 그리디를 허락하는지 확인해야 합니다.
이번 장에서 기억할 핵심은 단순합니다.
그리디는 현재의 최선 선택을 되돌리지 않고 쌓는 방식이다.
선택 기준은 반드시 정당성을 설명할 수 있어야 한다.
정렬은 그리디의 강력한 도구지만, 정렬 기준 자체가 답은 아니다.
동전과 배낭처럼 쉬워 보이는 문제도 조건에 따라 그리디가 깨진다.
작은 반례를 만드는 습관이 잘못된 탐욕을 막아준다.
다음 장에서는 그리디와 자주 비교되는 동적 계획법을 다룹니다. 그리디가 "지금 선택하고 되돌아보지 않는 방식"이라면, 동적 계획법은 "작은 답들을 저장해두고 조합하는 방식"입니다. 어떤 문제는 과감한 선택으로 풀리고, 어떤 문제는 차분한 누적으로 풀립니다. 두 방식을 구분할 수 있게 되면 코딩 테스트 문제를 보는 눈이 한 단계 더 선명해집니다.
이 노트는 보도·비평·교육·연구 목적으로 작성되었습니다. 저작권 문의가 있으시면 에서 알려주세요.