[알고리즘] 동적 프로그래밍

 

동적 프로그래밍이란?

동적 프로그래밍은 한 마디로 시간을 절약하기 위해 추가 공간을 사용하는 전략이다.

분할 정복이랑 자주 비교되는데, 둘의 차이를 먼저 짚고 가자.

• 분할 정복 → 재귀적, 하향식(Top-down), 하위 문제 결과를 저장하지 않음
• 동적 프로그래밍 → 하위 문제의 해를 메모이제이션 또는 테이블화로 저장해서 재사용

참고로 재귀/반복은 구현 스타일, 분할 정복/DP는 설계 패러다임, 하향식/상향식은 문제를 푸는 방향이다. 헷갈리지 말 것.

 

 

동적 프로그래밍 적용 조건

 

DP를 쓰려면 다음 두 가지 조건이 모두 만족되어야 한다.

 

1. 겹치는 하위 문제 (Overlapping Subproblems)

문제를 풀다 보면 동일한 하위 문제가 반복적으로 등장해야 한다.

• ✅ 피보나치 수열 → fib(3), fib(4) 등이 여러 경로에서 반복 계산됨
• ❌ 이진 탐색 → 매번 새로운 탐색 범위를 다루므로 반복되는 하위 문제가 없음

2. 최적 부분 구조 (Optimal Substructure)

전체 문제의 해를 하위 문제들의 해로부터 구성할 수 있어야 한다.

• ✅ fib(6) = fib(5) + fib(4)
• ✅ 최단 경로 문제, 배낭 문제

팩토리얼은 DP가 필요 없다. n! = n × (n-1)!로 최적 부분 구조는 만족하지만, 동일한 하위 문제가 반복되지 않아서 DP의 이점이 없다.

 

 

두 가지 구현 방식 비교

두 조건이 모두 만족되면 아래 두 방식 중 하나를 선택할 수 있다.

구분 메모이제이션 (하향식) 테이블화 (상향식)

방향	큰 문제 → 작은 문제	작은 문제 → 큰 문제
구현	재귀 기반	반복문 기반
특징	필요한 하위 문제만 계산	모든 하위 문제를 순서대로 계산
단점	호출 스택 사용	불필요한 하위 문제도 계산할 수 있음

 

언제 뭘 쓸까?

• 어떤 하위 문제가 필요한지 미리 알기 어려우면 → 메모이제이션
• 계산 순서를 명확하게 정의할 수 있으면 → 테이블화
• 성능/메모리가 중요하면 → 테이블화 (재귀 오버헤드 없음)
• 빠르게 구현하고 싶으면 → 메모이제이션

 

 

호출 스택과 공간 복잡도

 

 

재귀를 쓰면 호출 스택이 공간 복잡도에 영향을 미친다. 이걸 모르면 공간 복잡도 분석을 잘못하게 되니 꼭 알아두자.

 

호출 스택이란?

함수가 호출될 때마다 스택 프레임이 하나씩 쌓인다. 스택 프레임에는 반환 주소, 매개변수, 지역 변수 등이 담긴다. 함수 실행이 끝나야 해당 프레임이 제거된다.

재귀 함수에서는 현재 호출이 끝나기 전에 또 다른 호출이 발생하므로 프레임이 계속 쌓인다.

예시: fib(5) 호출 시

fib(5) → fib(4) → fib(3) → fib(2) → fib(1)
  └─ fib(4)가 끝나야 fib(5)가 끝남
       └─ fib(3)이 끝나야 fib(4)가 끝남 ...

재귀가 n단계 깊이까지 이어지면 스택 프레임이 최대 n개 쌓이므로 **호출 스택의 공간 복잡도 = O(n)**이 된다.

회전 초밥집에서 빈 접시를 쌓는 것과 같다. 위 접시가 있는 한 아래 접시는 치울 수 없다.

 

피보나치 방식별 복잡도 비교

 

