동적 프로그래밍 기초
동적 프로그래밍(Dynamic Programming, DP)은 큰 문제를 작은 부분 문제로 나누고, 그 결과를 저장해 재사용함으로써 중복 계산을 없애는 알고리즘 설계 기법입니다. 여기서는 피보나치 수열을 예제로 완전 탐색 → 메모이제이션 → 타뷸레이션 순서로 비교합니다.
핵심 개념
최적 부분 구조
큰 문제의 답이 작은 부분 문제들의 답으로 구성될 수 있는 성질입니다. fib(n) = fib(n-1) + fib(n-2)처럼, 전체 문제의 해가 부분 문제 해의 조합으로 표현됩니다.
핵심 개념
중복 부분 문제
재귀로 문제를 나누다 보면 같은 부분 문제가 여러 번 나타나는 경우가 많습니다. fib(5)를 계산할 때 fib(2)는 여러 경로에서 반복해서 계산됩니다. DP는 이 중복을 제거해 속도를 높입니다.
핵심 개념
완전 탐색 (재귀)
부분 문제를 저장하지 않고 매번 새로 계산하는 방식입니다. 구현은 간단하지만 같은 계산을 반복해 지수 시간(O(2ⁿ) 이하, 정확히는 약 1.618ⁿ)이 걸립니다. DP가 왜 필요한지 보여주는 기준점입니다.
핵심 개념
메모이제이션 (Top-down)
재귀 구조는 그대로 두되, 한 번 계산한 결과를 캐시(memo)에 저장해두고 재사용합니다. 재귀 호출 방향이 위(큰 문제)에서 아래(작은 문제)로 내려가 Top-down이라 부릅니다.
핵심 개념
타뷸레이션 (Bottom-up)
재귀 없이 반복문으로 작은 부분 문제부터 표(table)를 채워 올라갑니다. 가장 작은 문제(기저 사례)에서 시작해 큰 문제로 향하기 때문에 Bottom-up이라 부릅니다.
핵심 개념
시간·공간 트레이드오프
메모이제이션·타뷸레이션 모두 시간복잡도를 O(2ⁿ)에서 O(n)으로 낮추는 대신, 결과를 저장할 공간(캐시 또는 표)이 추가로 필요합니다 — 전형적인 시간과 공간을 맞바꾸는 전략입니다.
피보나치로 보는 동적 프로그래밍
동적 프로그래밍은 같은 부분 문제를 여러 번 계산하는 낭비를 저장으로 없애는 방법입니다. 이 토픽은 가장 작은 예인 피보나치로 '저장하지 않을 때'와 '저장할 때'의 차이를 숫자로 보여 줍니다. 배낭 문제 같은 2차원 DP는 DP 기초 토픽에서 이어집니다.
숫자로 확인하기
자주 하는 오해
면접에서 이렇게 물어요
면접 질문
계단 오르기(한 번에 1칸 또는 2칸) 경우의 수는 어떻게 구하나요?
n번째 계단에 오는 방법은 n − 1에서 한 칸, n − 2에서 두 칸 올라오는 경우의 합이라서 피보나치와 같은 점화식 dp[n] = dp[n − 1] + dp[n − 2]입니다.
면접 질문
메모이제이션과 타뷸레이션을 어떻게 고르나요?
필요한 부분 문제가 일부뿐이면 메모이제이션이 편하고, 재귀 깊이가 너무 깊거나 모든 부분 문제가 필요하면 표 채우기가 안전합니다.
면접 질문
공간을 줄일 수 있나요?
dp[i]가 바로 앞 몇 개에만 의존하면 그 값들만 변수로 유지해 O(n) 공간을 O(1)로 줄입니다. 대신 이전 값들로 경로를 복원할 수는 없습니다.
면접 질문
DP로 풀 수 있는 다른 대표 문제를 말해 보세요.
배낭 문제, 최장 공통 부분 수열(LCS), 행렬 연쇄 곱셈 등이 교재에서 다루는 대표 예입니다. 모두 부분 문제를 정의하고 점화식으로 연결하는 같은 틀입니다.
실제 시스템에서는
functools.cache는 같은 인자로 다시 호출하면 저장된 결과를 돌려줍니다(인자는 해시 가능해야 합니다). lru_cache는 기본 maxsize가 128이라 오래 쓰지 않은 결과가 버려질 수 있습니다.
HashMap에 두고 computeIfAbsent의 매핑 함수 안에서 재귀적으로 같은 맵에 값을 넣으면 안 됩니다. Java 문서는 매핑 함수가 계산하는 동안 이 맵을 수정해서는 안 되고, 수정이 감지되면 ConcurrentModificationException이 던져질 수 있다고 설명합니다. 메모이제이션을 직접 구현할 때는 먼저 get으로 확인하는 방식을 씁니다.
StackOverflowError 같은 한계에 걸릴 수 있어서, 반복문 방식으로 바꾸기도 합니다.
함께 보면 좋은 토픽
참고 자료
Java — 완전 탐색 (재귀)
/* ── 완전 탐색: 저장 없이 매번 새로 재귀 호출 ─────────────── */ public int fibNaive(int n) { if (n <= 1) return n; // 기저 사례 return fibNaive(n - 1) + fibNaive(n - 2); }
코드는 단 세 줄이지만, fib(n-2)가 fib(n-1) 내부에서도 다시 호출되는 식으로 같은 부분 문제가 기하급수적으로 반복됩니다.
호출 횟수는 대략 fib(n)에 비례해 늘어나 시간복잡도가 O(2ⁿ)에 가까워지고, n이 40만 넘어가도 체감될 만큼 느려집니다.
Java — 메모이제이션 (Top-down)
/* ── 메모이제이션: 재귀 구조 + 캐시로 중복 계산 제거 ──────── */ private Map<Integer, Integer> memo = new HashMap<>(); public int fibMemo(int n) { if (n <= 1) return n; if (memo.containsKey(n)) return memo.get(n); // 캐시 적중 → 재귀 없이 즉시 반환 int result = fibMemo(n - 1) + fibMemo(n - 2); memo.put(n, result); // 계산 결과를 캐시에 저장 return result; }
fibNaive와 재귀 구조는 동일하지만, memo.containsKey(n) 한 줄이 결정적인 차이를 만듭니다 — 이미 계산된 n이면 재귀 호출 자체가 일어나지 않습니다.
각 n은 정확히 한 번만 계산되므로 시간복잡도가 O(n)으로 줄어듭니다. 다만 재귀 호출 스택과 캐시(Map)를 함께 쓰므로 공간복잡도는 O(n)입니다.
Java — 타뷸레이션 (Bottom-up)
/* ── 타뷸레이션: 재귀 없이 표를 아래에서부터 채움 ─────────── */ public int fibTab(int n) { if (n <= 1) return n; int[] dp = new int[n + 1]; dp[0] = 0; dp[1] = 1; // 기저 사례를 먼저 채움 for (int i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; // 이전 두 값으로 다음 값 계산 } return dp[n]; } /* ── 참고: dp[i]는 직전 두 값에만 의존 → 변수 2개로 O(1) 공간 가능 ─ */ public int fibOptimized(int n) { if (n <= 1) return n; int prev2 = 0, prev1 = 1; for (int i = 2; i <= n; i++) { int cur = prev1 + prev2; prev2 = prev1; prev1 = cur; } return prev1; }
재귀가 전혀 없어 호출 스택이 쌓이지 않으므로 큰 n에서도 StackOverflowError 걱정이 없고, 반복문 하나로 끝나 실전에서 메모이제이션보다 대체로 더 빠릅니다.
시간복잡도는 O(n)으로 메모이제이션과 같지만, fibOptimized처럼 직전 두 값만 유지하면 배열 전체(O(n))가 아닌 변수 두 개(O(1))만으로도 충분합니다.
Q1
동적 프로그래밍(DP)의 핵심 아이디어는?
Q2
메모이제이션(Memoization)과 타뷸레이션(Tabulation)의 차이는?
Q3
완전탐색(브루트포스) 대비 DP가 훨씬 빠른 이유는?