그리디 알고리즘은 언제 통할까? - 매트로이드로 이해하기

이전에 읽으면 좋은 글

그리디 알고리즘(Greedy Algorithm)과 그 적용

그리디 알고리즘을 공부하다 보면 늘 궁금한 게 있다. 어떤 문제는 그리디로 최적해를 찾을 수 있고, 어떤 문제는 안 된다. 대체 그 차이가 뭘까?

 

이 질문의 답이 바로 매트로이드(Matroid)다. 이번 글에서는 매트로이드가 무엇인지, 왜 그리디 알고리즘과 관련이 있는지를 알아보려고 한다.

 

1. 그리디는 왜 실패할까?

먼저 그리디가 실패하는 경우를 살펴보자. 대표적인 예시가 배낭 문제(Knapsack Problem)다.

 

배낭 용량이 10이고, 다음 세 물건이 있다고 하자.

• 물건 A는 무게 6, 가치 6이다. 가치 밀도는 1.0이다.
• 물건 B는 무게 5, 가치 4.5다. 가치 밀도는 0.9다.
• 물건 C는 무게 5, 가치 4.5다. 가치 밀도는 0.9다.

그리디 알고리즘은 가치 밀도가 높은 A를 먼저 선택한다. 그러면 남은 용량이 4밖에 안 되어 B도 C도 담을 수 없다. 총 가치는 6이다. 하지만 최적해는 B와 C를 담는 것으로, 총 가치는 9다.

 

왜 그리디가 실패했을까? A를 선택한 순간 B와 C를 동시에 담을 공간이 사라졌다. 현재 해 {A}를 최적 해 {B, C}로 바꾸려면 여러 단계를 동시에 수행해야 한다. 그리디는 한 번에 한 걸음씩만 나아갈 수 있는데, 작은 해를 큰 해로 키울 방법이 없다.

 

2. 증강성

2.1. 증강성이란

반대로 그리디가 성공하는 경우를 보자. 최소 신장 트리(MST) 문제다.

 

최소 신장 트리와 프림(Prime), 크루스칼(Kuskal) 알고리즘

 

크루스칼 알고리즘은 간단하다. 모든 간선을 가중치 순으로 정렬하고, 작은 것부터 확인하면서 사이클을 만들지 않으면 선택한다. 이 단순한 전략이 항상 최적해를 찾는다.

 

이유를 이해하려면 증강성(Augmentation Property)이라는 개념이 필요하다. 그래프 이론에서 숲(forest)이란 사이클이 없는 간선 집합이다. 증강성은 다음을 의미한다.

두 숲 A와 B가 있고 B의 간선이 더 많다면, B의 어떤 간선을 A에 추가해도 여전히 숲이다.

 

2.2. 증강성이 성립하는 이유

이것이 왜 성립하는지 보자. 정점이 n개인 그래프에서 간선 a개를 가진 숲은 (n - a)개의 컴포넌트로 나뉜다. 간선 하나가 두 컴포넌트를 합칠 때마다 컴포넌트 수가 1씩 줄어들기 때문이다.

 

 

숲 A에 간선이 a개, 숲 B에 간선이 b개 있고 a < b라고 하자. 그러면 A는 (n - a)개의 컴포넌트를, B는 (n - b)개의 컴포넌트를 가진다. A의 컴포넌트가 더 많다.

 

B의 임의의 간선 e = (u, v)를 보자. 만약 B의 모든 간선이 A의 컴포넌트 내부만 연결한다면, B도 A만큼 많은 컴포넌트를 가져야 한다. 하지만 B의 컴포넌트가 더 적다는 모순이 생긴다. 따라서 B에는 A의 서로 다른 컴포넌트를 연결하는 간선이 반드시 존재한다. 그 간선을 A에 추가하면 사이클이 생기지 않는다.

 

이것이 왜 중요한가? 작은 해를 큰 해로 키울 수 있다는 뜻이다. 배낭 문제에서는 이게 불가능했지만, MST에서는 가능하다.

 

