동적계획법, dynamic programming 기본

동적계획법이란 하나의 문제를 한 번만 풀도록 하는 알고리즘으로. 

하나의 복잡한 문제를 여러 서브문제로 나누어서

그 결과값을 저장함으로써 하나의 서브문제는 한 번만 풀도록 하여 같은 계산을 줄이는 방법이다. 

 

그러면 동적계획법으로 풀어야한다는 것을 어떻게 판단할까?

동적계획법에는 두드러지는 두 가지 특징이 있는데 먼저

Overlapping Subproblems와 Optimal Substructure라는 특징이 있다. 

 

아래 두 글을 번역하였다.

Overlapping Subproblems Property in Dynamic Programming | DP-1 - GeeksforGeeks

 

Optimal Substructure Property in Dynamic Programming | DP-2 - GeeksforGeeks

 

1) Overlapping Subproblems:

분할정복법처럼 DP는 여러 서브 문제의 결과를 합친다.

그러나 주요한 차이점은 서브 문제의 결과값을 계속 사용하는지의 여부이다.

DP는 똑같은 서브 문제의 결과값을 계속해서 재사용해야할 때 사용한다. 달리 말하면 겹치는(overlapping), 혹은 공통된 서브 문제가 없는 문제인 경우에는 DP가 효율적이지 않다. 값을 저장해야할 필요가 없기 때문이다. 

예를 들어 이진트리 같은 경우에는 분할정복법으로 풀 수 있는데 이때 이진트리는 공통된 서브 문제가 없고, 각기 다른 서브 문제들의 합이기 때문에 DP로 풀 필요가 없는 것이다. 

https://www.geeksforgeeks.org/binary-search/

 그러나 피보나치 수열의 경우에는 상황이 달라진다. 이때는 서브문제들을 계속해서 계산해나가기 때문이다. 

https://afteracademy.com/blog/optimal-substructure-and-overlapping-subproblems

                                                           

피보나치는 앞 전 두 숫자의 합이 해당 수가 되는데

예를 들어 5번째 수를 구하기 위해서는 4번째, 3번째 수를 알아야 하고

4번째 수를 알기 위해서는 3번째 2번째를,

3번째 수를 알기 위해서는 2번째 1번째 수를 알아야 한다.

계속해서 subproblem의 문제가 겹치고 있다는 것을 확인할 수 있다.

이 경우에는 DP로 푸는 것이 적절하다. 

 

2) Optimal Substructure: 

subproblem의 최적해가 해당 problem의 최적해라면 그 문제는 Optimal substructure을 가지고 있다고 말할 수 있다.

 The Shortest Path problem을 예로 들면 

노드 x가 u와 v 사이의 가장 짧은 거리 위에 있다면

u와 v간의 가장 짧은 거리는 u와 x 그리고 x와 v사이의 거리의 합이다.

이때 이 문제는 Optimal Substructue을 가지고 있다고 말할 수 있다. 

 

그러나 the Longest Path problem은 Optimal SUbstructure의 특성을 가지지 못한다.

사이클이 없는 path에서 q에서 t까지 가는 가장 긴 방법은 r을 거치거나  s를 거치는 방법이다.

그러나 q->r->t는 q->r의 가장 긴 거리과 r->t의 가장 긴 거리의 합이 아니다.

q->r의 가장 긴 거리는 q->s->t->r이고 

r->t의 가장 긴 거리는 r->q->s->t이기 때문이다.

 

문제 해결 방법

문제는 Topdown 방식과 bottom up 방식으로 풀 수 있다.

 

1)  topdown 

Topdown 방식은 재귀를 사용한다는 특징이 있다. 개인적으로 topdown 방식을 더 까다롭게 느꼈다.

먼저 subproblem의 결과값을 저장할 배열을 생성하고 배열에서 절대 나올 수 없는 값들로 초기화한다.

이 배열이 후에 정의되었는가의 유무를 이 초기값을 통해 판단할 수 있기 때문이다.  

 

top down이라는 이름에 걸맞게 5번째 값을 구하고 싶으면 5번째 값부터 계산을 시작한다. 

해당값이 정의되지 않았으면 재귀방식으로 아래로 계속 내려가다가 정의되면 stack을 깨고 올라온다. 

/* Java program for Memoized version */
public class Fibonacci 
{ 
final int MAX = 100; 
final int NIL = -1; 

int lookup[] = new int[MAX]; 

/* Function to initialize NIL values in lookup table */
void _initialize() 
{ 
	for (int i = 0; i < MAX; i++) 
		lookup[i] = NIL; 
} 

/* function for nth Fibonacci number */
int fib(int n) 
{ 
	if (lookup[n] == NIL) 
	{ 
	if (n <= 1) 
		lookup[n] = n; 
	else
		lookup[n] = fib(n-1) + fib(n-2); 
	} 
	return lookup[n]; 
} 

public static void main(String[] args) 
{ 
	Fibonacci f = new Fibonacci(); 
	int n = 40; 
	f._initialize(); 
	System.out.println("Fibonacci number is" + " " + f.fib(n)); 
} 

} 
// This Code is Contributed by Saket Kumar 

 

2) bottom up

/* Java program for Tabulated version */
public class Fibonacci 
{ 
int fib(int n) 
{ 
	int f[] = new int[n+1]; 
	f[0] = 0; 
	f[1] = 1; 
	for (int i = 2; i <= n; i++) 
		f[i] = f[i-1] + f[i-2]; 
	return f[n]; 
} 

public static void main(String[] args) 
{ 
	Fibonacci f = new Fibonacci(); 
	int n = 9; 
	System.out.println("Fibonacci number is" + " " + f.fib(n)); 
} 

} 
// This Code is Contributed by Saket Kumar 

bottom up은 5번째 값을 구하고 싶으면 첫번째 값부터 계산해서 올라간다.