DP(동적 계획법) 정복하기: Top-down vs Bottom-up

1. DP(Dynamic Programming)의 두 가지 구현 방식

DP는 크게 배열을 채워나가는 방향에 따라 두 가지로 나뉩니다.

① Bottom-Up (바텀업 / Tabulation) - 실무와 코테에서 가장 많이 쓰임

개념: 가장 작은 문제부터 차례대로 답을 구해가며 배열을 채웁니다.
특징: for 반복문을 사용합니다. 함수 호출(재귀)이 없어서 실행 속도가 빠르고 메모리 에러(Stack Overflow) 걱정이 없습니다.
비유: 1층부터 차곡차곡 벽돌을 쌓아 10층 건물을 완성하는 방식입니다.

② Top-Down (탑다운 / Memoization)

개념: 가장 큰 문제를 먼저 호출한 뒤, 쪼개가면서 작은 문제로 내려가고, 그 답을 구하면 메모장(배열이나 딕셔너리)에 기록해두며 다시 올라옵니다.
특징: 재귀함수를 사용합니다. 구조가 직관적이지만 파이썬에서는 재귀 깊이 제한에 걸릴 위험이 있습니다.
비유: 10층에서 "9층이 없네? 9층부터 만들어"라고 지시를 내리며 1층까지 내려갔다가 다시 올라오는 방식입니다.

2. 배열(테이블) 초기화 방법

과거의 경험을 저장해둘 '메모장(배열)'을 만드는 과정입니다. 파이썬에서는 보통 1차원 리스트나 2차원 리스트를 사용합니다.

1차원 배열 (주로 선형적인 문제에 사용)

피보나치 수열, 계단 오르기 등 변수가 1개(예: $N$ 번째 계단)일 때 씁니다.

python# N이 10일 때, 0번부터 10번 인덱스까지 총 11칸의 빈 배열 생성
dp = [0] * (10 + 1)

2차원 배열 (조건이 두 개 이상일 때 사용)

배낭 문제(무게, 가치), 격자 지도 이동(X좌표, Y좌표) 등 변수가 2개일 때 씁니다.

python# 가로가 5, 세로가 4인 빈 2차원 배열 생성
# [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], ...]
dp = [[0] * 5 for _ in range(4)]

3. 점화식 세우기 (DP의 핵심)

점화식이란 현재 내 상태(정답)를 과거의 상태(정답)들을 이용해 수식으로 표현한 것 입니다. 이 공식을 찾는 것이 DP 문제의 90%를 차지합니다.

점화식 찾는 3단계 꿀팁

Base Case (기저 상태) 설정: 가장 작은 단위의 정답은 하드코딩해 줍니다. (예: 1번 계단 가는 법=1가지, 2번 계단=2가지)
N번째 상태 가정하기: " $N$ 번째 정답을 구하기 바로 직전의 상태가 무엇일까?"를 고민합니다.
수식 만들기:
- dp[N] = dp[N-1] + dp[N-2] (피보나치, 타일링 류)
- dp[N] = max(dp[N-1], dp[N-2] + 현재값) (최댓값 찾기, 배낭 문제 류)

예시: 계단 오르기 문제

한 번에 1칸 또는 2칸씩 오를 수 있을 때, $N$ 번째 계단에 도달하는 경우의 수는?

직전 상태 고민: $N$ 번째 계단에 도착하려면 반드시 $N-1$ 번째에서 1칸 올라오거나, $N-2$ 번째에서 2칸 올라와야 합니다.
점화식: dp[N] = dp[N-1] + dp[N-2]

Bottom-Up (Tabulation) 템플릿

python# 1. 배열 초기화
dp = [0] * (n + 1)

# 2. Base Case 설정 (초기값)
dp[1] = 1
dp[2] = 2

# 3. 점화식을 이용해 반복문 돌리기 (Bottom-Up)
for i in range(3, n + 1):
    dp[i] = dp[i-1] + dp[i-2]  # 구한 점화식 적용