2.3. 증강성과 그리디의 연결

 

증강성이 왜 그리디를 정당화하는지 보자. 크루스칼 알고리즘이 만든 해를 A, 최적해를 B라고 하자. 만약 A가 B보다 작다면, 증강성에 의해 B의 어떤 간선을 A에 추가할 수 있다.

 

그런데 알고리즘은 이미 모든 간선을 가중치 순으로 확인했다. 그런 간선이 있었다면, 사이클을 만들지 않으므로 이미 선택했을 것이다. 모순이다. 따라서 A와 B는 같은 크기여야 하고, A도 최적해다.

 

3. 상속성

3.1. 상속성이란

증강성만으로는 부족하다. 상속성(Heredity Property)이라는 조건도 필요하다.

독립 집합의 부분집합도 독립 집합이다.

쉽게 말해, 좋은 조합의 일부분도 좋은 조합이어야 한다.

 

3.2. MST에서의 상속성

MST 문제에서 확인해보자. 사이클이 없는 간선 집합, 즉 숲에서 간선을 몇 개 빼면 어떻게 될까? 여전히 사이클이 없다. 간선을 빼서 갑자기 사이클이 생길 리는 없다.

 

3.3. 상속성의 필요성

이 성질은 왜 필요할까? 그리디는 원소를 하나씩 추가한다. 중간 단계의 해가 유효하지 않으면 잘못된 길로 갈 수 있다. 상속성은 지금까지 선택한 것들이 항상 유효한 부분해라는 것을 보장한다.

 

3.4. 배낭 문제와의 비교

배낭 문제와 비교해보자. 배낭 문제도 상속성은 만족한다. {A, B}가 배낭에 들어가면 {A}만으로도 들어간다. 하지만 증강성은 만족하지 않는다. 현재 해 {A}에 최적 해 {B, C}의 원소를 추가하려 해도 배낭 용량을 초과한다. 이것이 배낭 문제에서 그리디가 실패하는 이유다.

 

4. 매트로이드

 

4.1. 매트로이드의 정의

매트로이드(Matroid)는 원소들의 집합 S와 독립 집합들의 모임 I로 이루어진 구조 M = (S, I)다. 다음 두 조건을 만족해야 한다.

1. 상속성 - A ∈ I이고 B ⊆ A이면, B ∈ I
2. 증강성 - A, B ∈ I이고 |A| < |B|이면, B의 어떤 원소 x에 대해 A ∪ {x} ∈ I

4.2. 그래픽 매트로이드

그래프 G = (V, E)의 그래픽 매트로이드(Graphic Matroid)는 다음과 같다.

• 원소 집합 S = 모든 간선 E
• 독립 집합 I = 사이클이 없는 간선 집합들 (숲들)

앞서 확인했듯이 이 구조는 상속성과 증강성을 모두 만족한다.

 

4.3. 기저와 그 성질

더 이상 원소를 추가할 수 없는 독립 집합을 기저(basis)라고 부른다. 매트로이드에는 중요한 성질이 있다.

모든 기저의 크기가 같다.

두 기저 A와 B가 있고 |A| < |B|라고 하자. 증강성에 의해 B의 원소를 A에 추가할 수 있다. 하지만 A는 이미 기저이므로 더 이상 추가할 수 없다. 모순이다.

 

그래픽 매트로이드에서 정점이 n개일 때, 모든 기저는 정확히 (n-1)개의 간선을 가진다. 이것이 신장 트리다.

 

5. 가중치 매트로이드

5.1. 가중치 매트로이드와 그리디 알고리즘

실제 문제에서는 각 원소에 가중치가 있다. 가중치 매트로이드에서 목표는 가중치 합을 최대화하거나 최소화하는 독립 집합을 찾는 것이다.

 

그리디 알고리즘은 다음과 같다.

