DP(Dynamic Programming) 개념, 풀이법

 

* DP(Dynamic Programming)란 ?

: 큰 문제를 작은문제로 나누고 작은문제로 큰문제를 푸는 방법. 작은문제가 중복된다.

(vs 분할정복: 분할정복과 비슷한데 분할정복은 작은문제가 중복되지 않는다.)

 

 

* DP 의 특징

1) Overlapping Subproblem: 부분문제(작은문제)가 겹친다.

2) Optimal Substructure: 최적 부분 구조. 문제의 정답을 작은 문제의 정답에서 구할 수 있다.

정답의 작은 문제의 정답은 항상 같다.

 

 

* DP 알고리즘으로 풀 수 있는 대표적인 예

: 피보나치 수 !

0 1 1 2 3 5 8 13 21 34 55 89 ...

F0 = 0 F1 = 1 ... Fn = Fn-1 + Fn-2(n ≥ 2)

Fn 이라는 큰문제 값을 Fn-1 과 Fn-2 의 작은 합으로 구할 수 있다.

 

즉, N번째 피보나치 수를 구하는 문제는 N-1 번째 피보나치 수를 구하는 문제와 N-2 번째 피보나치 수를 구하는 문제로 나눌 수 있다.(Optimal Substructure)

 

N-1 번째 피보나치 수는 어떠할 까?

N-2 번째 피보나치 수와 N-3 번째 피보나치 수의 합으로 구할 수 있다.

 

즉, N번째 피보나치 수를 구할 때도 N-1 번째 피보나치 수를 구할 때도 N-2 번째 피보나치 수를 중복 사용한다.

작은문제가 겹친다.(Overlapping Subproblem)

int fibonacci(int n) {
    if(n <= 1){
         return n; 
    } else { 
    	return fibonacci(n-1) + fibonacci(n-2); 
    } 
}

Top-down 방식인 재귀함수로 푼 DP.

n 부터 1까지 큰 문제를 작은문제로 쪼개며 풀어나간다.

 

 

* DP 특징에 따른 풀이 방법

정답이 구할 때마다 같기 때문에, 정답을 한 번 구하면 그 정답을 어딘가에(ex. 배열) 메모해놓는다. (Memoization)

문제 시 삭제

F(5)를 처음엔 다 왼쪽처럼 구하지만, 다음에 F(3)을 구할 때는 미리 저장해 놓은 F(3) 값을 바로 반환한다. (오른쪽)

int memo[100];
int fibonacci(int n) { 
    if(n <= 1) { 
    	return n; 
    } else {
    	if(memo[n] > 0) {
             return memo[n];
        }
        memo[n] = fibonacci(n-1) + fibonacci(n-2);
        return memo[n]; 
    } 
}

Top-down 방식에 메모이제이션을 적용한 풀이법.

* 시간복잡도: 모든 문제를 딱 한번은 풀기 때문에 O(N)

 

 

* DP를 구현하는 방법

1. Top-down: 재귀. 큰 문제를 쪼개면서 작은문제로 내려가는 것.

2. Bottom-up: for문. 작은 문제를 점점 합치면서 큰 문제를 푸는 것.

int d[100];

int fibonacci(int n){
     d[0] = 0;
     d[1] = 1;
     for(int i = 2; i<=n; i++){ 
          d[i] = d[i-1] + d[i-2]; 
     } 
     return d[n];
}

Bottom-up 방식인 for문으로 푼 DP. Top-down 은 위 코드 참고.

0 부터 n 까지 작은 문제로 큰 문제를 풀어나간다.

 

둘다 상관없는데 재귀가 자신있으면 Top-down, for문이 편하면 Bottom-up 으로 풀기.

Top-down만이나 Bottom-up으로만 풀 수 있는 문제도 있긴 한데, 그건 매우 어려운 문제들이라 일단은 DP 문제에 익숙해지는데 집중하기.

 

 

* 점화식 세우는 법 !

: 피보나치 수를 구했던 것 처럼 점화식이 구하는 작업이 필요하다.

: 문제를 어떻게 작게 만들 것인가를 찾자.

 

---

 

* 예시문항

https://i-believe-in-me.tistory.com/414

[BOJ][C++] 1463번 1로 만들기(feat. DP)