[알고리즘 설명][Python] 다이나믹 프로그래밍(dp, dynamic programming)

이 게시글은 CS(컴퓨터공학) 프로그래밍 기초를 어느 정도 알고 있다고 가정하고 아주 간단하게 설명하는 게시글입니다.

혹시나 모르는 부분이 있으면 댓글로 질문해주세요.

 

한 줄 요약 : 초기식과 점화식을 구하고 캐시(cache) 데이터를 잘 재활용하면 됩니다. 그런데 초기식과 점화식을 구하는 것이 정말로 어렵기 때문에 다이나믹 프로그래밍 문제는 많이 풀어본 것만이 답입니다.

 

개념은 쉬우나 적용하기가 상당히 어려운 3대 알고리즘 패러다임이 존재합니다.

- 다이나믹 프로그래밍

- 그리디 알고리즘

- 분할 정복 알고리즘

이 중에서 이번에는 dp에 대해 간단하게 설명합니다.

아래에는 백준(BOJ) 문제들에 나왔던 초기식 및 점화식을 소개하며 맨 아래에는 왜 다이나믹 프로그래밍이 개념은 쉬우나 끝도 없이 어려워질 수 있는지 알게 됩니다.

 

다이나믹 프로그래밍(동적 계획법)은 뭔가 이름을 보면 막 다이나믹 하게 코딩해야 할 것 같은 느낌이 들죠?

하지만 이 알고리즘을 정말 간단하게 설명하면 "다음 데이터를 구하기 위해 이전 데이터들을 재활용 하자"입니다.

정말 얼탱이가 없지만 이게 핵심이 맞습니다.

 

다이나믹 프로그래밍의 가장 기초인 피보나치 수를 예시로 들어줍니다.

피보나치 수는 0, 1, 1, 2, 3, 5, 8, 13, ...으로 이루어져 있는 수열입니다.

잘 보시면 

0 + 1 = 1

1 + 1 = 2

1 + 2 = 3

2 + 3 = 5

이렇게 다음 수를 구하기 위해 앞에 있는 2개의 숫자를 재활용하여 더해주는 모습이 보이죠?

초기식은 dp[0] = 0, dp[1] = 1로 해주면 되고요. 점화식은 dp[i] = dp[i-1] + dp[i-2]로 해주면 됩니다.

이것이 바로 다이나믹 프로그래밍입니다.

초기식과 점화식을 사용해서 다음 데이터를 구하기 위해 이전 데이터들을 재활용하는 것입니다.

이 과정을 Python으로 구현하면 다음과 같습니다.

import sys

input = sys.stdin.readline

# dp 크기 제한
LIMIT = 40

# dp 테이블 설정
dp:list = [0 for _ in range(LIMIT + 1)]

# 초기식
dp[0], dp[1] = 0, 1

# 점화식
for i in range(2, LIMIT + 1, 1) :
    dp[i] = dp[i-1] + dp[i-2]
    
# 40번째 피보나치 수를 출력합니다.
print(dp[40]) # 결과 : 102334155

# dp는 이전 데이터들을 저장하므로 20번째 피보나치 수를 즉시 출력할 수 있습니다.
print(dp[20]) # 결과 : 6765

dp는 또한 cache 역할도 하므로 초기식과 점화식을 활용하여 패턴이 존재하는 데이터들을 생성해서 값을 불러올 때 dp 테이블에 인덱싱하여 O(1) 시간 복잡도로 즉시 출력할 수 있습니다.

즉, 초기식과 점화식을 잘 구해서 정확하게 알고 있다면 구현하기가 갑자기 쉬워지는 것이 dp의 매력입니다.

하지만 치명적인 단점은 숫자들의 패턴만 보고 초기식과 점화식을 유도하기가 너무 어렵다는 것입니다.

거의 아이큐 테스트나 다름이 없죠.

 

그리고 저희가 수학 고교 과정에서 예시로 아래와 같은 점화식 형태를 정말 지겹게 많이 봤을 거예요.

고등학교 교육과정 속 주요 선형 점화식 총정리

우리가 수능이나 내신에서 주구장창 지겹도록 보았던 점화식들이 알고 보면 전부 선형 점화식(Linear Recurrence Relation)의 카테고리에 속합니다. 이 수식들을 마스터해두면 DP 문제에서 이전 상태 데이터를 어떻게 누적해야 하는지 완벽하게 감을 잡을 수 있습니다.

