슈렉

문제 해결은 상태 정의에서 시작된다

동적계획법(DP)은 점화식과 관련이 깊다. 하지만 점화식은 상태 간의 관계를 수식화한 결과물에 불과하다.
사실 DP문제가 어려운 점은 그리고 DP 문제의 출발점은 ‘무엇을 상태로 잡을 것인가’라는 결정이다.

DP란 결국 문제를 쪼개어 푸는 방식이다. 그렇다면 먼저 물어야 할 질문은 다음과 같다.

이 문제를 어떤 기준에서 나눌 수 있는가?
그 나눔의 단위를 어떤 상태로 정의할 것인가?

상태란 문제를 구성하는 단위이자 그 단위 간 전이 구조를 정의하는 것이다.
DP를 정확히 이해한다는 것은 문제 상황을 일정한 단위로 나누고 그 단위 간 관계를 수식으로 표현할 수 있는 언어를 구성하는 일이다.

상태 정의는 몇 가지 구조로 나뉜다

▸ 단일 인덱스 기반 상태

• 이 구조에서 ‘상태’는 단 하나의 변수, 즉 진행 인덱스로만 정의된다.
  이때 인덱스 $i$는 문제를 구성하는 일련의 단계를 순서대로 따라가고 있다는 의미이다.
  중요한 점은, 이전에 어떤 선택이 이루어졌는지에 대한 정보가 전혀 필요하지 않다는 것이다.
  • 성립 조건
    1. 이전 상태의 선택 이력이 현재 선택 가능성에 영향을 주지 않아야 한다
       즉, 선택의 결과가 오직 현재 위치 $i$만으로 결정되어야 한다.
    2. 전이 조건이 $i$ 하나로 정의되어야 한다
       예: $f(i)=f(i-1)+f(i-2)$
       이 수식은 $i$ 앞의 두 인덱스에서 상태 값을 받아 현재를 구성한다. 그 외의 조건은 존재하지 않는다.
  • 예시
    피보나치 수열: 현재 항을 만들기 위해 필요한 것은 오직 두 항($i-1$, $i-2$)뿐이다.
    LIS 문제: 각 $i$에 대해 $A[i]$보다 작은 $A[j]$들 중 최대 $f(j)$를 찾으면 된다.
    이때 $j$가 어떤 경로로 왔는지, 그 이전에 어떤 수들이 선택되었는지는 전혀 중요하지 않다.
  • 전형적인 오류
    상태 $f(i)$만 정의해놓고, 실제로는 전이할 때 ‘최댓값’, ‘이전 선택값’, ‘조건’ 등을 추가로 참조하는 경우
    → 이 경우는 사실상 단일 인덱스 기반이 아니라 이중 인자 기반 상태로 재정의되어야 한다.

▸ 이중 인자 기반 상태 (인덱스 + 누적 조건)

여기서 상태는 두 개의 변수로 구성된다. 첫 번째는 여전히 ‘진행 인덱스’ $i$이며, 두 번째는 현재까지의 누적된 자원 혹은 제약 변수이다.
이 두 번째 변수는 현재 상태가 전이 가능한지를 판단하기 위한 제약 조건의 잔여치로 해석된다.

• 성립 조건
  1. 이전 선택이 남긴 자원 사용량이 이후 선택 가능성에 직접적인 영향을 미쳐야 한다
  2. 같은 인덱스라도 자원 상태에 따라 전이 결과가 달라져야 한다
     → $f(i,w)$, $f(i,c)$ 등의 형태가 된다. 이때 $w$는 잔여 무게, $c$는 잔여 비용 등이 될 수 있다.
• 예시
  0/1 배낭 문제: $f(i,w)=max(f(i-1,w),f(i-1,w-weigh{t}_i)+valu{e}_i)$
  → 현재 물건을 고를 수 있는지는 잔여 무게 $w$가 기준이 된다.
  제한 경로 탐색: 현재 노드 $u$에 비용 $b$로 도달했을 때의 상태 $f(u,b)$를 정의함. 다음 노드 $v$로 가는 데 드는 비용 $c$에 따라 전이 가능성이 결정된다.
• 오류 지점
  전이 조건에서 $w$ 순회를 잘못 설정하거나, 0/1 배낭에서 같은 물건을 두 번 고르는 실수를 하는 경우
  → 이 경우는 전이 방향을 잘못 구성했거나 상태 정의 자체가 불완전한 것이다.

▸ 조합 기반 상태 (선택 이력 의존형)

이 구조에서는 상태 정의에 현재까지의 선택 집합 또는 이력 정보를 포함해야 한다.
즉, 단일 인덱스나 누적 값으로는 상태를 완전히 식별할 수 없고, 어떤 조합이 선택되었는지를 명시적으로 포함시켜야 한다.

• 성립 조건
  1. 이전까지의 선택 조합이 이후의 선택 가능성을 결정해야 한다
  2. 동일한 인덱스라도 선택 이력에 따라 전이 방향과 결과가 달라져야 한다
• 예시
  외판원 순회(TSP): $f(S,u)$ 형태의 상태. $S$는 지금까지 방문한 정점들의 집합, $u$는 현재 위치한 정점
  → 전이: 아직 방문하지 않은 정점 $v$에 대해
  $f(S,u)=\underset{v\notin S}{min}(f(S\cup v,v)+dist(u,v))$
  순열 구성: 비트마스크 $mask$로 어떤 원소를 이미 선택했는지 표현, 남은 원소의 선택은 $mask$에 따라 달라짐
• 주의할 점
  상태 공간이 $O(2^n)$ 이상으로 커질 수 있음
  → 비트마스크 등의 압축 표현이 필수적이며, 메모이제이션이 없다면 실현 불가

▸ 다차원 인덱스 기반 상태 (이중 진행 축 구조)

문제를 구성하는 두 개의 독립적인 축이 동시에 전개될 때, 두 인덱스를 함께 상태로 포함한다.
여기서 두 인덱스는 단순히 서로 다른 위치가 아니라 서로 다른 차원의 진행 상태이다.

• 성립 조건
  1. 두 차원의 현재 위치가 모두 필요해야 현재 상황을 완전히 규정할 수 있다
  2. 전이가 두 축의 위치 조합에 따라 결정되어야 한다
• 예시
  최장 공통 부분 수열(LCS): 상태 $f(i,j)$는 각각 문자열 A, B의 위치
  → 전이: 두 문자가 같으면 대각선 이동, 다르면 좌 또는 상 방향 중 큰 값 선택
  격자 DP: $f(i,j)$는 격자 좌표, 전이는 $(i-1,j)$ 또는 $(i,j-1)$에서 결정됨
• 오류 사례
  격자 DP에서 $i$와 $j$ 중 하나만 상태로 정의하거나, 좌표 이동을 혼동하여 불가능한 전이를 시도하는 경우

▸ 구간 기반 상태 (범위 단위 분할 구조)

두 개의 인덱스를 사용하는 경우라도, 이들이 ‘서로 다른 축의 위치’가 아니라 연속된 구간의 양 끝을 나타내는 경우, 상태는 구간 전체를 단위로 정의해야 한다.

• 성립 조건
  1. 하나의 상태가 특정 구간 [$l$, $r$] 전체를 의미해야 한다
  2. 전이는 이 구간을 중간 지점 $k$에서 분할하고, 양쪽 결과를 결합하는 구조여야 한다
• 예시
  행렬 곱셈 최적화: $f(l,r)=\underset{l\le k<r}{min}(f(l,k)+f(k+1,r)+cost(l,k,r))$
  회문 분할: 문자열 [$l$, $r$]이 회문인지 판단하고, 최소 분할 횟수를 계산
• 전이 핵심
  전이는 항상 어떤 중간 지점에서 범위를 쪼개고, 두 하위 구간 결과를 병합하는 구조여야 한다.

▸ 트리 기반 상태 (계층 구조 전이)

문제의 대상이 트리 구조를 따르고 전이가 인덱스나 좌표가 아닌 노드 간의 계층 관계를 기반으로 정의된다면 상태는 선형 인덱스가 아니라 노드의 위치와 그 하위 구조에 의해 결정되어야 한다.

이 구조는 다음 조건에서 등장한다:

• 문제의 입력이 트리 구조이며
• 전이가 부모 → 자식 또는 자식 → 부모 방향으로 구조적 흐름을 따를 때

예를 들어, 트리 최대 독립 집합(Tree Maximum Independent Set) 문제를 보자. 각 노드의 선택 여부에 따라 자식 노드의 선택 가능성이 달라지며, 상태는 $f(u,0)$ 또는 $f(u,1)$처럼 노드 $u$와 선택 여부로 정의된다.

전이는 다음과 같이 구성된다:

• 부모 노드를 선택하지 않은 경우, 자식 노드를 선택해도 된다
• 부모 노드를 선택한 경우, 자식 노드는 반드시 제외해야 한다

따라서 전이는 단순히 인덱스를 증가시키는 방식이 아니라, 트리의 구조를 따라 전개되는 종속 흐름이다.

또한 서브트리에서 어떤 값을 집계하는 문제들도 이 구조에 포함된다. 예를 들어 서브트리 합, 서브트리 내 최댓값, DFS 순회 기반 DP 등은 항상 자식 → 부모 또는 루트 → 리프 방향의 전이 흐름을 가진다.

상태가 트리 구조상의 노드 단위로 정의되며 전이가 인접한 인덱스가 아닌 계층적 구조 흐름에 따라 전개된다면 트리 기반 상태 정의가 필요하다.

상태 정의는 실패할 수 있다

DP에서 상태는 문제를 나누는 기준이자, 점화식이 성립하기 위한 전제 조건이다. 상태를 제대로 정의하지 못하면 점화식을 구성할 수 없거나, 상태 공간이 과도하게 커지거나 전이 구조가 성립하지 않아 알고리즘 전체가 무너질 수 있다.

실제로 자주 발생하는 상태 정의 실패는 아래 세 가지 유형으로 나뉜다.

불필요한 정보를 상태에 포함하면 상태 수만 증가하고, 의미는 달라지지 않는다.
이 경우 점화식은 구성되지만 동일한 계산을 여러 상태에서 반복하게 되므로 시간과 공간 효율이 크게 나빠진다.