1. 원소들을 가중치 내림차순으로 정렬
2. 각 원소 x를 순서대로 확인
   - 현재 집합 A에 x를 추가해도 독립 집합이면 추가
   - 아니면 넘어감
3. 더 이상 추가할 수 없으면 종료

 

5.2. 그리디 알고리즘의 정당성

매트로이드에서 이 알고리즘은 항상 최적해를 찾는다. 증명의 핵심 아이디어는 교환 논증(exchange argument)이다.

 

그리디가 만든 기저를 G = {g₁, g₂, ..., gₖ}라 하자. 가중치 내림차순이다. 최적 기저를 H = {h₁, h₂, ..., hₖ}라 하자. 역시 가중치 내림차순이다.

 

만약 w(G) < w(H)라면, 어떤 첫 번째 위치 i에서 w(gᵢ) < w(hᵢ)다. 그 이전까지는 모두 w(g₁) ≥ w(h₁), ..., w(gᵢ₋₁) ≥ w(hᵢ₋₁)이다.

 

G' = {g₁, ..., gᵢ₋₁}와 H' = {h₁, ..., hᵢ}를 보자. |G'| = i-1 < i = |H'|이고 둘 다 독립 집합이다. 증강성에 의해 H'의 어떤 원소를 G'에 추가할 수 있다.

 

H' \ G'의 어떤 원소 hⱼ를 G'에 추가할 수 있다. j ≤ i이므로 w(hⱼ) ≥ w(hᵢ) > w(gᵢ)다. 그런데 그리디는 가중치가 큰 것부터 확인한다. hⱼ는 gᵢ보다 먼저 고려되었고, G' ∪ {hⱼ}가 독립 집합이므로 선택했어야 한다. 모순이다.

 

따라서 w(G) ≥ w(H)이고, H가 최적이므로 w(G) = w(H)다. 그리디 해도 최적해다.

 

6. 증강성을 보이는 방법

새로운 문제를 만났을 때 증강성을 어떻게 확인할 것인가? 완벽한 증명은 어렵지만, 자주 등장하는 패턴이 있다.

 

6.1. 기본 아이디어

증강성을 보이려면 다음을 확인해야 한다.

A, B가 독립 집합이고 |A| < |B|일 때, B의 어떤 원소를 A에 추가해도 독립 집합이다.

 

핵심은 A와 B의 구조적 차이를 찾는 것이다. 집합 크기가 다르면 구조도 달라진다. 이 차이를 이용해서 B의 원소 중 A에 추가 가능한 것을 찾는다.

 

6.2. 패턴 1: 컴포넌트/연결성 기반

그래픽 매트로이드가 대표적이다.

 

핵심 관찰

• 간선이 많을수록 컴포넌트가 적다
• |A| < |B|이면 A가 B보다 컴포넌트가 많다
• 이 역관계를 이용한다

접근 방법

1. 집합 크기와 역관계인 측정값을 찾는다 (예: 컴포넌트 수)
2. |A| < |B|이면 측정값이 f(A) > f(B)임을 보인다
3. B의 원소를 A에 추가할 수 있음을 보인다

그래픽 매트로이드에서는 B의 어떤 간선이 A의 서로 다른 컴포넌트를 연결한다. 그 간선을 A에 추가하면 사이클이 생기지 않는다.

 

6.3. 패턴 2: 카테고리/그룹 기반

분할 매트로이드가 대표적이다.

문제 설정

• n개의 그룹 P₁, P₂, ..., Pₙ이 있다
• 각 원소는 정확히 하나의 그룹에 속한다
• 독립 집합은 각 그룹에서 최대 하나씩만 포함한다

핵심 관찰

• |A| < |B|이면 A가 B보다 적은 그룹을 사용한다
• 비둘기집 원리로 B는 A가 안 쓴 그룹을 사용한다

접근 방법

