[2026] 동적 프로그래밍(DP) | 코딩 테스트 필수 알고리즘 완벽 정리
![[2026] 동적 프로그래밍(DP) | 코딩 테스트 필수 알고리즘 완벽 정리](/og/s/algorithm-series-12-dynamic-programming.webp)
이 글의 핵심
동적 프로그래밍(DP): 코딩 테스트 필수 알고리즘 DP 기본 개념·Top-Down (메모이제이션).
들어가며
”같은 계산을 반복하지 마세요”
동적 프로그래밍(DP)은 중복 계산을 저장해서 O(2ⁿ) → O(n)으로 최적화하는 기법입니다.
코딩 테스트 준비하며 깨달은 것
알고리즘 문제를 풀다 보면 “이게 실무에 무슨 도움이 될까?” 하는 의문이 들 때가 있습니다. 저도 그랬습니다. 하지만 실제 프로젝트에서 성능 문제에 부딪히면, 알고리즘 지식이 얼마나 중요한지 깨닫게 됩니다. 예를 들어, 사용자 검색 기능이 느려서 고민하다가 해시 테이블을 적용하니 응답 시간이 10초에서 0.1초로 줄어든 경험이 있습니다. 코딩 테스트는 단순히 취업을 위한 관문이 아니라, 문제 해결 능력을 키우는 훈련장입니다. 처음엔 브루트 포스로 풀다가, 시간 복잡도를 개선하는 과정에서 “아, 이렇게 생각하면 되는구나” 하는 깨달음을 얻을 때의 쾌감은 말로 표현하기 어렵습니다. 이 글에서는 단순히 정답 코드만 제시하는 게 아니라, 문제를 어떻게 접근하고 최적화하는지 사고 과정을 함께 공유하겠습니다.
사전 지식 (초보자를 위한 기초)
1. 재귀(Recursion)란?
재귀는 함수가 자기 자신을 호출하는 것입니다. 마치 거울 앞에 거울을 놓으면 무한히 반복되는 것처럼요. 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
# 간단한 재귀 예시: 팩토리얼
# 5! = 5 × 4 × 3 × 2 × 1 = 120
def factorial(n):
# 기저 조건 (재귀를 멈추는 조건)
if n <= 1:
return 1
# 재귀 호출 (자기 자신을 호출)
return n * factorial(n - 1)
print(factorial(5)) # 120
# 실행 과정:
# factorial(5) = 5 × factorial(4)
# = 5 × (4 × factorial(3))
# = 5 × (4 × (3 × factorial(2)))
# = 5 × (4 × (3 × (2 × factorial(1))))
# = 5 × (4 × (3 × (2 × 1)))
# = 5 × 4 × 3 × 2 × 1
# = 120재귀의 핵심:
- 기저 조건: 재귀를 멈추는 조건 (없으면 무한 반복!)
- 재귀 호출: 문제를 작은 문제로 쪼개서 해결
2. 중복 계산 문제
재귀를 사용하면 같은 계산을 여러 번 하게 됩니다. 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
# 피보나치 수열: 1, 1, 2, 3, 5, 8, 13, ...
# fib(n) = fib(n-1) + fib(n-2)
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)
# fib(5)를 계산하면:
#
# fib(5)
# / \
# fib(4) fib(3)
# / \ / \
# fib(3) fib(2) fib(2) fib(1)
# / \ / \ / \
# fib(2) fib(1) f(1) f(0) f(1) f(0)
# / \
# f(1) f(0)
#
# fib(3)이 2번 계산됨! (중복!)
# fib(2)가 3번 계산됨! (중복!)
# fib(1)이 5번 계산됨! (중복!)
#
# 너무 비효율적입니다!문제점:
fib(40)을 계산하면 10억 번 이상 계산- 컴퓨터가 수십 초 걸림
3. 동적 프로그래밍(DP)이란?
DP는 한 번 계산한 결과를 저장해두고, 다음에 필요할 때 저장된 값을 재사용하는 기법입니다. 비유:
- 재귀: 전화번호를 매번 계산해서 찾기
- DP: 전화번호를 메모장에 적어두고 필요할 때 메모장 보기 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
# DP를 사용한 피보나치
def fib_dp(n, memo={}):
# 이미 계산했으면 저장된 값 반환
if n in memo:
return memo[n]
# 기저 조건
if n <= 1:
return n
# 계산 후 저장
memo[n] = fib_dp(n-1, memo) + fib_dp(n-2, memo)
return memo[n]
print(fib_dp(40)) # 즉시 출력! (0.001초)
# fib(40) 비교:
# 일반 재귀: 10억 번 계산 (수십 초)
# DP: 40번만 계산 (즉시)4. DP를 사용하는 문제의 특징
DP는 다음 2가지 조건이 있을 때 사용합니다: 1) 최적 부분 구조 (Optimal Substructure)
- 큰 문제의 답이 작은 문제의 답으로 구할 수 있음
- 예:
fib(5) = fib(4) + fib(3)2) 중복되는 부분 문제 (Overlapping Subproblems) - 같은 작은 문제를 여러 번 계산함
- 예:
fib(3)을 여러 번 계산 DP 문제 키워드: - “최대/최소 값 구하기”
- “경우의 수 구하기”
- “가능한지 판단하기”
- 피보나치, 계단 오르기, 배낭 문제 등
5. DP의 2가지 방법
Top-Down (하향식 - 재귀) 아래 코드는 python를 사용한 구현 예제입니다. 함수를 통해 로직을 구현합니다. 코드를 직접 실행해보면서 동작을 확인해보세요.
# 큰 문제부터 시작 → 작은 문제로 쪼갬
# fib(5) → fib(4) → fib(3) → ...
def fib_topdown(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib_topdown(n-1, memo) + fib_topdown(n-2, memo)
return memo[n]Bottom-Up (상향식 - 반복문) 아래 코드는 python를 사용한 구현 예제입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
# 작은 문제부터 시작 → 큰 문제로 쌓아감
# fib(0), fib(1), fib(2), ....→ fib(5)
def fib_bottomup(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[0] = 0
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]비교:
- Top-Down: 이해하기 쉬움, 필요한 것만 계산
- Bottom-Up: 더 빠름, 메모리 효율적
1. DP 기본 개념
피보나치 수열로 이해하기
문제: n번째 피보나치 수 구하기 아래 코드는 python를 사용한 구현 예제입니다. 함수를 통해 로직을 구현합니다. 코드를 직접 실행해보면서 동작을 확인해보세요.
# ❌ 단순 재귀 (O(2ⁿ) - 매우 느림!)
def fib_naive(n):
if n <= 1:
return n
return fib_naive(n-1) + fib_naive(n-2)
print(fib_naive(40)) # 수십 초 걸림!문제점: 같은 값을 여러 번 계산 아래 코드는 text를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.
fib(5)
├─ fib(4)
│ ├─ fib(3)
│ │ ├─ fib(2) ← 중복!
│ │ └─ fib(1)
│ └─ fib(2) ← 중복!
└─ fib(3) ← 중복!
├─ fib(2)
└─ fib(1)2. Top-Down (메모이제이션)
재귀 + 캐싱 (메모이제이션)
메모이제이션은 한 번 구한 fib(k) 값을 딕셔너리에 저장해 두었다가, 같은 k가 다시 필요할 때 재귀 호출 대신 저장된 값을 꺼내 씁니다. 전화번호를 외운 뒤에는 매번 계산하지 않고 메모장만 보는 것과 같습니다.
다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
# ✅ 메모이제이션 (O(n))
def fib_memo(n, memo={}):
# 이미 계산한 값이면 바로 반환 (O(1))
if n in memo:
return memo[n]
# 기저 조건
if n <= 1:
return n
# 재귀 호출 + 결과 저장
# fib(n) = fib(n-1) + fib(n-2)
memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
return memo[n]
print(fib_memo(40)) # 즉시 출력! (0.001초 미만)
# 단순 재귀 vs 메모이제이션 비교:
# fib_naive(40): 2^40 = 약 1조 번 계산 (수십 초)
# fib_memo(40): 40번만 계산 (즉시)
#
# 탐색 과정 (n=5):
# fib_memo(5) 호출
# → fib_memo(4) 호출
# → fib_memo(3) 호출
# → fib_memo(2) 호출
# → fib_memo(1) = 1 (기저)
# → fib_memo(0) = 0 (기저)
# → memo[2] = 1
# → fib_memo(1) = 1 (기저)
# → memo[3] = 2
# → fib_memo(2) = 1 (memo에서 가져옴, 재계산 안 함!)
# → memo[4] = 3
# → fib_memo(3) = 2 (memo에서 가져옴)
# → memo[5] = 5
#
# 각 값은 딱 한 번만 계산됨!메모이제이션 주의사항: 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
# ❌ 잘못된 사용: memo를 기본 인자로 사용
def fib_bad(n, memo={}):
# 기본 인자는 함수 정의 시 한 번만 생성됨
# 여러 번 호출 시 같은 dict를 공유
pass
# 첫 호출
fib_bad(10) # memo에 0~10 저장
# 두 번째 호출
fib_bad(5) # 이미 저장된 값 사용 (의도치 않은 공유)
# ✅ 올바른 사용: memo를 None으로 초기화
def fib_good(n, memo=None):
if memo is None:
memo = {} # 매 호출마다 새로운 dict 생성
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib_good(n-1, memo) + fib_good(n-2, memo)
return memo[n]Python 데코레이터
아래 코드는 python를 사용한 구현 예제입니다. 필요한 모듈을 import하고, 함수를 통해 로직을 구현합니다. 코드를 직접 실행해보면서 동작을 확인해보세요.
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_cached(n):
if n <= 1:
return n
return fib_cached(n-1) + fib_cached(n-2)
print(fib_cached(100)) # 매우 빠름3. Bottom-Up (타뷸레이션)
반복문 + 테이블 (Bottom-Up)
Bottom-Up은 작은 문제부터 순서대로 풀어 테이블을 채웁니다: 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
# ✅ Bottom-Up (O(n), 재귀보다 빠름)
def fib_dp(n):
# 기저 조건
if n <= 1:
return n
# DP 테이블 생성
# dp[i]: i번째 피보나치 수
dp = [0] * (n + 1)
# 초기값 설정
dp[0] = 0 # fib(0) = 0
dp[1] = 1 # fib(1) = 1
# 작은 문제부터 순서대로 해결
for i in range(2, n + 1):
# 점화식: fib(i) = fib(i-1) + fib(i-2)
# 이미 계산된 값(dp[i-1], dp[i-2])을 사용
dp[i] = dp[i-1] + dp[i-2]
# 최종 답 반환
return dp[n]
print(fib_dp(100)) # 즉시 출력
# 계산 과정 (n=5):
# dp = [0, 0, 0, 0, 0, 0]
#
# 초기화:
# dp = [0, 1, 0, 0, 0, 0]
#
# i=2: dp[2] = dp[1] + dp[0] = 1 + 0 = 1
# dp = [0, 1, 1, 0, 0, 0]
#
# i=3: dp[3] = dp[2] + dp[1] = 1 + 1 = 2
# dp = [0, 1, 1, 2, 0, 0]
#
# i=4: dp[4] = dp[3] + dp[2] = 2 + 1 = 3
# dp = [0, 1, 1, 2, 3, 0]
#
# i=5: dp[5] = dp[4] + dp[3] = 3 + 2 = 5
# dp = [0, 1, 1, 2, 3, 5]
#
# return dp[5] = 5Top-Down vs Bottom-Up 비교: 다음은 python를 활용한 상세한 구현 코드입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
# Top-Down (메모이제이션)
# 장점:
# - 재귀로 직관적
# - 필요한 부분만 계산 (일부 문제에서 유리)
# 단점:
# - 재귀 호출 오버헤드
# - 스택 오버플로우 위험 (깊이 제한)
# - 상대적으로 느림
# Bottom-Up (타뷸레이션)
# 장점:
# - 반복문으로 빠름
# - 스택 오버플로우 없음
# - 공간 최적화 쉬움
# 단점:
# - 모든 부분 문제를 계산 (불필요한 계산 가능)
# - 점화식을 찾기 어려울 수 있음
# 실전에서는 Bottom-Up을 더 많이 사용공간 최적화
아래 코드는 python를 사용한 구현 예제입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
# ✅ O(1) 공간
def fib_optimized(n):
if n <= 1:
return n
prev2, prev1 = 0, 1
for _ in range(2, n + 1):
current = prev1 + prev2
prev2, prev1 = prev1, current
return prev1
print(fib_optimized(100))4. DP 문제 풀이 패턴
패턴 1: 1차원 DP
예제: 계단 오르기 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
def climb_stairs(n):
"""
1칸 또는 2칸씩 올라갈 수 있을 때 경우의 수
문제 이해:
- n=1: 1가지 (1칸)
- n=2: 2가지 (1+1칸, 2칸)
- n=3: 3가지 (1+1+1칸, 1+2칸, 2+1칸)
- n=4: 5가지
- n=5: 8가지
"""
# 기저 조건
if n <= 2:
return n
# DP 테이블 생성
# dp[i]: i번째 계단에 도달하는 경우의 수
dp = [0] * (n + 1)
# 초기값 설정
dp[1] = 1 # 1번 계단: 1가지 (1칸)
dp[2] = 2 # 2번 계단: 2가지 (1+1칸, 2칸)
# 점화식: dp[i] = dp[i-1] + dp[i-2]
# i번째 계단에 도달하는 방법:
# 1. (i-1)번째 계단에서 1칸 올라오기: dp[i-1]가지
# 2. (i-2)번째 계단에서 2칸 올라오기: dp[i-2]가지
for i in range(3, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
print(climb_stairs(5)) # 8
# 계산 과정 (n=5):
# dp = [0, 1, 2, 0, 0, 0]
#
# i=3: dp[3] = dp[2] + dp[1] = 2 + 1 = 3
# (2번에서 1칸) + (1번에서 2칸)
# dp = [0, 1, 2, 3, 0, 0]
#
# i=4: dp[4] = dp[3] + dp[2] = 3 + 2 = 5
# (3번에서 1칸) + (2번에서 2칸)
# dp = [0, 1, 2, 3, 5, 0]
#
# i=5: dp[5] = dp[4] + dp[3] = 5 + 3 = 8
# (4번에서 1칸) + (3번에서 2칸)
# dp = [0, 1, 2, 3, 5, 8]
#
# return 8공간 최적화 버전: 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
def climb_stairs_optimized(n):
if n <= 2:
return n
# 이전 두 값만 저장 (O(1) 공간)
prev2, prev1 = 1, 2 # dp[1], dp[2]
for i in range(3, n + 1):
current = prev1 + prev2
prev2, prev1 = prev1, current # 값 이동
return prev1
# 공간복잡도: O(n) → O(1)
# dp[i]는 dp[i-1]과 dp[i-2]만 필요하므로
# 전체 배열을 유지할 필요 없음패턴 2: 2차원 DP
예제: 최소 경로 합 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
def min_path_sum(grid):
"""
(0,0)에서 (n-1,m-1)까지 최소 합
"""
n, m = len(grid), len(grid[0])
dp = [[0] * m for _ in range(n)]
# 초기값
dp[0][0] = grid[0][0]
# 첫 행
for j in range(1, m):
dp[0][j] = dp[0][j-1] + grid[0][j]
# 첫 열
for i in range(1, n):
dp[i][0] = dp[i-1][0] + grid[i][0]
# 나머지
for i in range(1, n):
for j in range(1, m):
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
return dp[n-1][m-1]
# 테스트
grid = [
[1, 3, 1],
[1, 5, 1],
[4, 2, 1]
]
print(min_path_sum(grid)) # 7 (1→3→1→1→1)패턴 3: 배낭 문제 (Knapsack)
0-1 배낭 문제는 각 물건을 넣거나 넣지 않는 선택을 최적화합니다: 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
def knapsack(weights, values, capacity):
"""
0-1 배낭 문제
문제: 배낭 용량 capacity 이하로 물건을 담아 가치 최대화
제약: 각 물건은 0개 또는 1개만 선택 가능 (0-1)
입력:
- weights: 각 물건의 무게
- values: 각 물건의 가치
- capacity: 배낭 용량
"""
n = len(weights)
# DP 테이블 생성
# dp[i][w]: i번째 물건까지 고려했을 때, 용량 w에서의 최대 가치
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
# i=0: 물건이 없으면 가치 0 (이미 초기화됨)
# w=0: 용량이 0이면 가치 0 (이미 초기화됨)
for i in range(1, n + 1):
for w in range(capacity + 1):
# 선택 1: i번째 물건을 넣지 않는 경우
# 이전 상태(i-1번째까지)의 가치를 그대로 가져옴
dp[i][w] = dp[i-1][w]
# 선택 2: i번째 물건을 넣는 경우
# 조건: 현재 물건의 무게가 용량 이하여야 함
if weights[i-1] <= w:
# i번째 물건을 넣으면:
# - 남은 용량: w - weights[i-1]
# - 가치: dp[i-1][w - weights[i-1]] + values[i-1]
# 두 선택 중 최대값 선택
dp[i][w] = max(
dp[i][w], # 넣지 않는 경우
dp[i-1][w - weights[i-1]] + values[i-1] # 넣는 경우
)
# 모든 물건을 고려했을 때, 전체 용량에서의 최대 가치
return dp[n][capacity]
# 테스트
weights = [2, 3, 4, 5] # 무게
values = [3, 4, 5, 6] # 가치
capacity = 8 # 배낭 용량
print(knapsack(weights, values, capacity)) # 10
# DP 테이블 계산 (일부):
# dp[i][w]: i번째까지, 용량 w
#
# w: 0 1 2 3 4 5 6 7 8
# i=0: 0 0 0 0 0 0 0 0 0 (물건 없음)
# i=1: 0 0 3 3 3 3 3 3 3 (무게2, 가치3)
# i=2: 0 0 3 4 4 7 7 7 7 (무게3, 가치4)
# i=3: 0 0 3 4 5 7 8 9 9 (무게4, 가치5)
# i=4: 0 0 3 4 5 7 8 9 10 (무게5, 가치6)
#
# 최종 답: dp[4][8] = 10
# 선택된 물건: 무게3(가치4) + 무게5(가치6) = 총 무게8, 총 가치10공간 최적화 (1차원 배열): 아래 코드는 python를 사용한 구현 예제입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.
def knapsack_optimized(weights, values, capacity):
n = len(weights)
dp = [0] * (capacity + 1)
for i in range(n):
# 뒤에서부터 업데이트 (덮어쓰기 방지)
for w in range(capacity, weights[i] - 1, -1):
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[capacity]
# 공간복잡도: O(n*capacity) → O(capacity)5. DP 문제 접근법
1단계: DP인지 판단
아래 코드는 text를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.
✅ DP 신호:
- "최대/최소 값"
- "경우의 수"
- "가능 여부"
- 중복되는 부분 문제
❌ DP 아님:
- 그리디로 풀림
- 단순 시뮬레이션2단계: 점화식 세우기
# 예: 계단 오르기
# dp[i] = i번째 계단까지 가는 경우의 수
# dp[i] = dp[i-1] + dp[i-2]3단계: 초기값 설정
# 예: 계단 오르기
dp[1] = 1 # 1칸: 1가지
dp[2] = 2 # 2칸: 2가지 (1+1, 2)4단계: 구현 선택
# Top-Down: 재귀가 자연스러울 때
# Bottom-Up: 반복문이 명확할 때 (더 빠름)실전 팁
디버깅 팁
아래 코드는 python를 사용한 구현 예제입니다. 함수를 통해 로직을 구현합니다. 코드를 직접 실행해보면서 동작을 확인해보세요.
# DP 테이블 출력
def print_dp_table(dp):
for row in dp:
print(row)
# 중간 과정 확인
print(f"dp[{i}] = {dp[i]}")최적화 팁
# 1. 공간 최적화: 이전 행만 필요하면 1차원 배열
# 2. 시간 최적화: 불필요한 계산 스킵
# 3. 메모 초기화: defaultdict 활용정리
핵심 요약
- DP: 중복 계산 저장, O(2ⁿ) → O(n)
- Top-Down: 재귀 + 메모이제이션
- Bottom-Up: 반복문 + 테이블 (더 빠름)
- 점화식: dp[i] = f(dp[i-1], dp[i-2], …)
추천 문제
백준: