코딩 테스트에서 탐욕법(Greedy Algorithm) 문제를 풀고 채점을 돌릴 때, "이게 과연 항상 정답을 보장할까?"라며 등골이 서늘해진 경험이 있으신가요? 그리디 알고리즘은 "미래는 생각하지 않고, 오직 현재 눈앞에 있는 최적의 이익만을 좇는다"는 직관적이고 맹목적인 전략입니다. 어떤 문제에서는 이 무식한 전략이 마법처럼 100% 최적해(Optimal Solution)를 찾아내지만, 배낭 문제(Knapsack)처럼 교묘한 함정이 있는 문제에서는 완전히 엉터리 답을 뱉어냅니다. 그렇다면 대체 언제 그리디를 써도 안전하고, 언제 쓰면 안 되는 것일까요? 내 직감이 맞았음을 수학적으로 완벽하게 증명하기 위해 등장한 개념이 바로 '매트로이드(Matroid)' 이론입니다. 오늘은 그리디가 성립하는 두 가지 필수 속성과, 이를 뒷받침하는 매트로이드의 기초 개념을 아주 쉽게 풀어서 해부해 봅니다.
1. 그리디가 100% 성공하기 위한 두 가지 필수 조건
알고리즘 교과서에서는 특정 문제에 그리디를 적용해도 안전하다는 것을 증명하기 위해 다음 두 가지 속성이 반드시 성립해야 한다고 강조합니다.
1-1. 탐욕적 선택 속성 (Greedy Choice Property)
"앞선 단계에서의 탐욕적인 선택이 이후 단계의 선택에 전혀 피해를 주지 않는다"는 성질입니다. 즉, 내가 지금 당장 눈앞의 100만 원을 집어 드는 행동이, 나중에 1,000만 원을 얻을 기회를 물리적으로 차단하지 않아야 합니다. 동전 거스름돈 문제에서 500원짜리로 먼저 크게 거슬러 주는 것이, 나중에 100원짜리로 거슬러 주는 것에 악영향을 미치지 않는 것과 같은 이치입니다. (단, 400원짜리 동전이 추가되는 순간 이 속성이 깨져버립니다.)
1-2. 최적 부분 구조 (Optimal Substructure)
"문제 전체에 대한 최적해가 부분 문제들의 최적해로 완벽하게 쪼개진다"는 성질입니다. A에서 B를 거쳐 C로 가는 최단 경로를 구했다면, 그 경로 중 A에서 B로 가는 구간 역시 A~B 간의 최단 경로여야만 한다는 수학적 사실입니다. 이 두 가지가 증명되면 그리디는 DP(동적 계획법)를 완벽히 대체할 수 있는 가장 빠른 치트키가 됩니다.
2. 매트로이드(Matroid): 그리디의 수학적 보증 수표
하지만 위 두 가지 속성을 실제 문제에서 논리적으로 증명하기란 여간 까다로운 일이 아닙니다. 1935년 해슬러 휘트니(Hassler Whitney)는 행렬(Matrix)의 독립성 개념을 확장하여 "어떤 문제의 구조가 매트로이드(Matroid)라는 특별한 수학적 구조를 띠고 있다면, 그 문제에 그리디를 적용했을 때 무조건 100% 최적해가 나온다"는 위대한 정리를 발표했습니다.
2-1. 매트로이드가 성립하기 위한 두 가지 규칙
어떤 데이터 집합(Set)이 다음 두 규칙을 만족하면 매트로이드 구조라고 부릅니다.
- 유전적 성질 (Hereditary Property): 어떤 집합이 규칙에 어긋나지 않는 올바른 상태(독립 집합)라면, 그 집합에서 원소를 아무거나 몇 개 빼내어 만든 부분 집합 역시 무조건 올바른 상태여야 합니다.
- 교환 성질 (Exchange Property / Augmentation): 크기가 서로 다른 올바른 두 집합 A와 B가 있을 때 (A가 원소를 더 많이 가짐), 큰 집합 A에 있는 원소 하나를 작은 집합 B로 넘겨주어도 B는 여전히 올바른 상태를 유지할 수 있는 원소가 A 안에 최소한 1개 이상 존재해야 합니다.
이 두 가지 외계어 같은 조건이 뜻하는 바는 명확합니다. "막힌 길이 없고, 언제든 다른 대안(교환)이 열려있으므로 눈치 보지 말고 당장 제일 좋아 보이는 놈부터 골라잡아도 절대 손해보지 않는다"는 것을 수학적으로 강력하게 보증해 주는 것입니다.
3. 크루스칼(Kruskal) 알고리즘과 매트로이드
매트로이드 구조의 가장 아름답고 대표적인 예시가 바로 최소 신장 트리(MST)를 구하는 크루스칼 알고리즘입니다. 크루스칼은 가중치가 가장 작은 간선부터 그리디하게 줍고 보는 무식한 알고리즘이지만 항상 100% 완벽한 정답을 도출합니다.
사이클(순환)이 없는 간선들의 모임을 '독립 집합'이라고 해봅시다. 사이클이 없는 간선 무리에서 선을 몇 개 빼도 여전히 사이클은 없습니다(유전적 성질 만족). 또한, 크기가 다른 두 개의 사이클 없는 트리가 있을 때, 큰 트리에서 간선을 하나 뽑아 작은 트리에 붙여도 사이클이 생기지 않도록 만들 수 있습니다(교환 성질 만족).
그래프의 간선 구조가 완벽한 매트로이드 성질을 띠고 있기 때문에, 크루스칼은 비용이 적은 것부터 맹목적으로 담는 탐욕적 선택을 하더라도 수학적으로 절대 오답이 나올 수 없는 완벽성을 부여받게 된 것입니다.
1. 그리디(Greedy) 알고리즘이 정답을 보장하려면, 당장의 선택이 미래에 피해를 주지 않는 탐욕적 선택 속성과 최적 부분 구조가 반드시 성립해야 합니다.
2. 이를 수학적으로 증명하는 틀이 매트로이드(Matroid) 이론이며, 어떤 문제의 구조가 유전적 성질과 교환 성질을 띤다면 그리디의 완벽한 정당성이 입증됩니다.
3. 최소 신장 트리를 구하는 크루스칼 알고리즘이 맹목적으로 저렴한 간선부터 골라도 항상 최적해를 내는 이유가 바로 그래프가 전형적인 매트로이드 구조를 이루고 있기 때문입니다.