A가 사용하는 그룹은 |A|개, B가 사용하는 그룹은 |B|개다. |A| < |B|이므로, B가 사용하는 그룹 중 A가 사용하지 않는 그룹이 최소 하나 존재한다. 그 그룹에서 B가 선택한 원소를 A에 추가하면 여전히 각 그룹에서 최대 하나씩만 선택한다.

 

6.4. 패턴 3: 시간/순서 기반

스케줄링 문제가 대표적이다.

 

문제 설정

• n개의 작업, 각 작업 i는 마감 dᵢ를 가진다
• 독립 집합은 마감을 지킬 수 있는 작업 집합이다

 

핵심 관찰

• 작업을 마감 순으로 정렬하면 시간대에 순서대로 배치할 수 있다
• |A| < |B|이면 A가 B보다 적은 시간대를 사용한다
• B의 어떤 작업은 A가 안 쓴 시간대에 배치 가능하다

구체적인 증명은 7.2절에서 다룬다.

 

7. 실전 적용

7.1. 문제 분석 프로세스

새로운 문제를 만났을 때 다음 단계를 따른다.

1단계. 독립 집합 정의

무엇이 "유효한 해"인지 명확히 정의한다. 보통 문제의 제약 조건을 만족하는 부분집합이 독립 집합이 된다.

2단계. 상속성 확인

독립 집합에서 원소를 빼면 여전히 독립 집합인가? 대부분의 경우 자명하다.

3단계. 증강성 증명

가장 중요하고 어려운 단계다.

 

3-1. A, B를 독립 집합이라 하고 |A| < |B|라고 가정한다.

 

3-2. A와 B의 구조적 차이를 분석한다. 컴포넌트 수인지, 사용한 그룹이나 카테고리 수인지, 차지한 시간대나 위치 수인지 파악한다.

 

3-3. 6장의 적합한 패턴을 선택한다.

 

3-4. B에서 A로 추가 가능한 원소 x를 찾는다.

 

3-5. A ∪ {x}가 독립 집합임을 확인한다.

 

4단계. 그리디 알고리즘 작성

5장의 그리디 알고리즘 템플릿을 따른다. 독립성 검사 함수만 구현하면 된다.

 

7.2. 예제: 작업 스케줄링으로 이해하기

문제 정의

n개의 작업이 주어진다. 작업 i는 다음 정보를 가진다.

• 마감 시간 dᵢ (1 이상의 정수)
• 이익 pᵢ (양의 실수)

각 작업은 정확히 1시간이 걸리고, 한 번에 하나씩만 처리할 수 있다. 시간대 1, 2, 3, ...이 있고, 작업을 시간대 t에 배치하면 시간 t에 완료된다.

 

작업 i를 시간대 t에 배치하려면 t ≤ dᵢ여야 한다. 마감을 지킨 작업들의 이익 합을 최대화하려고 한다.

 

독립 집합 정의

작업의 부분집합 S가 독립 집합이다 ⟺ S의 모든 작업을 마감 내에 완료할 수 있다.

 

즉, S의 작업들을 시간대에 배치했을 때, 각 작업 i ∈ S가 배치된 시간대 t가 t ≤ dᵢ를 만족하도록 할 수 있으면 S는 독립 집합이다.

 

상속성 증명

S가 독립 집합이고 T ⊆ S라고 하자. S의 작업들을 마감 내에 배치하는 방법이 존재한다. T의 작업들은 S의 부분집합이므로, S의 배치에서 T에 속하지 않는 작업들을 제거하면 T의 배치를 얻는다. 작업을 제거해도 마감 조건은 여전히 만족되므로, T도 독립 집합이다.

 

증강성 증명

A, B를 독립 집합이라 하고 |A| < |B|라고 하자.

 

A의 작업들을 마감 시간의 비내림차순으로 정렬한다. 이 순서대로 시간대 1, 2, ..., |A|에 배치하면 모든 마감을 지킬 수 있다. (k번째 작업의 마감은 최소한 k 이상이므로)

 

