핵심 정리
| 질문 | 의미 |
|---|---|
| 상태는 무엇인가 | dp[i]가 정확히 어떤 답인지 |
| 전이는 무엇인가 | 작은 상태에서 큰 상태를 어떻게 만드는지 |
| 초기값은 무엇인가 | 시작 상태와 불가능 상태 |
| 계산 순서는 무엇인가 | 필요한 이전 값이 먼저 계산되는지 |
csharp
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];
}구조
동적 프로그래밍은 같은 계산을 여러 번 반복하지 않도록 답을 저장합니다. 피보나치 재귀는 같은 Fib(k)를 계속 다시 계산하지만, DP는 한 번 계산한 값을 재사용합니다.
text
Fib(5)
-> Fib(4) + Fib(3)
-> Fib(3)이 여러 번 등장DP가 잘 맞는 문제는 보통 두 조건을 가집니다.
| 조건 | 의미 |
|---|---|
| 중복 하위 문제 | 같은 작은 문제가 반복됨 |
| 최적 부분 구조 | 전체 답이 작은 답들로 구성됨 |
메모이제이션과 타뷸레이션
메모이제이션은 재귀를 유지하면서 계산 결과를 캐시에 저장합니다. 타뷸레이션은 작은 상태부터 반복문으로 테이블을 채웁니다.
csharp
int Fib(int n)
{
if (n <= 1) return n;
if (memo[n] != -1) return memo[n];
memo[n] = Fib(n - 1) + Fib(n - 2);
return memo[n];
}상태 잡기
| 문제 신호 | 상태 예시 |
|---|---|
| i번째까지의 최댓값 | dp[i] |
| i번째, j번째 선택 | dp[i, j] |
| 특정 용량까지의 최댓값 | dp[i, w] |
| 마지막 선택이 중요 | dp[i, state] |
| 이전 몇 개만 필요 | 배열 압축 가능 |
DP는 코드보다 상태 정의가 더 중요합니다. dp[i]가 “i번째를 반드시 포함한 답”인지, “i번째까지 고려한 답”인지가 다르면 전이식도 달라집니다.
주의할 점
DP 배열의 초기값을 0으로 두면 “계산하지 않음”과 “답이 0”을 구분하지 못하는 문제가 생길 수 있습니다. 불가능 상태는 -1, 큰 값, bool 방문 배열 등으로 명확히 표현하세요.
또 2차원 DP는 메모리부터 계산해야 합니다. 100000 x 100000 테이블은 만들 수 없습니다.
참고 링크
1 sources