벨만이란 단어는 알고리즘이나 강화학습을 배우게 되면 자주 맞닥뜨리는 이름이다.
강화학습과 제어이론에서 다루는 벨만 최적 방정과 그래프 이론 교과서에서 배우는 벨만-포드 알고리즘이다.

두 벨만은 모두 동일인이다. 그러나, 이 두 개념은 보통은 별개로 취급된다. 하나는 추상적 최적성 조건으로, 다른 하나는 특정 계산 절차로.

먼저 벨만 방정식을 보자.
벨만 방정식이 정의되는 맥락은 마르코프 결정 과정(MDP)이다.

상태 $S$, 행동 $A$, 전이 확률 $P(s^{\prime }|s,a)$, 보상 함수 $R(s,a,s^{\prime })$, 할인율 $\gamma$로 구성된다.
이 안에서 에이전트는 정책 $\pi$를 따르며 행동하고, 목표는 장기 보상의 기대값을 최대로 만드는 최적 정책 ${\pi }^{\ast }$를 찾는 것이다.

상태 가치 함수와 행동 가치 함수는 다음과 같이 정의된다.

$$V^{\pi }(s)={\mathbb{E}}_{\pi }(\sum _{t=0}^{\mathrm{\infty }}{\gamma }^{t}R(s_t,a_t,s_{t+1})|s_0=s)$$

$$Q^{\pi }(s,a)={\mathbb{E}}_{\pi }(\sum _{t=0}^{\mathrm{\infty }}{\gamma }^{t}R(s_t,a_t,s_{t+1})|s_0=s,a_0=a)$$

최적 정책 하에서는 다음 관계가 성립한다.

$$V^{\ast }(s)=\underset{a}{max}{Q}^{\ast }(s,a),Q^{\ast }(s,a)=\sum _{s^{\prime }}P(s^{\prime }|s,a)(R(s,a,s^{\prime })+\gamma V^{\ast }(s^{\prime }))$$

이를 결합하면 최적 상태 가치 함수에 대한 벨만 최적 방정식이 도출된다.

$$V^{\ast }(s)=\underset{a}{max}\sum _{s^{\prime }}P(s^{\prime }|s,a)(R(s,a,s^{\prime })+\gamma V^{\ast }(s^{\prime }))$$

이 식은 계산법이 아니다.
“최적성이라면 반드시 자기 일관성을 가져야 한다”라는 선언이다.

이제 이 방정식을 최단 경로 문제에 끌어와 보자.
그래프 $(V,E,w)$와 시작점 $s$가 있다.

상태는 정점, 행동은 출력 간선의 선택이다.
전이는 결정론이다. 간선 $(u,v)$를 택하면 확실히 $v$에 도착한다.
따라서 $P(v|u,(u,v))=1$이다.

보상은 비용의 음수로 둔다. $R(u,(u,v),v)=-w(u,v)$.
할인율은 $\gamma =1$이다. 비용은 시점에 따라 달라지지 않기 때문이다.

이 치환을 대입하면 최적 상태 가치는 이렇게 된다.

$$V^{\ast }(v)=-\underset{s⇝v}{min}\sum w$$

여기서 $d(v)=-V^{\ast }(v)$로 치환하면 곧장 다음 한 줄이 나온다.

$$d(v)=\underset{(u,v)\in E}{min}\{d(u)+w(u,v)\}$$

벨만 방정식이 특수한 제약 아래에서 간선 완화 연산으로 단순화된 것이다.
벨만-포드가 반복하는 바로 그 한 줄이다.

연산자 $T$를 정의하자.

$$(Td)(v)=\underset{(u,v)\in E}{min}\{d(u)+w(u,v)\}$$

초기 조건은 $d^{(0)}(s)=0,d^{(0)}(v\ne s)=+\mathrm{\infty }$다.

갱신은 다음과 같다.

$$d^{(k+1)}=T{d}^{(k)}$$

