왜 동적 계획법이 필요한가
앞 장에서 그리디 알고리즘은 "지금 가장 좋아 보이는 선택"을 반복한다고 배웠습니다. 하지만 모든 문제가 그렇게 풀리지는 않습니다. 지금의 선택이 미래의 선택에 영향을 주고, 여러 가능성을 비교해야 하는 문제에서는 단순한 기준 하나로 답을 보장하기 어렵습니다.
동적 계획법은 이런 상황에서 자주 등장합니다. 이름은 어렵지만 핵심은 단순합니다.
이미 계산한 작은 문제의 답을 저장해 두고, 다시 필요할 때 재사용한다.
예를 들어 피보나치 수열을 생각해 봅시다.
fib(1) = 1
fib(2) = 1
fib(n) = fib(n - 1) + fib(n - 2)이를 그대로 재귀로 구현하면 다음과 같습니다.
function fib(n):
if n == 1 or n == 2:
return 1
return fib(n - 1) + fib(n - 2)fib(6)을 계산한다고 해 봅시다.
fib(6)
= fib(5) + fib(4)
= (fib(4) + fib(3)) + (fib(3) + fib(2))이 과정에서 fib(3)처럼 같은 계산이 여러 번 등장합니다. 더 깊이 내려가면 fib(2), fib(1) 같은 호출도 반복됩니다. 문제의 답은 맞지만, 이미 구한 값을 또 구하고 또 구하기 때문에 비효율적입니다.
동적 계획법, 줄여서 DP는 바로 이 중복 계산을 줄이기 위한 방법입니다. 한 번 구한 fib(3)의 값을 저장해 두면, 다음에 fib(3)이 필요할 때 다시 재귀 호출을 하지 않고 저장된 값을 꺼내 쓰면 됩니다.
AI 생성 이미지
동적 계획법의 기본 생각
동적 계획법을 쓰려면 보통 두 가지 조건을 확인합니다.
첫째, 큰 문제의 답을 작은 문제의 답으로 만들 수 있어야 합니다. 예를 들어 fib(6)은 fib(5)와 fib(4)의 답을 이용해 구할 수 있습니다.
둘째, 같은 작은 문제가 여러 번 반복됩니다. fib(3), fib(2) 같은 값이 여러 경로에서 다시 필요합니다.
이 두 조건이 함께 있으면 저장이 힘을 발휘합니다. 작은 문제의 답을 저장해 두면 전체 계산량이 크게 줄어듭니다.
초보자는 DP를 볼 때 "점화식"이라는 말에서 막히는 경우가 많습니다. 점화식은 어려운 공식이 아닙니다. 쉽게 말해 "현재 답을 이전 답들로 어떻게 만들 것인가"를 적은 규칙입니다.
피보나치에서는 다음 규칙이 점화식입니다.
dp[n] = dp[n - 1] + dp[n - 2]여기서 dp[n]은 "n번째 피보나치 수"를 저장하는 칸입니다. 즉, DP는 문제의 답을 저장할 칸을 만들고, 그 칸을 어떤 순서와 규칙으로 채울지 정하는 방식입니다.
메모이제이션: 필요할 때 계산하고 저장하기
첫 번째 방식은 메모이제이션입니다. 메모이제이션은 재귀 함수와 저장소를 함께 사용합니다. 함수가 호출되었을 때 이미 계산한 값이면 바로 반환하고, 아직 계산하지 않았다면 계산한 뒤 저장합니다.
피보나치 수열에 적용하면 다음과 같습니다.
memo = empty dictionary
function fib(n):
if n == 1 or n == 2:
return 1
if n in memo:
return memo[n]
memo[n] = fib(n - 1) + fib(n - 2)
return memo[n]흐름은 이렇습니다.
fib(n)을 호출한다.기본값이면 바로 답을 반환한다.
이미 저장된 값이면 저장소에서 꺼내 반환한다.
없으면 작은 문제를 계산한다.
계산한 값을 저장하고 반환한다.
메모이제이션은 "위에서 아래로 내려가는 방식"이라고 볼 수 있습니다. 큰 문제를 먼저 호출하고, 필요한 작은 문제를 재귀적으로 계산합니다. 그래서 보통 탑다운 방식이라고 부릅니다.
장점은 문제의 재귀 구조가 그대로 드러난다는 점입니다. "큰 문제를 작은 문제로 나눈다"는 생각을 코드로 옮기기 쉽습니다. 단, 재귀 호출을 사용하므로 호출 깊이가 너무 깊어지면 스택 문제가 생길 수 있습니다.
테이블 채우기: 작은 값부터 차례로 만들기
두 번째 방식은 테이블을 직접 채우는 방법입니다. 미리 배열을 만들고, 가장 작은 문제부터 차례대로 답을 채워 갑니다.
피보나치 수열은 다음처럼 계산할 수 있습니다.
function fib(n):
if n == 1 or n == 2:
return 1
dp = array of size n + 1
dp[1] = 1
dp[2] = 1
for i from 3 to n:
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]처음부터 dp[1], dp[2]를 알고 있어야 dp[3]을 만들 수 있습니다. 다시 dp[3]을 알아야 dp[4]를 만들 수 있습니다. 즉, 필요한 값이 먼저 계산되도록 순서를 정해야 합니다.
테이블 채우기는 "아래에서 위로 올라가는 방식"입니다. 작은 문제의 답을 먼저 구해 큰 문제로 확장하므로 바텀업 방식이라고도 합니다.
메모이제이션과 테이블 방식은 서로 다른 알고리즘이라기보다 같은 DP 생각을 구현하는 두 가지 방법입니다.
| 구분 | 메모이제이션 | 테이블 채우기 |
|---|---|---|
| 방향 | 큰 문제에서 필요한 작은 문제로 내려감 | 작은 문제부터 큰 문제로 올라감 |
| 구현 | 재귀 + 저장소 | 반복문 + 배열 |
| 장점 | 재귀 관계를 표현하기 쉬움 | 호출 스택 부담이 적음 |
| 주의점 | 종료 조건과 저장 확인이 필요함 | 계산 순서를 정확히 정해야 함 |
DP 문제를 푸는 네 가지 질문
DP 문제는 감으로 풀려고 하면 어렵습니다. 대신 다음 네 가지 질문으로 나누어 생각하면 훨씬 분명해집니다.
1. 상태는 무엇인가?
상태는 저장할 값의 의미입니다. dp[i]가 무엇을 뜻하는지 말로 정확히 정의해야 합니다.
예를 들어 피보나치에서는 다음과 같습니다.
dp[i] = i번째 피보나치 수계단 문제에서는 이렇게 정의할 수 있습니다.
dp[i] = i번째 계단에 도착하는 방법의 수상태 정의가 흐리면 점화식도 흔들립니다. dp[i]가 "i번째까지의 답"인지, "i번째에 도착한 답"인지, "i번째를 반드시 선택한 답"인지 구분해야 합니다.
2. 점화식은 무엇인가?
점화식은 현재 상태를 이전 상태로 계산하는 규칙입니다.
dp[i] = 이전에 구한 어떤 값들의 조합계단을 한 번에 1칸 또는 2칸 오를 수 있다면, i번째 계단에 도착하는 방법은 두 가지에서 옵니다.
i - 1번째 계단에서 1칸 오기i - 2번째 계단에서 2칸 오기
따라서 점화식은 다음과 같습니다.
dp[i] = dp[i - 1] + dp[i - 2]3. 초기값은 무엇인가?
DP는 이전 값을 이용해 현재 값을 만듭니다. 그러려면 출발점이 필요합니다. 이를 초기값이라고 합니다.
계단 오르기에서 1번째 계단에 가는 방법은 1가지입니다. 2번째 계단에 가는 방법은 1칸 + 1칸, 2칸으로 2가지입니다.
dp[1] = 1
dp[2] = 2초기값이 틀리면 뒤의 값이 모두 틀어집니다. DP에서 초기값은 작은 부분이지만 매우 중요합니다.
4. 계산 순서는 어떻게 되는가?
dp[i]를 계산하려면 dp[i - 1]과 dp[i - 2]가 먼저 있어야 합니다. 따라서 작은 i부터 큰 i로 계산해야 합니다.
for i from 3 to n:
dp[i] = dp[i - 1] + dp[i - 2]반대로 어떤 문제에서는 뒤에서 앞으로 계산해야 할 때도 있습니다. 중요한 것은 "현재 값을 만들기 위해 필요한 값이 이미 계산되어 있는가?"입니다.
예제 1: 계단 오르기
문제는 다음과 같습니다.
한 번에 1칸 또는 2칸 오를 수 있다. n번째 계단까지 가는 방법의 수를 구하라.
작은 예시를 봅시다.
n = 44번째 계단에 도착하는 마지막 움직임은 두 가지입니다.
3번째 계단에서 1칸 오른다.
2번째 계단에서 2칸 오른다.
따라서 4번째 계단에 가는 방법 수는 3번째 계단에 가는 방법 수와 2번째 계단에 가는 방법 수를 더한 값입니다.
dp[4] = dp[3] + dp[2]일반화하면 다음과 같습니다.
dp[i] = dp[i - 1] + dp[i - 2]의사코드는 다음과 같습니다.
function countWays(n):
if n == 1:
return 1
dp = array of size n + 1
dp[1] = 1
dp[2] = 2
for i from 3 to n:
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]이 문제는 1차원 DP입니다. dp[i]처럼 하나의 숫자 인덱스만으로 상태를 표현할 수 있기 때문입니다.
예제 2: 최소 비용으로 도착하기
이번에는 각 칸을 밟을 때 비용이 든다고 해 봅시다.
cost = [10, 15, 20]한 번에 1칸 또는 2칸 이동할 수 있고, 마지막 칸까지 가는 최소 비용을 구하고 싶습니다. 여기서는 시작점이 첫 칸 바로 앞에 있으며, 첫 이동으로 0번 칸이나 1번 칸에 올라설 수 있다고 가정하겠습니다. 그래서 0번 칸에 도착하는 비용은 cost[0], 1번 칸에 도착하는 비용은 cost[1]입니다.
이때 상태를 다음처럼 정의할 수 있습니다.
dp[i] = i번째 칸에 도착할 때 필요한 최소 비용i번째 칸에 도착하는 방법은 두 가지입니다.
i - 1번째 칸에서 온다.i - 2번째 칸에서 온다.
둘 중 비용이 더 작은 길을 선택하고, 현재 칸의 비용을 더합니다.
dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]의사코드는 다음과 같습니다.
function minCost(cost):
n = length(cost)
if n == 0:
return 0
if n == 1:
return cost[0]
dp = array of size n
dp[0] = cost[0]
dp[1] = cost[1]
for i from 2 to n - 1:
dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]
return dp[n - 1]계단 오르기와 구조가 비슷하지만 목표가 다릅니다. 앞의 문제는 "방법의 수"를 구해야 하므로 경우의 수를 더했습니다. 이번 문제는 "최소 비용"을 구해야 하므로 min을 사용합니다.
이처럼 DP에서는 상태의 의미에 따라 점화식의 연산이 달라집니다. 개수를 구하면 더하기가 자주 나오고, 최솟값을 구하면 min, 최댓값을 구하면 max가 자주 나옵니다.
예제 3: 간단한 배낭 문제
배낭 문제는 DP를 배울 때 자주 만나는 대표 문제입니다. 물건마다 무게와 가치가 있고, 배낭에 담을 수 있는 최대 무게가 정해져 있습니다. 이때 담을 수 있는 가치의 최댓값을 구합니다.
작은 예시를 봅시다.
물건 1: 무게 2, 가치 3
물건 2: 무게 3, 가치 4
물건 3: 무게 4, 가치 5
배낭 최대 무게: 5각 물건은 한 번만 선택할 수 있다고 하겠습니다. 어떤 물건은 담고, 어떤 물건은 담지 않습니다. 여기서는 상태를 두 가지 정보로 정의해야 합니다.
dp[i][w] = 앞에서 i개의 물건을 고려했고, 배낭 용량이 w일 때 얻을 수 있는 최대 가치dp[i][w]를 구할 때는 i번째 물건을 선택하지 않는 경우와 선택하는 경우를 비교합니다. 여기서 i는 "앞에서 i개의 물건을 고려했다"는 뜻이고, 실제 배열에서는 i번째 물건이 weights[i - 1], values[i - 1]에 들어 있다고 생각하면 됩니다.
선택하지 않으면 이전 값 그대로입니다.
dp[i][w] = dp[i - 1][w]선택하려면 현재 물건의 무게가 w보다 작거나 같아야 합니다. 선택할 수 있다면 남은 용량에서의 최댓값에 현재 물건의 가치를 더합니다.
dp[i - 1][w - weights[i - 1]] + values[i - 1]둘 중 더 큰 값을 고릅니다.
dp[i][w] = max(
dp[i - 1][w],
dp[i - 1][w - weights[i - 1]] + values[i - 1]
)의사코드는 다음과 같습니다.
function knapsack(weights, values, capacity):
n = length(weights)
dp = 2D array of size (n + 1) x (capacity + 1), filled with 0
for i from 1 to n:
weight = weights[i - 1]
value = values[i - 1]
for w from 0 to capacity:
dp[i][w] = dp[i - 1][w]
if weight <= w:
dp[i][w] = max(
dp[i][w],
dp[i - 1][w - weight] + value
)
return dp[n][capacity]이 문제는 2차원 DP입니다. 상태를 표현하려면 "몇 개의 물건까지 봤는가"와 "현재 배낭 용량이 얼마인가"라는 두 정보가 필요하기 때문입니다.
처음에는 2차원 배열이 복잡해 보일 수 있습니다. 하지만 각 칸의 의미를 명확히 잡으면 읽기 쉬워집니다.
dp[i][w]
= i개의 물건만 사용해서
= 용량 w 안에서 만들 수 있는
= 최대 가치상태를 문장으로 말할 수 있으면, 점화식도 그 문장에서 나옵니다.
메모리를 줄일 수 있는 경우
피보나치나 계단 오르기 문제는 사실 전체 배열을 모두 저장하지 않아도 됩니다. dp[i]를 계산할 때 필요한 값은 바로 앞의 두 값뿐입니다.
function countWays(n):
if n == 1:
return 1
prev2 = 1
prev1 = 2
for i from 3 to n:
current = prev1 + prev2
prev2 = prev1
prev1 = current
return prev1이렇게 하면 공간 복잡도를 O(n)에서 O(1)로 줄일 수 있습니다. 다만 처음 DP를 배울 때는 배열을 사용하는 편이 좋습니다. 각 상태가 눈에 보이기 때문입니다. 익숙해진 뒤에 필요한 값만 남기는 방식으로 개선하면 됩니다.
모든 DP가 이렇게 쉽게 줄어드는 것은 아닙니다. 현재 값을 계산할 때 어떤 이전 값들이 필요한지 확인한 뒤, 정말 더 이상 필요 없는 값만 지워야 합니다.
자주 틀리는 부분
첫째, 상태 정의 없이 코드부터 쓰는 실수입니다. DP는 저장하는 값의 의미가 가장 중요합니다. dp[i]가 무엇인지 한 문장으로 설명하지 못하면 코드를 쓰기 전에 멈춰야 합니다.
둘째, 초기값을 대충 정하는 실수입니다. dp[0]을 사용할지, dp[1]부터 시작할지에 따라 코드가 달라집니다. 작은 입력 n = 1, n = 2를 직접 넣어 보며 확인해야 합니다.
셋째, 계산 순서를 잘못 잡는 실수입니다. 현재 값을 계산하는 데 필요한 값이 아직 비어 있으면 올바른 결과가 나오지 않습니다. 반복문 방향은 점화식이 요구하는 순서에 맞춰야 합니다.
넷째, 모든 문제를 DP로 풀려고 하는 실수입니다. DP는 강력하지만 항상 필요한 것은 아닙니다. 중복되는 작은 문제가 없거나, 단순 정렬·해시·그리디로 충분한 문제라면 더 간단한 방법이 좋습니다.
다섯째, 인덱스를 혼동하는 실수입니다. 특히 배낭 문제처럼 i번째 물건과 배열의 i - 1번째 위치가 함께 나오면 헷갈리기 쉽습니다. 이런 경우 변수 이름을 분명히 하고, 작은 예시로 표를 직접 채워 보는 것이 좋습니다.
정리
동적 계획법은 어려운 기법을 외우는 것이 아닙니다. 반복되는 계산을 저장하고 재사용하는 생각입니다.
문제를 만나면 다음 네 가지 질문을 차례로 던져 보세요.
dp상태는 무엇을 의미하는가?현재 상태는 어떤 이전 상태들로 만들 수 있는가?
가장 작은 문제의 초기값은 무엇인가?
어떤 순서로 계산해야 필요한 값이 먼저 준비되는가?
이 네 가지가 정리되면 DP 문제는 훨씬 다루기 쉬워집니다. 처음에는 피보나치, 계단 오르기처럼 1차원 문제부터 시작하고, 이후 배낭 문제처럼 여러 조건을 함께 저장해야 하는 2차원 문제로 확장하면 됩니다.
이 노트는 보도·비평·교육·연구 목적으로 작성되었습니다. 저작권 문의가 있으시면 에서 알려주세요.