동적 계획법(DP)

정의

겹치는 부분 문제를 저장해 재사용해서 전체 문제를 푸는 방법입니다.

DP는 “계획을 세운다”기보다, 문제를 작은 단위로 쪼갰을 때 같은 계산이 반복되는 구조를 발견하고, 그 결과를 메모해 두는 접근입니다. 그래서 보통 시간을 메모리로 바꾸는 기법이라고 설명합니다.

핵심은 두 가지입니다. (1) 최적 부분 구조(전체 최적해가 부분 최적해로 구성됨), (2) 중복 부분 문제(같은 부분 문제가 반복됨). 이 두 조건이 맞으면 DP로 성능을 크게 개선할 수 있습니다.

핵심 메시지

“DP는 정답을 기억하는 기술이다.
같은 계산을 두 번 하지 않기 위해, 부분 문제의 결과를 저장한다.”

- 점화식과 상태 정의가 DP의 전부 -

DP가 필요한 순간

브루트포스 / 재귀가 같은 선택을 반복한다면 DP 신호입니다.

예를 들어 “N까지 가는 방법 수”, “최대/최소 값”, “부분 수열/부분 합”처럼, 특정 인덱스/값에서의 결과가 이후 계산에 반복해서 쓰이는 문제는 DP로 최적화할 여지가 큽니다.

💡 TIP / 참고사항

DP는 “공식 암기”가 아니라 상태(state) 정의가 핵심입니다.
상태를 한 문장으로 말할 수 있어야 합니다. 예: dp[i] = i번째까지 봤을 때의 최적해

 

핵심 구성 요소

DP는 보통 상태 → 점화식 → 초기값 → 순서로 완성됩니다.

요소	예시	설명
상태(State)	dp[i]	“무엇을 저장할지”를 정의합니다. 보통 i(인덱스), w(무게), t(시간) 같은 축으로 표현됩니다.
점화식(Transition)	dp[i]=min(...)	현재 상태가 이전 상태들로부터 어떻게 계산되는지를 나타냅니다.
초기값(Base)	dp[0]=0	가장 작은 문제의 정답을 정의합니다. 초기값이 흔들리면 전체가 무너집니다.
계산 순서(Order)	for i=1..N	점화식이 참조하는 상태들이 먼저 계산되도록 순서를 설계합니다.

Top-Down vs Bottom-Up

DP 구현은 크게 메모이제이션과 테이블 방식으로 나뉩니다.

👍 Top-Down (Memoization)

• 재귀로 풀되, 계산 결과를 캐시해 중복 호출을 제거합니다.
• 필요한 상태만 계산되는 경우가 있어, 구현이 직관적인 편입니다.
• 단, 재귀 깊이가 깊으면 스택 오버플로우 위험이 있습니다.

👎 Bottom-Up (Table)

• 작은 문제부터 순서대로 테이블을 채우며 올라갑니다.
• 스택 오버플로우가 없고, 성능 예측이 쉬운 편입니다.
• 단, 불필요한 상태까지 채워 메모리를 더 쓸 수 있습니다.

💡 TIP / 참고사항

둘 중 무엇이 “정답”은 아닙니다.
재귀가 자연스러운가? → Top-Down, 순서가 명확한가? → Bottom-Up 으로 시작하면 됩니다.

 

DP 설계 절차

DP는 “문제 읽기”보다 상태 문장 만들기가 먼저입니다.

1

상태(state)를 한 문장으로 정의한다 “dp[i]는 i번째까지 고려했을 때의 정답”처럼, 저장할 의미를 먼저 고정합니다.

2

선택(transition)을 나열한다 현재 상태에서 할 수 있는 선택지를 나열하고, “이 선택이 어떤 이전 상태로 가는지”를 연결합니다.

3

초기값과 계산 순서를 결정한다 어떤 상태가 “시작점”인지 정하고, 참조 관계가 깨지지 않도록 채우는 순서를 잡습니다.

✅ 핵심 요약

• ✔️ DP는 중복되는 부분 문제의 결과를 저장해 전체 문제를 빠르게 푸는 방법이다.
• ✔️ 핵심은 상태 정의이며, “dp가 무엇을 의미하는지”를 한 문장으로 고정해야 한다.
• ✔️ 상태 → 점화식 → 초기값 → 순서를 잡으면, 대부분의 DP 문제는 구조가 보인다.