$$ \begin{aligned} & \textbf{1. 등차수열 (Arithmetic Progression)} \\ & \text{[점화식]} \quad a_{n+1} = a_n + d \quad (d \text{는 공차}) \\ & \text{[일반항]} \quad a_n = a_1 + (n-1)d \\ \\ \\ & \textbf{2. 등비수열 (Geometric Progression)} \\ & \text{[점화식]} \quad a_{n+1} = r \cdot a_n \quad (r \text{은 공비}) \\ & \text{[일반항]} \quad a_n = a_1 \cdot r^{n-1} \\ \\ \\ & \textbf{3. 덧셈 함수형 점화식 (개차수열 형태)} \\ & \text{[점화식]} \quad a_{n+1} = a_n + f(n) \\ & \text{[일반항]} \quad a_n = a_1 + \sum_{k=1}^{n-1} f(k) \quad (n \ge 2) \\ \\ \\ & \textbf{4. 곱셈 함수형 점화식 (축차대입 형태)} \\ & \text{[점화식]} \quad a_{n+1} = f(n) \cdot a_n \\ & \text{[일반항]} \quad a_n = a_1 \cdot \prod_{k=1}^{n-1} f(k) = a_1 \cdot \left( f(1) \cdot f(2) \cdots f(n-1) \right) \quad (n \ge 2) \\ \\ \\ & \textbf{5. 일차 선형 결합 기본형 (알파형 점화식)} \\ & \text{[점화식]} \quad a_{n+1} = p \cdot a_n + q \quad (p \neq 1, q \neq 0) \\ & \text{[변형식]} \quad a_{n+1} - \alpha = p(a_n - \alpha) \quad \left( \text{단, } \alpha = \frac{q}{1-p} \right) \\ & \text{[일반항]} \quad a_n = (a_1 - \alpha) \cdot p^{n-1} + \alpha \\ \\ \\ & \textbf{6. 인접 3항간 선형 점화식 (피보나치 확장형)} \\ & \text{[점화식]} \quad a_{n+2} + p \cdot a_{n+1} + q \cdot a_n = 0 \\ & \text{[특성방정식]} \quad x^2 + px + q = 0 \text{ 의 두 근을 } \alpha, \beta \text{ 라 할 때:} \\ & \text{[일반항]} \quad a_n = A \cdot \alpha^{n-1} + B \cdot \beta^{n-1} \quad (A, B \text{는 초기 조건 } a_1, a_2 \text{ 로 결정}) \end{aligned} $$

결국 고교 시절에 이러한 점화식 문제들을 잘 풀었다면 dp 문제도 원활하게 잘 풀 수 있습니다.

 

PS(Programming Solving) 분야에서는 거의 웬만하면 선형 점화식입니다.

하지만 가끔 비선형 점화식들이 나오긴 하는데 아래와 같이 나오는 경우입니다.

알고리즘 속 주요 비선형 점화식

선형 점화식이 과거의 값들에 상수를 곱해 단순히 더하는 수준이었다면, 비선형 점화식(Non-linear Recurrence Relation)은 DP 테이블의 결과값끼리 서로 곱해지거나 구간이 유동적으로 쪼개지는 형태를 가집니다. 알고리즘 최적화의 끝판왕 문제들에서 주로 찾아볼 수 있습니다.

$$ \begin{aligned} & \textbf{1. 카탈란 수 (Catalan Numbers) — 계승 및 분할 유형} \\ & \text{[적용 문제]} \quad \text{올바른 괄호 쌍의 개수, 다각형을 삼각형으로 쪼개는 경우의 수 등} \\ & \text{[초기식]} \quad dp[0] = 1 \\ & \text{[점화식]} \quad dp[n] = \sum_{i=0}^{n-1} dp[i] \cdot dp[n-1-i] \quad (n \ge 1) \\ & \text{[특징]} \quad \text{이전 DP 테이블의 값인 } dp[i] \text{ 와 } dp[n-1-i] \text{ 가 서로 곱해지는 전형적인 비선형 구조입니다.} \\ \\ \\ & \textbf{2. 행렬 곱셈 순서 최적화 (Matrix Chain Multiplication) — 구간 DP 유형} \\ & \text{[적용 문제]} \quad \text{연속된 행렬을 곱할 때 연산 횟수를 최소화하는 연산 순서 찾기} \\ & \text{[초기식]} \quad dp[i][i] = 0 \quad (\text{행렬 1개의 곱셈 비용은 0}) \\ & \text{[점화식]} \quad dp[i][j] = \min_{i \le k \lt j} \left( dp[i][k] + dp[k+1][j] + r_i \cdot c_k \cdot c_j \right) \\ & \quad \quad \quad \quad \left( \text{단, } r_i \text{는 } i\text{번째 행렬의 행 크기, } c_k\text{는 } k\text{번째 행렬의 열 크기} \right) \\ & \text{[특징]} \quad \text{고정된 오프셋이 아니라, 구간을 가르는 변수 } k \text{ 에 의해 다중 분기가 일어나는 비선형 최적화식입니다.} \\ \\ \\ & \textbf{3. 최적 이진 탐색 트리 (Optimal Binary Search Tree)} \\ & \text{[적용 문제]} \quad \text{각 데이터의 검색 빈도가 다를 때, 탐색 비용을 최소화하는 이진 탐색 트리 구성} \\ & \text{[초기식]} \quad dp[i][i-1] = 0, \quad dp[i][i] = \text{weight}[i] \\ & \text{[점화식]} \quad dp[i][j] = \min_{i \le k \le j} \left( dp[i][k-1] + dp[k+1][j] \right) + \sum_{m=i}^{j} \text{weight}[m] \\ & \text{[특징]} \quad \text{구간 내부에서 루트 노드가 될 후보 } k \text{ 를 모두 탐색하며 좌우 서브트리의 최소 비용을 조합합니다.} \end{aligned} $$