$d^{(k)}(v)$는 $s$에서 $v$로 가는 경로 중 간선 수가 $k$ 이하인 것의 최소 비용이다.
따라서 $k=|V|-1$이면 모든 단순 경로가 포함되고, 최단 경로 값이 결정된다.

벨만-포드가 $|V|-1$회 반복하는 이유가 여기서 확보된다.

음수 사이클의 판정도 이 틀로 설명된다.

$\gamma =1$인 문제에서, 음수 사이클은 강화학습의 언어로는 양의 순보상 사이클이다.
값 함수는 발산한다. 따라서 값이 존재하지 않는다.

이때 $|V|$번째 반복에서 다시 갱신이 발생한다.
그래서 벨만-포드는 이 반복을 이용해 음수 사이클을 판정한다.
단순한 구현상의 트릭이 아니라, “최적값이 존재하지 않는다”는 원리의 신호다.

이 과정을 예시로 따라가자.

정점은 $S,A,B,C$다.

간선은 다음과 같다.
$(S,A)=2,(S,B)=5,(A,B)=1,(A,C)=4,(B,C)=-2$

초기 상태는
$d(S)=0,d(A)=d(B)=d(C)=\mathrm{\infty }$

첫 번째 반복에서
$d(A)=2,d(B)=3,d(C)=1$

두 번째와 세 번째 반복에서는 변동이 없다.

네 번째 반복에서도 변동이 없으면 음수 사이클은 없다.

그러나 $(C,A)=-7$을 추가하면
네 번째 반복에서 $d(A)=-6$으로 갱신된다.

따라서 음수 사이클이 존재한다고 판정한다.

다른 언어로도 같은 과정을 설명할 수 있다.

$(min,+)$ 반군에서 인접 행렬 $W$의 $(min,+)$ 거듭제곱 $W^{\otimes k}$는 길이 $k$ 경로의 비용을 담는다.
$T^k{d}^{(0)}$는 $W^{\otimes \le k}$와 시작 벡터의 곱과 같다.

동시 완화는 배치 값 반복이다.
비동기 완화는 순차 값 반복이다.
SPFA는 비동기 반복에 큐 기반의 스케줄링을 붙인 변형이다.
다익스트라는 비음수 가중치에서 우선순위 큐로 최적 순서를 잡는 비동기 반복이다.
DAG에서는 위상정렬을 통해 단 한 번의 순차 갱신으로 충분하다.

원리는 동일하고, 실행 순서만 다르다.

정점 수 $n$, 간선 수 $m$.
각 반복에서 $m$개의 완화를 수행하고, 이를 $n-1$회 반복한다.
복잡도는 $O(nm)$.

한 반복에서 갱신이 없으면 조기 종료한다.
$n$번째 반복에서 갱신이 일어나면 음수 사이클이다.

마지막으로 문장을 닫자.

벨만-포드는 독립적인 절차가 아니다.
벨만 방정식이 결정론 전이, $\gamma =1$, 보상 $=-$비용이라는 특수 조건 속으로 들어가면, 간선 완화라는 한 줄 연산으로 귀결된다.

그리고 그 한 줄이 반복될 때 최단 경로가 계산된다.

같은 원리에서 출발해, 다른 언어로 기술되고, 다른 상황에서 실행될 뿐이다.

$$d^{(k+1)}(v)=\underset{(u,v)\in E}{min}\{d^{(k)}(u)+w(u,v)\}$$

이 한 줄은 방정식과 알고리즘을 잇는 다리다.
원리에서 절차로 내려오는 길이 이렇게 수학적으로 닫힌다.

모든 재귀는 while로 바꿀 수 있다

용어부터 정리

