완전탐색, 동적계획법, 탐욕 알고리즘을 나누는 조건은 무엇인가?

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

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

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

 

 

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

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

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

 

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

 

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

 

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

 

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

 

---

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

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

선택 구조란 각 선택이 다른 선택에 영향을 주거나
특정한 규칙을 따라 이어질 수 있는 관계를 뜻한다.

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

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

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

수학적 표현

• 해 공간: $S = {x_1, x_2, ..., x_n}$
• 전수 평가: $\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)이라는 수학적 구조로 나타난다.

상태 정의와 구조화 (formalizing)

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

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

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

 

■ 점화식과 상태 전이

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

→ $f(i) = \min {f(i - 1) + a,\ f(i - 2) + b}$
→ $f(i) = \max {f(i - 1),\ f(i - 3) + c_i}$
→ $f(i, j) = \min {f(i - 1, j),\ f(i, j - 1)} + d(i, j)$
→ $f(s) = \min_{t \in T(s)} {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) = \min_{j < i} 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})$의 정의

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

1. $\emptyset \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 \exists x \in B \setminus A,; A \cup {x} \in \mathcal{I}$ (교환 가능성)

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

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

정보량 해석

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

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

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

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

구조적 조건 요약

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

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

예시

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

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

 

정리하자면

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

 

▸ 세 전략의 비교

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

구분	완전탐색	동적계획	그리디 알고리즘
선택 간 관계	관계 없음	정보적으로 종속	구조적으로 독립
상태 구성 방식	모든 조합 열거	점화식 기반 수열	독립 집합의 확장
수학적 조건	공리 없음	점화식, 최적 부분 구조	매트로이드 공리
정보량 해석	$H(Y	X) = H(Y)$	$H(Y
상호정보량	정의 불가 또는 $0$	$I(X;Y) > 0$	$I(X;Y) = 0$
전략 형태	전체 열거	재귀 기반 구성	순간 최적 선택

● 완전탐색은 선택 구조를 알 수 없을 때, 전체 가능성을 시도하는 방식이다.

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