동적 계획법이 성립하는 조건: 최적 부분 구조와 메모이제이션
동적 계획법은 부분 문제의 최적해로 전체 최적해를 만드는 최적 부분 구조와, 같은 부분 문제가 반복되는 중복 부분 문제가 함께 있을 때 성립한다. 메모이제이션이 왜 통하고 언제 안 통하는지 피보나치 예제로 정리했다.
동적 계획법(DP, Dynamic Programming)은 큰 문제를 작은 부분 문제로 쪼갠 뒤, 한 번 계산한 부분 문제의 답을 저장해 두고 다시 쓰는 방식이다. 이 방식이 제대로 통하려면 두 가지 성질이 있어야 한다. 하나는 최적 부분 구조로, 부분 문제의 최적해를 모으면 전체 최적해가 나오는 성질이다. 다른 하나는 중복 부분 문제로, 같은 부분 문제가 계산 과정에서 여러 번 등장하는 성질이다. 메모이제이션은 이 저장하고 다시 쓰는 과정을 구현하는 대표적인 기법이다.
알고리즘 교과서 Introduction to Algorithms(흔히 CLRS로 부른다)는 이 두 성질을 동적 계획법이 성립하는 핵심 조건으로 정의한다. 이 글은 세 용어가 어떻게 맞물리는지, 왜 하나라도 빠지면 안 되는지에 초점을 둔다. 배낭 문제 같은 개별 문제 풀이나 위에서 아래로 푸는 메모이제이션과 반복문으로 표를 채우는 방식의 성능 비교는 다루지 않는다.
최적 부분 구조란 무엇인가
최적 부분 구조는 전체 문제의 최적해가 그 부분 문제들의 최적해로 이루어지는 성질이다. 부분을 각각 최선으로 풀어 합치면 전체도 최선이 된다는 뜻이다.
최단 경로로 설명하면 이해가 빠르다. A에서 C로 가는 최단 경로가 중간에 B를 지난다고 하자. 그렇다면 A에서 B까지 구간도 반드시 최단 경로여야 한다. 만약 A에서 B로 가는 더 짧은 길이 따로 있다면, 그 길로 갈아타는 순간 A에서 C까지 전체 거리도 줄어들어 최단이라는 전제가 깨지기 때문이다. 이처럼 큰 문제의 최적해 안에 작은 문제의 최적해가 그대로 들어 있는 구조를 최적 부분 구조라고 한다. CLRS도 전체 최적해가 부분 문제의 최적해를 포함하는 성질로 이를 정의한다.
메모이제이션은 중복 계산을 어떻게 없애나
이미 계산한 부분 문제의 답을 표에 적어 두고, 같은 입력이 다시 들어오면 계산을 건너뛰고 그 값을 꺼내 쓴다. 이 저장 공간 덕분에 같은 계산을 두 번 하지 않는다.
피보나치 수열이 교과서적인 예다. fib(n) = fib(n-1) + fib(n-2)를 그냥 재귀로 풀면 fib(n-2)나 fib(n-3) 같은 값이 수없이 다시 계산된다. n이 커질수록 호출 횟수가 대략 2의 n제곱에 비례해 폭발한다. 반면 각 fib(k)의 답을 한 번만 계산해 저장하면, 서로 다른 부분 문제는 n개뿐이라 전체 계산량이 n에 비례하는 수준으로 내려간다.
from functools import cache
@cache
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)파이썬에서는 표를 직접 만들 필요도 없다. Python 공식 문서에 따르면 functools.cache 데코레이터는 3.9 버전에서 추가됐고, 호출 인자별 결과를 딕셔너리에 저장하는 functools.lru_cache(maxsize=None)과 같은 동작을 한다. 위 함수에 @cache 한 줄만 붙이면 결과가 자동으로 저장되고 재사용된다. 저장한 값을 곧바로 꺼내 쓰는 부분은 부분 문제를 정수 인덱스로 표에 대응시키는 것이라, 배열 인덱싱으로 O(1) 조회가 되는 원리와 같은 이치다. 다만 위에서 아래로 재귀하며 푸는 방식은 입력이 커질수록 함수 호출이 쌓이는 호출 스택이 깊어지므로, 재귀 깊이 한계도 함께 고려해야 한다.
여기서 메모이제이션이 실제로 이득이 되는 조건이 바로 중복 부분 문제다. 피보나치처럼 같은 부분 문제가 반복해 등장해야 저장해 둔 값을 다시 꺼내 쓸 일이 생긴다. 부분 문제가 전부 제각각이라 한 번씩만 나온다면, 저장해도 다시 찾을 일이 없어 메모리만 쓰고 이득은 없다.
두 조건이 함께 있어야 동적 계획법이 성립한다
정리하면 두 성질의 역할이 다르다. 최적 부분 구조는 부분해를 합쳐 만든 답이 정말 최적이라는 정확성을 보장하고, 중복 부분 문제는 저장과 재사용이 실제로 계산량을 줄인다는 효율을 보장한다. 둘 중 하나만 있으면 동적 계획법의 이점을 온전히 얻지 못한다.
최적 부분 구조가 없으면 메모이제이션을 붙여도 틀린 답이 나올 수 있다. CLRS는 그래프에서 정점을 다시 밟지 않는 최장 단순 경로(longest simple path) 문제를 최적 부분 구조가 성립하지 않는 예로 든다. 두 지점 사이의 최장 경로를 두 구간으로 쪼갰을 때, 각 구간의 최장 경로를 이어 붙이면 정점이 겹쳐 단순 경로라는 조건이 깨질 수 있어서, 부분의 최적해가 전체의 최적해를 만들어 주지 않는다.
반대로 중복 부분 문제가 없으면, 즉 부분 문제가 모두 서로 다르면 메모이제이션은 재사용할 값이 없어 순수 재귀와 다를 게 없다. 그래서 동적 계획법을 적용할 문제인지 판단할 때는 부분해를 합쳐 전체 최적이 나오는지, 같은 부분 문제가 반복되는지를 먼저 확인하는 것이 실무의 순서다. 참고로 메모이제이션처럼 위에서 아래로 재귀하며 저장하는 방식과 반복문으로 표를 아래에서 위로 채우는 방식은 둘 다 이 두 조건을 이용하는 같은 동적 계획법의 서로 다른 구현일 뿐이다.
