DP(Dynamic Programming)?

▶ DP(Dynamic Programming)?

: 큰 문제를 작은 문제로 나눠서 푸는 알고리즘.

: 분할정복 알고리즘과 비슷. 분할정복은 작은 문제가 한 번씩 나오지만, DP는 작은 문제가 여러번 반복되어 나온다는 차이가 있다.

 

[DP의 특징 2가지]

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

2) Optimal Substructure: 최적 부분 구조를 가진다.

 

* Overlapping Subproblem?

Overlapping Subproblem의 대표적인 예로 피보나치 수를 구하는 방법을 들어보자.

 

피보나치 수는 다음과 같이 표현할 수 있다.

 

F0 = 0

F1 = 1

Fn = Fn-1 + Fn-2(n>=2)        => 0, 1, 1, 2, 3, 5, 8, 13, ...

 

위의 조건을 이해했다면 아래 문제를 생각해보자.

 

Q. N번째 피보나치 수를 구하라.

이 문제는 작은 문제 2개로 나타낼 수 있다.

즉, N-1번째 피보나치 수를 구하는 문제, N-2번째 피보나치 수를 구하는 문제로 나타낼 수 있다.

 

Q. N-1번째 피보나치 수를 구하라.

이 문제 역시, 작은 문제 2개로 나타낼 수 있는데,

N-2번째 피보나치 수를 구하는 문제와 N-3번째 피보나치 수를 구하는 문제로 나타낼 수 있다.

 

Q. N-2번째 피보나치 수를 구하라.

이 문제의 작은 문제는 N-3 번째 피보나치 수를 구하는 문제, N-4번째 피보나치 수를 구하는 문제일 것이다.

 

위 문제들을 보면 작은문제들인 N-2번째 피보나치 수를 구하는 문제와 N-3번째 피보나치 수를 구하는 문제가 반복된다.

 

이렇게 Overlapping Subproblem는 큰 문제와 작은 문제를 같은 방법으로 풀 수 있고

문제를 작은 문제로 쪼갤 수 있다는 특징을 갖는다. == 문제가 겹친다.

 

 

* Optimal Substructure?

: 문제의 정답을 작은 문제의 정답에서 구할 수 있는 구조

 

Optimal Substructure의 예시)

서울에서 부산을 가장 빠른 길이 대전과 대구를 순서대로 거쳐야 한다면(서울->대전->대구->부산)

대전에서 부산을 가는 가장 빠른 길은 대구를 거쳐야 한다.(대전->대구->부산)

 

위에서 본 피보나치 수열도 작은 문제의 정답을 합하는 것으로 구할 수 있다.(Fn = Fn-1 + Fn-2)

 

Optimal Substructure을 만족한다면, 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정하다.

 

예를 들어, 

10번째 피보나치 수를 구하면서 구한 4번째 피보나치 수,

9번째 피보나치 수를 구하면서 구한 4번째 피보나치 수,

8번째 피보나치 수를 구하면서 구한 4번째 피보나치 수,

...

4번째 피보나치 수를 구하면서 구한 4번째 피보나치 수까지

4번째 피보나치 수는 항상 같을 수 밖에 없다.

---

▶ 다이나믹 프로그래밍 문제를 정리해보자면,

 

1) 다이나믹 프로그래밍에서 각 문제는 한 번만 풀어야 한다.

2) Optimal Substructure를 만족하기 때문에, 같은 문제는 구할 때마다 정답이 같다.

3) 따라서 정답을 한 번 구했으면, 정답을 어딘가에 메모해놓는다.

4) 이런 메모하는 것을 코드의 구현에서는 배열에 저장하는 것으로 할 수 있다.

5) 메모를 한다고 해서 영어로 Memorization이라고 한다.

 

위에서 설명한 피보나치 수를 다이나믹 알고리즘으로 풀어보자.

 

그냥 재귀로 풀었을 때,

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

모든 경우의 수를 구하므로, f(3), f(2), f(1), f(0)의 경우가 겹친다.

memorization을 이용한 DP로 풀었을 때,

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];
    }
}

겹치는 경우를 memo[100] 배열에 저장하고 있으므로, 더이상 탐색하지 않는다. 그림에서 보여지듯이 시간복잡도가 매우 줄어들 것이다.

여러번 풀 때는 저장된 값을 불러오기만 하면 된다.

각각이 O(1)의 시간복잡도를 가지므로 전체는 O(n)의 시간복잡도를 갖는다.

---

▶ 다이나믹을 푸는 2가지 방법

1) Top-down: 재귀함수 이용

: 큰 문제를 점점 쪼개면서 작은문제로 푸는 것

2) Bottom-up: for문 이용

: 작은문제가 점점 합쳐지면서 원래 문제를 풀게 하는 것

 

Top-down은 위에서 봤으니 Bottom-up 방법을 더 자세히 살펴보자.

 

* Bottom-up

1) 문제를 크기가 작은 문제부터 차례로 푼다.

2) 문제의 크기를 조금씩 크게 만들면서 문제를 점점 푼다.

3) 작은 문제를 풀면서 왔기 때문에, 큰 문제는 항상 풀 수 있다.

4) 그러다보면 언젠가 풀어야하는 문제를 풀 수 있다.

 

위에서 Top-down(재귀)으로 푼 걸 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];
 }

---

▶ DP 문제풀이전략

: 점화식 세우는 것이 관건이다.

 

피보나치 수열에서 봤드시 DP문제는 Fn = Fn-1 + Fn-2 같은 점화식을 세울 수 있어야 한다.

그럼 점화식은 어떻게 구하는 것일까?

 

먼저, 점화식의 정의를 세워야 한다.

 

1. 점화식의 정의를 글로 적어보고, 식으로 대충 표현해본다.

: 점화식을 통해 N번째 피보나치 수를 구해야 한다.

: D[N] = 

 

2. 문제를 작은문제로 나눠야 한다.

작은문제도 어떻게 문제를 작게 만들지 글로 적어보고 식으로 표현한다.

: N번째 피보나치 수는 N-1번째 피보나치 수 + N-2번째 피보나치 수이다.

: D[N] = D[N-1] + D[N-2] ← 완성

 

잘 안와닿으므로 문제를 풀면서 익혀보자...

 

 

출처: BOJ 온라인 강의(알고리즘 기초)