독립(independence)이란 무엇인가 (3): 그리디 알고리즘이 성립하는 매트로이드
탐욕 알고리즘은 왜 매트로이드 위에서 항상 최적인가
수많은 알고리즘 중에서 탐욕 알고리즘은
가장 단순하면서도 동시에 가장 위험한 방식이다.
탐욕 알고리즘이란 문제를 풀 때, 매 순간 가장 좋아 보이는 선택만을 반복하는 방식을 말한다.
다시 말해, 지금 이 순간 국소적으로 최선이라 판단되는 것을 고르고 그렇게 쌓인 선택들이 결국 전체적으로도 최선이 되기를 기대하는 방법이다.
예시적인 질문은 항상 이렇다.
지금 당장 가장 비용이 적거나 효율적인 선택을 했는데
나중에 이 선택을 되돌릴 수 없다면
정말 이 선택은 전체적으로도 옳은 판단이었을까
이 방식은 빠르고 간결하다.
그러나 대부분의 경우, 탐욕 알고리즘은 실패한다. 지금 적은 비용을 보이는 선택이 결국 전체 비용을 증가시킬 수 있기 때문이다.
당장의 최선이 전체적 최선으로 이어진다는 보장이 없기 때문이다.
그럼에도 불구하고
수학자들은 어떤 문제에서는 이 단순한 방식이 항상 옳다는 사실을 발견했다. 바로 그 조건이 매트로이드라는 구조이다.
매트로이드 위에서 탐욕 알고리즘은 항상 전체적으로도 최선의 결과를 만들어낸다.
따라서 이 글에서는 다음과 같은 질문을 본격적으로 파고든다.
탐욕 알고리즘은 왜 실패할 수밖에 없는 방식인가
그런데 왜 매트로이드 위에서는 그것이 항상 옳아지는가
매트로이드의 공리와 탐욕 알고리즘의 동작 원리는 어떻게 맞물리는가
이 정당성은 어떤 수학적 직관 위에 놓여 있는가
탐욕 알고리즘은 어떤 구조 위에서만 성공하는가
탐욕 알고리즘(Greedy Algorithm)은 매 순간 가장 좋아 보이는 선택을 반복하여 전체 해답을 구성하려는 방식이다.
이 알고리즘은 간단하고 빠르며 과거의 선택을 되돌아보지 않는다.
그러나 이 방식이 항상 정답을 보장하는 것은 아니다.
탐욕 알고리즘이 실제로 옳은 결과를 내기 위해서는 그 작동 방식 자체가 어떤 구조 위에 놓여 있어야 한다.
탐욕 알고리즘의 단계 요약
탐욕 알고리즘은 다음과 같은 단계를 따른다.
- 선택 가능한 모든 후보 요소들을 정리한다.
- 정해진 기준에 따라 이들을 정렬한다.
- 가장 우선순위가 높은 항목을 선택한다.
- 해당 항목이 조건을 만족하면 포함하고, 아니면 제외한다.
- 더 이상 고려할 요소가 없을 때 종료하고 결과를 반환한다.
이 단순한 방식은
기저적으로는 정렬 기준, 조건 판별, 선택의 비가역성이라는 세 가지 축 위에 놓인다.
탐욕 알고리즘의 구체적인 각 단계
후보 정렬 – 정렬 기준은 왜 필요한가.
탐욕 알고리즘은 각 요소를 “좋아 보이는 순서”로 정렬한다. 이 순서가 없으면 탐욕은 작동하지 않는다.
좋아 보인다는 건 단순한 감각이 아니라 문제마다 정해진 평가 기준에 따라
각 항목에 우선순위(priority)를 부여한다는 뜻이다.
예를 들어 그래프에서는 비용이 낮은 간선이 우선 고려되고 배낭 문제에서는 가치 대비 무게 비율이 높은 물건이 먼저 선택된다.
정렬 기준이 잘못 설정되면 탐욕 알고리즘은 출발부터 잘못된 방향으로 흐르게 되고 당연히 최적 해가 될 수 없다.
선택 시 조건 검증 – 조건의 의미와 역할.
가장 우선순위가 높은 항목이라 해도 문제의 핵심 제약조건을 만족하지 않으면 선택되지 않는다.
이 조건은 문제의 구조를 유지하는 핵심 기준이다. 그래프 문제에서는 사이클이 생기지 않아야 하고 벡터 선택 문제에서는 선형 독립성이 유지되어야 하며 작업 스케줄링에서는 시간 충돌이 없어야 한다.
조건 검증이 없다면 탐욕 알고리즘은 단순히 가장 좋아 보이는 걸 누적하는 비논리적 선택이 된다.
선택/배제 결정 – 알고리즘의 비가역성.
탐욕 알고리즘은 한 번 결정하면 되돌아보지 않는다. 건너뛴 후보는 다시 고려하지 않으며 한 번 선택된 항목도 수정되지 않는다.
이 일방향성은 알고리즘의 단순함을 보장하지만 바로 그렇기 때문에 구조적 정당성이 없는 문제에서는 위험 요소가 된다.
종료 및 결과 해석 – 이 선택이 왜 해답이라 주장하는가.
모든 후보를 평가하고 선택 과정을 마쳤을 때 탐욕 알고리즘은 그 결과를 ‘해답’이라 주장한다.
하지만 그 주장이 정당하려면 그 결과가 전체 가능한 조합들 중 최적해와 같거나 최소한 동등해야 한다.
이 지점에서 탐욕 알고리즘은 논리적으로 질문을 떠안게 된다. “지금까지의 선택이 정말 전체적으로도 옳은 선택이었는가.”
탐욕 알고리즘이 실패하는 구조적 이유
1. 정렬 기준이 전체 최적을 보장하지 않는다
탐욕 알고리즘은 항상 정해진 기준에 따라 후보를 정렬한 뒤, 순서대로 선택한다.
하지만 이 정렬 기준이 문제의 전체 구조를 고려하지 않는다면,
→ 처음 선택이 아무리 좋아 보여도
→ 나중에 더 좋은 조합을 완전히 놓치게 된다.
예:
- 무게 제한: 50
- 물건 1: 무게 10, 가치 60 (비율 6)
- 물건 2: 무게 20, 가치 100 (비율 5)
- 물건 3: 무게 30, 가치 120 (비율 4)
탐욕 알고리즘은 물건 1, 2를 선택 (총 가치 160)하지만, 최적해는 물건 2, 3 선택 (총 가치 220)
즉, 탐욕 선택은 되돌릴 수 없기 때문에, 잘못된 기준은 전역 최적을 막는다.
2. 조건 검증이 없으면 문제의 구조를 위반하게 된다
탐욕 알고리즘은 좋아 보인다고 무작정 선택하는 것이 아니다.
반드시 문제가 요구하는 제약 조건을 만족해야만 선택이 유효하다.
예 1: 그래프
간선을 선택할 때
→ 사이클이 생기면 트리가 아니다
→ 트리가 아니면 불필요한 간선이 포함된다
→ 불필요한 간선은 비용을 늘리고, MST 조건을 위반하게 된다
예 2: 선형대수
벡터를 선택할 때
→ 이미 선택된 벡터들의 선형결합으로 표현 가능한 벡터를 고르면
→ 새로운 방향을 추가하지 못하게 되고
→ 전체 공간을 생성할 수 없게 된다
즉, 조건 검증을 생략하면 구조의 핵심 제약(독립성)을 위반하게 되며 전체 구성이 불가능한 상태에 도달하게 된다.
3. 탐욕 알고리즘은 선택을 되돌릴 수 없다.
탐욕 알고리즘은 한 번 선택한 것을 다시 되돌아가서 고치지 않는다.
이 성질은 효율을 주지만 동시에 돌이킬 수 없는 구조적 리스크를 만든다.
예:
일정 스케줄링 문제에서
→ 먼저 마감이 느리지만 효율이 높은 작업을 선택하면
→ 나중에 마감이 빠른 작업을 수행할 수 없게 되어
→ 전체 스케줄이 실패하게 된다
즉, 탐욕 알고리즘은 과거 선택을 수정하지 않는다.
한 번의 선택이 전체 해를 결정짓는다.
이 방식이 실패하지 않으려면 문제 구조 자체가 어떤 순서로 선택해도 최적에 도달하도록 되어 있어야 한다.
→ 매트로이드는 그런 구조다.
이 방식이 항상 통하는 구조 – 매트로이드 위에서의 정당성
탐욕 알고리즘이 실패하지 않기 위해선
→ 선택이 미래로 확장 가능해야 하며
→ 과거 선택이 전체 구조를 가로막지 않아야 한다.
매트로이드는 바로 그런 조건을 만족하는 수학적 구조다.
- 각 선택은 독립성을 유지하며
- 더 큰 독립 집합으로 확장될 수 있다
특히, 매트로이드의 확장 가능성 공리는 다음을 보장한다:
→ 탐욕적으로 하나씩 누적한 선택들이
→ 최종적으로 최적 독립 집합과 같은 크기, 같은 조건을 만족하게 된다
즉, 매트로이드는 되돌릴 수 없는 선택 흐름에서도 항상 최적 해에 도달할 수 있도록 논리적 확장 경로를 보장하는 구조이다.