콜스택은 함수 호출이 중첩될 때 각 호출의 지역 변수, 매개변수, 복귀 주소를 쌓아두는 메모리 영역이다.
스택 프레임은 그 안에 쌓이는 한 호출분량의 저장 단위다.
기저 사례는 더 이상 쪼개지 않고 값을 확정하는 경우다.
상태는 다음 계산을 위해 유지해야 하는 값들의 묶음이고,
후처리는 재귀 호출이 끝난 뒤 그 결과를 가지고 추가로 계산하는 부분이다.
재귀 호출 뒤에 아무 일도 남아있지 않은 경우를 꼬리 재귀,
호출 뒤에 뭔가 더 하거나 여러 번 호출하는 경우를 비꼬리 재귀라고 부른다.
콜스택이 하던 저장을 프로그래머가 직접 스택, 큐 같은 구조로 대신하는 걸 명시적 스택이라고 한다.

꼬리 재귀 예시

가장 단순한 건 카운트다운이다.

def countdown(n):
    if n == 0:
        return
    print(n)
    return countdown(n - 1)  # 호출 뒤에 계산이 없음 → 후처리 없음

이건 상태인 n만 갱신하는 while로 곧바로 바꿀 수 있다.

def countdown_loop(n):
    while n != 0:
        print(n)
        n -= 1

배열을 양끝에서 교환해 뒤집는 것도 꼬리 재귀다.

def reverse_rec_inplace(A, start=0, stop=None):
    if stop is None: stop = len(A)
    if stop - start <= 1:
        return
    A[start], A[stop-1] = A[stop-1], A[start]
    return reverse_rec_inplace(A, start+1, stop-1)  # 후처리 없음

투 포인터로 반복문 하나로 끝난다.

def reverse_two_pointers(A, start=0, stop=None):
    if stop is None: stop = len(A)
    i, j = start, stop - 1
    while i < j:
        A[i], A[j] = A[j], A[i]
        i += 1; j -= 1

비꼬리 재귀 예시

팩토리얼 정의를 보면 후처리가 뭔지 바로 보인다.

def fact(n):
    if n == 0:
        return 1
    return n * fact(n - 1)
    # fact(...) 호출이 끝난 뒤 n과 곱하는 부분이 후처리

이걸 꼬리형으로 재정의하면 이렇게 된다.

def fact_tail(n, acc=1):
    if n == 0:
        return acc
    return fact_tail(n-1, acc*n)  # 후처리가 acc 갱신으로 바뀜

def fact_loop(n):
    acc = 1
    while n > 0:
        acc *= n
        n -= 1
    return acc

혹은 기존 정의를 유지하고 콜스택의 곱셈 대기를 직접 스택으로 구현할 수 있다.

def fact_stack(n):
    stack = []
    while n > 0:
        stack.append(n)  # 곱해야 할 값을 저장
        n -= 1
    acc = 1
    while stack:
        acc *= stack.pop()
    return acc

비꼬리 재귀의 전형은 이진트리 중위 순회다.

def inorder(node):
    if node is None:
        return
    inorder(node.left)
    print(node.value)  # 왼쪽 끝난 뒤의 후처리
    inorder(node.right)

반복문으로 바꾸면 현재 노드와 방문 단계를 스택에 저장해서 처리한다.

def inorder_iter(root):
    stack = []
    curr = root
    while curr or stack:
        while curr:
            stack.append(curr)  # 왼쪽 처리 전 상태 저장
            curr = curr.left
        curr = stack.pop()
        print(curr.value)       # 후처리
        curr = curr.right

일반화

한 번의 재귀 호출로 끝나고 후처리가 없는 꼬리 재귀는 상태만 갱신하는 while로 바로 변환 가능하다.
후처리나 다중 호출이 있는 비꼬리 재귀는 두 가지다. 수식을 바꿔 꼬리형으로 만들고 루프로 바꾸거나, 명시적 자료구조로 호출 상태를 저장·복원한다.
이 과정을 따르면 어떤 재귀든 반복문으로 옮길 수 있다.

1. 문제 상황

정수 구간 [l, r)의 합을 구하는 재귀 함수를 생각한다.
즉, l부터 r-1까지의 정수를 모두 더하는 것이다.

이 문제를 재귀로 구현하는 방법은 크게 두 가지가 있다.