예시
$f(i,sum,last)$에서 last는 전이 과정에 전혀 영향을 주지 않는데도 상태에 포함한 경우
→ last 값만큼 상태가 중복 생성되며, 점화식의 전이 대상도 불필요하게 많아진다.

▸ 불완전 정의 (under-specified)

전이에 반드시 필요한 정보가 상태에 포함되지 않으면 점화식을 만들 수 없다.
이런 상태는 전이 대상이 명확하지 않기 때문에 점화식이 모호해지거나 구현이 불가능해진다.

예시
격자에서 이동 경로를 계산하는데,
이전에 어떤 방향으로 움직였는지를 알아야 전이 조건이 달라지는 경우
→ 방향 정보가 빠진 상태에서는 그 전이 조건을 판단할 수 없다.

▸ 불안정 정의 (untracked condition)

문제 조건 중에서 ‘특정 조건을 만족한 적이 있는가’와 같은 이력이 전이 조건에 영향을 주는 경우
이 정보가 상태에 반영되지 않으면 전이 결과가 달라질 수 있어 점화식은 잘못된 경로를 따라갈 수 있다.

예시
“출발점에서 반드시 특정 지점을 한 번 이상 지나야 한다” 같은 조건이 있는데 그 지점을 지났는지 여부를 상태에 포함하지 않음
→ 올바른 해를 걸러낼 수 없고, 잘못된 해가 함께 저장된다.

상태 공간은 줄일 수 있어야 한다

상태를 잘 정의했더라도 전체 상태 공간의 크기가 크다면 효율적인 알고리즘을 구성하기 어렵다.
이를 해결하기 위한 대표적인 상태 공간 축소 기법은 다음과 같다.

▸ 롤링 배열 (rolling array)

전이가 이전 몇 개의 상태에만 의존한다면 전체 테이블을 만들지 않고 일부만 유지하면 된다.
배열을 순환하거나 교체하며 공간을 줄일 수 있다.

적용 조건

• 전이가 고정폭 참조일 때 (예: $f(i)$가 $f(i-1)$, $f(i-2)$만 필요)

예시

• 피보나치 수열: $f(n)=f(n-1)+f(n-2)$
  → 과거 두 개의 값만 유지하면 되므로 $O(n)$을 $O(1)$로 줄일 수 있음

▸ 대칭성 제거 (symmetry elimination)

해가 대칭 구조를 가질 경우, 중복되는 절반의 상태는 계산하지 않아도 된다.
이는 순열, 조합, 색상 구분 없는 문제 등에서 자주 활용된다.

적용 조건

• 상태 공간이 좌우나 순서 등에서 대칭인 구조를 가질 때

예시

• 조합 문제: $n$개 중 $k$개 선택할 때, $k$와 $n-k$는 대칭이므로 한 쪽만 계산
• 색이 구분되지 않는 공을 나누는 문제에서
  → 같은 조합을 다른 순서로 나눈 것을 중복 처리하지 않음

▸ 지배 제거 (dominance pruning)

항상 성능이 낮은 상태는 더 이상 계산할 필요가 없다.
이런 상태는 다른 상태에 비교 열등하므로 DP 테이블에서 제거할 수 있다.

적용 조건

• 문제에서 “이 상태는 다른 상태보다 항상 나쁘다”는 기준을 정할 수 있을 때

예시

• 배낭 문제: 무게가 더 무겁고, 가치도 낮은 상태는
  → 동일한 무게 제한 내에서 더 나은 선택으로 항상 대체 가능하므로 제외

DP는 점화식이 아니라 상태에서 시작된다.

점화식은 상태 정의가 끝난 다음에야 만들 수 있다.  
상태가 문제 상황을 정확히 구분하고 그 상태들 사이의 전이 조건이 일관되게 연결될 때   비로소 점화식은 구성 가능하다.

또한, 정의된 상태가 많아지면 이를 줄이는 방법도 필요하다.  
전이 방식은 그대로 두고 상태의 표현만 최적화하는 것이 공간 축소 전략이다.  
이처럼 동적계획법은 세 가지 단계를 거친다.

① 상태를 정의하고  
② 상태 간 관계를 수식으로 표현하며
③ 불필요한 상태를 제거하여 계산을 줄인다.

DP는 계산을 줄이는 기술이 아니라 문제를 분해하고 표현하는 방식의 선택이다.  
이 선택은 점화식보다 먼저 내려져야 한다.

문제를 해결한다는 것은 일련의 선택을 구성한다는 의미이다.
입력 상태에서 출발하여 어떤 출력을 도출하기 위해 우리는 여러 개의 결정을 순차적으로 내리게 된다.

이때 각 선택이 서로 어떤 관계를 갖는지는 결정적이다.
한 번의 선택이 이후 선택에 영향을 주는가
아니면 각각의 선택은 서로 무관하게 작동하는가
이러한 관계 구조에 따라 적절한 문제 해결 전략은 달라진다. 선택 간 관계를 전혀 모른다면 가능한 모든 조합을 시도해야 한다.
선택 사이에 반복되는 패턴이 존재한다면 이전 상태를 기반으로 이후 상태를 점화식으로 정의할 수 있다.
각 선택이 서로 독립적이라면 매 순간 가장 좋은 항목을 고르는 방식이 전체 최적을 이끌 수도 있다.

이 글은 선택 간 관계 구조를 기준으로 완전탐색, 동적계획법, 탐욕 알고리즘이라는 세 가지 전략이
어떤 조건 위에서 작동하며 그 조건들이 수학적으로 어떻게 정식화될 수 있는지를 설명하고자 한다.
이 세 전략은 단순한 구현 방식의 차이가 아니라 선택이 정의되는 공간과 그 공간의 구조에 대한 서로 다른 전제를 반영한다.

▸ 선택 간 관계에 따른 세 가지 경우

선택이란 하나의 상태를 결정하는 행위이며 문제 해결이란 이러한 선택들을 누적해 전체 경로를 구성하는 일이다.
그렇다면 중요한 질문은 다음과 같다.

 이 선택들은 서로 어떤 관계를 가지는가? 이 물음에 따라 우리는 세 가지 서로 다른 전략을 갖게 된다.

⇨ 선택들 사이의 관계를 모른다면
가능한 모든 조합을 시도해야 한다.
이것이 완전탐색이다.

⇨ 선택들 사이에 정보적 연결이 존재한다면
이전 상태를 기반으로 다음 상태를 점화식으로 정의할 수 있다.
이것이 동적계획법이다.

⇨ 선택들이 구조적으로 독립되어 있다면
매 순간의 선택만으로 전체 최적을 이룰 수 있다.
이것이 탐욕 알고리즘이다.

세 전략은 서로 다른 방식으로
‘선택 간 구조가 있다’ 또는 ‘없다’라는 사실을 전제한다.
그리고 이 전제는 이후 알고리즘 선택을 결정한다.

▸ 완전탐색 – 선택 구조를 모를 때

완전탐색은 가능한 모든 경우의 수를 하나하나 시도하는 전략이다.
이는 선택 간에 구조가 없다고 가정할 때 사용된다.

완전탐색은 이러한 관계가 전혀 주어지지 않은 상황에서 출발한다.
이때 우리는 가능한 모든 선택의 조합을 해 공간 $S$로 정의한다.
이 집합 $S$의 원소 $x\in S$ 각각에 대해 목표 함수 $f(x)$를 직접 계산하거나 조건을 평가한다.

→ 모든 $x\in S$에 대해 $f(x)$를 개별적으로 판별해야 한다
→ $S$는 문제의 크기에 따라 기하급수적으로 커질 수 있다

완전탐색은 어떤 선택이 다른 선택을 구성하거나 예측할 수 있다는 전제를 포함하지 않는다.
그렇기 때문에 선택들 사이에 중복된 부분 구조를 찾을 수 없으며
한 번의 판단으로 다른 가능성을 줄이거나 제외할 수 없다.

• 해 공간: $S=x_1,x_2,...,x_n$
• 전수 평가: $\mathrm{\forall }x\in S,;f(x)$를 계산 또는 조건 비교

• 선택 $X$를 알더라도 결과 $Y$의 불확실성이 줄어들지 않는다
• 조건부 엔트로피: $H(Y|X)=H(Y)$
• 상호정보량 정의 불가 또는 $I(X;Y)=0$

→ 어떤 정보를 알아도 다음 상태에 대한 예측이 전혀 가능하지 않다
→ 판단 이전의 상태와 판단 이후의 상태가 정보적으로 분리되어 있다

• 공리가 없다
• 점화식이 없다
• 상태 간 유도 관계가 없다

이런 조건에서 완전탐색은 전략이라기보다 전제 부재 상태에서 유일하게 할 수 있는 방법이다.

• 조합 가능한 모든 비밀번호를 대입하는 brute-force
• 미로에서 가능한 모든 경로를 시도하는 DFS with no pruning
• 퍼즐 문제의 모든 배치를 평가하는 방식

이러한 예시들의 공통점은
모든 경우를 고려할 수밖에 없는 상황이며 그 이유는 선택 사이에 불필요한 중복을 제거하거나
다른 선택으로부터 유추할 수 있는 구조가 없기 때문이다.

완전탐색은 선택들 사이의 관계가 전혀 주어지지 않았을 때 사용된다.
이 전략은 해 공간 전체를 열거하며,
모든 가능성을 동일하게 취급한다.
이 구조 아래서는 어떤 선택도 다른 선택에 비해 더 우선시될 수 없다.
모든 경우를 고려해야 한다는 점에서,
완전탐색은 구조가 아니라 무지 위에서 작동하는 방식이다.

▸ 동적계획법 – 정보적 종속 구조 위의 선택

동적계획법(Dynamic Programming)은
선택들이 정보적으로 연결되어 있다는 구조 위에서 작동한다.

이는 각 선택이 서로 독립적으로 이루어지는 것이 아니라 이전 선택의 결과가 이후 선택의 가능성과 결과값에 영향을 준다는 의미이다. 이러한 의존 구조는 명시적인 함수 관계로 표현되며 구체적으로는 점화식(recursion formula)이라는 수학적 구조로 나타난다.

동적계획법은 문제를 유한한 상태 공간(state space) 위에 정의한다 (formalizing).
여기서 상태(state)란 어떤 부분 문제의 해결을 위해 필요한 정보를 최소 단위로 요약한 표현이다.