비선형 점화식 문제가 나오면 그냥 망했다...고 생각하고 자신의 직관을 믿어서 하는 방법 밖에 없습니다.

 

하지만 거의 대부분 dp 문제들은 선형 점화식입니다.

즉, 아무리 어려워도 선형 점화식 형태를 잘 기억해서 잘 유도하면 끝나는 문제입니다.

단, 아래와 같이 몇 가지 주의사항들을 챙겨주세요.

1. 피보나치 수열처럼 dp[i-1], dp[i-2]만 참고하는 것도 있으나 가금 dp[i-5]까지 확인해야 하는 경우도 있습니다. 이 점을 잘 유의해주세요.

2. dp[i] = dp[i-1] + dp[i-2]로 깔끔하게 떨어지면 얼마나 좋을까요? 하지만 dp[i] = (dp[i-1] + dp[i-2]) % MOD처럼 모듈러 연산을 적용해야 하는 경우도 있습니다.

3. dp[i] = min(dp[i-1] + dp[i-2], dp[i-1] + dp[i-3])처럼 min, max가 혼합될 수도 있습니다. 이런 경우는 보통 그리디 알고리즘도 같이 오는 경우이니 이 점 유의해야 합니다.

4. 특정 범위에서는 다른 점화식을 사용해야 할 수도 있습니다. 예시로 i < 5까지는 dp[i] = dp[i-1] + dp[i-2]로 해결되나 i >= 5부터는 dp[i] = dp[i-1] + dp[i-3]으로 확 바뀌는 경우가 생길 수도 있습니다.

5. 점화식은 1개가 아닐 수도 있습니다. 점화식이 2개 이상인 경우도 있으며 이 때 각각 다른 점화식으로 잘 구해야 합니다.

6. 점화식은 1차원이 아닌 2차원 테이블 혹은 3차원 테이블이 될 수도 있으며 재수 없으면 4차원 테이블이 나오는 경우도 있습니다.

7. 추가로 dp[i] = min(dp[i-1] + cost1, dp[i-2] + cost2)처럼 dp 테이블 데이터가 아닌 외부 데이터가 들어올 수도 있습니다. 이 점도 참고해야 합니다.

8. 이게 진짜 더럽고 짜증나는 부분인데 순수 dp로 안 풀리고 다른 알고리즘을 사용해야 하는 경우입니다. 예를 들어 똑같이 피보나치 수열의 점화식 dp[i] = (dp[i-1] + dp[i-2]) % MOD라고 해도 최대 index가 10^18이면 O(N)으로 해결이 안 됩니다. 그러므로 분할 정복을 활용한 거듭제곱으로 행렬 곱셈을 해서 아주 빠르게 dp[i]를 구해야 하는 경우가 생길 수도 있습니다.

9. 모든 과거를 다 참고해야 하는 경우가 있습니다. 그 예시가 prefix(누적 합)로 이 때는 prefix[i] = prefix[i-1] + value[i-1] 형식의 점화식을 사용해야 할 수도 있습니다.

10. 메모리가 많이 제한되는 경우 가장 마지막 데이터들을 삭제하고 필요한 데이터만 cache에 저장하는 방법도 있습니다.

