기본 개념 시리즈에서 피보나치로 DP의 원리를 익혔다. 이제 문제가 바뀌어도 스스로 DP를 설계할 수 있어야 한다. 설계에서 가장 먼저 해야 할 일은 dp[i]에 무엇을 저장할지 결정하는 것이다.
dp 배열이란
dp 배열은 "중간 계산 결과를 저장하는 공간"이다. dp[i]에 어떤 값을 저장할지는 문제마다 다르다.
피보나치에서는 dp[i] = i번째 피보나치 수였다. 그런데 모든 문제가 이렇게 단순하지 않다. 상태를 잘못 정의하면 점화식을 세울 수 없다.
상태 정의 방법
"지금 모르는 게 뭔가?"로 시작하면 된다.
동전 교환 문제를 예로 보자. 동전 종류 [1, 5, 10]이 있을 때 금액 N원을 만드는 최소 동전 수를 구해야 한다.
"지금 모르는 게 뭔가?" → 각 금액을 만드는 최소 동전 수.
그래서 dp[i] = 금액 i원을 만들 수 있는 최소 동전 수로 정의한다.
최종 답은 dp[N]이 된다.
상태 정의가 맞는지 확인하는 법
정의한 상태가 올바른지 두 가지를 확인한다.
- 최종 답을 표현할 수 있는가 :
dp[N]이 구하려는 값인가 - 이전 상태로부터 계산 가능한가 :
dp[i]를dp[j](j < i)로 표현할 수 있는가
동전 문제에서:
dp[N]이 N원을 만드는 최소 동전 수 → 최종 답 Odp[i]를dp[i - 동전]값들로 계산 가능 → 이전 상태 활용 O
상태가 2차원이 되는 경우
때로는 dp[i] 하나로 상태를 표현하기 부족할 때가 있다.
무게 제한이 있는 배낭 문제를 보자. N개의 물건이 있고 배낭에 담을 수 있는 무게는 W다. 물건마다 무게와 가치가 있을 때 최대 가치를 구해야 한다.
"지금 모르는 게 뭔가?" → i번 물건까지 고려했을 때 무게 j로 담을 수 있는 최대 가치.
변수가 두 개다. 그래서 dp[i][j] = 물건 1~i를 고려하고 용량이 j일 때의 최대 가치로 정의한다.
dp[i]만으로 다음 상태를 결정할 수 없다면 변수를 추가해야 한다. "현재 상황을 완전히 설명하려면 어떤 정보가 필요한가"를 따져보자.
상태 정의 연습
상태 정의는 경험이 쌓일수록 자연스러워진다. 처음에는 다음 질문을 순서대로 던져보자.
- "최종 답은 무엇인가?" → 그것을 dp 배열의 값으로
- "어떤 인덱스에서 꺼내면 최종 답이 되는가?" → dp 배열의 인덱스로
- "인덱스 하나로 충분한가, 아니면 더 필요한가?" → 2D, 3D 결정