단순 재귀	O(2ⁿ)	O(n)	호출 스택 때문
메모이제이션	O(n)	O(n)	호출 스택 + 저장 리스트
테이블화	O(n)	O(n)	테이블 저장 필요
최적화된 반복	O(n)	O(1)	변수 2개만 유지

 

반복 방식은 스택 프레임이 쌓이지 않아서 변수 a, b 두 개만으로 O(1) 공간에 해결 가능하다.

 

 

테이블화 절차 (일반적인 흐름)

 

테이블화로 문제를 풀 때는 다음 순서를 따른다.

1. 주어진 문제를 작은 하위 문제로 나눈다
2. 원래 문제와 하위 문제의 관계를 나타내는 점화식을 도출한다
3. 하위 문제의 해를 저장할 테이블을 준비한다
4. 이미 알고 있는 기저 사례부터 테이블에 채운다
5. 저장된 값을 활용해 반복문으로 큰 문제의 답을 단계별로 계산한다

 

예시: 이항 계수 (Binomial Coefficient)

 

이항 계수는 DP의 특성을 잘 보여주는 좋은 예시다.

이항 계수란?

(a + b)ⁿ을 전개했을 때 각 항의 계수. C(n, k)로 표현하며 "n개 중 k개를 선택하는 경우의 수"를 의미한다.

공식으로는 이렇게 계산할 수 있다.

C(n, k) = n! / (k! × (n-k)!)

하지만 DP에서는 이 공식 대신 파스칼의 삼각형에서 도출한 점화식을 사용한다.

파스칼의 삼각형 → 점화식 도출

파스칼의 삼각형에서 양쪽 끝은 항상 1이고, 내부 값은 바로 위 왼쪽 + 위 오른쪽이다.

        1
       1 1
      1 2 1
     1 3 3 1
    1 4 6 4 1

이로부터 점화식을 도출하면:

 

 

기저 사례

C(n, 0) = 1   # 아무것도 선택 안 하는 경우
C(n, n) = 1   # 전부 선택하는 경우

 

 

일반 사례 (0 < k < n)

• n번째 원소를 선택하지 않는 경우 → C(n-1, k)
• n번째 원소를 선택하는 경우 → C(n-1, k-1)

두 경우가 겹치지 않으므로 더할 수 있다.

C(n, k) = C(n-1, k-1) + C(n-1, k)

 

왜 단순 재귀로 풀면 안 될까?

 

점화식 구조 자체는 분할 정복이지만, C(3,1), C(2,1) 같은 하위 문제가 여러 경로에서 반복 계산된다. 그래서 DP로 결과를 저장하고 재사용해야 효율적이다.

테이블화로 C(5, 3) 구하기

테이블에서 행은 n, 열은 k를 나타낸다. 테이블 크기는 (n+1) × (k+1).

def binomial(n, k):
    c = [[0] * (k+1) for _ in range(n+1)]
    
    for i in range(n+1):
        for j in range(min(i, k)+1):
            if j == 0 or j == i:
                c[i][j] = 1          # 기저 사례
            else:
                c[i][j] = c[i-1][j-1] + c[i-1][j]  # 점화식
    
    return c[n][k]

 

복잡도 분석

• 시간 복잡도: O(n × k) (각 셀을 한 번씩 계산)
• 공간 복잡도: O(n × k) (전체 테이블 저장)

공간 최적화 가능: 다음 행을 계산하는 데 이전 행만 있으면 되므로, 전체 테이블 대신 이전 행만 유지하면 공간을 더 줄일 수 있다.

 

핵심 요약

 

동적 프로그래밍	공간을 써서 시간을 아끼는 전략
적용 조건	겹치는 하위 문제 + 최적 부분 구조
메모이제이션	재귀 + 결과 저장 (하향식)
테이블화	반복문 + 테이블 채우기 (상향식)
호출 스택	재귀 깊이만큼 O(n) 공간 소모
이항 계수	C(n,k) = C(n-1,k-1) + C(n-1,k)