탐욕 알고리즘(Greedy Algorithm)
1. 개요
가. 정의
탐욕 알고리즘(Greedy Algorithm)이란 매 단계에서 그 순간에 가장 좋아 보이는 국소 최적(local optimum)의 선택을 하고 한 번 내린 결정을 되돌리지 않음으로써 전역 최적해(global optimum)에 도달하려는 문제 해결 전략으로, 선택이 전역 최적으로 이어질 수 있는 탐욕 선택 속성(greedy choice property)과 최적 부분 구조(optimal substructure)가 성립하는 문제에 한해 올바른 답을 보장한다.
탐욕 알고리즘은 "지금 당장 가장 유리한 것을 집고 뒤돌아보지 않는다"는 지극히 단순한 직관을 알고리즘으로 형식화한 것이다. 거스름돈을 내줄 때 가장 큰 단위의 동전부터 집는 일상적 행동이 전형적 예로, 사람은 모든 조합을 따져 보지 않고도 큰 동전부터 쓰면 매수가 줄어든다는 것을 경험적으로 안다. 이처럼 탐욕 전략은 "전체를 보지 않고 눈앞의 최선만으로 결정"하기 때문에 구현이 간결하고 대개 다항 시간(흔히 O(n log n))에 끝나, 완전탐색이나 동적 계획법보다 압도적으로 빠르다. 바로 이 속도가 탐욕 알고리즘을 매력적으로 만들지만, 동시에 "국소 최적의 연속이 과연 전역 최적인가"라는 정당성 문제가 늘 따라붙는다.
탐욕 알고리즘의 가치와 위험은 동전의 양면이다. 특정 조건을 만족하는 문제(최소 신장 트리, 허프만 부호화, 분수 배낭, 작업 스케줄링 등)에서는 탐욕이 증명 가능하게 최적해를 내지만, 조건이 깨지면 그럴듯하지만 명백히 틀린 답을 낸다. 따라서 탐욕 알고리즘을 다루는 기술사의 핵심 역량은 "탐욕으로 풀리는 문제인지를 먼저 판별하고, 풀린다면 탐욕 선택의 정당성을 논증하며, 풀리지 않으면 동적 계획법이나 완전탐색으로 전환"하는 설계 판단에 있다.
나. 등장 배경과 필요성
많은 최적화 문제는 가능한 해의 수가 입력 크기에 대해 지수적으로 폭증한다. 예컨대 n개의 작업을 어떤 순서로 처리할지, n개의 물건 중 무엇을 배낭에 담을지는 각각 n!·2ⁿ 규모의 경우의 수를 가져, 모든 경우를 나열하는 완전탐색(brute force)은 n이 조금만 커져도 현실적으로 불가능하다. 동적 계획법(DP)은 중복 부분 문제를 저장해 이 폭증을 다항 시간으로 억제하지만, 상태 공간이 크면 메모리와 시간이 여전히 부담스럽다. 이 지점에서 "모든 경우를 따지지 않고도 올바른 답에 도달하는 지름길"에 대한 요구가 생기며, 문제가 특정 구조를 가질 때 탐욕 알고리즘이 그 지름길을 제공한다.
여기서 중요한 점은, 완전탐색과 DP가 "모든 가능성을 어떻게든 훑는" 수동적 전략인 데 반해 탐욕은 "문제의 구조를 이해해 대부분의 가능성을 처음부터 쳐다보지 않는" 능동적 전략이라는 것이다. 이 차이는 단순한 속도 향상을 넘어, 문제에 내재한 질서(정렬 가능한 우선순위, 교환 가능한 요소, 매트로이드 구조)를 통찰해야만 탐욕이 성립한다는 뜻이기도 하다. 따라서 탐욕 알고리즘을 설계한다는 것은 곧 "이 문제의 어떤 성질이 전수 탐색을 불필요하게 만드는가"를 밝혀내는 작업이며, 이는 알고리즘 설계자의 문제 분석력을 가장 직접적으로 시험하는 영역이다.
또한 현실의 많은 시스템은 실시간성과 자원 제약 아래에서 "완벽하지 않아도 빠르고 충분히 좋은" 해를 요구한다. 네트워크 라우터는 밀리초 단위로 경로를 갱신해야 하고, 운영체제 스케줄러는 매 순간 다음 실행 프로세스를 즉시 골라야 하며, 데이터 압축기는 스트림을 지나가며 부호를 생성해야 한다. 이런 환경에서는 전체를 다시 계산하는 DP보다, 들어오는 정보에 대해 국소적으로 즉시 결정하는 탐욕 전략이 구조적으로 더 적합하다. 나아가 완전 최적해가 NP-난해(NP-hard)여서 다항 시간에 풀 수 없는 문제(집합 커버, 외판원 문제 등)에서는, 탐욕이 최적은 아니어도 보장된 근사비(approximation ratio)를 가진 실용적 해를 제공해 이론과 실무를 잇는다. 이처럼 탐욕 알고리즘은 "정확성을 조건부로 보장하는 빠른 최적화기"이자 "난해 문제의 믿을 만한 근사기"라는 이중의 필요성 위에 서 있다.
2. 탐욕 알고리즘의 동작 원리와 정당성 조건
탐욕 알고리즘이 옳게 작동하기 위한 두 가지 핵심 조건은 탐욕 선택 속성과 최적 부분 구조이다. 이 둘이 성립해야만 "국소 최적의 연쇄가 전역 최적"이라는 비약이 정당화된다.
flowchart TB
PROB["최적화 문제"] --> Q1{"탐욕 선택 속성 성립?"}
Q1 -->|"아니오"| DPFULL["동적 계획법 / 완전탐색 전환"]
Q1 -->|"예"| Q2{"최적 부분 구조 성립?"}
Q2 -->|"아니오"| DPFULL
Q2 -->|"예"| GREEDY["탐욕 알고리즘 적용 (최적해 보장)"]
GREEDY --> PROOF["정당성 증명: 교환 논증 / 매트로이드"]
탐욕 선택 속성이란 "전역 최적해 중 적어도 하나는 각 단계의 탐욕적 선택을 포함하도록 구성할 수 있다"는 성질이다. 즉 지금 집는 국소 최선이 최종 최적해의 일부가 될 수 있어야 한다. 이를 엄밀히 보이는 표준 기법이 교환 논증(exchange argument)이다. 임의의 최적해를 가정한 뒤, 그 해에서 탐욕이 고른 요소가 빠져 있다면 다른 요소와 맞바꾸어도 해가 나빠지지 않음을 보여, 탐욕 선택을 포함하는 최적해가 반드시 존재함을 증명한다. 예컨대 활동 선택 문제에서 "종료 시각이 가장 이른 활동을 먼저 고르는" 탐욕이 옳은 이유는, 임의 최적해의 첫 활동을 종료가 더 이른 탐욕 활동으로 바꿔도 이후 선택 가능한 활동이 줄지 않기 때문이다. 교환 논증은 탐욕 알고리즘의 정당성을 다루는 가장 보편적 도구이므로 반드시 숙지해야 한다.
교환 논증을 조금 더 구체적으로 보면, 그 뼈대는 "탐욕 해와 최적 해가 다르다면, 최적 해를 조금씩 탐욕 해 쪽으로 변형해도 품질이 떨어지지 않는다"를 보이는 것이다. 첫 선택이 다르면 최적 해의 첫 선택을 탐욕의 첫 선택으로 교체하고, 그래도 여전히 최적임을 확인한 뒤, 이 과정을 두 번째·세 번째 선택으로 반복한다. 모든 선택을 다 교체하고 나면 최적 해가 탐욕 해와 완전히 같아지므로, 결국 "탐욕 해도 최적"이라는 결론에 이른다. 이 귀납적 교체가 어느 단계에서든 품질을 해치지 않음을 증명하는 것이 교환 논증의 핵심이며, 바로 그 증명이 가능해야만 탐욕을 안심하고 채택할 수 있다.
최적 부분 구조란 "문제의 최적해가 부분 문제의 최적해로 구성된다"는 성질로, 탐욕이 한 요소를 확정한 뒤 남은 부분 문제 역시 같은 탐욕 전략으로 최적해를 얻을 수 있어야 함을 뜻한다. 이 성질은 동적 계획법도 공유하는데, 두 기법의 결정적 차이는 부분 문제를 푸는 방식에 있다. 동적 계획법은 여러 부분 문제의 해를 모두 구해 비교·조합하지만, 탐욕은 "탐욕 선택 하나로 부분 문제를 단 하나로 좁혀" 그 한 갈래만 따라 내려간다. 바로 이 "선택지를 하나로 줄여 되돌아보지 않음" 덕분에 탐욕이 DP보다 빠르지만, 그 선택이 틀리면 전체가 틀어지는 위험을 함께 진다.
flowchart LR
S0["전체 문제"] --> C1["탐욕 선택 1 (국소 최적)"]
C1 --> S1["축소된 부분 문제"]
S1 --> C2["탐욕 선택 2"]
C2 --> S2["더 작은 부분 문제"]
S2 --> DOTS["..."]
DOTS --> SOL["전역 최적해"]
C1 -. "되돌아보지 않음(irrevocable)" .-> C1
정당성이 보장되지 않는 대표 반례가 거스름돈 문제이다. 동전 단위가 {1, 5, 10, 25}처럼 정준(canonical) 체계이면 "큰 단위부터" 탐욕이 최소 매수를 보장하지만, {1, 4, 6} 체계에서 8을 거슬러 줄 때 탐욕은 6+1+1=3개를 택하는 반면 최적해는 4+4=2개다. 같은 문제라도 입력 조건(동전 체계)이 바뀌면 탐욕의 정당성이 무너진다는 이 사실은, 탐욕 알고리즘을 쓰기 전에 반드시 정당성을 검증해야 함을 선명하게 보여 준다. 검증 없이 "직관적으로 맞아 보인다"는 이유로 탐욕을 적용하는 것은 전형적 설계 오류다.
이 반례가 주는 교훈은 단순히 "탐욕이 가끔 틀린다"가 아니라, 국소 최적의 함정(local optimum trap)이라는 더 일반적인 구조적 한계를 드러낸다는 데 있다. 탐욕은 현재 선택이 미래에 미칠 파급을 보지 못한 채 눈앞의 이득만 좇으므로, "지금 조금 손해를 보더라도 나중에 크게 이득"인 경로를 원천적으로 탐색하지 못한다. {1, 4, 6} 체계에서 6을 집는 순간 남은 2를 1+1로밖에 채울 수 없게 되는 것이 바로 이 함정이다. 동적 계획법이 모든 선택지를 저장·비교해 이런 '지연된 이득'을 포착하는 것과 대조적으로, 탐욕은 그 한 갈래를 아예 버린다. 따라서 탐욕의 정당성 검증이란 본질적으로 "이 문제에는 국소 최적의 함정이 존재하지 않음"을 보이는 작업이며, 교환 논증은 바로 그 부재를 증명하는 도구다.
3. 설계 절차와 대표 알고리즘
이상의 두 조건을 갖춘 문제에서 탐욕 알고리즘의 설계는 대체로 공통된 절차를 따른다. 먼저 최적화 대상(목적 함수)을 정의하고, 매 단계의 탐욕 선택 기준(정렬 키)을 정한 뒤, 선택이 제약을 위반하지 않는지 검사하며 해를 누적하고, 마지막으로 교환 논증 등으로 정당성을 증명한다. 많은 탐욕 알고리즘이 "특정 기준으로 정렬한 뒤 앞에서부터 순회"하는 꼴을 가지므로 지배적 비용이 정렬의 O(n log n)인 경우가 많다([[sorting-algorithms]] 참조).
이 절차에서 가장 창의적이고 어려운 단계는 탐욕 선택 기준을 정하는 일이다. 나머지 단계(제약 검사·해 누적)는 기계적이지만, "무엇을 기준으로 가장 좋은 것을 고를 것인가"는 문제마다 다르고 잘못 고르면 곧바로 오답으로 이어진다. 그래서 숙련된 설계자는 그럴듯한 후보 기준을 여러 개 세운 뒤 각각에 대해 작은 반례를 적극적으로 찾아 걸러 내고, 반례가 나오지 않는 기준에 대해서만 교환 논증으로 정당성을 확정하는 방식으로 접근한다. 아래 흐름도는 이 공통 절차를 도식화한 것이다.
flowchart TB
START["문제 정의 · 목적함수"] --> SORT["탐욕 기준으로 후보 정렬"]
SORT --> LOOP{"남은 후보 있나?"}
LOOP -->|"예"| PICK["기준상 최선 후보 선택"]
PICK --> FEASIBLE{"제약 위반 없나?"}
FEASIBLE -->|"예"| ADD["해 집합에 추가"]
FEASIBLE -->|"아니오"| SKIP["건너뛰기"]
ADD --> LOOP
SKIP --> LOOP
LOOP -->|"아니오"| PROOF["정당성 검증 후 해 반환"]
가. 활동 선택과 작업 스케줄링
활동 선택 문제(activity selection)는 시작·종료 시각이 주어진 활동 집합에서 서로 겹치지 않는 최대 개수의 활동을 고르는 문제다. 탐욕 기준은 "종료 시각이 가장 이른 활동을 먼저 선택"이며, 선택한 활동과 겹치지 않는 다음 활동을 반복해 고른다. 종료가 이를수록 뒤에 남는 시간이 많아 더 많은 활동을 담을 여지가 커지기 때문에 이 기준이 옳다. 예컨대 회의실 하나에 (1–4), (3–5), (0–6), (5–7), (3–9), (5–9), (6–10), (8–11), (8–12), (2–14), (12–16) 열한 개 회의 요청이 있으면, 종료 시각순 탐욕은 (1–4)→(5–7)→(8–11)→(12–16) 네 개를 배정해 최적을 달성한다. 흥미롭게도 "가장 짧은 활동부터" 또는 "가장 일찍 시작하는 활동부터"라는 그럴듯한 다른 기준은 반례가 존재해 최적을 보장하지 못하는데, 이는 어떤 탐욕 기준을 고르느냐가 정당성을 좌우함을 보여 주는 중요한 교훈이다. 이 원리는 CPU 스케줄링, 강의실·설비 예약, 광고 슬롯 배치 등 자원 하나에 겹치지 않는 작업을 최대한 채우는 실무 문제에 폭넓게 적용된다. 변형으로 각 활동에 가치(weight)가 부여되어 "개수가 아니라 가치 합을 최대화"해야 하면, 단순 종료시각 탐욕은 더 이상 최적을 보장하지 못하고 가중 구간 스케줄링(weighted interval scheduling)이라는 동적 계획법 문제로 전환된다는 점도 함께 알아 두어야 한다. 이는 "활동마다 가치가 같다"는 숨은 전제가 탐욕의 정당성을 받치고 있었음을 드러내며, 전제가 바뀌면 기법도 바뀌어야 한다는 반복되는 교훈을 다시 확인시켜 준다.
나. 분수 배낭 문제
분수 배낭(fractional knapsack)은 용량 W의 배낭에 물건들을 담아 가치 합을 최대화하되 물건을 쪼개 담을 수 있는 문제다. 탐욕 기준은 "단위 무게당 가치(가치/무게)가 높은 물건부터 가득 담고, 마지막 물건은 남은 용량만큼 쪼개 담기"이다. 예를 들어 용량 50kg 배낭에 (가치 60, 무게 10), (가치 100, 무게 20), (가치 120, 무게 30) 세 물건이 있으면 단위가치는 각각 6, 5, 4이므로, 1번(10kg·60)→2번(20kg·100)을 통째로 담고 3번은 남은 20kg만큼(2/3) 담아 가치 60+100+80=240을 얻는다. 쪼갤 수 있으므로 단위가치 순서가 곧 최적 순서가 되어 탐욕이 정확히 최적해를 낸다.
그러나 물건을 쪼갤 수 없는 0/1 배낭으로 조건이 바뀌면 같은 탐욕이 최적을 보장하지 못한다. 용량 10kg에 (가치 60, 무게 10), (가치 70, 무게 10)... 같은 구성에서는 "단위가치 순서로 하나만 담기"가 더 가치 큰 조합을 놓칠 수 있기 때문이다. 0/1 배낭은 "담는다/안 담는다"의 조합을 따져야 하므로 탐욕 선택 속성이 깨지고, 동적 계획법(또는 분기한정)으로 풀어야 한다. 분수 배낭과 0/1 배낭의 이 극명한 대비는 "쪼갤 수 있는가"라는 제약 하나가 탐욕의 정당성을 가르는 결정적 요인임을 보여 주는, 기술사 답안에서 자주 쓰이는 대표 사례다([[dynamic-programming]] 참조).
다. 허프만 부호화
허프만 부호화(Huffman coding)는 문자별 출현 빈도에 따라 가변 길이 접두어 부호(prefix code)를 생성해 데이터를 무손실 압축하는 탐욕 알고리즘이다. 탐욕 기준은 "빈도가 가장 낮은 두 노드를 반복해서 합치기"로, 매 단계 최소 빈도 두 노드를 꺼내 합 노드로 묶어 이진 트리를 상향 구축한다. 자주 나오는 문자에는 짧은 부호를, 드문 문자에는 긴 부호를 부여해 평균 부호 길이가 정보 엔트로피에 근접하도록 만든다. 예컨대 문자 a·b·c·d·e·f의 빈도가 45·13·12·16·9·5라면, 허프만은 가장 드문 f(5)·e(9)를 먼저 합쳐 14를 만들고, 다음으로 작은 c(12)·b(13)를 합쳐 25를 만드는 식으로 트리를 상향 구축한다. 이렇게 완성된 트리에서 a는 1비트, 나머지는 3~4비트 부호를 받아, 고정 길이 3비트 부호(총 300비트 규모)보다 작은 약 224비트로 줄어든다 — 자주 쓰는 문자에 짧은 부호를 몰아준 효과다. 이 "최소 빈도 우선" 탐욕의 정당성 또한 교환 논증으로 증명되며(최적 트리에서 가장 깊은 두 잎은 빈도가 가장 낮은 두 문자로 바꿔도 손해가 없다), 최소 힙(우선순위 큐)을 쓰면 O(n log n)에 동작한다. 허프만 부호화는 JPEG·MP3·ZIP(DEFLATE)·PNG 등 광범위한 압축 표준의 엔트로피 부호화 단계에 실제로 내장되어, 탐욕 알고리즘이 산업 표준의 심장부에서 작동하는 대표 사례로 꼽힌다.
라. 그래프에서의 탐욕: 최소 신장 트리와 Dijkstra
그래프 문제에서도 탐욕은 핵심 설계 전략이다. 최소 신장 트리(MST)를 구하는 Kruskal 알고리즘은 "가중치가 가장 작은 간선부터, 순환을 만들지 않으면 채택"하는 탐욕이고, Prim 알고리즘은 "현재 트리에 가장 싸게 연결되는 정점을 하나씩 흡수"하는 탐욕이다. 둘 다 그래프의 컷 성질(cut property) — "임의의 컷을 가로지르는 최소 가중치 간선은 어떤 MST에 반드시 포함된다" — 에 의해 최적성이 보장된다. Kruskal은 간선을 정렬하고 유니온-파인드(Union-Find)로 순환을 검사해 O(E log E)에, Prim은 최소 힙을 써서 O(E log V)에 동작하며, 통신망 케이블 포설 최소화, 전력망 설계, 군집화(single-linkage clustering) 등에 쓰인다.
Kruskal과 Prim이 같은 MST를 서로 다른 순서로 쌓아 올린다는 점은 탐욕 전략의 유연성을 보여 준다. Kruskal이 "전체 간선을 가중치순으로 훑으며 숲(forest)의 조각들을 점차 합치는" 전역적 관점이라면, Prim은 "한 정점에서 출발해 트리를 한 겹씩 키우는" 국소 성장 관점이다. 어느 쪽이든 매 단계의 탐욕 선택(최소 간선·최소 연결 정점)이 컷 성질에 의해 안전함이 보장되므로 결과의 최적성은 동일하며, 간선이 많은 조밀 그래프에서는 Prim(인접 행렬 기반 O(V²))이, 희소 그래프에서는 Kruskal이 유리한 식으로 그래프 밀도에 따라 선택이 갈린다. 한편 앞서 다룬 [[shortest-path]]의 Dijkstra 알고리즘 역시 "미확정 정점 중 잠정 거리가 최소인 정점을 확정"하는 탐욕으로, 음이 아닌 가중치라는 조건이 탐욕 선택의 정당성을 떠받친다. 흥미롭게도 Prim과 Dijkstra는 "현재 집합에 가장 가까운 정점을 흡수"한다는 뼈대가 거의 같되, Prim은 '간선 가중치 자체'를, Dijkstra는 '출발점으로부터의 누적 거리'를 기준으로 삼는다는 점만 다르다. 이처럼 그래프 알고리즘의 상당수가 탐욕 패러다임 위에 서 있다는 점은 탐욕 전략의 설계적 보편성을 잘 보여 준다.
4. 비교: 탐욕 · 동적 계획법 · 완전탐색
최적화 문제를 푸는 세 가지 대표 패러다임인 탐욕·동적 계획법·완전탐색은 "얼마나 많은 경우를 따지는가"와 "정확성을 어디까지 보장하는가"에서 갈린다. 아래 표는 그 차이를 정리하되, 차이가 생기는 이유는 각 기법이 부분 문제를 다루는 방식에 뿌리를 둔다.
| 구분 | 탐욕 알고리즘 | 동적 계획법 | 완전탐색 |
|---|---|---|---|
| 핵심 전략 | 국소 최적 선택·되돌리지 않음 | 부분 문제 해 저장·조합 | 모든 경우 나열 |
| 부분 문제 처리 | 선택으로 하나로 좁힘 | 여러 해를 모두 비교 | 분기 전수 탐색 |
| 최적해 보장 | 조건 성립 시에만 | 항상(해당 구조에서) | 항상 |
| 시간 복잡도 | 대개 O(n log n) | 다항(상태 수×전이) | 지수(n!·2ⁿ) |
| 메모리 | 작음 | 상태 테이블만큼 큼 | 작음(재귀 스택) |
| 적합 상황 | 탐욕 선택 속성 성립 | 중복 부분 문제·최적 부분 구조 | 소규모·정확성 절대 |
탐욕과 동적 계획법은 둘 다 최적 부분 구조를 요구한다는 점에서 가깝지만, 탐욕 선택 속성의 유무가 둘을 가른다. 이 속성이 성립하면 "각 단계의 선택을 비교 없이 즉시 확정"할 수 있어 탐욕이 DP보다 지수적으로 빠르고 메모리도 거의 쓰지 않는다. 반대로 이 속성이 없으면(0/1 배낭처럼) 탐욕은 틀리고 DP로 모든 선택지를 저장·비교해야 한다. 따라서 실무적 함의는 "탐욕 선택 속성이 증명되면 탐욕을, 중복 부분 문제만 있으면 DP를, 둘 다 불확실하고 입력이 작으면 완전탐색을" 택하라는 것이다. 특히 같은 문제라도 제약 조건이 바뀌면 적합한 기법이 달라진다는 점(분수 배낭↔0/1 배낭)을 간과하면, 겉보기엔 정답 같지만 특정 입력에서 어긋나는 치명적 결함을 만든다.
복잡도의 차이를 수치로 체감해 보면 세 패러다임의 간극이 분명해진다. 입력 크기 n=40인 0/1 배낭을 완전탐색으로 풀면 2⁴⁰≈1조 가지를 따져야 해 현대 CPU로도 수십 분 이상 걸리지만, 용량 W가 1,000 수준이면 동적 계획법은 40×1,000=4만 개의 상태만 채워 밀리초에 끝난다. 반면 같은 물건을 쪼갤 수 있는 분수 배낭이라면 탐욕은 단위가치로 정렬하는 O(40 log 40)≈200여 연산이면 충분하다. 이처럼 "완전탐색 지수 → DP 다항 → 탐욕 준선형"으로 내려가는 비용 절감은 극적이지만, 그 절감은 각 단계에서 문제 구조에 대한 더 강한 가정을 대가로 산다 — DP는 최적 부분 구조를, 탐욕은 거기에 더해 탐욕 선택 속성을 요구한다. 공짜 점심은 없으며, 빠른 알고리즘일수록 적용 조건이 까다롭다는 이 원리가 패러다임 선택의 바탕이 된다.
세 기법의 관계를 한 문장으로 요약하면, 완전탐색은 "느리지만 항상 옳은 기준선", 동적 계획법은 "중복을 제거해 완전탐색을 다항으로 압축한 안전한 최적화기", 탐욕은 "특정 구조를 전제로 DP마저 한 갈래로 줄인 가장 빠른 최적화기"이다. 실제 시스템은 종종 이들을 결합한다 — 예컨대 0/1 배낭의 분기한정(branch and bound)은 완전탐색의 탐색 공간을 탐욕적 상한(분수 배낭 해)으로 가지치기해 실용 성능을 끌어올린다.
5. 심화: 매트로이드 이론과 근사 알고리즘
탐욕 알고리즘이 "언제 최적을 보장하는가"에 대한 가장 깊은 이론적 답은 매트로이드(matroid)에 있다. 매트로이드는 유한 집합과 그 부분집합들의 모임(독립 집합)이 유전성(hereditary)과 교환 성질(exchange property)을 만족하는 구조로, "어떤 문제가 가중 매트로이드로 표현되면 탐욕 알고리즘이 항상 최적해를 보장한다"는 정리(Rado-Edmonds)가 성립한다. 최소 신장 트리가 탐욕(Kruskal)으로 최적을 얻는 근본 이유도 그래프의 그래픽 매트로이드(graphic matroid) 구조에서 나온다. 이 이론은 "직관적으로 탐욕이 맞을까"를 넘어 "탐욕이 맞을 충분조건이 무엇인가"를 수학적으로 규명한다는 점에서, 개별 교환 논증을 일반화하는 강력한 틀이다. 다만 모든 탐욕 성공 사례가 매트로이드로 설명되는 것은 아니며(활동 선택 등은 더 약한 조건으로도 성립), 매트로이드는 충분조건이지 필요조건은 아니다. 매트로이드 이론이 실무에 주는 함의는, 새로운 최적화 문제를 만났을 때 "이 문제의 해 집합이 유전성과 교환 성질을 만족하는가"를 점검함으로써 탐욕 적용 가능성을 구조적으로 선판별할 수 있다는 데 있다. 두 매트로이드의 교집합(matroid intersection)까지는 여전히 다항 시간에 풀리지만 세 개 이상의 교집합은 NP-난해로 넘어간다는 경계도 알려져 있어, 문제를 몇 개의 매트로이드 제약으로 환원할 수 있느냐가 탐욕·다항 알고리즘의 적용 한계를 가늠하는 이론적 잣대가 된다.
탐욕의 또 다른 중요한 무대는 근사 알고리즘(approximation algorithm)이다. NP-난해 최적화 문제는 다항 시간에 최적해를 구할 수 없다고 여겨지므로, 실무에서는 "최적은 아니지만 최적 대비 일정 비율 이내임을 보장하는" 근사해로 타협한다. 대표적으로 집합 커버(Set Cover) 문제에서 "아직 덮지 못한 원소를 가장 많이 덮는 집합을 반복 선택"하는 탐욕은 ln n 배 근사비를 보장하며, 이는 P≠NP 가정 아래 이론적으로 거의 최선의 근사비임이 알려져 있다. 외판원 문제(TSP)의 최근접 이웃(nearest neighbor) 탐욕이나, 작업 부하 분산의 최장 작업 우선(LPT) 탐욕도 보장된 근사비를 가진 실용적 해법이다. 이처럼 탐욕은 "정확한 최적화기"일 뿐 아니라 "난해 문제의 믿을 만한 근사기"로서, 정확성을 일부 양보하는 대신 다항 시간과 성능 보장을 얻는 전형적 트레이드오프를 구현한다.
근사 알고리즘에서 탐욕이 특히 선호되는 이유는 단순성과 분석 가능성에 있다. 지역 탐색·유전 알고리즘·정수 계획법 같은 대안은 더 좋은 해를 낼 수 있으나 수렴성·실행 시간을 사전에 보장하기 어려운 반면, 탐욕 근사는 구현이 간단하면서도 "최적해의 몇 배 이내"라는 최악의 경우 보장(worst-case guarantee)을 수학적으로 증명할 수 있다. 예컨대 여러 기계에 작업을 분배해 완료 시각을 최소화하는 문제에서 LPT(긴 작업 우선) 탐욕은 최적 대비 (4/3 − 1/3m) 이내임이 증명되어, 실무에서 "이 스케줄은 아무리 나빠도 최적보다 33% 이상 나쁘지 않다"는 식의 명확한 품질 약속을 할 수 있다. 이런 보장의 존재 여부가 운영 환경에서 알고리즘을 신뢰하고 채택할 수 있는지를 가르는 결정적 요소이며, 바로 이 점이 탐욕 근사가 수많은 스케줄러·배치 시스템의 기본 전략으로 자리 잡은 배경이다.
최근 동향으로는 온라인·스트리밍 환경에서의 탐욕이 주목받는다. 전체 입력을 미리 볼 수 없이 데이터가 흘러 들어오는 상황(온라인 광고 할당, 실시간 매칭, 스트리밍 집합 커버)에서는 되돌아보지 않는 탐욕의 성질이 오히려 자연스러운 적합성을 갖는다. 온라인 이분 매칭의 RANKING 알고리즘이 1−1/e 경쟁비를 달성하는 것처럼, 탐욕 기반 온라인 알고리즘의 경쟁 분석(competitive analysis)은 활발한 연구 영역이다. 또한 준모듈러 함수(submodular function) 최대화에서 탐욕이 1−1/e 근사를 보장한다는 결과는 추천 시스템·데이터 요약·센서 배치 등 현대 AI·데이터 응용에서 탐욕의 이론적 토대를 제공하며, 탐욕 알고리즘이 고전 자료구조를 넘어 최신 분야로 확장되고 있음을 보여 준다.
6. 고려사항 및 시사점
지금까지 살펴본 탐욕 알고리즘의 원리·사례·이론을 실제 시스템 설계로 옮길 때, 기술사는 단순히 "빠르다"는 이유로 탐욕을 선택하기보다 정당성·적용 조건·대안과의 관계를 종합적으로 판단해야 한다. 다음은 그 판단에서 핵심적으로 고려해야 할 사항이다.
정당성 증명 없는 탐욕 적용을 경계한다. 탐욕은 "직관적으로 맞아 보인다"는 이유만으로 채택해서는 안 되며, 교환 논증이나 매트로이드 구조로 탐욕 선택 속성과 최적 부분 구조를 반드시 검증해야 한다. 거스름돈·0/1 배낭처럼 조건이 바뀌면 탐욕이 틀리는 사례가 흔하므로, 요구사항 분석 단계에서 "이 문제가 정말 탐욕으로 풀리는가, 반례는 없는가"를 선제적으로 점검해 '그럴듯하지만 틀린' 해를 배제해야 한다.
문제 조건과 제약에 따라 기법을 전환한다. 같은 배낭 문제도 '쪼갤 수 있는가'에 따라 탐욕(분수)과 DP(0/1)로 적합한 기법이 갈리고, 그래프의 음수 간선 유무가 Dijkstra(탐욕) 적용 가능성을 좌우한다. 탐욕 선택 속성이 성립하면 탐욕을, 중복 부분 문제만 있으면 DP를, 입력이 작고 정확성이 절대적이면 완전탐색을 택하는 식으로, 조건을 진단해 올바른 패러다임을 선택하는 설계 판단이 핵심이다.
탐욕 기준(정렬 키)의 선택이 정당성을 결정한다. 활동 선택에서 '종료 시각 우선'은 최적이지만 '가장 짧은 활동 우선'은 반례가 있듯, 동일 문제라도 어떤 기준으로 탐욕적 선택을 하느냐가 정답과 오답을 가른다. 따라서 여러 후보 기준을 비교하고 각각의 반례를 검토해 정당성이 증명된 기준만 채택해야 하며, 이 과정을 생략하면 특정 입력에서만 실패하는 잠복 결함을 낳는다.
근사와 정확성의 트레이드오프를 서비스 요구에 맞춰 조율한다. NP-난해 문제에서는 최적해 대신 탐욕 근사해가 현실적 선택이며, 집합 커버의 ln n 근사처럼 보장된 근사비를 아는 것이 중요하다. 실시간성·자원 제약이 큰 시스템(라우팅·스케줄링·스트리밍)에서는 '완벽한 최적'보다 '빠르고 충분히 좋은' 탐욕해가 합리적일 수 있으므로, 정확성·응답성·자원의 균형점을 SLA와 비용 관점에서 판단해야 한다.
구현상의 함정과 경계 사례를 검증한다. 탐욕은 대개 정렬 후 순회 구조이므로 정렬 안정성·동률(tie) 처리 규칙을 명시해야 재현성 있는 결과를 얻는다. Kruskal의 유니온-파인드 경로 압축 누락, 허프만 트리의 빈도 동률 처리, 활동 선택의 경계(종료=시작) 조건 등 작은 구현 오류가 최적성을 깨뜨릴 수 있으므로, 도달 불가·빈 입력·동일 가중치 같은 경계 사례에 대한 검증을 설계에 포함한다.
탐욕과 다른 패러다임의 결합을 적극 활용한다. 탐욕은 단독으로 쓰일 뿐 아니라 다른 기법의 가속·초기화 수단으로도 유용하다. 분기한정은 탐욕적 상한으로 완전탐색을 가지치기하고, 지역 탐색(local search)과 메타휴리스틱은 탐욕해를 초기해로 삼아 개선하며, 매트로이드 교집합 같은 확장 이론은 탐욕의 적용 범위를 넓힌다. 이처럼 탐욕을 전체 최적화 설계의 한 구성 요소로 바라보는 통합적 관점이 실무 문제 해결력을 높인다.
종합하면 탐욕 알고리즘은 "매 순간 최선을 집고 되돌아보지 않는다"는 단순한 전략이지만, 그 정당성은 탐욕 선택 속성과 최적 부분 구조, 나아가 매트로이드라는 깊은 구조에 의해 뒷받침된다. 조건이 성립하면 탐욕은 최소 신장 트리·허프만 부호화·활동 선택처럼 증명 가능한 최적해를 다항 시간에 제공하고, 난해 문제에서는 보장된 근사비로 실용적 해를 내놓는다. 기술사는 문제의 구조를 정확히 진단해 탐욕·동적 계획법·완전탐색 중 올바른 패러다임을 선택하고, 정당성을 논증하며, 정확성과 성능의 균형점에서 기법을 조합하는 역량을 갖추어야 한다.
참고자료
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, "Introduction to Algorithms" (3rd/4th ed.), Chapter 16: Greedy Algorithms, MIT Press. https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
- D. A. Huffman, "A Method for the Construction of Minimum-Redundancy Codes", Proceedings of the IRE, 1952. https://ieeexplore.ieee.org/document/4051119
- J. Edmonds, "Matroids and the greedy algorithm", Mathematical Programming, 1971. https://link.springer.com/article/10.1007/BF01584082
- V. Chvátal, "A Greedy Heuristic for the Set-Covering Problem", Mathematics of Operations Research, 1979. https://pubsonline.informs.org/doi/10.1287/moor.4.3.233
한 줄 요약: 탐욕 알고리즘은 매 단계 국소 최적을 선택하고 되돌리지 않는 전략으로, 탐욕 선택 속성과 최적 부분 구조(나아가 매트로이드)가 성립하면 최소 신장 트리·허프만 부호화·분수 배낭처럼 다항 시간에 최적해를 보장하지만 조건이 깨지면 틀린 답을 내므로, 정당성을 교환 논증으로 검증하고 동적 계획법·완전탐색과의 경계를 진단해 올바른 패러다임을 선택하는 것이 핵심이다.