# ① 체인형: 오른쪽 끝을 하나씩 줄이는 방식
def sum_chain(l, r):
    if r - l == 1:  # 구간 길이가 1이면 원소 그대로 반환
        return l
    return sum_chain(l, r-1) + (r-1)

# ② 분할형: 중간 지점을 기준으로 두 구간으로 나누는 방식
def sum_divide(l, r):
    if r - l == 1:  # 구간 길이가 1이면 원소 그대로 반환
        return l
    mid = (l + r) // 2
    return sum_divide(l, mid) + sum_divide(mid, r)

직관적으로 보면, 분할형은 재귀 깊이가 짧아 보이기 때문에 더 빠를 것 같은 착각이 생길 수 있다.

2. 호출 구조 살펴보기

아래 그림은 n = 8일 때 두 방식의 호출 구조이다.
여기서 n은 구간 길이(r - l)이다.

체인형 (n=8)

sum(1,9)
 └ sum(1,8)
    └ sum(1,7)
       └ sum(1,6)
          └ sum(1,5)
             └ sum(1,4)
                └ sum(1,3)
                   └ sum(1,2)
                      └ sum(1,1)

• 깊이: 8
• 호출 횟수: 8

분할형 (n=8)

           sum(1,9)
       /             \
  sum(1,5)         sum(5,9)
  /     \           /     \
(1,3) (3,5)     (5,7)  (7,9)
 / \   / \       / \    / \
...   ...      ...    ...

• 깊이: 약 log₂(8) = 3
• 호출 횟수: 15 (2n - 1)
• 리프 노드(구간 길이 1)는 8개 → 모든 원소를 한 번씩 처리해야 한다.

3. 복잡도 비교

둘 다 총 연산량은 O(n)이다.
분할형은 깊이가 짧지만, 모든 원소를 처리해야 하는 사실은 변하지 않는다.

4. 언제 유리하고 언제 불리한가

체인형이 유리한 경우

• n이 작아 스택 깊이가 문제가 되지 않는 경우
• 호출 오버헤드가 중요한 경우 (호출 수가 더 적다)
• 단순 반복문을 재귀로 바꾸는 정도의 용도일 때

체인형이 불리한 경우

• n이 커서 재귀 깊이가 너무 깊어지는 경우 (스택 오버플로우 위험)
• 병렬로 나눠 처리하고 싶은 경우

분할형이 유리한 경우

• 병렬 실행 환경인 경우: 하위 구간을 동시에 처리할 수 있어 실행 시간을 log n 수준으로 줄일 수 있다.
• 스택 깊이를 줄이고 싶은 경우
• 본질적으로 분할 후 결합이 필요한 문제(예: 병합정렬, 세그먼트 트리)일 때

분할형이 불리한 경우

• 단일 스레드 환경에서 단순한 합만 구할 때: 호출 수가 많아져 오히려 느릴 수 있다.
• 결합 단계의 연산이 매우 작아서 분할 이점이 없는 경우

5. 왜 분할정복이 항상 빠르지 않은가

깊이와 전체 시간은 다른 개념이다.

• 깊이는 재귀 호출이 한 번에 얼마나 길게 이어지는지를 나타낸다.
• 전체 시간은 모든 호출에서 실행하는 연산량의 합이다.
• 구간 합처럼 모든 원소를 반드시 한 번씩 처리해야 하는 문제는, 깊이가 줄어도 리프 노드 수(=원소 수)가 그대로라 전체 연산량이 변하지 않는다.

6. 확장 아이디어

• 병렬 계산: 전체 연산량은 O(n)이지만, 병렬 환경에서는 실행 시간이 O(log n)에 가까워질 수 있다.
• 다수의 구간 합 질의: 전처리로 누적합(prefix sum)을 만들면 질의당 O(1)에 가능하다.
• 값이 자주 바뀌는 경우: 세그먼트 트리를 사용하면 질의와 갱신을 모두 O(log n)에 할 수 있다.

7. 결론

