동적 계획법 쉽게 이해하기를 검색하는 사람 중 많은 경우는 이미 피보나치 예제는 봤습니다. 그런데도 실제 문제를 보면 갑자기 손이 멈춥니다. 이유는 점화식 자체보다 무엇을 상태로 둘지를 정하지 못하기 때문입니다.
이번 글에서는 DP를 점화식 암기 과목처럼 설명하지 않고, 왜 문제 적용이 막히는지부터 상태 정의와 사고 흐름 중심으로 더 자세하게 정리하겠습니다. 이번 보강판에서는 상태 정의 흐름을 카드와 단계 그림으로도 더 명확히 보여줍니다.
DP가 필요한 문제는 어떤 모습일까
DP가 잘 맞는 문제는 보통 같은 계산이 반복되고, 큰 문제의 답을 작은 문제의 답으로 조립할 수 있습니다. 즉 중복 부분 문제와 최적 부분 구조가 보이면 DP를 의심해 볼 수 있습니다.
- 같은 하위 문제를 여러 번 풀게 된다
- 작은 답을 쌓아 큰 답을 만들 수 있다
- 브루트포스로 가면 경우의 수가 너무 커진다
이 세 가지가 동시에 보이면 DP 가능성이 커집니다. 반대로 각 선택이 서로 거의 독립적이거나 현재 최선만 고르면 되는 문제라면 그리디가 더 맞을 수도 있습니다.
왜 점화식은 아는데 문제를 못 풀까
입문자가 가장 많이 막히는 지점은 점화식 쓰는 법보다 상태 정의입니다. 예를 들어 dp[i]가 무엇을 뜻하는지 애매하면, 점화식도 자연스럽게 나오지 않습니다. 상태 의미가 흐리면 구현은 맞는 것 같은데 예제가 자꾸 틀립니다.
즉 DP의 시작점은 “이 인덱스에서 무엇을 저장할 것인가”를 정하는 일입니다. 최대값인지, 최소값인지, 경우의 수인지, 가능 여부인지가 먼저 분명해야 합니다.
# 예: 계단 오르기
# dp[i] = i번째 계단에 도착했을 때의 최대 점수
for i in range(2, n + 1):
dp[i] = max(dp[i-2], dp[i-3] + stair[i-1]) + stair[i]이 코드는 식만 보면 복잡하지만, dp[i]의 의미가 먼저 분명하면 식도 훨씬 덜 낯설게 느껴집니다. 반대로 dp[i]가 무엇인지 설명할 수 없으면 점화식은 거의 암기 수준으로 남습니다.
DP를 풀 때 머릿속 순서
- 상태를 정의한다
- 그 상태가 이전 어떤 상태에서 오는지 본다
- 점화식을 만든다
- 초기값을 채운다
- 탑다운 또는 바텀업으로 계산한다
이 순서를 거꾸로 가면 대부분 막힙니다. 특히 초기값과 상태 정의를 대충 넘기면 구현에서 자주 무너집니다. 많은 입문자가 “식은 세웠는데 왜 index error가 나지?” 또는 “왜 첫 테스트만 틀리지?” 같은 문제를 겪는 이유가 여기 있습니다.
메모이제이션과 바텀업은 어떻게 다를까
메모이제이션은 재귀 호출 위에 캐시를 얹는 감각이고, 바텀업은 작은 상태부터 표를 채워 올라가는 감각입니다. 둘 다 같은 문제를 풀 수 있지만, 입문자에게는 바텀업이 계산 순서를 눈으로 보기 쉬운 경우가 많습니다.
다만 문제에 따라 재귀 구조가 더 자연스러우면 메모이제이션이 이해를 돕기도 합니다. 핵심은 어느 방식이든 같은 상태를 반복 계산하지 않게 만드는 것입니다.
DP는 흔히 그리디와 비교해서 헷갈리기 쉬운데, 그런 대비 감각은 그리디 알고리즘이 어려운 이유 같은 후속 글과도 자연스럽게 이어질 수 있습니다. 개념 쪽 참고는 동적 계획법 개요처럼 중복 부분 문제와 최적 부분 구조를 설명하는 자료와 함께 보면 좋습니다.
자주 하는 실수
- dp 배열 의미를 끝까지 명확히 못 정한다
- 초기값을 빼먹는다
- 점화식은 맞는데 인덱스가 어긋난다
- 사실은 그리디나 BFS가 더 맞는 문제인데 무조건 DP로 보려 한다
즉 DP는 어려운 기술이라기보다, 문제를 작은 상태로 잘 나누는 훈련에 더 가깝습니다. DP가 약한 사람은 수식이 약한 경우보다, 상태를 언어로 설명하는 연습이 부족한 경우가 많습니다.
정말 실력이 늘고 있는지 확인하려면 점화식을 쓰기 전에 “dp[i]는 무엇이다”를 먼저 말해보는 습관이 좋습니다. 이 한 문장이 자연스럽게 나오면 절반은 풀린 셈입니다.
마무리
동적 계획법이 어려운 이유는 점화식이 길어서가 아니라, 어떤 정보를 상태로 저장해야 하는지 처음에 잘 안 잡히기 때문입니다.
그래서 DP를 잘하려면 식을 외우기보다, dp[i]가 정확히 무엇을 뜻하는지 한 문장으로 말할 수 있는가를 먼저 확인하는 편이 훨씬 중요합니다.
