[알고리즘 Deep Dive #2] 동적 프로그래밍(DP): 중복 계산 없애기
알고리즘 Deep Dive #2 – DP: 중복 부분 문제를 저장해 재사용하는 방법
들어가며
알고리즘 문제를 풀다 보면 종종 이런 상황을 마주하게 된다.
지금 가장 좋아 보이는 선택을 했는데, 전체 결과가 최적이 아니다.
이전 포스트에서 살펴본 Greedy Algorithm**은 각 단계에서 **현재 가장 좋은 선택을 반복하는 방식으로 문제를 해결한다. 하지만 어떤 문제들은 현재의 선택이 이후 선택에 영향을 주기 때문에 단순한 탐욕 전략이 최적해를 보장하지 못한다.
이때 등장하는 대표적인 해결 방법이 Dynamic Programming, 즉 **동적 프로그래밍(DP)**이다.
DP의 핵심 아이디어는 단순하다.
같은 계산을 반복하지 않는다.
많은 알고리즘 문제에서는 동일한 부분 문제가 여러 번 등장한다. 단순 재귀나 브루트포스 접근은 이 부분 문제들을 매번 다시 계산하지만, DP는 한 번 계산한 결과를 저장해두고 재사용한다.
이렇게 중복 계산을 제거하면 알고리즘의 시간 복잡도가 크게 줄어들 수 있다. 예를 들어 단순 재귀로 풀면 지수 시간이 걸리던 문제도 DP를 사용하면 선형 시간으로 해결되는 경우가 많다.
이 글에서는 다음 순서로 동적 프로그래밍을 정리해 본다.
- DP의 핵심 개념
- 피보나치 수열로 보는 기본 원리
- 탑다운과 바텀업 접근 방식
- 실제 문제에 적용하는 설계 방법
DP란?
Dynamic Programming(DP)은 문제를 작은 부분 문제로 나누고, 그 결과를 저장하여 재사용하는 방식으로 전체 문제를 해결하는 알고리즘 설계 방법이다.
핵심 아이디어는 다음 한 문장으로 정리할 수 있다.
부분 문제의 결과를 저장해두고, 같은 계산을 다시 하지 않는다.
많은 알고리즘 문제에서는 동일한 부분 문제가 반복적으로 등장한다. 단순 재귀 방식은 이 부분 문제들을 매번 다시 계산하지만, DP는 한 번 계산한 결과를 저장해 두고 필요할 때 바로 가져다 쓴다.
이 방식은 중복 계산을 제거하여 알고리즘의 시간 복잡도를 크게 줄여 준다.
예를 들어 단순 재귀로 해결하면 지수 시간에 가까운 계산이 필요한 문제도, DP를 적용하면 선형 시간이나 다항 시간으로 해결할 수 있는 경우가 많다.
DP가 적용되는 조건
모든 문제에 DP를 적용할 수 있는 것은 아니다. 일반적으로 다음 두 가지 조건이 만족될 때 DP를 사용할 수 있다.
1. 최적 부분 구조 (Optimal Substructure)
전체 문제의 최적해가 부분 문제의 최적해로 구성되는 성질을 의미한다.
즉 큰 문제를 해결하기 위해 작은 문제의 최적해를 조합할 수 있어야 한다.
예를 들어 어떤 문제의 최적해가 다음과 같은 형태로 표현된다면 이 조건을 만족한다.
1
전체 문제의 해 = 부분 문제의 해 + 추가 선택
2. 중복 부분 문제 (Overlapping Subproblems)
문제를 분해하는 과정에서 같은 부분 문제가 여러 번 등장하는 경우를 의미한다.
예를 들어 재귀적으로 문제를 나누다 보면 동일한 계산이 반복될 수 있다.
1
2
f(n) → f(n-1), f(n-2)
f(n-1) → f(n-2), f(n-3)
이처럼 f(n-2) 같은 계산이 여러 번 등장하면 중복 부분 문제가 존재한다고 볼 수 있다.
DP는 이러한 결과를 저장(memoization)하여 중복 계산을 제거한다.
이 두 가지 조건이 만족될 때 동적 프로그래밍은 매우 강력한 도구가 된다. 다음 섹션에서는 가장 유명한 예제인 피보나치 수열을 통해 DP의 핵심 원리를 살펴보겠다.
피보나치 수열로 이해하는 DP의 핵심
동적 프로그래밍의 원리를 이해하기 위해 가장 자주 사용되는 예제가 *Fibonacci sequence*이다.
피보나치 수열은 다음과 같이 정의된다.
F(n)=F(n-1)+F(n-2)
즉 하나의 값이 이전 두 값의 합으로 결정되는 구조를 가진다.
단순 재귀 방식
가장 직관적인 방법은 정의 그대로 재귀 함수를 작성하는 것이다.
1
2
3
4
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)
하지만 이 방식에는 큰 문제가 있다. 같은 계산이 계속 반복된다는 점이다.
예를 들어 fib(5)를 계산하면 내부적으로 다음과 같은 호출이 발생한다.
1
2
3
4
5
fib(5)
├─ fib(4)
│ ├─ fib(3)
│ └─ fib(2)
└─ fib(3)
여기서 fib(3)과 fib(2)는 여러 번 반복 계산된다. 이 때문에 시간 복잡도는 O(2ⁿ) 수준으로 증가한다.
탑다운 DP (메모이제이션)
이 문제를 해결하는 가장 간단한 방법은 이미 계산한 결과를 저장하는 것이다.
1
2
3
4
5
6
7
8
9
10
memo = {}
def fib(n):
if n <= 1:
return n
if n in memo:
return memo[n]
memo[n] = fib(n-1) + fib(n-2)
return memo[n]
이 방식은 필요한 순간에만 계산하고 결과를 저장한다. 이를 메모이제이션(memoization)이라고 부른다.
한 번 계산된 값은 다시 계산되지 않기 때문에 전체 시간 복잡도는 O(n)으로 줄어든다.
바텀업 DP (테이블 방식)
또 다른 방법은 작은 문제부터 차례대로 계산하는 방식이다.
1
2
3
4
5
6
7
8
def fib(n):
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
이 방식에서는 재귀 호출을 사용하지 않는다. 대신 작은 값부터 순서대로 계산하면서 테이블을 채워 나간다.
핵심 정리
피보나치 예제를 통해 확인할 수 있는 DP의 핵심은 다음과 같다.
- 같은 계산이 반복되는 구조가 존재한다.
- 이미 계산한 결과를 저장한다.
- 저장된 값을 재사용하여 중복 계산을 제거한다.
탑다운 vs 바텀업
동적 프로그래밍은 크게 두 가지 방식으로 구현할 수 있다.
- 탑다운(Top-down): 재귀를 사용하여 큰 문제를 작은 문제로 내려가며 해결
- 바텀업(Bottom-up): 작은 문제부터 시작해 점점 큰 문제를 만들어 해결
두 방식 모두 같은 점화식을 사용하지만 계산 순서와 구현 방식이 다르다.
탑다운 (Top-down, Memoization)
탑다운 방식은 재귀 호출을 통해 필요한 부분 문제만 계산한다. 이미 계산한 값은 메모리에 저장해두고 재사용한다.
1
2
3
4
5
6
7
8
9
10
memo = {}
def fib(n):
if n <= 1:
return n
if n in memo:
return memo[n]
memo[n] = fib(n-1) + fib(n-2)
return memo[n]
특징은 다음과 같다.
- 큰 문제에서 시작해 필요한 문제만 계산
- 재귀 구조라서 구현이 직관적
- 깊은 재귀에서는 스택 오버플로 위험이 있다.
바텀업 (Bottom-up, Tabulation)
바텀업 방식은 가장 작은 문제부터 순서대로 계산하면서 테이블을 채워 나간다.
1
2
3
4
5
6
7
8
def fib(n):
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
특징은 다음과 같다.
- 작은 문제부터 순차적으로 계산
- 반복문 기반이라 스택 문제 없음
- 문제의 계산 순서를 알아야 구현 가능
두 방식 비교
| 접근 방식 | 탑다운 (메모이제이션) | 바텀업 (테이블) |
|---|---|---|
| 방향 | 큰 문제 → 작은 문제 | 작은 문제 → 큰 문제 |
| 구현 | 재귀 + 캐시 | 반복문 |
| 계산 범위 | 필요한 것만 계산 | 전체 테이블 계산 |
| 스택 사용 | 사용 (재귀) | 사용 안 함 |
| 언제 유리 | 순서 불명확할 때 | 순서 명확할 때 |
언제 어떤 방식을 쓸까?
일반적으로 다음 기준으로 선택할 수 있다.
- 계산 순서가 명확하다 → 바텀업
- 필요한 부분만 계산하고 싶다 → 탑다운
- 재귀 깊이가 깊다 → 바텀업
실전 알고리즘 문제에서는 두 방식이 동일한 점화식을 기반으로 서로 변환 가능한 경우가 많다.
DP 문제를 설계하는 3단계
동적 프로그래밍 문제를 처음 접하면 어디서부터 시작해야 할지 막막할 수 있다. 하지만 대부분의 DP 문제는 다음 세 단계로 접근하면 해결의 실마리를 찾을 수 있다.
1단계: DP 상태 정의
가장 먼저 해야 할 일은 dp 배열이 무엇을 의미하는지 정의하는 것이다.
즉 다음 질문에 답해야 한다.
dp[i] 또는 dp[i][j]는 무엇을 의미하는가?
예를 들어 여러 문제에서 dp의 의미는 다음과 같이 정의된다.
1
2
3
LIS: dp[i] = i번째 원소를 마지막으로 하는 최장 증가 부분 수열의 길이
격자 경로: dp[i][j] = (i, j)까지 도달하는 경우의 수
배낭 문제: dp[w] = 무게 w까지 담을 수 있는 최대 가치
DP 문제의 절반은 이 상태 정의를 찾는 과정이라고 할 수 있다.
2단계: 점화식 도출
dp의 의미가 정해지면 다음 단계는 점화식(Recurrence Relation)을 만드는 것이다.
점화식은 현재 상태가 이전 상태들로부터 어떻게 계산되는지를 나타낸다.
예를 들어 최장 증가 부분 수열 문제에서는 다음과 같은 점화식을 얻을 수 있다.
1
dp[i] = max(dp[j] + 1) (단, j < i 이고 arr[j] < arr[i])
즉 arr[i]보다 작은 이전 원소들을 확인하여 그 위치에서 끝나는 수열 길이에 +1을 하는 방식이다.
이처럼 점화식은 문제의 구조에서 자연스럽게 도출된다.
3단계: 초기값 설정
마지막 단계는 초기값(Base Case)을 설정하는 것이다.
점화식이 동작하려면 시작점이 필요하다.
예를 들어 LIS 문제에서는
1
dp[i] = 1
로 초기화한다.
각 원소는 자기 자신만으로 길이 1의 증가 수열을 만들 수 있기 때문이다.
핵심 정리
DP 문제를 풀 때는 다음 순서를 기억하면 된다.
1
2
3
1. dp 상태 정의
2. 점화식 도출
3. 초기값 설정
이 세 단계를 명확히 정리하면 대부분의 DP 문제는 구현 단계로 자연스럽게 이어진다.
언제 DP를 써야 할까?
알고리즘 문제를 풀다 보면 가장 어려운 질문 중 하나는 이것이다.
이 문제를 DP로 풀어야 할까?
모든 최적화 문제가 DP로 풀리는 것은 아니기 때문에, 몇 가지 판단 기준을 가지고 접근하는 것이 중요하다.
1. 최적값 또는 경우의 수를 묻는 문제
DP는 보통 다음과 같은 형태의 질문에서 등장한다.
- 최대값 / 최소값
- 경우의 수
- 가능한 방법의 개수
- 최적의 선택
예를 들어 다음과 같은 문제들이다.
최대 이익을 구하라
최소 비용을 구하라
가능한 경로의 개수를 구하라
이러한 문제들은 여러 선택의 결과를 비교해야 하기 때문에 DP로 해결되는 경우가 많다.
2. 선택이 서로 영향을 주는 문제
그리디 알고리즘은 각 선택이 독립적일 때 잘 동작한다. 하지만 어떤 문제에서는 현재 선택이 이후 선택에 영향을 준다.
예를 들어 다음과 같은 상황이다.
현재 선택 → 이후 가능한 선택이 달라짐
이 경우 단순히 “지금 가장 좋은 선택”을 반복하는 방식으로는 최적해를 보장할 수 없다. 따라서 여러 선택의 결과를 비교하는 DP 접근이 필요하다.
3. 같은 계산이 반복되는 구조
문제를 분해했을 때 같은 부분 문제가 반복된다면 DP를 고려할 수 있다.
예를 들어 재귀적으로 문제를 나누면 다음과 같은 형태가 나타날 수 있다.
f(n) → f(n-1), f(n-2)
이 경우 f(n-2) 같은 계산이 여러 번 반복된다. DP는 이러한 결과를 저장하고 재사용하여 계산량을 크게 줄인다.
언제 탑다운을 쓰나?
처리 순서를 미리 알 수 없을 때다.
예시: 내리막길 (BOJ 1520)
격자에서 항상 높이가 낮은 곳으로만 이동할 때, (0,0)에서 (N-1,M-1)까지의 경로 수.
4방향 이동이 가능해서 바텀업으로 처리 순서를 정할 수 없다. 높이가 낮은 방향이면 어디든 갈 수 있기 때문이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import sys
sys.setrecursionlimit(500 * 500 + 10)
input = sys.stdin.readline
n, m = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]
dp = [[-1] * m for _ in range(n)]
def dfs(i, j):
if i == n-1 and j == m-1:
return 1
if dp[i][j] != -1: # 이미 계산한 칸
return dp[i][j]
dp[i][j] = 0
for di, dj in [(-1,0),(1,0),(0,-1),(0,1)]:
ni, nj = i+di, j+dj
if 0 <= ni < n and 0 <= nj < m and grid[ni][nj] < grid[i][j]:
dp[i][j] += dfs(ni, nj)
return dp[i][j]
print(dfs(0, 0))
핵심: 높이가 엄격히 감소하는 방향으로만 이동 → 사이클 없음 → DAG → 메모이제이션 DFS 가능
dp[i][j] = (i, j)에서 출발해 목적지까지 가는 경로의 수
언제 바텀업을 쓰나?
처리 순서가 명확할 때다.
예시: LIS (최장 증가 부분 수열)
1
2
3
4
5
6
7
8
9
10
11
n = int(input())
arr = list(map(int, input().split()))
dp = [1] * n # 각 원소를 끝으로 하는 LIS 길이
for i in range(1, n):
for j in range(i):
if arr[j] < arr[i]:
dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))
dp[i]는 항상 dp[0..i-1]만 참조하므로 왼→오른쪽 순서가 명확하다.
DP 적용 판단 흐름
실전 문제에서는 다음과 같은 흐름으로 접근할 수 있다.
1
2
3
4
5
6
7
8
9
최적값 or 경우의 수를 구하는 문제인가?
└── Yes
선택이 독립적인가?
└── Yes → 그리디 시도
└── No → DP
처리 순서를 알 수 있는가?
└── Yes → 바텀업
└── No → 탑다운 (메모이제이션 DFS)
물론 이 기준이 절대적인 것은 아니지만, 많은 문제에서 유용한 출발점이 된다.
마무리
동적 프로그래밍은 처음에는 어렵게 느껴지지만, 결국 핵심은 단순하다.
- 문제를 작은 부분 문제로 나눈다.
- 중복되는 계산을 저장한다.
- 점화식을 통해 전체 문제를 해결한다.
이 원리를 이해하면 많은 최적화 문제를 효율적으로 해결할 수 있다.
다음 글에서는 동적 프로그래밍의 대표적인 응용 문제인 배낭 문제(Knapsack)를 통해 DP가 실제 문제에서 어떻게 활용되는지 살펴보겠다.
자주 하는 실수
1. dp 초기값을 잘못 설정
1
2
dp = [0] * n # 경우의 수 문제에서 자기 자신(1)으로 초기화해야 할 때
dp = [1] * n # ✅
2. 재귀 깊이 초과
1
2
# N이 클 때 반드시 추가
sys.setrecursionlimit(10**6)
3. 모듈러 연산 누락
1
2
# 경우의 수가 클 때 중간에 mod 적용 안 하면 메모리 초과
dp[i] = (dp[i-1] + dp[i-2]) % MOD
정리
DP는 “모든 경우를 따진다”는 브루트포스의 비효율을 “중복 계산 제거”로 해결한다. 그리디처럼 증명이 필요하지 않고, 점화식만 올바르면 항상 최적을 보장한다.
다음 포스트에서는 DP의 가장 유명한 응용 문제인 배낭 문제(Knapsack)를 다룬다. 0/1 배낭, 분할 배낭, 그리고 오늘 풀었던 변형 문제까지.
Tags: #Algorithm #DynamicProgramming #DP #Memoization #Tabulation #Greedy #AlgorithmStudy #Python