즉, 전체 문제를 더 작은 부분 문제들로 나누었을 때 각 부분 문제는 어떤 조건에서 정의되고 어떤 하위 문제들에 의존하는지를 나타내야 한다. 이때 상태는 보통 정수 인덱스에 따라 순서화된 수열의 형태를 갖는다.
이 상태들은 일반적으로 정수 인덱스로 순서화된 수열의 형태를 갖는다.

예를 들어,
→ $f(i)$는 ‘입력 길이 $i$일 때의 최소 비용’을 나타내는 상태 함수일 수 있다.

■ 점화식과 상태 전이

각 상태는 이전 상태들로부터 유도되며,
이 관계는 점화식(recursion)의 형태로 주어진다:

→ $f(i)=minf(i-1)+a,f(i-2)+b$
→ $f(i)=maxf(i-1),f(i-3)+c_i$
→ $f(i,j)=minf(i-1,j),f(i,j-1)+d(i,j)$
→ $f(s)=\underset{t\in T(s)}{min}f(t)+w(t,s)$

이러한 점화식은 단순한 계산 규칙이 아니다.

이는 다음과 같은 수학적 명제이다:

즉, 각 상태는 독립적으로 계산되지 않으며 정의된 전이 관계와 조건을 충족하는 상태 집합 위에서만 유효하다.

■ 점화식의 역할

점화식은 문제 해결 과정의 상태 전이 구조(state transition structure) 자체를 수식으로 표현한다.
따라서 동적계획법이 올바르게 작동하기 위해서는 다음이 선행되어야 한다:

• 유한한 상태 공간이 명확히 정의되어야 하며
• 각 상태 간의 전이 방식이 일관된 규칙에 따라 구성되어야 한다

이러한 구조가 갖추어졌을 때,
동적계획법은 부분 문제의 해를 누적적으로 조합하여 전체 문제의 최적 해를 도출하는 체계적인 방법이 된다.

이전 상태의 해를 반복적으로 사용한다면,
해당 부분 문제를 여러 번 계산하는 낭비가 발생한다.
동적계획법은 이러한 중복된 하위 문제(overlapping subproblems)를 인식하고 각 상태의 해를 저장하여 재활용한다.
이를 메모이제이션 또는 탑다운 캐싱 혹은 하향식 재귀 구조라고 한다.

정보 이론 관점에서 이전 상태 $X$를 알면 현재 상태 $Y$의 불확실성이 줄어든다.

→ $H(Y|X)<H(Y)$
→ $I(X;Y)>0$

이는 선택 간에 정보적 종속 관계가 존재한다는 것을 뜻한다.
즉, 과거 선택이 미래 선택에 대해 정보량을 제공하며 이는 전체 계산의 예측 가능성과 효율을 높인다.
동적계획법은 구조적으로는 순차적이며, 정보적으로는 종속적인 전략이다.
Greedy는 구조적 독립을 가정하며 완전탐색은 종속도 독립도 가정하지 않는다.

• 상태는 순차적으로 구성된다 (수열 구조)
• 각 상태는 이전 상태로부터 결정된다 (점화식)
• 하위 문제는 여러 경로에서 재사용된다 (overlap)
• 동일 상태에 대해 최적해가 중복되면 캐싱한다 (메모이제이션)

• 피보나치 수열: $f(n)=f(n-1)+f(n-2)$
• 최단 경로: $f(i)=\underset{j<i}{min}f(j)+\text{cost}(j,i)$
• 배낭 문제: $dp[i][w]=max(dp[i-1][w],;dp[i-1][w-w_i]+v_i)$

이들 모두에서 공통적으로
이전 상태들로부터 현재 상태를 계산한다는 점 그리고 이 구조가 재귀적으로 반복된다는 점이다.

실제로 동적계획법에서 가장 중요한 것은 점화식 그 자체가 아니라 상태 공간(state space)을 어떻게 설계하고 축소할 것인가이다.
이 상태 정의만 제대로 한다면 점화식은 자연스럽게 구성될 것이다.

이에 대한 더 자세한 글을 해당 블로그의 다른 글에서 다루겠다.

▸ 탐욕 알고리즘 – 구조적으로 독립된 선택

탐욕 알고리즘(Greedy Algorithm)은 각 선택이 다른 선택에 영향을 주지 않는 구조 위에서만
전역 최적 해를 보장할 수 있다. 즉, 선택들 사이에 구조적 독립성이 존재해야 한다.

이 구조는 임의의 선택들이 모여 구성된 독립 집합 $\mathcal{I}$이 특정한 수학적 조건을 만족할 때 정의된다.
이 조건은 매트로이드(Matroid)라는 구조 위에서 정식화된다.

전체 원소 집합 $E$와
그 부분집합 중 ‘독립’한 집합들의 모임 $\mathcal{I}$가 있을 때,
다음 세 가지 공리를 만족하면 매트로이드라 한다:

1. $\mathrm{\varnothing }\in \mathcal{I}$ (공집합 독립성)
2. $A\in \mathcal{I},;B\subseteq A\Rightarrow B\in \mathcal{I}$ (부분집합 폐쇄성)
3. $A,B\in \mathcal{I},;|A|<|B|\Rightarrow \mathrm{\exists }x\in B\setminus A,;A\cup x\in \mathcal{I}$ (교환 가능성)

이 세 조건이 만족될 때
→ 항상 가장 기여도가 높은 항목부터 선택해도
→ 최적의 독립 집합을 구성할 수 있다

즉, 탐욕 선택이 항상 옳아진다.

탐욕 알고리즘이 전역 최적 해를 구성하려면 각 선택이 다른 선택에 대한 정보를 포함하지 않아야 한다.

→ $I(X;Y)=0$
→ $H(X,Y)=H(X)+H(Y)$

이는 선택 간에 정보적 중복이 없음을 의미한다.
즉, 어떤 항목의 선택 여부가 다른 항목의 평가에 아무런 영향을 주지 않는다.

→ 선택들은 서로 예측 불가능하며
→ 서로로부터 생성되지도 않는다

• 선택 가능한 조합이 매트로이드의 독립 집합을 이룬다
• 각 선택은 구조적으로 독립되며 교환 가능하다
• 기여도는 전체 맥락과 무관하게 비교 가능해야 한다
• 선택 순서에 따라 결과가 바뀌지 않는다

이러한 조건이 없다면 탐욕 선택은 최적 해를 보장하지 않으며 단지 근사적인 결과만을 제공할 수 있다.

• 크루스칼 알고리즘 (최소 신장 트리)
  → 간선들이 사이클 없이 연결되어 있어야 함 (그래픽 매트로이드)
  → 매번 가장 비용이 낮은 간선을 선택해도 전체 최적을 구성
• 작업 스케줄링 문제 (무충돌 작업 최대 선택)
  → 시간 간격이 겹치지 않는 최대 작업 집합
  → 각 작업을 독립적인 단위로 간주

이들 문제는 선택 구조가 매트로이드 공리를 만족하기 때문에 탐욕적 선택이 전체 최적 구성을 이끌 수 있는 것이다.

탐욕 알고리즘은 선택들 사이에 구조적으로 독립적인 조건이 있을 때 현재 순간의 판단만으로 전체 최적을 이끌 수 있는 전략이다.
이 구조는 매트로이드라는 수학적 조건으로 명확히 정의되며 선택 간 교환 가능성과 정보적 분리성이 핵심 전제이다.
이 조건이 무너지면, 탐욕 전략은 최적 해를 보장하지 않는다.

▸ 세 전략의 비교

지금까지의 세 전략은 모두 선택 간의 구조에 대한 서로 다른 전제를 바탕으로 구성된다.
마지막으로 각 전략이 성립하는 조건을 정리하고 그 차이를 표를 통해 명확히 구분해보자.

● 동적계획법은 선택 간에 정보적 종속이 존재할 때, 점화식을 통해 해를 구성한다.
● 탐욕 알고리즘은 선택들이 구조적으로 독립일 때, 각 단계의 최선이 전체 최선이 된다.

우리는 이전 글에서 '독립'이란 개념이 단순히 떨어져 있다는 의미를 넘어서
어떤 대상이 다른 것으로부터 생성될 수 없고, 다른 정보로부터 예측될 수 없는 상태임을 확인하였다.
엄밀한 수학 용어는 아니지만 편의상 매트로이드 이론에서는 구조적 독립, 정보이론에서는 정보적 독립이라는 이름으로 구체화된다.

이번 글에서는 정보이론에서의 독립이 어떤 수학적 구조로 정의되며 이 개념이 어떻게 정보량, 예측력, 알고리즘 최적성과 연결되는지를 다룬다.

확률에서의 독립의 정의

● 두 확률 변수 X, Y가 있을 때, X의 값을 알아도 Y의 확률 분포가 바뀌지 않는다면 두 변수는 정보적으로 독립이라 한다.
● 즉, X에 대한 정보는 Y에 대해 아무런 예측력을 제공하지 않는다.
● 이는 조건부 확률로 표현하면 다음과 같다:

P(Y | X) = P(Y)

● 이 등식이 모든 X에 대해 성립하면, 우리는 다음과 같이 정리한다:

두 확률 변수 X, Y가 독립이다 ⇔ 조건부 확률 P(Y|X) = P(Y)

한편, 확률에서의 독립을 정보이론에서의 독립으로 논의를 확장시키기 위해 먼저 엔트로피라는 개념에 대해서 알아야 한다.

정보량의 기준 – 엔트로피란 무엇인가

● 엔트로피 H(X)는 변수 X의 불확실성 정도를 수치화한 개념이다.

H(X) = - ∑ P(x) log P(x)

● X가 완전히 예측 가능하다면 → H(X) = 0
● X가 완전히 랜덤하다면 → H(X)는 최대

즉, 엔트로피는 'X를 설명하기 위해 얼마나 많은 정보가 필요한가'를 수치로 표현한 것이다.

정보적 관계의 측정 – 상호정보량(Mutual Information)

상호정보량(mutual information)은 두 확률 변수 X와 Y가 얼마나 많은 정보를 공유하고 있는지를 수치로 나타낸 개념이다.

