동적 계획법(DP) — 메모이제이션과 타뷸레이션 쉽게 이해하기

동적 계획법은 더 작은 부분 문제의 답을 저장해 두었다가 나중에 다시 활용해 문제를 푸는 방법입니다. 같은 부분 문제가 반복해서 나타나고, 전체 답을 그 작은 답들로부터 만들 수 있을 때 특히 유용합니다.

대표적인 두 가지 방식은 메모이제이션과 타뷸레이션입니다. 메모이제이션은 재귀 풀이 과정에서 답을 저장합니다. 타뷸레이션은 보통 배열이나 표를 사용해 아래에서 위로 답을 채워 나갑니다.

동적 계획법이 잘 작동하는 경우

동적 계획법은 두 가지 조건이 맞을 때 유용합니다.

첫째, 부분 문제가 겹쳐야 합니다. 즉, 같은 중간 결과가 두 번 이상 필요해야 합니다. 둘째, 더 큰 문제의 답을 더 작은 문제의 답들로 일관되게 만들 수 있어야 합니다.

이 조건이 맞지 않으면, 이전 결과를 저장하는 것이 메모리만 더 쓰고 큰 도움이 되지 않을 수 있습니다.

메모이제이션 vs. 타뷸레이션

메모이제이션: 위에서 아래로 저장

메모이제이션은 재귀적 아이디어에서 시작합니다. 알고리즘이 어떤 부분 문제를 처음 풀면 그 결과를 저장합니다. 이후에는 다시 계산하지 않고 저장된 값을 재사용합니다.

이 방식은 점화식은 분명하지만, 필요한 모든 상태를 어떤 순서로 계산해야 하는지가 명확하지 않을 때 특히 다루기 쉽습니다.

타뷸레이션: 아래에서 위로 구성

타뷸레이션은 기저 사례에서 시작해, 필요한 의존 관계가 맞도록 상태를 차례대로 채워 나갑니다.

이 방식은 이미 깔끔한 반복 순서를 알고 있고, 표를 어떻게 채울지 직접 제어하고 싶을 때 더 다루기 쉽습니다.

동적 계획법 예시: 피보나치 수열

피보나치 수열은 다음과 같이 정의됩니다.

$$F(0) = 0, \quad F(1) = 1$$

그리고 $n \ge 2$일 때,

$$F(n) = F(n-1) + F(n-2)$$

단순한 재귀 풀이에서는 같은 계산이 반복됩니다. 예를 들어 $F(5)$를 구하려면 $F(4)$와 $F(3)$이 필요하고, 다시 $F(4)$를 구할 때도 $F(3)$이 또 필요합니다. 이렇게 반복되는 $F(3)$ 호출이 바로 동적 계획법이 없애 주는 낭비입니다.

피보나치에서의 메모이제이션

메모이제이션을 사용하면 점화식은 그대로 두되, 각 값을 처음 계산한 뒤 저장합니다.

$F(5)$의 경우 유용한 계산 순서는 다음과 같습니다.

• $F(0)=0$을 계산하고 저장
• $F(1)=1$을 계산하고 저장
• $F(2)=1$을 계산하고 저장
• $F(3)=2$를 계산하고 저장
• $F(4)=3$을 계산하고 저장
• $F(5)=5$를 계산하고 저장

핵심은 각 상태를 한 번만 계산한다는 점입니다. 이후의 요청은 저장된 값을 읽기만 하면 됩니다.

피보나치에서의 타뷸레이션

타뷸레이션에서는 기저 사례부터 위로 쌓아 올립니다.

$$\begin{aligned} F(0) &= 0 \\ F(1) &= 1 \\ F(2) &= F(1) + F(0) = 1 \\ F(3) &= F(2) + F(1) = 2 \\ F(4) &= F(3) + F(2) = 3 \\ F(5) &= F(4) + F(3) = 5 \end{aligned}$$

이 방식은 의존 순서를 분명하게 보여 줍니다. 새로운 값은 항상 이미 알고 있는 항들을 사용해 계산됩니다.

동적 계획법이 더 빠를 수 있는 이유

어떤 문제에서 중요한 서로 다른 상태가 $k$개뿐이라면, 동적 계획법은 그 $k$개의 상태를 각각 한 번씩만 풀려고 합니다. 그러면 매우 큰 재귀 호출 트리가 훨씬 작은 계산으로 바뀔 수 있습니다.

정확히 얼마나 빨라지는지는 문제에 따라 다릅니다. 동적 계획법이 자동으로 빠른 것은 아닙니다. 원래 풀이에서 중복 계산이 실제로 큰 비중을 차지할 때 효과가 있습니다.

동적 계획법에서 자주 하는 실수

부분 문제가 겹치지 않는데 사용하는 경우

모든 재귀 문제가 동적 계획법 문제는 아닙니다. 거의 모든 부분 문제가 서로 다르다면, 결과를 캐시해도 줄어드는 계산량이 충분하지 않을 수 있습니다.

상태를 잘못 정의하는 경우

상태에는 다음 단계로 넘어가는 데 필요한 정보가 모두 들어 있어야 합니다. 중요한 정보가 빠지면 점화식이 그럴듯해 보여도 잘못된 답이 나올 수 있습니다.

기저 사례를 잘못 잡는 경우

기저 사례는 전체 방법의 출발점입니다. 시작값이 틀리면, 그 위에 쌓이는 모든 상태도 함께 틀어집니다.

표를 잘못된 순서로 채우는 경우

타뷸레이션은 각 상태를, 그것이 의존하는 상태들보다 나중에 채울 때만 제대로 작동합니다. 점화식이 맞아도 채우는 순서가 틀리면 실패할 수 있습니다.

동적 계획법은 항상 최적화 문제라고 생각하는 경우

유명한 예시 중에는 최대값이나 최소값을 구하는 문제가 많지만, 동적 계획법은 경우의 수 세기나 판별 문제에도 쓰입니다. 진짜 신호는 “최적”이라는 말이 아니라, 재사용 가능한 부분 문제가 있다는 점입니다.

동적 계획법이 사용되는 곳

동적 계획법은 편집 거리, 최장 공통 부분 수열, 경로 수 세기, 배낭 문제 형태의 최적화, 그리고 일부 최단 경로 문제 등에 등장합니다.

이 방법을 써 볼지 판단할 때는 두 가지를 물어보면 됩니다.

• 더 작은 부분 문제가 반복되는가?
• 더 큰 답을 그 작은 답들로부터 만들 수 있는가?

두 질문의 답이 모두 예라면, 동적 계획법은 매우 유력한 선택지입니다.

비슷한 문제에 도전해 보기

한 번에 $1$칸 또는 $2$칸씩 올라갈 수 있을 때, $n$개의 계단을 오르는 방법의 수를 직접 구해 보세요. 점화식이 단순하고, 반복되는 부분 문제도 쉽게 보이기 때문에 피보나치 다음 단계의 좋은 연습 예제입니다.