실전 예시

피보나치로 보는 재귀 vs DP(Top-Down / Bottom-Up)의 차이

DP가 왜 필요한지 가장 직관적으로 보여주는 예시가 피보나치(Fibonacci)입니다. 동일한 문제를 “어떤 방식으로 계산하느냐”에 따라 시간 복잡도가 극단적으로 갈립니다.

1) 일반 재귀

같은 계산을 수만 번 반복하는 방식

재귀로 피보나치를 풀면 구현은 가장 간단하지만, fib(n-1), fib(n-2)가 계속 중복 호출됩니다. 호출 트리가 기하급수적으로 커지기 때문에 n이 조금만 커져도 사실상 멈춘 것처럼 느려집니다.

시간 복잡도	공간 복잡도	특징
O(2n)	O(n)	중복 호출이 폭발적으로 증가 (n이 커지면 사실상 실행 불가)

// Java - 일반 재귀 (비효율) public class Fibonacci { public int fib(int n) { if (n <= 1) return n; // 호출될 때마다 중복 계산이 기하급수적으로 발생함 return fib(n - 1) + fib(n - 2); } } 

💡 TIP / 참고사항

“재귀가 느리다”가 아니라, 중복 계산이 많아지는 형태의 재귀가 느린 겁니다.
동일한 fib(k)가 수천/수만 번 재호출되면, CPU는 같은 일을 계속 반복하게 됩니다.

 

2) DP: Top-Down

재귀 + 메모이제이션(Memoization)

Top-Down은 “재귀로 풀되, 한번 계산한 값은 저장”하는 방식입니다. 핵심은 호출 전에 이미 계산해봤는지(memo 체크) 먼저 확인하는 겁니다.

시간 복잡도	공간 복잡도	특징
O(n)	O(n)	중복 호출 제거, 필요한 상태만 계산할 수 있음(문제에 따라 장점)

// Java - Top-Down DP (Memoization) public class FibonacciDP { // 계산된 값을 저장할 저장소 (캐시 역할) private int[] memo = new int[101]; public int fib(int n) { if (n <= 1) return n; // 1) 이미 계산한 적이 있다면 저장된 값을 즉시 반환 (중복 계산 방지) if (memo[n] != 0) return memo[n]; // 2) 계산 결과를 배열에 저장 (기억하기) memo[n] = fib(n - 1) + fib(n - 2); return memo[n]; } } 

💡 TIP / 참고사항

이 예시는 memo 배열의 기본값이 0이라서, fib(n)이 0이 될 수 있는 경우(예: fib(0))와 겹치지 않아 안전합니다.
하지만 DP 문제에 따라 “0이 유효한 값”일 수 있으니, 그때는 -1로 초기화하거나 visited 배열을 별도로 둡니다.

 

3) DP: Bottom-Up

테이블 채우기(Tabulation)

Bottom-Up은 작은 문제부터 정답을 채워 올라가며 dp 테이블을 완성하는 방식입니다. 재귀 호출이 없어서 StackOverflow 위험이 없고, 계산 흐름이 명확해 실무/코테에서 많이 사용됩니다.

시간 복잡도	공간 복잡도	특징
O(n)	O(n)	순서가 명확, 재귀 스택 없음, 구현이 안전함

// Java - Bottom-Up DP (Tabulation) public class FibonacciDP { public int fib(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]; } } 

💡 TIP / 참고사항

피보나치처럼 “직전 2개만 필요”한 DP는 공간을 더 줄일 수도 있습니다.
즉, dp 배열을 전부 만들지 않고 변수 2개(prev, curr)만으로 O(1) 공간으로 최적화가 가능합니다.

 

✅ 핵심 요약

• ✔️ 일반 재귀는 중복 계산 때문에 O(2ⁿ)로 폭발합니다.
• ✔️ Top-Down은 재귀에 캐시(memo)를 붙여 중복 호출을 제거해 O(n)으로 줄입니다.
• ✔️ Bottom-Up은 테이블을 아래부터 채우며 스택 오버플로우 없이 안전하게 O(n)을 달성합니다.