정보이론은 정보적 독립을 상호정보량(mutual information)을 통해 수치화한다.
두 변수 X와 Y에 대해 X를 알게 되었을 때 Y에 대한 불확실성이 얼마나 줄어드는지를 상호정보량 I(X; Y)로 정의한다. 이는 다음과 같다 :

I(X; Y) = H(Y) - H(Y | X)

여기서 H(Y)는 Y의 엔트로피, H(Y|X)는 X를 알고 있을 때 Y의 조건부 엔트로피이다.

● X를 알면 Y의 불확실성이 줄어든다 → I(X;Y) > 0
● X를 알아도 Y의 불확실성이 줄어들지 않는다 → I(X;Y) = 0

정리: I(X; Y) = 0 ⇔ X와 Y는 정보적으로 독립이다.

 한편, 상호정보량은 세 가지 방식으로 정의할 수 있으며 각각은 같은 본질을 다른 구조로 표현한 것이다.

1) I(X; Y) = H(Y) − H(Y | X)
2) I(X; Y) = H(X) − H(X | Y)
3) I(X; Y) = H(X) + H(Y) − H(X, Y)

이 정의들을 이해하기 위해서는 각 항이 나타내는 개념을 정확히 파악해야 한다.

▶ H(X)는 확률 변수 X의 엔트로피이다. 이는 X가 얼마나 불확실한지를 수치화한 값이며, X를 완전히 예측하거나 설명하기 위해 필요한 정보량이다
▶  H(Y | X)는 X를 알고 있을 때 Y에 남아 있는 조건부 불확실성이다
▶  H(X, Y)는 X와 Y를 하나의 쌍으로 묶어 함께 고려할 때 필요한 총 정보량이며 이를 결합 엔트로피라고 한다
▶  H(X) + H(Y)는 X와 Y가 서로 완전히 독립일 때 두 엔트로피를 단순히 합한 값이다

이제 각 정의가 의미하는 바를 살펴보자.

1)번 수식에 대한 해설 :

I(X; Y) = H(Y) − H(Y | X)는 X를 알게 되었을 때 Y의 불확실성이 얼마나 줄어드는지를 나타낸다.

즉 X가 Y의 예측에 얼마나 기여하는지를 수치로 표현한 것이다.

1) + 2) 수식에 대한 해설 :

또한,  I(X; Y) = H(Y) − H(Y | X) = H(X) − H(X | Y) 의 관계가 성립함을 알 수 있다.

I(X; Y) = H(X) − H(X | Y) = H(Y) − H(Y | X)

이러한 방정식을 다음과 같이 직관적으로 이해할 수 있을 것 같다.

• X를 알면 Y의 불확실성이 줄어든다 → 그만큼의 정보가 I(X; Y)
• Y를 알면 X의 불확실성이 줄어든다 → 그만큼의 정보가 I(Y; X)

그런데 I(X; Y) = I(Y; X)이므로 둘은 동일한 값이다

이러한 대칭성은 상호정보량이 정보의 방향이 아니라 정보의 상호 작용을 측정하는 값이라는 것을 보여준다.

즉, X가 Y를 설명하는 정도와 Y가 X를 설명하는 정도가 동일한 척도로 나타나는 것이다.

3) 수식에 대한 해설 :

I(X; Y) = H(X) + H(Y) − H(X, Y)는 X와 Y의 개별 정보량을 단순히 더한 값과, 두 변수를 함께 설명할 때 필요한 실제 정보량 간의 차이를 의미한다. 이 차이는 곧 X와 Y가 공유하고 있는 중복된 정보의 양을 뜻한다.

→ 항상 H(X, Y) ≤ H(X) + H(Y)가 성립한다.
→ 등호가 성립하는 경우는 X와 Y가 완전히 독립일 때뿐이다.

이제 상호정보량이 정보적 독립성과 어떻게 연결되는지를 보자.

상호정보량 I(X; Y)가 0이라면 이는 H(Y | X) = H(Y)임을 의미한다.

즉 X를 알아도 Y에 대한 불확실성은 전혀 줄어들지 않으며 X는 Y의 예측에 기여하지 못한다.

동시에 이 경우 H(X, Y) = H(X) + H(Y)도 성립하게 되며, 이는 두 변수가 어떤 중복된 정보도 공유하지 않는다는 것을 의미한다.

즉 Y는 X로부터 생성된 정보가 아니며 X로부터 Y를 유도하거나 설명할 수 없다는 뜻이다.

I(X; Y) = 0
⇔ H(Y | X) = H(Y)
⇔ H(X, Y) = H(X) + H(Y)

따라서 상호정보량이 0이라는 것은 다음 두 조건을 동시에 만족한다는 의미이다.

→  예측 불가능성: X를 알아도 Y를 예측할 수 없다
→  생성 불가능성: Y는 X로부터 만들어질 수 없다

이 두 조건이 모두 만족될 때 X와 Y는 정보적으로 완전히 독립이라 한다.

정보량 함수는 Submodular하다

정보이론의 또 하나의 중요한 구조는 엔트로피 함수가 submodular하다는 점이다.

정보이론에서 엔트로피 함수는 submodular 함수로 간주된다.
이는 다음과 같이 정의된다:

일반적인 submodular 함수 f에 대해,

f(A) + f(B) ≥ f(A ∪ B) + f(A ∩ B)

정보량 함수 H는 다음의 차분 형태를 따른다:

어떤 두 집합 A ⊆ B, 원소 x에 대해

H(A ∪ {x}) − H(A) ≥ H(B ∪ {x}) − H(B)

● 이는 정보의 한계효용 감소(diminishing return)를 뜻한다.
● 이미 많이 아는 상태에서는 새 정보 하나가 기여하는 양이 작아진다.
● 반대로 거의 모르는 상태일수록 새 정보는 더 많은 기여를 한다.

→  submodular 구조는 정보가 단순히 축적되는 양이 아니라 기존 지식 위에서 상대적으로 측정되는 값임을
수학적으로 드러낸다.
→  정보는 절대량이 아니라 맥락에 따라 달라지는 차이의 크기로 정의된다.

다음과 같은 실제 문제들은 모두 동일한 정보량 함수 H의 submodular 성질을 공유한다:

□ 정보 획득 (센서 배치)

센서 배치 문제는 관측 가능한 영역의 정보량을 최대화하는 문제이다.
센서 집합 A에 대해 정보량을 H(A)로 정의하면, 이는 센서들이 측정하는 확률 변수들의 엔트로피이다.
센서 s를 A에 추가할 때의 정보 기여도는 H(A ∪ {s}) − H(A)로 측정되며, A가 커질수록 이 값은 감소한다.
즉 H는 submodular 함수이며, 이로 인해 탐욕적으로 기여도가 큰 위치를 선택해도 근사 최적해가 보장된다.

□ 질의 선택 (Query Selection)

어떤 질문을 던질지를 결정할 때도 동일한 구조가 적용된다.
질문 집합 A에 대해 정보량을 H(A)로 정의하면, 이는 질문을 통해 얻는 응답의 엔트로피이다.
질문이 늘어날수록 새 질문 하나의 기여는 감소하므로 H는 submodular 함수가 된다.
따라서 매 순간 가장 많은 정보를 제공하는 질문을 선택하는 탐욕 전략이 이론적으로 정당화된다.

□ Active Learning

라벨링할 샘플을 선택하는 문제에서도 정보량 함수 H는 동일하게 정의된다.
라벨링된 데이터 집합 A가 주어졌을 때, H(A)는 모델의 불확실성 감소량을 의미한다.
샘플 x를 추가할 때의 기여도는 H(A ∪ {x}) − H(A)이며, 이미 유사한 샘플이 많을수록 이 값은 작아진다.
따라서 H는 submodular하며 반복적으로 기여도가 큰 샘플을 선택하는 전략이 효율적이다.

□ Feature Selection
입력 변수 중 어떤 피처를 선택할지를 결정하는 문제에서도 피처 집합 A에 대한 정보량 함수 H(A)는 예측 성능이나 모델 정보량을 기반으로 정의된다. 새로운 피처 하나의 기여도는 기존 선택된 피처 구성에 따라 줄어들며, 이로 인해 H는 submodular이다. 따라서 탐욕적으로 정보 기여가 큰 피처를 선택해도 최적에 근접한 결과를 얻을 수 있다.

위의 예시들을 살펴보면, 현재 시점에서 가장 정보 기여도가

큰 항목을 매번 선택하는 탐욕 알고리즘이 최적해에 매우 근접한 해를 준다는 점을 알 수 있다.
이는 단조 증가하는 submodular 함수 위에서, 선택 가능한 항목 수에 제한이 있을 경우 탐욕 선택이 전체 최적값의

(1 − $\frac{1}{e}$) 이상을 보장한다는 Nemhauser, Wolsey, Fisher 정리에 의해 이론적으로 뒷받침된다.

( 참고: https://shoeraegi.tistory.com/94 )

그러나 여기서 중요한 점은, 근사 최적이지 전역 최적은 아니라는 것이다.
탐욕 알고리즘이 항상 전역 최적을 보장하려면, 선택할 수 있는 항목들의 조합이 아주 특정한 조건을 만족해야 한다.
그 조건이 바로 매트로이드이다.

매트로이드에서는 어떤 항목을 고른 뒤라도, 이후 단계에서 남은 항목 중 교체 가능한 조건이 보장된다.
즉, 한 번의 탐욕적 선택이 나중에 발목을 잡지 않는다는 성질이 존재한다.
하지만 정보량 함수는 submodular이기 때문에, 기여도가 맥락에 따라 달라지고 순서에 민감해지기 시작한다.
이로 인해, 앞선 선택이 나중 선택의 가능성을 제한하고 탐욕이 전역 최적을 놓칠 수 있다.

예를 들어 feature selection 문제를 생각해보자.
처음에 A라는 feature가 단독으로 가장 높은 정보 기여도를 보여 탐욕적으로 선택했다고 하자.
하지만 이후 B와 C를 함께 선택했을 때, 이 조합이 A보다 훨씬 높은 정보량을 제공하는 경우가 있다.
탐욕은 이 조합을 찾지 못한다. 왜냐하면 탐욕 알고리즘은 매 단계에서 단독 기여도만 비교하고

B와 C의 조합적 시너지를 고려하지 않기 때문이다.

이처럼 서로 간에 조합 효과가 중요한 경우, 초기 선택이 이후 선택을 제한하는 경우, 선택 집합은 더 이상 매트로이드가 아니게 된다.
교환성이 성립하지 않고 탐욕적 선택은 전역 최적을 보장할 수 없다.

feature selection은 이러한 조건을 모두 갖춘 대표적인 예이다.
1) 기여도는 맥락에 따라 변하고
2) 일부 feature들은 단독으로는 미약하지만 조합 시 시너지 효과를 낸다
3) 한 번 선택한 feature는 이후 선택을 제한한다