# 4. 최종 정답 출력
print(dp[n])

결국 DP는 손으로 $N=1, 2, 3, 4$ 일 때의 정답을 직접 써보면서 규칙(점화식)을 눈치채는 것이 가장 중요합니다.

Top-Down (Memoization) 템플릿

계단 오르기(피보나치 유형) 문제를 재귀함수를 활용한 Top-Down (Memoization) 방식으로 푸는 예시

Top-Down 방식의 핵심은 이미 메모장(dp 배열)에 적힌 값이 있다면, 계산하지 말고 그대로 가져와서 쓴다(Return) 입니다.

pythonimport sys
# 파이썬은 기본 재귀 깊이 제한이 1000이므로, Top-Down을 쓸 땐 꼭 늘려줘야 합니다.
sys.setrecursionlimit(10**6) 

def solve() -> None:
    n = int(input())
    
    # 1. 메모장(배열) 초기화 (-1이나 0 등 절대 나올 수 없는 값으로 채움)
    # 아직 계산하지 않았다는 것을 표시하기 위함입니다.
    dp = [-1] * (n + 1)
    
    # 2. Top-Down 재귀 함수 정의
    def get_steps(x: int) -> int:
        # Base Case: 1칸이거나 2칸일 때는 정해진 답 반환
        if x == 1:
            return 1
        if x == 2:
            return 2
            
        # 메모이제이션 핵심: 이미 계산해둔 값(-1이 아님)이라면, 바로 그 값을 반환
        if dp[x] != -1:
            return dp[x]
            
        # 아직 계산하지 않았다면 재귀 호출로 답을 구하고, 그 결과를 메모장(dp[x])에 저장
        dp[x] = get_steps(x - 1) + get_steps(x - 2)
        
        return dp[x]
        
    # 가장 큰 목표인 n부터 거꾸로 파고 내려감
    print(get_steps(n))

if __name__ == "__main__":
    solve()

Top-Down 코드 작동 원리 (예: `get_steps(5)` 호출 시)

get_steps(5)가 호출됩니다. 아직 dp[5]가 -1이므로, get_steps(4) + get_steps(3)을 호출합니다.
꼬리를 물고 내려가서 get_steps(1)과 get_steps(2)까지 도달합니다. (Base Case)
밑바닥부터 계산된 값이 다시 위로 올라오면서 dp[3], dp[4], dp[5]를 채웁니다.
결정적 순간: get_steps(4)를 계산할 때 한 번 get_steps(3)을 호출해서 dp[3]에 정답을 적어두었습니다. 이후 get_steps(5)의 나머지 절반인 get_steps(3)을 호출할 때는, 재귀를 다시 타지 않고 if dp[x] != -1: 조건에 걸려 메모장에 적힌 값을 단 O(1)만에 반환합니다.

(꿀팁) 파이썬만의 사기적인 Top-Down 기능 `@cache`

실무나 코딩 테스트에서 파이썬을 쓰신다면, 배열을 만들 필요도 없이 함수 위에 @cache 데코레이터 한 줄만 붙여주면 파이썬이 알아서 딕셔너리를 만들어 메모이제이션을 대신 해줍니다.

pythonimport sys
from functools import cache
sys.setrecursionlimit(10**6)

def solve() -> None:
    n = int(input())
    
    @cache  # 이 한 줄이 백그라운드에서 dp 배열 역할을 전부 대신함
    def get_steps(x: int) -> int:
        if x == 1: return 1
        if x == 2: return 2
        
        # 배열 저장 로직 없이 순수 점화식만 쓰면 됨
        return get_steps(x - 1) + get_steps(x - 2)
        
    print(get_steps(n))

if __name__ == "__main__":
    solve()

알고리즘 구조를 이해하기 위해서는 첫 번째 방식(직접 배열에 메모)을 꼭 손으로 구현해 보셔야 하지만, 실전 코테에서 시간을 단축할 때는 이 @cache 방법이 아주 강력한 무기가 됩니다!