[DP-1] Dynamic Programming 개념과 구현 방식

Python 코딩테스트 알고리즘 스터디 8주차 — 동적 계획법(DP) 내용을 정리한 글이다.

다이나믹 프로그래밍은 이미 계산한 결과를 기억해두고 다시 계산하지 않는 방식이다.

---

1. DP란 무엇인가

핵심 아이디어

다이나믹 프로그래밍(이하 DP)은 중복 부분 문제와 최적 부분 구조를 가진 문제를 효율적으로 푸는 기법이다.

• 중복 부분 문제: 같은 하위 문제가 반복적으로 등장한다
• 최적 부분 구조: 전체 문제의 최적해가 부분 문제들의 최적해로 구성된다

"기억하며 풀기"가 DP의 핵심이다. 같은 계산을 두 번 하지 않는다.

재귀의 중복 계산 문제: 피보나치 트리

피보나치 수열을 순수 재귀로 구현하면 무슨 일이 일어나는지 살펴보자. fib(5)를 계산하는 호출 트리를 그리면 다음과 같다.

fib(5)
↙ fib(4)				↘ fib(3) 2회
↙ fib(3) 2회		↘ fib(2) 3회		↙ fib(2) 3회		↘ fib(1)

fib(3)이 2번, fib(2)가 3번, fib(1)이 5번 호출된다. fib(n)을 순수 재귀로 계산하면 O(2^n)이 걸린다. n이 40이면 약 10억 번의 연산이 필요하다.

문제의 핵심은 이미 계산한 값을 버린다는 점이다. fib(3)을 처음 계산했을 때 그 결과를 어딘가에 저장해두고 두 번째 요청 때 재사용하면, 중복 계산을 완전히 없앨 수 있다.

---

2. 메모이제이션 vs 타뷸레이션

DP를 구현하는 방식은 크게 두 가지다.

구분	메모이제이션 (Top-Down)	타뷸레이션 (Bottom-Up)
방향	큰 문제 → 작은 문제	작은 문제 → 큰 문제
구현	재귀 + 캐시	반복문 + 배열
계산 범위	필요한 것만 계산	전부 계산
스택 오버플로	재귀 깊이 한도 주의	없음
코드 직관성	점화식에 가까움	초기화 순서가 중요
공간 최적화	어려움	가능

Top-Down (메모이제이션) fib(5) 호출 → fib(4) 호출 → fib(3) 호출 → ... → 캐시 저장 → 중복 호출 시 즉시 반환 점화식을 그대로 코드로 옮기기 쉽다

Bottom-Up (타뷸레이션) dp[0] = 0, dp[1] = 1 초기화 → dp[2] = dp[1]+dp[0] = 1 → dp[3] = dp[2]+dp[1] = 2 → ... → dp[n] 계산 스택 오버플로 걱정 없이 공간 최적화 가능

코딩 테스트에서는 두 방식 모두 통하지만, 공간 최적화가 필요하거나 재귀 깊이가 깊어질 가능성이 있을 때는 Bottom-Up을 선호한다.

---

3. 점화식이란

점화식은 n번째 값을 이전 값들로 표현하는 수식이다. DP 풀이의 출발점은 항상 점화식 도출이다.

피보나치 점화식

f(n) = f(n-1) + f(n-2)    (n ≥ 2)

초기값: f(0) = 0, f(1) = 1

점화식을 코드로 옮기는 방법에는 Top-Down과 Bottom-Up이 있다. 점화식 자체는 같고, 계산 방향만 다르다.

---

4. Top-Down: 메모이제이션

functools.lru_cache 활용

functools.lru_cache는 함수의 반환값을 인수를 키로 캐시하는 데코레이터다. 동일한 인수로 다시 호출되면 계산 없이 캐시에서 반환한다. maxsize=None으로 설정하면 캐시 크기 제한이 없다.

import functools @functools.lru_cache(maxsize=None) def fib_top_down(n): if n <= 1: return n return fib_top_down(n - 1) + fib_top_down(n - 2)

print(fib_top_down(10)) print(fib_top_down(50))

55 12586269025

순수 재귀로는 fib(50) 계산에 수십 초가 걸리지만, 메모이제이션을 적용하면 즉시 반환한다.

딕셔너리로 직접 구현

lru_cache를 사용할 수 없는 환경이라면 딕셔너리로 직접 캐시를 관리한다.

memo = {} def fib_memo(n): if n in memo: return memo[n] if n <= 1: return n memo[n] = fib_memo(n - 1) + fib_memo(n - 2) return memo[n]

print(fib_memo(10)) print(fib_memo(50))

55 12586269025

