[Algorithm] DP(Dynamic Programming), 동적 계획법 (Bottom-Up, Top-Down)

#. 동적 계획법? 

ㅇ 동적계획법 = 다이나믹 프로그래밍(Dynamic Programming), DP

- 벨만-포드 알고리즘을 개발한 벨만이 만들어낸 알고리즘

- 알고리즘 이름을 어떻게 지으면 기억에 잘 남고, 간지(?)가 날지 생각하다가 다이나믹이라는 단어가 좋아서 이렇게 되었다는..

ㅇ 특징

- 다음 상태를 구하기 위해, 이전 상태를 저장하고, 사용(Memoization)

- 무엇을 어떻게 저장할지 정하는 것이 중요

- 많이 풀어보고, 생각 과정을 연습하는 것이 중요..

ㅇ 적용 순서

1. 상태 정의

- dp배열을 만들었을 때, index값이 의미하는 상태

- 문제의 초기상태를 정의(직관적인 작은 문제의 해)

2. 점화식 구하기

- 다음 상태를 나타내기 위한 표현식

3. 시간복잡도 계산

4. 구현

ㅇ 적용 방법

1. Top-Down : 재귀함수 사용

- Python에서는 시간복잡도 문제 발생 가능성이 있음

2. Bottom-Up : 반복문 사용

#. Solve

네트워크 선을 1m, 2m의 길이를 갖는 선으로 자르려고 합니다

예를 들어 4m의 네트워크 선이 주어진다면

1) 1m+1m+1m+1m 

2) 2m+1m+1m 

3) 1m+2m+1m 

4) 1m+1m+2m 

5) 2m+2m 

...

네트워크 선의 길이가 Nm라면 자를 수 있는 방법의 수

우선

Bottom-Up

Top-Down

을 참고해도 좋을 듯 하다.

DP(Dynamic Programming), 동적 계획법은 원래 Bottom-Up 방식이지만, Top-Down 방식도 사용할 수도 있다.

Top-Down 방식은 재귀함수를 이용하여 순환하는 방식으로 동작하므로 동적계획법이라고 부르지 않는 사람도 있다고 한다.

하지만, 재귀를 사용하면서도 memoization하여 table에 기록한 후 재사용하기때문에 Top-Down방식도 동적계획법이라고 보기도 하고,

재귀가 뻣어나가는 방식도 점화식과 비슷하므로 넓은 의미에서 동적계획법이라고 부르기도 한다고 한다.

정석은 그래도 작은 문제부터 큰 문제로 확장하면서 문제를 해결하는 방식인 Bottom-Up 방식이 진정한 동적계획법이라고 할 수 있다.

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

#include <cstdio>   ////////////////////////////////// // Botton-Up /////////////////////////////////   int dp[50] = { 0, 1, 2, };   int main(void) {     int n, i;     scanf("%d", &n);       for (i = 3; i <= n; i++) {         dp[i] = dp[i - 2] + dp[i - 1];     }       printf("%d\n", dp[n]);       return 0; }     ////////////////////////////////// // Top-Down //////////////////////////////////   int dp[50];   int DFS(int n)  {     if (dp[n]) return dp[n];     if (n == 1 || n == 2) return n;       return dp[n] = DFS(n - 2) + DFS(n - 1); }   int main(void) {     int n;       scanf("%d", &n);       printf("%d\n", DFS(n));       return 0; } Colored by Color Scripter

cs

// Bottom-Up

line 7) 직관적으로 풀 수 있는 작은 문제는 풀어놓는다.

line 14) 점화식을 적용하여 반복문을 돌리는 과정이다.

     작은 문제에서 구한 해를 이용하여 큰 문제를 풀기 때문에 시간복잡도를 줄일 수 있다.

// Top-Down

line 20~36) 재귀를 활용하여 동적계획법을 적용한다.

line 32) 이미 작은 문제에서 구한 해가 테이블에 저장되어있다면 그래도 사용한다.

line 33) n이 1 또는 2일 경우는 그 수를 그래도 반환

line 35) 해를 return해주면서 해를 table에 저장해준다.

(작은 문제의 해를 재사용하기 위함)

#. Result

  - Input --------------------------------------------------------

7

------------------------------------------------------------------

  - Output --------------------------------------------------------

21

------------------------------------------------------------------