결국, 정보량이 절대적인 값이 아니라 이미 알고 있는 것에 따라 상대적으로 정의되는 값이기 때문에 정보량 기반의 선택 문제는 대부분 매트로이드 구조를 벗어난다. 탐욕 전략은 여전히 강력한 근사 해를 제공하지만, 항상 최적이라는 보장은 사라진다.

독립이란 어떤 선택이 다른 것에 의해 예측되거나 구성되지 않는다는 말이며 매트로이드는 그 조건이 성립하는 선택 공간이다.
이 위에서는 탐욕이 항상 최적 해를 만든다. 하지만 정보량 함수처럼 기여도가 맥락에 따라 바뀌면
선택이 순서에 묶이고 교환이 불가능해져 탐욕은 최적을 보장하지 않는다.

그래픽 매트로이드 사례: 크루스칼 알고리즘

크루스칼 알고리즘에 대해 알기 위해 먼저 그래프의 한 종류인 최소 신장 트리(MST)를 알아야 한다.

그래프 $G=(V,E)$가 주어져 있다고 하자.
각 간선 $e\in E$에는 비용(weight)이 존재한다.
우리는 다음 조건을 만족하는 간선 집합을 찾고자 한다:

• 모든 정점이 연결되어 있어야 한다 (연결 그래프)
• 사이클이 없어야 한다 (트리 구조)
• 간선들의 비용 합이 최소여야 한다 (최소 비용)

이러한 간선 집합을 최소 신장 트리(Minimum Spanning Tree, MST)라고 한다.
MST는 항상 정점 수가 $|V|$개일 때 간선 수는 $|V|-1$개이다.

