DP는 지금 검색 수요가 뚜렷하지만, 단어만 외우면 실제 판단 기준이 남지 않는 주제입니다. 이 글에서는 DP top-down과 bottom-up 선택 기준 이해를 목표로 핵심 개념과 실무 판단 기준을 차근차근 정리합니다.
대상 독자는 DP 문제에서 재귀와 반복문 중 무엇을 써야 할지 헷갈리는 코딩테스트 학습자입니다. 처음부터 세부 구현이나 상품명만 따라가기보다, 왜 이 주제가 필요한지와 어디서 실수하는지를 먼저 잡겠습니다.
둘 다 같은 DP지만 출발 방향이 다르다
DP에서 메모이제이션과 테이블 방식은 서로 다른 알고리즘이라기보다 같은 상태 전이를 계산하는 두 방식입니다. top-down은 큰 문제에서 필요한 작은 문제로 내려가고, bottom-up은 작은 문제부터 차례로 올라옵니다.
예를 들어 피보나치 수를 구할 때 fib(n)을 재귀로 부르고 결과를 저장하면 top-down입니다. 반대로 dp[0], dp[1]부터 dp[n]까지 반복문으로 채우면 bottom-up입니다.
- top-down: 재귀 호출 + 결과 저장
- bottom-up: 반복문 + 테이블 채우기
- 둘 다 상태와 점화식이 맞아야 한다
- 차이는 계산 순서와 구현 안정성에서 나온다
메모이제이션은 필요한 상태만 계산한다
메모이제이션은 재귀 함수의 결과를 저장해 같은 상태를 다시 계산하지 않는 방식입니다. 상태 정의가 자연스럽게 재귀로 떠오르는 문제에서 구현이 빠릅니다.
Python에서는 functools.cache나 lru_cache를 사용하면 캐시 딕셔너리를 직접 만들지 않아도 됩니다.
from functools import cache
@cache
def fib(n: int) -> int:
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)테이블 방식은 계산 순서를 직접 통제한다
bottom-up은 작은 상태부터 테이블을 채웁니다. 재귀 깊이 문제를 피할 수 있고, 어떤 값이 먼저 계산되는지 눈으로 확인하기 쉽습니다.
대신 순회 방향을 잘못 잡으면 아직 계산되지 않은 값을 참조하거나, 같은 단계의 값을 잘못 재사용할 수 있습니다.
def fib(n: int) -> int:
if n <= 1:
return 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]선택 기준은 문제 모양에서 나온다
코딩테스트에서는 어떤 방식이 더 고급인지보다, 제한 시간 안에 안정적으로 맞출 수 있는지가 중요합니다. 상태가 그래프처럼 복잡하고 필요한 상태만 방문하면 되는 문제는 top-down이 편할 수 있습니다.
반대로 상태 범위가 작고 모든 값을 순서대로 채우면 되는 문제는 bottom-up이 안정적입니다. 특히 재귀 제한이 걸릴 수 있는 Python에서는 bottom-up을 선호할 때가 많습니다.
- 상태 정의가 먼저 떠오르고 재귀 관계가 자연스러우면 top-down을 시도한다
- 초기값과 순회 방향이 명확하면 bottom-up으로 바꾼다
- 재귀 깊이가 커질 가능성이 있으면 bottom-up을 우선 검토한다
- 모든 상태를 다 계산할 필요가 없으면 top-down이 더 간단할 수 있다
실수는 초기값과 순서에서 많이 나온다
DP 오답은 점화식보다 초기값과 순회 순서에서 나오는 경우가 많습니다. top-down에서는 종료 조건을 빠뜨리면 무한 재귀가 되고, bottom-up에서는 앞에서 채워야 할 값을 뒤에서 참조하면 틀립니다.
문제를 풀 때는 작은 입력을 손으로 먼저 계산해 보고, 테이블이 어떤 순서로 채워져야 하는지 확인하는 습관이 중요합니다.
- base case가 충분한지 확인한다
- dp 배열 크기가 상태 범위를 덮는지 본다
- 점화식이 참조하는 값이 먼저 계산되는지 확인한다
- 같은 행 값을 재사용하는 문제는 순회 방향을 특히 조심한다
조금 더 깊게 보면
초안 단계에서 핵심 개념만 잡으면 글이 얕게 끝날 수 있습니다. 그래서 여기서는 실제 적용할 때 확인해야 할 기준과 자주 생기는 오해를 한 단계 더 내려가 보겠습니다.
작은 입력을 손으로 그리면 선택이 쉬워진다
DP 방식 선택은 머릿속으로만 하면 어렵습니다. 작은 입력을 표로 그려보면 top-down과 bottom-up 중 무엇이 자연스러운지 보입니다. 상태가 몇 개이고, 각 상태가 어떤 이전 상태를 참조하는지 직접 써보는 것이 중요합니다.
예를 들어 계단 오르기 문제는 dp[i]가 dp[i-1]과 dp[i-2]를 참조합니다. 이 경우 0부터 n까지 순서대로 채우면 되기 때문에 bottom-up이 매우 자연스럽습니다.
i 0 1 2 3 4 5
dp[i] 1 1 2 3 5 8
dp[i] = dp[i - 1] + dp[i - 2]top-down이 편한 문제
top-down은 상태 전이가 분기형으로 생기거나, 모든 상태를 다 방문하지 않아도 되는 문제에서 편합니다. 재귀 함수가 문제 정의와 거의 같아지는 경우가 많아 처음 정답을 만들기 좋습니다.
다만 Python에서는 재귀 깊이 제한을 조심해야 합니다. 입력 크기가 크고 일자로 깊게 들어가는 구조라면 bottom-up 전환을 검토해야 합니다.
- 상태가 트리나 그래프처럼 필요한 곳만 방문된다
- 점화식은 떠오르지만 순회 순서가 바로 보이지 않는다
- 가지치기나 불가능 상태 처리가 자연스럽다
- 문제 설명 자체가 재귀적이다
bottom-up이 편한 문제
bottom-up은 상태 범위가 명확하고, 작은 상태에서 큰 상태로 가는 순서가 분명할 때 좋습니다. 반복문으로 작성하기 때문에 재귀 깊이 문제가 없고, 디버깅 때 테이블 값을 출력하기도 쉽습니다.
특히 2차원 DP, knapsack, 문자열 DP처럼 테이블 모양이 보이는 문제는 bottom-up으로 정리하는 편이 안정적입니다.
def climb_stairs(n: int) -> int:
if n <= 1:
return 1
prev2 = 1
prev1 = 1
for _ in range(2, n + 1):
current = prev1 + prev2
prev2 = prev1
prev1 = current
return prev1공간 최적화는 마지막에 한다
DP를 처음부터 1차원이나 변수 두 개로 줄이려 하면 오히려 틀리기 쉽습니다. 먼저 2차원 또는 전체 배열로 점화식이 맞는지 확인하고, 그 다음 참조하는 이전 상태가 적을 때만 줄이는 편이 안전합니다.
공간 최적화는 정답을 만든 뒤 적용하는 개선입니다. 특히 같은 행의 값을 재사용하는 knapsack류 문제는 순회 방향 하나로 정답이 바뀔 수 있으므로 더 조심해야 합니다.
- 상태와 점화식을 먼저 맞춘다
- 전체 테이블로 작은 입력을 검증한다
- 현재 값이 참조하는 이전 상태 범위를 확인한다
- 1차원으로 줄일 때 순회 방향을 따로 검증한다
- 마지막에 시간복잡도와 공간복잡도를 정리한다
실전 적용 시나리오
이 주제를 실제 작업에 적용한다면 먼저 작은 범위에서 시작하는 편이 좋습니다. DP를 알고 있다는 것과, 프로젝트나 학습 문제 안에서 올바른 판단을 내리는 것은 다른 문제입니다.
DP 문제에서 재귀와 반복문 중 무엇을 써야 할지 헷갈리는 코딩테스트 학습자라면 처음부터 모든 세부 선택지를 외우기보다, 현재 상황에서 무엇을 확인해야 하는지 체크리스트로 좁혀야 합니다. 그래야 글을 읽고 바로 다음 행동으로 옮길 수 있습니다.
- 먼저 DP가 필요한 상황인지 문제를 한 문장으로 적는다
- 현재 방식이 실패하는 지점을 로그, 예제, 표, 작은 입력 중 하나로 확인한다
- 메모이제이션, top-down, bottom-up 중 이번 문제와 직접 관련 있는 기준만 고른다
- 작은 예제로 먼저 검증하고, 그 다음 실제 프로젝트나 긴 입력으로 확장한다
- 결과가 좋아졌는지 주관적 느낌이 아니라 비교 가능한 기준으로 확인한다
이 순서를 따르면 글에서 배운 개념이 단순한 용어 정리로 끝나지 않습니다. 특히 개발 글은 예제 코드가 돌아가는지만 보지 말고, 왜 그 구조를 골랐는지 설명할 수 있어야 합니다. ETF 글도 마찬가지로 분배율이나 수익률 숫자 하나가 아니라 역할과 위험을 함께 설명할 수 있어야 합니다.
검토 체크리스트
마지막으로 실제 적용 전에 아래 항목을 확인하면 실수를 줄일 수 있습니다. 체크리스트는 정답을 대신하지 않지만, 빠뜨리기 쉬운 질문을 다시 꺼내는 데 도움이 됩니다.
- 이 주제를 써야 하는 문제가 정말 맞는가
- 비슷한 대안과 비교했을 때 장점과 비용을 함께 설명할 수 있는가
- 공식 문서나 신뢰할 수 있는 자료로 핵심 전제를 확인했는가
- 작은 예제나 제한된 데이터에서 먼저 검증했는가
- 실패했을 때 되돌릴 수 있는 기준과 로그를 남겼는가
- 초보자가 오해하기 쉬운 지점을 본문에서 따로 짚었는가
정리하면 DP 글의 목적은 용어를 하나 더 외우게 하는 것이 아니라, 독자가 다음 선택을 덜 흔들리게 만드는 것입니다. 그래서 본문에서는 개념, 예시, 실수, 체크리스트를 함께 묶어 읽는 편이 좋습니다.
정리
메모이제이션과 테이블 방식은 둘 중 하나만 외우는 문제가 아닙니다. 상태와 점화식은 같고 계산 방향만 다르다고 보면, 문제에 맞는 구현을 훨씬 침착하게 고를 수 있습니다.
관련해서 내부 글은 DP 점화식은 어떻게 세워야 할까, 누적합(prefix sum)은 언제 떠올려야 할까, 우선순위 큐는 언제 써야 할까와 함께 보면 좋습니다.
외부 기준은 CP-Algorithms – Introduction to DP, Python Docs – functools, Wikipedia – Dynamic programming를 기준으로 확인했습니다.