• 분할정복은 깊이를 줄일 수 있지만, 원소를 모두 처리해야 하는 문제에서는 전체 시간복잡도가 줄지 않는다.
• 병렬성과 메모리 사용량이 중요한 경우에는 분할형이 유리하고, 단순 합산이나 작은 입력에서는 체인형이 더 낫다.
• 알고리즘을 고를 때는 계산량과 환경(단일/병렬, 메모리 제약)을 함께 고려해야 한다.

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

동적계획법(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)$

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

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

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

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

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

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

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

▸ 세 전략의 비교

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

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

이분탐색의 구조

이 문제는 정수 범위 위의 단조 불리언 함수(monotonic boolean function)를 기반으로 한다.
수학적으로 이분탐색이 정확히 작동할 수 있는 구조 위에 놓여 있다.

1. 문제 정의

• 심사관은 여러 명 존재한다
• 각 심사관은 time[i]분마다 1명씩 심사 가능하다
• 사람 수는 n명이다
• 목표: 모든 사람이 심사를 마치기 위한 최소 시간 t를 구하라

2. 함수 정의

시간 t가 주어졌을 때, 각 심사관이 처리할 수 있는 인원을 모두 더하면
다음과 같은 함수 f(t)를 얻는다.

$$f(t)=\sum _{i=1}^m\lfloor \frac{t}{\text{time}[i]}\rfloor$$

이 함수는 단조 증가 함수이다.
즉, t가 커질수록 처리 인원은 절대 줄지 않는다.

3. 명제 정의

우리는 다음과 같은 참/거짓 명제를 생각할 수 있다.

$$P(t):=(f(t)\ge n)$$

이 명제는 t가 증가할수록 False → True로 바뀐다.
즉, 단조 불리언 함수이며, 한 번만 상태가 바뀐다.

목표는 P(t)가 처음으로 True가 되는 가장 작은 t를 찾는 것이다.

4. 이분탐색이 가능한 이유

이분탐색은 다음 조건을 만족할 때 사용할 수 있다:

• 정수 범위 t ∈ ℕ
• P(t)는 단조 불리언 함수 (False → True)
• 우리는 min { t | P(t) = True } 를 찾고자 한다

즉, "논리 명제의 최소 참 구간"을 찾는 탐색이 된다.

아래는 이를 구현한 이분탐색 알고리즘이다.

def solution(n, times):
    left, right = 1, max(times) * n
    while left <= right:
        mid = (left + right) // 2
        people = sum(mid // t for t in times)
        if people >= n:
            right = mid - 1
        else:
            left = mid + 1
    return left

언리얼 엔진에 NevarokML 설치하는 것이 생각보다 오래 걸렸다. 
언리얼 엔진으로 강화학습 환경 구성하려던 게 몇시간짜리 트러블슈팅이 됐다
처음엔 UE5.5 C++ 프로젝트로 빌드했는데 C++ 컴파일러 버전이 안 맞는다는 오류가 떴다
Visual Studio 설치부터 다시 하고 맞는 버전 찾는 데 시간 쓰고 드디어 빌드 환경 맞췄다
NevarokML 플러그인을 깃헙에서 클론해서 Plugins 폴더에 넣었는데 또 NNE 플러그인이 없다고 했다
언리얼 에디터에서 플러그인 설정 가서 NNE 활성화했지만 여전히 같은 오류
혹시나 해서 UE5.4로 버전 바꾸고 컴파일러 또 바꾸고 같은 작업 반복
그래도 안 됐다

이쯤 되면 누구나 고민한다 다른 플러그인 써야 하나 내가 뭐 놓쳤나
그때 NevarokML 공식 문서를 다시 봤다
거기엔 분명히 UE5.2까지만 지원한다고 적혀 있었다
UE5.2로 다시 설치하고 세팅했더니 아무 문제 없이 플러그인이 돌아갔다

이 과정에서 LLM의 약점을 명확히 느꼈다
코드 설명 문법 오류 알고리즘 이런 건 정말 빠르고 정확하다
근데 환경 세팅 버전 문제 플러그인 호환성 같은 건 기대 이하였다
왜냐면 LLM은 내가 주는 정보만으로 답을 만들어야 하는데 문제는 내가 뭘 모르는지조차 모를 때다
환경 설정에서 오류가 날 때는 내가 정확히 어떤 설정을 했고 어떤 구조에서 오류가 발생하는지 전체 상황을 공유하지 않으면 LLM도 그냥 이럴 수도 있고 저럴 수도 있다 수준에서 끝난다

게다가 실시간으로 상태를 점검할 수 없다는 한계도 크다
LLM은 내가 지금 어떤 파일을 열었고 어떤 버전을 설치했고 어떤 경로에 어떤 플러그인이 들어있는지 모른다
그걸 일일이 설명해줘야 하는데 정작 설명하는 나도 헷갈리는 경우가 많다
이게 LLM이 코드를 이해하지 못한다는 말과는 좀 다르다
LLM은 상태를 추적하지 못한다
시스템에서 벌어지는 일련의 흐름을 보는 눈이 없다

이번에 느낀 건 하나다
LLM은 결국 상황이 명확할 때만 제대로 작동한다
초기 설정이 꼬였거나 내가 뭘 놓쳤는지 감이 안 올 때는 공식 문서를 보고 하나하나 짚어보는 게 더 빠르다
LLM이 해줄 수 없는 건 상황 판단이다
지금 이 문제의 본질이 뭔지 전체 그림에서 뭐가 틀렸는지 찾는 건 여전히 사람 몫이다

그리고 이건 앞으로 어떤 프로젝트를 하든 꼭 기억해야 할 부분 같다
LLM은 강력한 도구지만 모든 걸 맡길 수는 없다
특히 환경 세팅 같은 거 직접 확인하고 체크하는 습관이 없으면 LLM이 아니라 누구도 답 못 준다

세상을 분류한다는 것

우리는 세상을 이해하기 위해 그것을 분류한다.
철학자는 존재를 분류했고 프로그래머는 객체를 분류한다.
각자의 언어는 다르지만 그들이 하는 일은 닮아 있다.

세계를 잘게 나누고 공통과 차이를 찾아내며 구조화된 틀 안에서 의미를 재구성한다.

철학에서 분류는 존재론의 시작이다.
어떤 것이 “무엇”인지 말하려면, 그것이 무엇과 같고 무엇과 다른지를 먼저 설명해야 한다.
그래서 아리스토텔레스는 “류”와 “종차”라는 개념을 통해 사물을 나눴다.

프로그래밍에서도 분류는 설계의 시작이다.
우리는 객체지향에서 “클래스”를 만들고, 그것을 상속하며 기능을 나누고 확장한다.
어떤 객체가 어떤 동작을 하는지 어떤 속성을 가지는지 정의하기 위해 먼저 그것이 속한 구조를 정한다.

분류는 단순히 정리의 기술이 아니다.
그것은 생각하는 방식, 세계를 틀에 담기 위한 노력이다.

철학의 분류 원리는 류와 종차이다.

아리스토텔레스는 존재를 분류하기 위해 두 개념을 도입했다.
바로 류(類, Genus)와 종차(種差, Differentia)다.

류는 공통적인 범주다. 여러 사물 사이의 유사성을 모아 상위 개념으로 묶은 것.
예를 들어, 인간과 고양이는 모두 ‘동물’이라는 류에 속한다.

하지만 같은 류에 속한다고 해서 모두 같은 것은 아니다.
무엇이 인간을 고양이와 다르게 만드는가?
그 고유한 차이를 아리스토텔레스는 종차라 불렀다.

그래서 인간은
“동물이라는 류”에,
“이성적이라는 종차”가 더해져 정의된다.
인간 = 동물(류) + 이성적(종차)

류는 공통을 말하고, 종차는 차이를 말한다.
아리스토텔레스는 이렇게 어떤 존재를 특정지었다.

객체지향 프로그래밍의 분류 방식 : 클래스와 상속

객체지향 프로그래밍도 세상을 분류한다.
우리는 비슷한 객체들을 묶어 클래스를 만들고,
그 클래스를 기반으로 객체를 생성하며,
필요할 땐 기존 클래스를 상속해 새로운 개념을 정의한다.

이때 상위 클래스는 류에 해당한다.
공통된 속성과 동작을 정의하고,
하위 클래스는 이를 물려받아 자신의 고유한 차이를 추가한다.

예를 들어보자.

Animal이라는 클래스가 있다면
그 안에는 모든 동물이 공통적으로 가지는 특징이 들어간다.
Human 클래스는 Animal을 상속받고,
여기에 “말한다”는 메서드를 더한다.

class Animal:        # 류
    def eat(self):
        return "먹는다"

class Human(Animal): # 종 = Animal + 고유 기능
    def speak(self):
        return "말한다"

상속은 공통과 차이를 분리하는 구조다.
류는 클래스가 되고 종차는 고유한 메서드가 된다.

코드에서 드러나는 류와 종차의 개념

객체지향에서 클래스는 본질을 담고,
상속은 그 본질을 계승하며 오버라이딩은 차이를 말한다.

이 구조는 철학자가 존재를 분류하던 방식과 닮아 있다.

아리스토텔레스는 "무엇인가를 정의하려면 그것이 속한 류를 말하고,
그 안에서의 차이를 밝혀야 한다"고 했다.

OOP에서도 객체는 같은 구조를 따르되 서로 다르게 행동한다.
그 차이는 오버라이딩을 통해 표현된다.

class Animal:
    def speak(self):
        return "소리를 낸다"

class Dog(Animal):
    def speak(self):  # 종차
        return "멍멍"

class Human(Animal):
    def speak(self):  # 종차
        return "말한다"

여기서 def speak()는 Dog와 Human에서 같은 메서드지만 다른 동작을 한다.
이것이 바로 철학에서 말하는 종차다.

그래서, 오버라이딩은
공통된 형상 위에 차이를 선언하는 일이다.

철학에서 존재는 "공통 + 차이"로 정의되었고,
객체지향도 마찬가지로 "상속 + 구현"으로 객체를 구성한다.

객체지향은 결국
존재를 분류하고 형식화하는 철학의 사유 방식을
하나의 코드 구조로 옮겨온 것이다.

철학과 OOP 개념

class Animal:              # 류
    def move(self):
        return "움직인다"

class Bird(Animal):        # 종 = Animal + 고유 기능
    def fly(self):         # 종차
        return "난다"

추상화는 공통과 차이의 경계에서

추상화는 본질을 남기고 나머지를 덜어내는 일이다.
철학에서 그것은 ‘개념’을 만드는 방식이고
프로그래밍에서는 ‘클래스’를 만드는 방식이다.

철학자에게 추상화란
수많은 구체적 사물들 속에서 공통된 속성을 끌어올리는 일이다.
사람, 개, 고양이를 보며 "이들은 모두 동물이다"라고 말하는 순간
그는 이미 ‘류’라는 추상화를 수행한 것이다.

프로그래머도 마찬가지다.
여러 객체들에서 반복되는 구조를 뽑아내고
그것을 클래스라는 틀로 만든다.
이 틀은 구체가 아니지만
수많은 구체를 만들어내는 시작점이 된다.

그런데 추상화는 단지 공통만을 말하지 않는다.
차이를 남기는 방식으로 공통을 정의한다.
바로 그 경계에서 류와 종차가 나뉘고,
슈퍼클래스와 오버라이딩이 갈라진다.

객체지향에서 추상화란
공통과 차이 사이의 균형을 설계하는 일이다.
너무 많은 것을 끌어올리면 본질을 잃고
너무 적게 정의하면 확장할 수 없다.

그래서 추상화는 단순한 구조화가 아니다.
그것은 생각하는 기술이며
존재를 어떻게 바라보고 나눌 것인가에 대한 깊은 태도다.