동적 계획법(Dynamic Programming, DP)

동적 계획법(Dynamic Programming, DP)

DP, 즉 다이나믹 프로그래밍(또는 동적 계획법)은 기본적인 아이디어로 

하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로

특정한 알고리즘이 아닌 하나의 문제해결 패러다임으로 볼 수 있다.

 

Richard Bellman이 1950년대에 사용한 단어로 이름은 그냥 멋있어 보여서 그렇게 지어졌으니 신경 쓰지 않아도 된다.
큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용한다. 그래서 혹자는 DP가 아닌 '기억하며 풀기'라고 부르기도 한다.

---

동적 계획법의 핵심 개념

---

(1) 겹치는 부분 문제 (Overlapping Subproblems)

• 큰 문제를 해결하는 과정에서 동일한 작은 문제들이 반복적으로 등장하는 구조를 의미한다.
• 예: 피보나치 수열의 단순 재귀 → 같은 값 계산이 수없이 반복된다.

(2) 최적 부분 구조 (Optimal Substructure)

• 큰 문제의 정답이 작은 문제들의 정답을 조합하여 만들어질 수 있는 성질이다.
• 예: fib(n) = fib(n-1) + fib(n-2)

 

일반적인 재귀(Naive Recursion) 방식 또한 DP와 매우 유사하다.

큰 차이점은 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복 되어 비효율적인 계산될 수 있다는 것이다.

 

예를 들어 피보나치 수열을 살펴보자. 피보나치 수열은 아래와 같다.
1,  1,  2,  3,  5,  8,  13,  21,  34,  55,  89,  144 ...

피보나치 수를 구하고 싶을 때 재귀로 함수를 구성하면 어떻게 될까? 단순하다. return f(n) = f(n-1) + f(n-2)

그런데 f(n-1), f(n-2)에서 각 함수를 1번씩 호출하면 동일한 값을 2번씩 구하게 되고 이로 인해 100번째 피보나치 수를 구하기 위해 호출되는 함수의 횟수는 기하급수 적으로 증가한다.(약 7해, #,###경 #,###조 ... 번 이상 함수 호출, 컴퓨터도 죽는다.)

왜냐하면, f(n-1)에서 한 번 구한 값을 f(n-2)에서 또 다시 같은 값을 구하는 과정을 반복하게 되기 때문이다. 아래의 그림처럼 반복되는 계산을 또 하게 된다.

 

그러나 한 번 구한 작은 문제의 결과 값을 저장해두고 재사용 한다면 어떨까?

앞에서 계산된 값을 다시 반복할 필요가 없이 약 200회 내에 계산이 가능해진다.

---

동적 계획법의 두 가지 접근 방식

---

(1) Top-Down 방식 (Memoization)

• 재귀를 사용하고, 필요할 때만 계산한 뒤 메모(memo)에 저장하여 중복 계산을 제거한다.

예시 코드:

function fib(n, memo = {}) {
if (n <= 1) return n;
if (memo[n]) return memo[n]; // 이미 계산했으면 재사용

memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
	return memo[n];
}

 

(2) Bottom-Up 방식 (Tabulation)

• 반복문을 사용하여 작은 문제부터 테이블(dp 배열)을 채워가는 방식이다.

예시 코드:

function fib(n) {

const dp = [0, 1];

for (let i = 2; i <= n; i++) {
	dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}

 

dp[0] = 0
dp[1] = 1
dp[2] = dp[1] + dp[0] = 1
dp[3] = dp[2] + dp[1] = 2
dp[4] = dp[3] + dp[2] = 3
dp[5] = dp[4] + dp[3] = 5
dp[6] = dp[5] + dp[4] = 8

 

 

• 재귀가 자연스러울 때 → Top-Down
• 명확한 DP 테이블이 보일 때 → Bottom-Up
• 성능 중요 + n이 크다 → Bottom-Up 권장 (스택 오버플로우 방지)

 

 

---

DP 문제인지 판단하는 법

---

1) 큰 문제를 작은 문제로 나눌 수 있는가?
2) 작은 문제들이 서로 겹치는가?
3) 큰 문제의 해답이 작은 문제의 해답을 조합해서 만들어지는가?

이 기준에 부합하면 DP 가능성을 고려할 수 있다.

---

대표적인 DP 문제 종류

---

• 피보나치 수열
• 계단 오르기
• 최대 부분합 (Kadane Algorithm)
• 동전 교환 문제
• 배낭 문제 (Knapsack)
• 최장 증가 부분 수열 (LIS)
• 최장 공통 부분 수열 (LCS)

---

정리

동적 계획법은

• 큰 문제를 반복되는 작은 문제로 쪼개고
• 계산된 결과를 저장하여 재사용함으로써
• 시간 복잡도를 크게 줄이는 알고리즘 기법이다.

DP 배열 정의 → 점화식 세우기 → 초기값 → 계산
이 프로세스를 익히면 대부분의 DP 문제를 해결할 수 있다.