[알고리즘] 동적 계획법(Dynamic Programming)

1. 동적 계획법(Dynamic Programming, DP)이란?

---

동적 계획법(Dynamic Programming, DP)은 큰 문제를 작은 문제로 나눠서 푸는 알고리즘 설계 기법이다.

분할 정복 알고리즘과 차이는 메모이제이션의 필요여부다. 

분할 정복 알고리즘은 계산된 소문제의 출력값을 저장하지 않는다. (1회용)

동적 계획법은 계산된 소문제의 출력값을 저장해서 다음 계산때 사용한다. (재활용)

 

동적 계획법을 적용시킬 수 있는 예시는 다음과 같다.

• f(a,b) = f(a-1,b) + f(a,b-1) (a,b >= 1 )
• f(0,0) = 1, 임의의 자연수 n에 대해 f(n,0) = f(0,n) = 1

[그림 1] 중복되는 연산

위 그림에서 초록색으로 칠해논 부분이 문제를 작은 문제로 분할하는 과정에서 중복되는 문제다.

그림의 패턴만 봐도 a, b의 값이 커지면 커질수록 중복되는 작은 문제들이 기하급수적으로 늘어날 것임을 짐작할 수 있다.

2. 문제로 살펴보는 동적 계획법

---

동적 계획법을 설명하기 위한 대표적인 문제가 피보나치 수열이다. 피보나치 수열은 아래와 같은 조건을 가진다.

f(1) = 1
f(2) = 1
f(n) = f(n-1) + f(n-2) // n > 2

 

위의 조건을 살펴보면 매 연산마다 중복되는 작은 문제들이 생겨난다. 피보나치 수열을 동적 계획법으로 접근해보자.

동적 계획법은 2가지 방법으로 접근할 수 있다.

1. Top-down : 큰 문제부터 시작해 작은 문제로 분할해가며 푸는 방법
2. Botton-up : 작은 문제를 풀어가며, 점점 쌓아가 큰 문제를 푸는 방법

코드로 살펴보자

Top-down 방식

// Top-down
int memo[100] = { 0, }; // 메모이제이션 
 
int fibonacci(int n) {
	if (n == 1 || n == 2) return 1;
    
    if (memo[n] != 0) return memo[n]; // 메모이제이션에 이전에 계산해논 값이 있다면 재활용 !!
    memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
    
    return memo[n];
}

Bottom-up 방식

// Bottom-up
int memo[101] = { 0, }; // 메모이제이션
 
int fibonacci(int n) {
	if (n == 1 || n == 2) return 1;
    
    memo[1] = 1; // 해석을 직관적으로 하기 위해 0번이 아닌 1번부터 시작
    memo[2] = 1;
    for (int i = 3; i <= n; i++) {
        memo[i] = memo[i - 1] + memo[i - 2];
    }
    
    return memo[n];
}

 

지금까지 DP 문제를 풀 때 항상 Bottom-up 방법으로 접근했었는데 Top-down 방법으로 접근하는 것도 연습해야겠다. 어쨋든 동적 계획법을 이용해 시간 복잡도를 O(n)으로 만들었다. 슬라이딩 윈도우 기법을 쓰면 공간 복잡도를 O(1)로 만들 수 있다는데, 이건 차차 공부해봐야지

3. 참고자료

---

[1] https://namu.wiki/동적 계획법