정점과 간선이 주어져 있을 때,
크루스칼 알고리즘(Kruskal's Algorithm)은 MST를 구하기 위한 대표적인 탐욕 알고리즘이다.
작동 방식은 다음과 같다:

• 모든 간선을 비용 오름차순으로 정렬한다.
• 정렬된 간선들 중에서 하나씩 순서대로 다음 조건을 확인한다:
  → 이미 선택한 간선들과 함께 사이클이 생기는가?
• 사이클이 생기지 않으면 간선을 선택한다.
• 사이클이 생기면 그 간선은 건너뛴다.
• 선택된 간선이 $|V|-1$개가 될 때까지 위 과정을 반복한다.

이 방식은 매 순간 가장 “저렴한” 간선을 고르고 선택된 간선 집합의 독립성(사이클 없음)을 유지하는 그리디한 접근 방식이다.

간선 집합의 독립성 – 그래픽 매트로이드 관점

앞서 우리는 그래프에서 사이클이 없는 간선 집합이 독립이라는 사실을 확인했다.
이는 정확히 그래픽 매트로이드(Graphic Matroid)의 정의와 일치한다.

정의:
그래프 $G=(V,E)$에 대해,
간선 집합 $I\subseteq E$가 사이클을 포함하지 않을 때 이를 독립 집합이라고 정의하면 $(E,\mathcal{I})$는 매트로이드를 이룬다.

즉, 사이클 없음 $⟺$ 독립성
→ 크루스칼 알고리즘은 매 단계마다 이 조건을 검사하는 것이다.

매트로이드 공리와 크루스칼 알고리즘의 일치

매트로이드는 다음 세 가지 공리를 만족해야 한다.
크루스칼 알고리즘은 이 공리들과 정확히 일치한다:

(1) 공집합은 항상 독립이다
→ 아무 간선도 선택하지 않은 초기 상태는 자명하게 사이클이 없음

(2) 독립 집합의 모든 부분집합도 독립이다
→ 사이클이 없는 간선 집합의 일부를 골라도 역시 사이클 없음

(3) 확장 가능성 공리
→ 더 큰 독립 집합이 있다면
→ 그 중 일부는 현재 집합에 추가해도 여전히 독립이다

크루스칼 알고리즘은
→ 매트로이드의 세 공리를 모두 만족하는
→ 그래픽 매트로이드의 독립 집합 위에서의 그리디하게 확장하는 과정이다.

Greedy Optimality – 왜 항상 최적인가?

매트로이드 위에서는

• 선택이 항상 독립성을 유지하고
• 더 큰 독립 집합으로 확장 가능한 구조이므로
  → 탐욕적으로 선택을 누적해도 전역 최적 해에 도달할 수 있다.

즉, 크루스칼 알고리즘은 다음을 보장한다:

• 비용이 가장 낮은 간선부터 선택하되
• 사이클이 생기지 않도록 선택하며
• 이 과정이 항상 전체 최적 구조로 확장된다.

MST를 만드는 크루스칼 알고리즘의 예시

이번 예시는 간선의 비용은 낮지만
선택 순서에 따라 사이클이 유발될 수 있는 구조를 포함한다.
크루스칼 알고리즘이 어떻게 가중치 오름차순 + 사이클 조건만으로 선택을 누적하며,
결국 전역 최적의 최소 신장 트리(MST)를 완성하는지 보여준다.

정점: A, B, C, D, E, F
간선 및 가중치는 다음과 같다:

크루스칼 알고리즘의 작동 과정:

1. e₁(A–B): 비용 1, 사이클 없음 → 선택
2. e₂(A–C): 비용 1, 사이클 없음 → 선택
3. e₃(B–C): 비용 1, A–B–C가 이미 연결됨 → 사이클 발생 → 제외
4. e₇(E–F): 비용 1, E–F 모두 고립 → 사이클 없음 → 선택
5. e₄(B–D): 비용 2, D는 아직 미연결 → 사이클 없음 → 선택
6. e₅(C–E): 비용 2, C–A–B–D와 E–F가 분리됨 → 사이클 없음 → 선택
7. e₉(C–F): 비용 2, C와 F는 이미 연결됨 → 사이클 발생 → 제외
8. e₆(D–E): 비용 3, D와 E는 이미 연결됨 → 사이클 발생 → 제외
9. e₈(A–F): 비용 4, A와 F는 이미 연결됨 → 사이클 발생 → 제외

최종 선택 간선: e₁, e₂, e₇, e₄, e₅
총 비용: 1 + 1 + 1 + 2 + 2 = 7
정점 수: 6 → 간선 수 5 → MST 조건 만족
사이클 없음 + 전체 연결 + 비용 최소 → MST 완성

이 예시는 크루스칼 알고리즘이
단순히 비용 순으로 탐색하면서도 매번 사이클 조건 하나만으로 정확한 선택을 한다는 점을 보여준다.
이는 매트로이드 관점에서 보면 그래픽 매트로이드의 독립 조건을 만족시키는 과정과 정확히 일치한다.

1. 그래픽 매트로이드란 무엇이고, 구조란 무엇인가

어떤 그래프 G = (V, E)가 있다.

이 그래프에서 사이클이 없는 간선 집합들은 모두 독립 집합이라 부른다.

이때 이 독립 집합들의 집합 전체를 ℐ라 하고 (E, ℐ)는 매트로이드가 된다.

즉, 그래픽 매트로이드란 ‘사이클이 없는 간선들의 집합’을 독립 집합으로 간주하는 구조이다.

‘구조적 제약만으로 탐욕 선택을 보장’한다는 말의 정확한 뜻은 다음과 같다.

선택 가능한 조합(즉 독립 집합들)의 모양이 매트로이드라는 특수한 구조를 갖고 있으면 가중치 기준으로 탐욕적으로 항목을 선택해도 항상 최적 해가 된다.

예: Prim 알고리즘은 항상 가중치가 가장 낮은 경계 간선을 하나씩 추가한다. 탐욕적 선택이 잘못되지 않으려면 현재까지의 선택에 새로운 간선을 추가하더라도 여전히 독립 집합(사이클이 없는 집합)으로 남아야 한다. 그리고 항상 그렇게 확장 가능한 구조가 매트로이드 구조이다.

이 구조는 ‘기여도’를 평가하지 않는다. Prim 알고리즘은 ‘지금 어떤 간선이 연결되면 가장 적은 비용으로 연결되냐’만 본다. 각 간선이 전체에 얼마나 이득을 주는가 얼마나 유용한가라는 함수적 개념은 전혀 없다. 단지 지금 사이클만 안 생기면 되고 가장 비용이 적으면 고른다.

2. Submodular 함수는 왜 필요한가

현실의 많은 문제는 다음과 같이 구성된다.

• 어떤 항목(예: 센서 피처 광고 팀원 등)을 선택한다.
• 항목들을 여러 개 조합할 수 있다.
• 각 조합에 대해 전체 성과를 평가하는 함수 f(S)가 있다.
• 우리는 이 성과를 최대화하려고 한다.

이때는 단순히 ‘이 항목을 고르면 독립이냐 아니냐’가 중요한 게 아니다. 이 항목을 추가하면 전체 성과가 얼마나 증가하는가가 핵심이다.

예를 들어 광고 세트를 고를 때 유사한 광고는 중복이 많아 성과가 떨어질 수 있다. 센서를 고를 때 서로 가까운 센서는 유사한 데이터를 제공해 기여도가 떨어진다. 피처를 고를 때 이미 비슷한 피처가 선택되어 있으면 성능 향상 폭이 작다.

이처럼 항목을 고를수록 한계 기여(marginal gain)가 줄어드는 함수 구조가 바로 Submodular 함수이다.

매트로이드가 ‘선택 가능한 조합의 구조’를 다루는 것이라면 Submodular 함수는 ‘선택된 조합의 성과를 어떻게 계산할 것인가’를 다룬다.

Prim 알고리즘과 Submodular 함수 기반 확장

앞서 우리는 그래픽 매트로이드 구조 위에서 Prim 알고리즘이 어떻게 작동하는지를 분석하였다. Prim 알고리즘은 최소 신장 트리(MST)를 구성하는 알고리즘으로 현재 선택된 정점 집합에서 연결 가능한 간선들 중 가중치가 가장 낮은 간선을 반복적으로 선택하여 신장 트리를 확장해 나간다. 이러한 선택 과정이 항상 전역 최적 해인 MST를 산출할 수 있는 이유는 그래픽 매트로이드의 공리 구조가 Prim 알고리즘의 탐욕적 선택 방식과 정확히 대응되기 때문이다.

Prim 알고리즘 – 매트로이드 공리 대응

Prim 알고리즘의 탐욕적 구조가 매트로이드의 세 가지 공리와 어떻게 맞닿는지를 구체적으로 짚어보자.

• 공집합 독립성 Prim 알고리즘의 초기 상태에서는 하나의 시작 정점 u₀만이 선택되어 있고 이 상태에서는 어떠한 간선도 포함되지 않는다. 이 상태는 당연히 사이클을 형성하지 않으므로 그래픽 매트로이드에서의 공집합 독립성 공리를 만족한다.
• 부분집합 보존성 Prim 알고리즘이 선택한 간선 집합이 독립 집합이었다면 그 어떤 부분집합도 역시 사이클을 포함하지 않게 된다. 이는 매트로이드의 두 번째 공리 즉 독립 집합의 부분집합은 여전히 독립이라는 성질과 일치한다.
• 확장 가능성 현재 선택된 독립 집합이 있고 그보다 더 큰 독립 집합이 존재한다면 매트로이드 구조에서는 항상 현재 집합의 원소 하나를 대체하여 더 큰 집합으로 확장할 수 있다. 이 공리는 이미 설명한 바와 같이 Prim 알고리즘의 순차적 확장 과정에 직접적으로 대응된다. Prim은 항상 독립 조건(사이클 없음)을 유지하면서 새로운 간선을 추가할 수 있기 때문이다.

이러한 세 가지 공리와의 대응은 다음 사실을 보장한다. → Prim 알고리즘이 선택할 수 있는 간선들이 그래픽 매트로이드 위의 독립 집합을 이루고 있으며 각 단계의 선택이 항상 그 독립성을 유지하도록 구성되어 있다는 점이다.

따라서 가중치가 모두 양수이고 그래프가 연결되어 있는 경우 Prim 알고리즘은 반복적인 지역 최적 선택만으로도 전역 최적 해인 MST를 정확히 산출할 수 있다.

관점을 전환하며: 선택 구조에서 선택 기여로

우리는 지금까지 탐욕 알고리즘이 작동하기 위한 구조적 조건에 집중했다. 예를 들어 그래픽 매트로이드에서는 사이클이 없는 간선 집합만을 선택할 수 있고, 이러한 선택 가능성 자체의 구조가 최적성을 보장하는 핵심이었다.

그러나 현실의 많은 문제는 단지 무엇이 선택 가능한가뿐 아니라 선택한 항목이 얼마나 성과에 기여하는가를 함께 고려해야 한다. 즉, 선택 가능성만으로는 충분하지 않고 각 항목이 얼마나 유용한지를 평가할 수 있는 함수적 기준이 요구된다.

이제 우리는 그러한 기여도를 수치화하여 평가하고 그것을 기반으로 탐욕적으로 항목을 선택하는 함수 중심의 탐욕 알고리즘으로 시선을 옮긴다.
이때 등장하는 개념이 바로 Submodular 함수이다.

Submodular 함수는 매트로이드처럼 가능한 조합의 모양에 주목하는 것이 아니라 각 조합의 기여도를 직접 평가하는 방식이다. 즉, 어떤 항목을 추가했을 때 전체 성과가 얼마나 향상되는지를 계산하며, 이를 통해 탐욕 알고리즘이 어느 정도 성능을 보장할 수 있는지 설명하는 수학적 틀을 제공한다.

매트로이드 기반 탐욕 알고리즘
→ 선택의 가능성에만 집중
→ “적은 비용이라면 넣고 사이클만 안 생기면 된다”
→ 기여도를 묻지 않는다
→ 그런데도 항상 최적 해를 구할 수 있다 (매트로이드 구조 덕분)

Submodular 함수 기반 탐욕 알고리즘
→ 선택의 기여도에 집중
→ “지금 넣었을 때 얼마나 도움이 되는가”를 매번 계산
→ 구조 제약도 함께 고려 가능 (예: 매트로이드 조건과 함께 사용)
→ 최적은 아니지만 (1 − $\frac{1}{e}$) 정도의 근사 보장이 가능

Submodular 함수 – 정의와 수학적 성질

우선 개념부터 정확히 정리한다.

• E는 선택 가능한 전체 항목들의 집합이다.
• 이 집합 E의 부분집합들 2^E에 대해 실수 값을 대응시키는 함수 f: 2^E → ℝ를 고려한다.
• 함수 f가 다음 두 조건을 만족하면 Submodular하고 단조 증가하는 함수라 한다.

단조 증가성 (Monotonicity)

∀ A ⊆ B ⊆ E에 대해 f(A) ≤ f(B)

Submodularity (아첨성 또는 준볼록성)

∀ A ⊆ B ⊆ E, x ∉ B에 대해 f(A ∪ {x}) − f(A) ≥ f(B ∪ {x}) − f(B)

이는 항목 x를 선택했을 때의 한계 이득(marginal gain)이 기존 선택 집합이 작을수록 더 크고 클수록 작아진다는 뜻이다.

Submodular 함수의 예시 – 센서 배치 문제

센서를 배치하여 정보를 최대한 수집하고자 하는 문제를 가정하자. 설치 가능한 센서의 집합을 E = {s₁, s₂, s₃}라 하자.

각 센서 조합에 대한 정보량 함수 f는 다음과 같다.

s₁부터 순차적으로 선택할 때의 한계 이득은 다음과 같다.

• Δ₁ = f({s₁}) − f(∅) = 5
• Δ₂ = f({s₁, s₂}) − f({s₁}) = 3
• Δ₃ = f({s₁, s₂, s₃}) − f({s₁, s₂}) = 1

이처럼 선택이 진행될수록 한계 이득이 5 → 3 → 1로 감소함을 볼 수 있다. 이것이 Submodular 함수의 핵심적 특징이다.

Submodular 함수 위에서의 탐욕적 선택 – 근사 보장

지금까지 Submodular 함수의 정의와 성질을 살펴보았다. 이제 이 함수를 기반으로 하는 탐욕 알고리즘이 어떤 조건 하에서 성능을 보장받을 수 있는지 즉 최적 해에 얼마나 가까운 결과를 산출할 수 있는지를 수학적으로 분석한다. 이를 위해 다음과 같은 조합 최적화 문제를 고려한다.

• 전체 항목 집합 E 중에서 k개를 선택하여 f(S)가 최대가 되도록 한다.
• 단 선택 제약은 매트로이드의 독립 집합 조건을 만족해야 한다.

이때 탐욕 알고리즘은 매 단계마다 아직 선택되지 않은 항목 중에서 현재 집합 S에 추가했을 때 한계 이득 f(S ∪ {x}) − f(S)가 가장 큰 항목 x를 선택한다. 이 과정을 k번 반복한다.

그 결과 얻어진 집합을 g라 하고 전역 최적 해를 opt라 하면 다음이 성립한다.

f(g) ≥ (1 − $\frac{1}{e}$) · f(opt)

이 보장은 다음 조건에서만 성립한다.

• f는 Submodular하고 단조 증가한다
• 선택 제약은 매트로이드 구조이다
• 선택 가능한 항목 수는 k개로 제한된다

이 보장은 교환 논증에 기반하여 증명된다. 탐욕 해 g와 최적 해 opt 간의 차이를 항목 단위로 비교하고 서로 교환할 때 성능 손해가 얼마나 줄어드는지를 단계별로 분석한다. 그 결과 누적 성능 차이가 기하급수적으로 줄어들며 (1 − $\frac{1}{e}$) 비율까지 수렴한다.

사례

집합 커버 문제 예시:

전체 원소 집합 U = {a, b, c, d, e}가 있고 부분집합의 모음 𝒮 = {S₁, S₂, S₃}가 다음과 같다고 하자.

• S₁ = {a, b}
• S₂ = {b, c, d}
• S₃ = {d, e}

각 부분집합을 하나의 항목으로 간주하고 함수 f(S)는 선택한 집합들의 합집합 원소 개수로 정의된다.

f(S) = |⋃_{Sᵢ ∈ S} Sᵢ|

이 함수는 다음과 같은 성질을 가진다.

• 집합을 더 많이 선택할수록 커버하는 원소 수는 증가한다 → 단조 증가
• 이미 많이 커버한 상태에서는 새로운 집합 하나의 기여가 작아진다 → Submodular

피처 선택 문제 예시:

예측 모델을 학습할 때 사용할 수 있는 피처들이 E = {x₁, x₂, …, xₙ}이라 하자. 함수 f(S)는 선택된 피처 집합 S를 사용하여 학습된 모델의 검증 정확도 또는 R² score로 정의된다.

현실에서는 새로운 피처를 추가할수록 모델 성능은 상승하지만 이미 중요한 피처가 포함된 경우 그 상승폭은 작아지는 경향이 있다.

따라서 실제 데이터 기반에서 학습된 f는 다음을 만족하는 경향이 있다.

• A ⊆ B일 때 f(A) ≤ f(B) → 단조 증가
• A ⊆ B, x ∉ B일 때 f(A ∪ {x}) − f(A) ≥ f(B ∪ {x}) − f(B) → Submodular

이 함수 f는 이론적으로 항상 Submodular 함수로 보장되지는 않는다. 그러나 실제 머신러닝 문제에서는 많은 경우 선택된 피처 집합이 커질수록 추가 피처의 기여도가 감소하는 경향이 관측된다. 즉 경험적으로 Submodular 구조에 근사하게 작동하는 경우가 많다. 이러한 성질 덕분에 탐욕 기반 피처 선택 알고리즘이 높은 성능을 보이는 구조적 근거가 된다.

탐욕 알고리즘은 왜 매트로이드 위에서 항상 최적인가

수많은 알고리즘 중에서 탐욕 알고리즘은
가장 단순하면서도 동시에 가장 위험한 방식이다.

탐욕 알고리즘이란 문제를 풀 때, 매 순간 가장 좋아 보이는 선택만을 반복하는 방식을 말한다.
다시 말해, 지금 이 순간 국소적으로 최선이라 판단되는 것을 고르고 그렇게 쌓인 선택들이 결국 전체적으로도 최선이 되기를 기대하는 방법이다.

예시적인 질문은 항상 이렇다.

지금 당장 가장 비용이 적거나 효율적인 선택을 했는데
나중에 이 선택을 되돌릴 수 없다면
정말 이 선택은 전체적으로도 옳은 판단이었을까

이 방식은 빠르고 간결하다.
그러나 대부분의 경우, 탐욕 알고리즘은 실패한다. 지금 적은 비용을 보이는 선택이 결국 전체 비용을 증가시킬 수 있기 때문이다.
당장의 최선이 전체적 최선으로 이어진다는 보장이 없기 때문이다.

그럼에도 불구하고
수학자들은 어떤 문제에서는 이 단순한 방식이 항상 옳다는 사실을 발견했다. 바로 그 조건이 매트로이드라는 구조이다.

매트로이드 위에서 탐욕 알고리즘은 항상 전체적으로도 최선의 결과를 만들어낸다.

따라서 이 글에서는 다음과 같은 질문을 본격적으로 파고든다.

탐욕 알고리즘은 왜 실패할 수밖에 없는 방식인가
그런데 왜 매트로이드 위에서는 그것이 항상 옳아지는가
매트로이드의 공리와 탐욕 알고리즘의 동작 원리는 어떻게 맞물리는가
이 정당성은 어떤 수학적 직관 위에 놓여 있는가

 탐욕 알고리즘은 어떤 구조 위에서만 성공하는가

탐욕 알고리즘(Greedy Algorithm)은 매 순간 가장 좋아 보이는 선택을 반복하여 전체 해답을 구성하려는 방식이다.
이 알고리즘은 간단하고 빠르며 과거의 선택을 되돌아보지 않는다.

그러나 이 방식이 항상 정답을 보장하는 것은 아니다.
탐욕 알고리즘이 실제로 옳은 결과를 내기 위해서는 그 작동 방식 자체가 어떤 구조 위에 놓여 있어야 한다.

탐욕 알고리즘의 단계 요약

탐욕 알고리즘은 다음과 같은 단계를 따른다.

1. 선택 가능한 모든 후보 요소들을 정리한다.
2. 정해진 기준에 따라 이들을 정렬한다.
3. 가장 우선순위가 높은 항목을 선택한다.
4. 해당 항목이 조건을 만족하면 포함하고, 아니면 제외한다.
5. 더 이상 고려할 요소가 없을 때 종료하고 결과를 반환한다.

이 단순한 방식은
기저적으로는 정렬 기준, 조건 판별, 선택의 비가역성이라는 세 가지 축 위에 놓인다.

탐욕 알고리즘의 구체적인 각 단계

후보 정렬 – 정렬 기준은 왜 필요한가.
탐욕 알고리즘은 각 요소를 “좋아 보이는 순서”로 정렬한다. 이 순서가 없으면 탐욕은 작동하지 않는다.
좋아 보인다는 건 단순한 감각이 아니라 문제마다 정해진 평가 기준에 따라
각 항목에 우선순위(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. 탐욕 알고리즘은 선택을 되돌릴 수 없다.

탐욕 알고리즘은 한 번 선택한 것을 다시 되돌아가서 고치지 않는다.
이 성질은 효율을 주지만 동시에 돌이킬 수 없는 구조적 리스크를 만든다.

예:
일정 스케줄링 문제에서
→ 먼저 마감이 느리지만 효율이 높은 작업을 선택하면
→ 나중에 마감이 빠른 작업을 수행할 수 없게 되어
→ 전체 스케줄이 실패하게 된다

즉, 탐욕 알고리즘은 과거 선택을 수정하지 않는다.
한 번의 선택이 전체 해를 결정짓는다.
이 방식이 실패하지 않으려면 문제 구조 자체가 어떤 순서로 선택해도 최적에 도달하도록 되어 있어야 한다.
→ 매트로이드는 그런 구조다.

 이 방식이 항상 통하는 구조 – 매트로이드 위에서의 정당성

탐욕 알고리즘이 실패하지 않기 위해선
→ 선택이 미래로 확장 가능해야 하며
→ 과거 선택이 전체 구조를 가로막지 않아야 한다.

매트로이드는 바로 그런 조건을 만족하는 수학적 구조다.

• 각 선택은 독립성을 유지하며
• 더 큰 독립 집합으로 확장될 수 있다

특히, 매트로이드의 확장 가능성 공리는 다음을 보장한다:
→ 탐욕적으로 하나씩 누적한 선택들이
→ 최종적으로 최적 독립 집합과 같은 크기, 같은 조건을 만족하게 된다

즉, 매트로이드는 되돌릴 수 없는 선택 흐름에서도 항상 최적 해에 도달할 수 있도록 논리적 확장 경로를 보장하는 구조이다.

이전 글에서는 독립이라는 개념이 단순히 다른 것과 떨어져 있다는 의미를 넘어서 자신의 존재나 작동이 다른 무언가에 의존하지 않고 스스로 성립된다는 뜻임을 살펴보았다.

이 철학은 수학적으로 두 가지 방식으로 구체화될 수 있다.
- 하나는 어떤 대상이 다른 구성 요소로부터 만들어질 수 없다는 생성 불가능성
- 다른 하나는 어떤 대상이 다른 정보로부터 예측될 수 없다는 예측 불가능성이다.

이번 글에서는 이러한 철학이 수학의 구체적인 구조 안에서 어떻게 표현되는지를 다룬다.
먼저 선형대수의 벡터 공간과 그래프 이론의 간선 구조처럼 서로 다른 분야에서 독립이 어떻게 정의되는지를 살펴본다.
그 다음 이들 각각의 독립 개념이 하나의 공통된 틀로 통합된 구조인 매트로이드의 개념으로 어떻게 일반화되는지를 설명한다.

벡터 공간에서의 독립 – 스스로 하나의 축을 만든다는 것

벡터 공간에서 두 벡터가 서로 독립이라는 말은
한 벡터가 다른 벡터의 선형결합으로 표현될 수 없는 상태를 뜻한다.

선형결합이란 두 벡터에 실수 계수를 곱해 더하는 것이다.
즉, 어떤 벡터가 다음과 같은 형태로 표현될 수 있는지를 본다.

선형결합의 일반 형태

a ⋅ v₁ + b ⋅ v₂

예를 들어 다음과 같은 벡터를 생각해보자.

→ v₁ = (1, 0)
→ v₂ = (0, 1)

이 두 벡터는 서로 독립이다.

→ v₁만으로는 v₂를 만들 수 없다
→ v₂만으로도 v₁을 만들 수 없다
→ 방향도 다르고 기여하는 공간도 다르다

그래서 이 둘은 함께 2차원 공간 전체를 생성한다.
즉, 두 벡터가 만들어내는 평면이 완전히 확장되는 것이다.

반대로 v₃ = (2, 0) 이라는 벡터를 보자.
이 벡터는 단지 v₁의 두 배일 뿐이다.

v₃ = 2 ⋅ v₁

이처럼 어떤 벡터가 다른 벡터들의 선형결합으로 표현될 수 있다면
그 벡터는 해당 벡터 집합에 선형적으로 종속되어 있다고 한다.

그래프에서의 독립 – 중복 없이 전체를 연결하는 구조

이번에는 벡터 공간과는 완전히 다른 구조인 그래프(graph)에서의 독립을 살펴본다.

그래프는 정점(vertex)과 간선(edge)으로 이루어진 네트워크 구조이다.
여기서 독립의 기준은 사이클(cycle) 여부다.
사이클이란 정점 몇 개를 따라 이동한 후 다시 출발점으로 되돌아오는 닫힌 경로를 뜻한다.

독립 간선의 기준
1) 사이클을 만들지 않는다
2) 어떤 간선도 나머지 간선들로 대체할 수 없다
3) 하나라도 빠지면 연결이 끊어진다