예시로 0 1 1 2 3일 때 메모리가 극한으로 제한되어 있다면 0 데이터를 제거하고 1 1 2 3 5 형식으로 저장해야 하는 경우도 있습니다.

11. 예시로 dp[8-i] = dp[9-i] + dp[10-i]처럼 역순으로 진행하는 경우도 있습니다.

 

자... 왜 어째서 다이나믹 프로그래밍은 개념은 그저 "다음 데이터를 구하기 위해 이전 데이터들을 활용한다"이나 막상 활용은 왜 악랄한지 보이죠? 출제자가 악용하면 끝도 없이 어려워질 수 있습니다.

 

아래에는 백준(BOJ)에서 나왔던 초기식 및 점화식이며 맨 마지막은 dp가 어디까지 악랄해질 수 있는지 확인할 수 있습니다.

🔥 다이나믹 프로그래밍(DP) 문제 유형별 점화식 해부

크롤링된 수많은 소스 코드들의 규칙성을 분석하여, DP의 가장 핵심인 초기식과 점화식을 유형별로 완벽하게 분류했습니다. 실전 코딩 테스트 및 대회에서 가장 빈번하게 등장하는 최적화 템플릿입니다.

1. 1차원 선형 DP (피보나치, 수열, 타일링)

과거의 1~2개 상태만 참조하여 일직선으로 값을 채워나가는 가장 기본적인 형태입니다.

1003번 (피보나치)	초기식: dp[0] = 1, dp[1] = 1 점화식: dp[i] = dp[i-1] + dp[i-2]
11726번 (2xn 타일링)	초기식: dp[1] = 1, dp[2] = 2 점화식: dp[i] = dp[i-1] + dp[i-2]
9461번 (파도반 수열)	초기식: dp[1] = 1, dp[2] = 1, dp[3] = 1 점화식: dp[i] = dp[i-1] + dp[i-5] (또는 dp[i-2] + dp[i-3])
2839번 (설탕 배달)	초기식: dp[3] = 1, dp[5] = 1 점화식: dp[i] = min(dp[i-3] + 1, dp[i-5] + 1)

2. 조건부 1차원 DP (선택 및 제약 조건)

단순 합산이 아니라, 특정 조건이나 배수 판별에 따라 max/min 분기가 일어나는 형태입니다.

1463번 (1로 만들기)	초기식: dp[1] = 0 점화식: dp[i] = dp[i-1] + 1 (이후 i%2==0, i%3==0 조건에 따라 min(dp[i], dp[i/K]+1) 갱신)
2579번 (계단 오르기)	초기식: dp[1] = step[1], dp[2] = step[1] + step[2] 점화식: dp[i] = step[i] + max(dp[i-2], dp[i-3] + step[i-1])

3. 2차원 배열 / 그리드 DP

행과 열을 가지는 2차원 테이블에서 자신의 상태(예: 이전 줄에서 고른 색상, 방향 등)를 배열의 열(Column)로 관리하는 형태입니다.

1149번 (RGB거리)	초기식: dp[0][0] = R[0], dp[0][1] = G[0], dp[0][2] = B[0] 점화식: dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + cost[i][0] (다른 색상도 동일)
1932번 (정수 삼각형)	초기식: dp[0][0] = triangle[0][0] 점화식: dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]
9465번 (스티커)	초기식: dp[0][1] = arr[0][1], dp[1][1] = arr[1][1] 점화식: dp[0][j] = max(dp[1][j-1], dp[1][j-2]) + arr[0][j]
17070번 (파이프 옮기기)	초기식: dp[0][1][0] = 1 (가로 상태 시작) 점화식: dp[i][j][0] = dp[i][j-1][0] + dp[i][j-1][1] (벽 여부 판별 후 상태 전이)

4. 자원 분배 DP (Knapsack Problem)

제한된 무게나 자원 내에서 가치를 극대화하기 위해 "물건을 넣을 것인가, 말 것인가"를 2차원 공간에 기록합니다.

12865번 (평범한 배낭)	초기식: dp[i][0] = 0, dp[0][j] = 0 점화식: 1. 무거워서 못 넣을 때: dp[i][j] = dp[i-1][j] 2. 넣을 수 있을 때: dp[i][j] = max(dp[i-1][j], dp[i-1][j-W[i]] + V[i])

5. 수열 탐색 DP (LIS, LCS)

배열을 이중 반복문으로 순회하며 최대 길이를 늘려가는 형태입니다.