B \ A에서 마감이 가장 빠른 작업을 j라고 하자.

 

만약 d_j > |A|라면:

• A는 시간대 1부터 |A|까지만 사용한다
• 시간대 |A| + 1은 비어있다
• d_j > |A|이므로, 작업 j를 시간대 |A| + 1에 배치할 수 있다
• A ∪ {j}는 독립 집합이다

만약 d_j ≤ |A|라면:

• 좀 더 복잡한 분석이 필요하지만, 결론은 같다
• A가 사용하는 시간대와 마감 관계를 분석하면, j를 배치할 수 있는 시간대를 찾을 수 있다

어느 쪽이든 A ∪ {j}는 독립 집합이다.

 

그리디 알고리즘

1. 모든 작업을 이익 내림차순으로 정렬
2. 빈 집합 S = ∅으로 시작
3. 각 작업 i를 순서대로 확인:
   a. S ∪ {i}가 독립 집합인지 확인
      - S ∪ {i}의 작업들을 마감 순으로 정렬
      - k번째 작업의 마감이 k 이상인지 확인
   b. 독립 집합이면 S ← S ∪ {i}
4. S 반환

 

정당성

(S, I)는 매트로이드다. 5.2절의 정리에 의해 그리디 알고리즘은 최대 가중치 독립 집합을 찾는다. 따라서 최대 이익을 얻는 작업 집합을 찾는다.

 

7.3. 다른 매트로이드 예시들

 

1) 유니폼 매트로이드 (Uniform Matroid)

집합 S = {1, 2, ..., n}에서 독립 집합은 크기가 k 이하인 모든 부분집합이다.

 

증강성은 자명하다. |A| < |B| ≤ k이면, B의 원소 중 A에 없는 것을 추가해도 크기가 k 이하다.

 

2) 분할 매트로이드 (Partition Matroid)

원소 집합 S가 k개의 그룹 P₁, ..., Pₖ로 분할된다. 독립 집합은 각 그룹에서 최대 하나씩 선택한 집합이다.

 

증강성은 6.2절에서 증명했다.

 

 

7.4. 체크리스트

증명을 완성했다면 다음을 확인하자.

□ 독립 집합이 명확히 정의되었는가?

□ |A| < |B| 가정이 명시되었는가?

□ 구조적 차이가 정량적으로 표현되었는가? (컴포넌트 수, 차원, 그룹 수 등)

□ B에서 적어도 하나의 원소 x를 찾았는가?

□ A ∪ {x} ∈ I임을 확인했는가? (이유와 함께)

□ 모든 논리적 단계가 빠짐없이 연결되는가?

 

8. 정리

매트로이드는 그리디가 통하는 구조를 설명하는 개념이다.

 

매트로이드는 상속성과 증강성 두 조건으로 정의된다. 상속성은 대부분 자명하게 만족한다. 증강성은 확인이 필요하며, 핵심은 집합 크기와 구조적 특징의 관계를 분석하는 것이다.

 

증강성을 보이는 방법에는 일반적인 패턴이 있다. 컴포넌트 개수를 이용한 방법, 비둘기집 원리를 이용한 방법, 시간대를 이용한 방법이 대표적이다. 문제의 구조에 맞는 패턴을 선택하면 접근 방법을 찾을 수 있다.

 

새로운 문제를 만났을 때는 다음 과정을 따른다. 먼저 독립 집합을 정의한다. 상속성을 확인한다. A와 B의 구조적 차이를 찾는다. 적합한 패턴을 선택한다. 증강성을 확인한다. 그리디 알고리즘을 서술한다. 5.2절의 정리를 인용하여 최적성을 결론짓는다.

 

이론적으로 완벽하게 증명하는 것은 어렵지만, 6장의 패턴을 참고하면 많은 경우 접근 방법을 찾을 수 있다. 매트로이드는 그리디 알고리즘을 이해하는 강력한 도구다.