예시로 이해해보자

 섬 A, B, C가 있다
→ 다리 A-B, B-C를 연결하면 세 섬이 이어진다
→ 이때 사이클은 없다
→ 다리 하나라도 끊기면 전체 연결이 무너진다
→ 각각의 간선이 필수적인 연결만을 담당하고 있다
→ 이 구조는 독립이다

이제 A-B, B-C에 더해 A-C까지 다리를 하나 더 놓는다면

→ A-B-C-A라는 사이클이 생긴다.
→ 어느 다리를 끊어도 나머지로 연결이 유지된다.
→ 일부 간선은 다른 간선들로 대체할 수 있다.
→ 이 구조는 더 이상 독립이 아니다.
→ 종속적인 연결이다.

수학은 왜 독립을 그렇게 중시하는가

수학은 어떤 대상을 구성할 때
최소한의 정보와 최소한의 요소만으로 충분히 만들 수 있느냐를 중요하게 여긴다.
즉, 중복된 요소를 제거하고 핵심만 남기는 작업이 수학적 사고의 본질이다.
이러한 사고 방식은 추상화라 불린다.

이 과정에서 수학자들은 각기 다른 맥락에서 등장하는 독립의 개념을 하나의 구조적 틀로 일반화하려 하였고
그 결과 등장한 것이 바로 매트로이드(Matroid)이다.

다양한 독립 개념을 통합한 수학적 구조 – 매트로이드

벡터의 독립, 그래프에서의 간선 독립 등 서로 다른 맥락처럼 보이는 개념들은 사실 같은 질문을 던진다.

이 구성 요소는 기존 것들로부터 만들어질 수 있는가

이 질문에 아니요라고 대답할 수 있는 요소들만을 모은 집합을
수학에서는 독립 집합이라 부른다.

이 개념을 수학적으로 추상화한 것이 바로 매트로이드(Matroid)이다.
매트로이드는 다음 세 가지 공리를 만족하는 구조다.

(1) 공집합은 항상 독립이다.
아무것도 없는 상태는 중복도 없고 종속도 없다.
따라서 자명하게 독립으로 간주된다.

