0x04. 동적 프로그래밍 (Dynamic Programming)

동적 프로그래밍이란?

동적 프로그래밍(Dynamic Programming, DP)은 특정 알고리즘이 아니라 문제를 푸는 설계 패러다임(Design Paradigm) 이다. 주로 최적화(Optimization) 문제, 즉 여러 선택지 중에서 최솟값이나 최댓값을 구하는 문제에 사용된다. 최단 경로(Shortest Path)나 작업 스케줄링(Job Scheduling) 같은 문제가 대표적이다.

DP의 핵심 아이디어는 큰 문제를 더 작은 하위 문제(Subproblem)로 쪼개어 풀되, 그 결과를 저장해 두고 재활용하는 것이다. 분할 정복(Divide and Conquer)과 비슷해 보이지만, DP는 상향식(Bottom-up) 으로 작은 문제부터 차근차근 풀어 올라간다는 점이 다르다.

분할 정복 vs. 동적 프로그래밍

분할 정복과 DP 모두 문제를 하위 문제로 쪼개어 해결하는 전략이다. 그렇다면 둘의 차이는 무엇일까?

분할 정복 알고리즘은 겹치는 하위 문제(Common Subproblems) 를 반복적으로 계산하면서 필요 이상의 작업을 하게 된다. 반면 DP 알고리즘은 모든 하위 문제를 딱 한 번만 풀고, 그 결과를 테이블에 저장한다. 이후 같은 하위 문제를 만나면 다시 계산하지 않고 테이블에서 꺼내 쓰기만 하면 된다.

정리하면, DP는 중복 계산을 제거함으로써 분할 정복보다 훨씬 효율적으로 동작한다. DP는 전형적으로 최적화 문제에 적용된다.

행렬 곱셈 (Matrix Chain Multiplication)

괄호 묶기 문제

$p \times q$ 행렬 A와 $q \times r$ 행렬 B의 곱은 $p \times r$ 행렬 C가 된다.

이때 곱셈의 비용은 $p \cdot q \cdot r$ 이다.

세 행렬 A( $p \times q$ ), B( $q \times r$ ), C( $r \times s$ )를 곱하는 방법은 두 가지다.

(A · B) · C: 비용 = $p \cdot q \cdot r + p \cdot r \cdot s$ = $p \cdot r \cdot (q + s)$
A · (B · C): 비용 = $q \cdot r \cdot s + p \cdot q \cdot s$ = $(p + r) \cdot q \cdot s$

괄호를 어떻게 묶느냐에 따라 연산 횟수가 극적으로 달라진다. 다음 예시를 보면 그 차이가 확연하다.

그렇다면 최적의 괄호 묶기를 어떻게 찾을 수 있을까? 모든 경우를 전수 조사(Brute-force)하는 것은 비현실적이다. 답은 DP에 있다.

왜 전수 조사가 이렇게 오래 걸릴까? 핵심 원인은 중복 계산(Recalculation) 이다. 같은 하위 문제를 수없이 반복해서 풀게 되기 때문이다.

최적해의 구조

핵심 관찰(Key Observation): 최적의 행렬 곱셈 순서 A $_i$ A $_{i+1}$ ... A $_j$ 가 있다고 하자. 이 순서가 A $_k$ 와 A $_{k+1}$ 사이에서 분할된다면, 왼쪽 부분(A $_i$ ... A $_k$ )과 오른쪽 부분(A $_{k+1}$ ... A $_j$ )도 각각 최적이어야 한다.

이것은 DP가 적용 가능한 문제인지 판단하는 핵심적인 성질들과 직결된다.

최적 부분 구조(Optimal Substructure)

전체 문제의 최적해(Optimal Solution) 가 더 작은 동일 문제의 최적해를 그 안에 포함하고 있는 성질이다. 쉽게 말해, 큰 문제의 최적해를 구성하는 조각들 역시 각각 최적이어야 한다는 뜻이다.

겹치는 하위 문제(Overlapping Subproblems)

재귀적으로 문제를 풀 때, 새로운 하위 문제가 아닌 이미 풀었던 동일한 하위 문제를 반복적으로 다시 풀게 되는 성질이다. 이것이 바로 DP가 테이블을 사용해 중복 계산을 제거하는 이유다.

최적성 원리(Principle of Optimality)

최적화 문제에서 결합 함수(combine)가 주어졌을 때, 최적 부분 구조가 항상 성립하면 최적성 원리가 성립한다고 말한다.

메모이제이션 (Memoization)

메모이제이션은 하향식(Top-down) 전략을 유지하면서 DP의 이점을 취하는 기법이다. 재귀 호출 시 이미 계산한 값이 있으면 저장된 결과를 바로 반환하여 중복 계산을 방지한다.

상향식 DP와 메모이제이션 방식 모두 시간 복잡도는 $\theta(n)$ 으로 동일하다.

MCM의 최적 부분 구조

DP 알고리즘은 다음 4단계로 개발한다.

최적해의 구조를 파악한다 (최적 부분 구조 찾기)
최적해의 값을 재귀적으로 정의한다 (점화식 세우기)
최적해의 값을 상향식으로 계산한다 (Bottom-up 테이블 채우기)
계산된 정보로부터 최적해를 구성한다 (역추적)

Step 1: 최적 부분 구조 파악

앞서 확인한 핵심 관찰에서 최적 부분 구조를 식별했다. 행렬 체인 곱셈 문제의 최적해는 문제를 두 개의 하위 문제로 분할하고 (A $_i$ A $_{i+1}$ ...A $_k$ 와 A $_{k+1}$ A $_{k+2}$ ...A $_j$ 를 각각 최적으로 괄호 묶기), 각 하위 문제의 최적해를 구한 뒤, 이를 결합하여 구축할 수 있다.