11053번 (LIS)	초기식: dp[i] = 1 (자기 자신 하나 포함) 점화식: dp[i] = max(dp[i], dp[j] + 1) (단, j < i 이고 arr[j] < arr[i] 일 때)
9251번 (LCS)	초기식: dp[i][0] = 0, dp[0][j] = 0 점화식: 1. 문자가 같을 때: dp[i][j] = dp[i-1][j-1] + 1 2. 문자가 다를 때: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

6. 트리 DP (Tree DP)

그래프(트리)의 바닥(Leaf)부터 꼭대기(Root)까지 서브트리의 해를 누적하며 올라오는 형태입니다.

15681번 (트리와 쿼리)	초기식: dp[now] = 1 (자신도 서브트리 크기 1로 산정) 점화식: dp[now] += dp[child] (자식 노드의 크기를 재귀적으로 누적)

🏆 7. 극한의 수학 최적화 DP (Ruby I)

세상의 그 어떤 꼼수도 통하지 않는 절대 영역입니다. 단순한 2차원 배열 할당을 넘어 고정밀도(High-Precision) 소수점 연산, 이항 계수 맵핑, 그리고 복소수 스케일링 보정까지 결합된 온몸 비틀기 최적화의 끝판왕입니다.

22222번 (지애 상수)	초기식 (수학적 기저): dp[0] 에 해당하는 기저 확률 및 조합 계수 벡터 초기화 (예: COMB = build_comb(N_MAX), 메모이제이션 배열 할당) 점화식 (모듈러 및 고정밀도 스케일링): dp[n] = Σ (부분식 곱결과 * 조합 계수 보정) 루프 종료 후 오차율 상쇄 보정: 최종 출력 = div_round(dp[final] * 72, 85)

특히 dp 문제가 어디까지 악랄해질 수 있는지 확인할려면 아래의 초기식 및 점화식을 확인해주세요.

해당 문제 정답 소스 코드는 여기를 확인해주세요.

[부록]지애 상수(22222) DP 점화식 해부

이 문제는 일반적인 프로그래밍의 한계를 넘어섭니다. 무한 급수와 테일러 전개, 복소수 평면에서의 스케일링을 모두 2차원 동적 계획법(DP) 테이블 하나로 압축해야 합니다. 고정소수점(Fixed-Point) 오차를 막기 위해 10³⁰⁰ 스케일을 곱해 정수 연산으로 온몸을 비틀어 뚫어낸, 세상에서 가장 아름답고 기괴한 점화식을 소개합니다.

코딩 테스트 수준을 까마득히 초월한 영역이므로, "DP가 극한으로 가면 수학 논문이 되는구나" 정도로 감상해 주시면 됩니다.

$$ \begin{aligned} & \textbf{1. 메인 DP 테이블 (조합 누적 기대값)} \\ & \text{[초기식]} \\ & dp[0][0] = 1 \quad \text{(실제 코드에서는 정밀도를 위해 } 10^{300} \text{ 으로 스케일링)} \\ \\ & \text{[점화식]} \\ & \text{대각선 } s = p + q \text{ 가 짝수이며, } (q - p) \equiv 0 \pmod 6 \text{ 인 } p, q \text{ 에 대하여:} \\ \\ & S_A = \sum_{i=0}^{p-1} \binom{p}{i} \left( \sum_{\substack{j \le q \\ j \equiv i \pmod 6}} \binom{q}{j} dp[i][j] \right) \\ \\ & S_B = \sum_{\substack{p \le j \lt q \\ j \equiv p \pmod 6}} \binom{q}{j} dp[p][j] \\ \\ & dp[p][q] = \frac{2}{3(2^{p+q} - 1)} \Big( S_A + S_B \Big) \\ \\ \\ & \textbf{2. 테일러 전개 보조 DP (}\sqrt{1+z}\textbf{ 의 계수)} \\ & \text{[초기식]} \\ & c[0] = 1 \\ & \text{[점화식]} \\ & c[n] = c[n-1] \cdot \frac{3 - 2n}{2n} \\ \\ \\ & \textbf{3. 최종 지애 상수 도출 (Final Aggregation)} \\ & \text{복소수 } U \text{ 에 대하여 } \alpha_n, \beta_n \text{ 을 } c[n] \cdot U^n \text{ 의 실수부와 허수부라 할 때 :} \\ & result = \sum_{p} (\alpha_p^2 + \beta_p^2) dp[p][p] + 2 \sum_{p \lt q} (\alpha_p \alpha_q + \beta_p \beta_q) dp[p][q] \end{aligned} $$

 

이래서 dp가 개념은 쉬우나 무한하게 악랄해질 수 있는 이유입니다.