(2) 독립 집합의 모든 부분집합도 역시 독립이다.
전체가 독립이라면 그 안의 일부도 반드시 독립이다.
독립성은 부분에 대해서도 유지되는 성질이다.

(3) 확장 가능성
더 작은 독립 집합은 더 큰 독립 집합으로 확장 가능해야 한다.

이 공리는 조금 더 정교하게 설명할 필요가 있다.

집합 A와 B가 있다고 하자.
원소는 벡터일수도 간선일수도 회로의 전선일 수도 있다. 또한, A, B는 독립 집합이다.
또한 A는 B보다 작다고 가정하자.이는 A의 원소 개수가 B보다 적다는 뜻이다

이 공리는 다음 조건을 요구한다

B에 포함된 원소 중 적어도 하나는 A에 추가했을 때에도 A는 여전히 독립이어야 한다

즉, 내가 독립적인 조합 A를 선택한 상태이고 누군가 그보다 더 많은 독립 요소를 가진 B를 선택했다면
B의 선택 중 일부는 A에 추가해도 여전히 문제가 없어야 한다.

예시

v₁ = (1, 0), v₂ = (0, 1), v₃ = (2, 0)
A = {v₁}, B = {v₁, v₂}

→ A와 B는 모두 독립
→ B의 v₂를 A에 추가하면 {v₁, v₂}
→ 여전히 독립 상태
→ 확장 가능성 공리 만족

즉, 매트로이드에서 정의한 3번 공리를 해석하면

독립이라는 것은 고립된 정적 상태가 아니라 더 많은 기여를 받아들일 수 있는 유연한 확장 가능성을 포함한 개념이다.

이 성질은 단지 수학적 정의가 아니라
일정한 구조 내에서 탐욕 알고리즘(Greedy Algorithm)이
정당하게 작동할 수 있는 이론적 기반이 되기도 한다.

독립(independence)이란 개념은 자연과학의 많은 맥락에서 반복적으로 자주 등장한다.

사실 그 이전에 우리가 무심코 사용하는 "독립"이라는 단어는 일상 속에서 아주 자연스럽게 등장한다.

예를 들어,

• "저 사람은 부모로부터 독립했어."
  → 부모 도움 없이 살아감. (혼자서 살아갈 수 있는 상태)
• "이 팀원은 독립적으로 일할 수 있어."
  → 혼자 힘으로 성과를 낼 수 있음. (다른 팀원 도움 없이 일을 완성)

이 일상의 예시들을 보면 독립이란 단순히 혼자라는 의미가 아니라
"혼자서도 무언가를 이루거나 작동할 수 있는 상태"임을 알 수 있다.

즉, 독립은 자연스럽게 "혼자서 가능하다"는 느낌과 연결되어 있다.

혼자 가능하다는 건, 곧 '다른 것에 의존하지 않아도 된다'는 것

그럼, "의존하지 않는다"는 건 뭘까?

• A가 B에 의존하지 않는다. → B가 없어도 A는 존재할 수 있다.
• A가 B에 의존한다. → B가 없으면 A도 존재할 수 없다.

즉, 의존성은 곧 '존재나 작동의 조건'이다.

그러니까 독립은 반대로
"자신의 존재나 작동이 다른 무언가의 조건이 아니라 자기 스스로 그 조건을 만족한다는 뜻" 이다.

이를 자연과학에서 특히 수학이라는 학문에서는 어떻게 쓰는지 생각해보자.

• 벡터 공간에서의 두 벡터가 서로 독립이란 뜻은
  → 하나의 벡터가 다른 벡터로부터 만들어지지 않는다는 뜻이다.(의존하지 않으며 자신이 스스로 하나의 축을 만듦)
  
  
• 확률적 독립이란
  → 다른 사건에 의존하지 않아도 확률이 성립하는 사건이다. (자기 확률을 스스로 결정함)
  
  
• 그래프에서 간선들의 집합이 독립이라는 뜻은
  → 간선들이 서로 연결돼 있긴 하지만 절대로 순환(cycle)을 만들지 않는다는 뜻이다.
  (어느 하나의 간선도 다른 간선들로 만들어진 경로에 의해 중복되지 않음.
  즉, 각각의 간선이 불필요한 연결 없이 필수적인 연결 구조만 구성함.)
  쉽게 말해, 그래프에서 독립적인 간선 집합은 "순환 없이 최소한의 연결만을 이루는 간선들의 집합이다."

마지막 그래프에서의 독립을 간단한 예시로 풀어보면

• 섬 3개를 다리로 연결한다고 할 때
  • 섬 3개는 최소 2개의 다리로 연결됨 (트리 형태)
  • 이때 두 다리 중 하나라도 없으면 연결 끊김 (필수적, 독립적)
• 만약 다리가 3개 이상이 되면
  • 반드시 어딘가에서 순환(cycle)이 발생
  • 이때 추가된 다리는 이미 존재하는 다른 다리 조합으로 대체 가능한 중복 연결 (종속적, 비독립적)

와 같다.

서로 다른 분야에서 나타나는 이 독립이라는 개념은 언뜻 보기에 사뭇 달라보인다.

그렇지만 그 개념의 본질까지 다른 것은 아니다. 일상 속에 쓰이는 독립의 의미와 마찬가지로

벡터 공간의 독립, 확률 이론의 독립, 그래프 구조에서의 독립은 모두 다른 대상에 의해 설명되거나 구성되지 않는 상태를 뜻한다.
즉, 존재하거나 작동하기 위해 타자의 개입이 필요하지 않은 상태, 다시 말해 자기 스스로 성립할 수 있는 상태라는 점에서 본질적으로 같다.

다만 이러한 독립이 구체적으로 드러나는 방식은 그 개념이 정의되는 수학적 공간의 연산 구조에 따라 달라질 뿐이다.

• 벡터 공간에서는 연산의 기본 단위가 선형결합이기 때문에 어떤 벡터가 다른 벡터들의 선형결합으로 나타날 수 없다는 사실은
  그 벡터가 새로운 차원을 형성한다는 구조적 의미를 갖는다.
• 확률 공간에서는 연산의 기본 단위가 조건부 확률이기 때문에 어떤 사건이 다른 사건을 알아도 예측되지 않는다는 것은
  그 사건이 정보적으로 분리되어 있다는 의미를 갖는다.

즉, 동일한 철학적 정의(의존의 부재)에서 출발한 독립 개념이 서로 다른 수학적 구조 안에서는
"차원을 확장하는 힘", "정보 간 예측의 단절", "경로의 비포함성"과 같은 서로 다른 형태로 구체화되는 것이다.

결국, "의존하지 않는다"는 이 하나의 문장은 수학 각 분야에서 "생성할 수 없다", "예측할 수 없다", "경로로 대체되지 않는다"와 같이 각 구조의 언어로 번역되어 표현되는 것이다.

이제 우리는 이러한 관점에서 독립이라는 개념을 두 가지 서로 다른 방향에서 다시 바라볼 수 있다. 하나는 구조적으로 생성 불가능한 상태로서의 독립 다른 하나는 정보적으로 예측 불가능한 상태로서의 독립이다.

구조적 독립과 정보적 독립

위의 두 관점으로 독립의 개념을 두 가지 다른 ‘독립’ 개념으로 나눌 수 있을 것이다.

이를 구조적 독립과 정보적 독립이라 하겠다.

• 구조적 독립이란
  어떤 대상이 구성 요소나 구조에 의해 생성되지 않음을 의미한다.
  이는 "생성 불가능성"의 의미와 정확히 대응된다. 이는 존재의 구조나 물리적 구성 차원에서의 독립성을 뜻한다.
  
  위에서 언급했듯이
  1) 하나의 벡터가 다른 벡터들의 선형결합으로 표현되지 않는다면 그것은 구조적으로 독립이다. 
  2)  어떤 간선이 다른 간선들로 만들어진 경로에 포함되지 않는다면 그것도 구조적으로 독립이다.
  3) 프로그래밍에서 모듈 A가 모듈 B에 전혀 의존하지 않고 작동한다면
  → A는 B에 대해 구조적으로 독립이다. 또한, 반대로 B도 A에 대해 구조적으로 독립이다.
  → 이는 서로 별개의 구조라는 뜻이며 한 쪽이 없어도 다른 쪽이 문제없이 존재할 수 있음을 의미한다.
  ( 위의 예시들에 대해서는 다음 글에서 자세히 다루겠다 ) 
  
  즉, 어떤 대상이 그 자체로 존재의 조건을 만족할 수 있는가를 묻는 것이다.
• 정보적 독립이란
  어떤 사건이나 대상이 다른 정보로부터 예측될 수 없음을 의미한다.
  이는 "예측 불가능성"의 개념과 대응된다.
  1) 주사위를 두 번 던졌을 때
  → 첫 번째 결과를 알아도 두 번째 결과의 확률은 바뀌지 않는다.
  → 두 사건은 정보적으로 독립이다.
  2) 두 센서 A, B가 각각 다른 위치의 데이터를 측정하고 있고
  → A의 측정값을 알더라도 B의 값을 더 정확히 추정할 수 없다면
  → A와 B는 정보적으로 독립이다.
  
  
  즉, 어떤 대상에 대해 아는 것이 다른 대상에 대한 추론 가능성이나 예측력을 높이지 못할 때, 우리는 이 둘이 정보적으로 독립이라 한다.

이 둘은 모두 '의존하지 않는다'는 공통 개념을 포함하지만
그 기준점은 완전히 다르다.

따라서 다음과 같이 두 개의 독립이 엇갈려서 나타날 수 있다.

예를 들어

• 두 사람의 생각이 전혀 예측되지 않는다면
  → 정보적으로는 독립일 수 있지만
  → 둘이 같은 교육 시스템에서 자라났다면 구조적으로는 의존적일 수 있다.
• 반대로, 서로 완전히 분리된 장치가 있다고 해도
  → 동일한 외부 정보를 바탕으로 작동한다면
  → 구조적으로는 독립이지만 정보적으로는 종속적일 수 있다.

이렇듯 서로 다른 분야에 걸쳐 다양하게 나타나는 독립이란 개념은 단순히 "의존하지 않는다"는 말로는 충분히 설명되지 않는다.