딕셔너리 방식은 lru_cache보다 약간 느리지만, Python 버전 제약이 없고 캐시 내용을 직접 조회하거나 수정할 수 있다는 장점이 있다.

---

5. Bottom-Up: 타뷸레이션

dp 배열 초기화

Bottom-Up은 가장 작은 문제부터 시작해 위로 올라간다.

1. dp 배열을 선언하고 초기값(base case)을 설정한다.
2. 점화식에 따라 작은 인덱스부터 큰 인덱스 순서로 채운다.

def fib_bottom_up(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]

print(fib_bottom_up(10)) print(fib_bottom_up(50))

55 12586269025

공간 최적화: 변수 2개로 줄이기

피보나치의 경우 dp[i]를 계산할 때 dp[i-1]과 dp[i-2]만 필요하다. 전체 배열을 유지할 필요 없이 변수 두 개로 공간을 O(n)에서 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(10)) print(fib_optimized(50))

55 12586269025

공간 최적화는 dp 배열 전체를 저장할 필요가 없을 때만 가능하다. 이전 값을 역추적해야 하는 경우(경로 복원 등)에는 전체 배열을 유지해야 한다.

---

6. Python 자주 쓰는 메서드

functools.lru_cache — Top-Down 메모이제이션 데코레이터

@lru_cache(maxsize=None)을 재귀 함수에 붙이면 동일한 인수로 호출될 때 캐시에서 값을 반환한다. maxsize=None으로 설정하면 캐시 크기 제한이 없다.

import functools import sys sys.setrecursionlimit(10000) @functools.lru_cache(maxsize=None) def fib(n): if n <= 1: return n return fib(n - 1) + fib(n - 2) print(fib(40)) fib.cache_clear() print(fib.cache_info())

102334155 CacheInfo(hits=0, misses=41, maxsize=None, currsize=41)

func.cache_clear()를 호출하면 캐시가 초기화되고, cache_info()로 캐시 상태를 확인할 수 있다.

@functools.cache — lru_cache(maxsize=None) 단축형 (Python 3.9+)

import functools @functools.cache def fib_cache(n): if n <= 1: return n return fib_cache(n - 1) + fib_cache(n - 2) print(fib_cache(50))

12586269025

@functools.cache는 @lru_cache(maxsize=None)과 동일하게 동작한다. Python 3.9 이상에서만 사용 가능하다.

sys.setrecursionlimit — 재귀 한도 확장

Python의 기본 재귀 한도는 1000이다. 깊이가 깊은 DP 재귀를 사용할 때는 미리 한도를 늘려두어야 한다.

import sys sys.setrecursionlimit(100000) print(sys.getrecursionlimit())

100000

dict — 수동 메모이제이션 테이블

lru_cache를 쓸 수 없는 환경이거나 캐시 내용을 직접 조회·수정해야 할 때 딕셔너리로 메모이제이션 테이블을 직접 관리한다.

memo = {} def fib_dict(n): if n in memo: return memo[n] if n <= 1: return n memo[n] = fib_dict(n - 1) + fib_dict(n - 2) return memo[n] print(fib_dict(50)) print(memo[10])

12586269025 55

DP 배열 초기화 패턴

n = 10 dp_zero = [0] * (n + 1) dp_inf = [float('inf')] * (n + 1) dp_neg_inf = [float('-inf')] * (n + 1) dp_inf[0] = 0 print(dp_zero) print(dp_inf[:5]) print(dp_neg_inf[:5])

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] [0, inf, inf, inf, inf] [-inf, -inf, -inf, -inf, -inf]

초기화 방식	사용 상황
[0] * (n+1)	경우의 수나 누적합 DP에서 기본 초기화
[float('inf')] * (n+1)	최솟값 DP에서 초기화 — 동전 교환, 최단 경로 등
[float('-inf')] * (n+1)	최댓값 DP에서 초기화 — 범위 밖의 전이를 자동으로 배제

---

7. 연습 문제

초급

번호	문제	난이도	핵심 접근
12945	피보나치 수	Lv.2	Bottom-Up dp 배열 채우기, 나머지 1234567 처리
12914	멀리 뛰기	Lv.2	dp[i] = dp[i-1] + dp[i-2], 피보나치 구조와 동일
12913	땅따먹기	Lv.2	각 행 최대값 선택, 이전 행과 다른 열만 가능

중급

번호	문제	난이도	핵심 접근
43105	정수 삼각형	Lv.3	꼭대기부터 최댓값 누적, 타뷸레이션 적용
42895	N으로 표현	Lv.3	사용 횟수별 만들 수 있는 수 집합 DP