[알고리즘-JAVA] 다이나믹 프로그래밍

다이나믹 프로그래밍 : 큰 문제를 작은 문제로 나눠서 푸는 방법이다.

 

다이나믹 프로그래밍의 2가지 속성

1. Overlapping Subproblem : 겹치는 부분문제

2. Optimal SubStructure : 문제의 정답을 작은 문제의 정답에서 구할 수 있을 때

 

Overlapping Subproblem

ex) 피보나치 수!

F0 = 0

F1 = 1

Fn = Fn-1 + Fn-2 (n>=2)

Fn-1 = Fn-2 + Fn-3

Fn-2 = Fn-3 + Fn-4

 

Optimal Substructure

Optimal Substructure를 만족한다면, 문제의 크기와 관계없이 어떤 한 문제의 정답은 항상 같다.

F10에서의 F4나

F11에서의 F4나 항상 같음.

 

따라서 ! 정답을 한번 구했으면 정답을 어디에다가 메모해놔서 한번만 계산하고자 한다.

=> Memorization!

컴퓨터에서는 메모지가 없기 때문에, 배열에다가 저장해둔다.

 

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

이런식으로 메모를 쓰는 코드를 만들어서 저장시킨다.

 

이제는 메모가 된 값을 확인하고, 메모가 있다면

그 메모를 불러와서 사용하는 코드를 작성한다.

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

 

다이나믹을 푸는 두가지 방법

1. Top-down : 큰 문제에서 세세한 문제로

2. Bottom-up : 작은 문제부터 큰 문제로

 

Top-down

1. 문제를 작은문제로 나눈다

2. 작은문제를 푼다

3. 작은 문제를 풀었으니, 이제 문제를 푼다.

 

ex) 피보나치

 1) 문제를 풀어야 한다.

fibonacci(n)

 2) 문제를 작은 문제로 나눈다.

fibonacci(n-1)과 fibonacci(n-2)로 문제를 나눈다.

 3.) 작은 문제를 푼다.

fibonacci(n-1)과 fibonacci(n-2)로 호출해 문제를 푼다.

 4 ) 작은 문제를 풀었으니, 이제 문제를 푼다.

fibonacci(n-1)과 fibonacci(n-2)의 값을 더해 문제를 푼다.

 

탑다운의 단점 : 시간복잡도 계산이 어렵다.

피보나치에서는...?

채워야하는 칸의 수 : N개 * 1칸을 채우는 복잡도 : O(1) 

 

Bottom-up

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

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

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

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

 

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

i =2 부터! 계속해서 증가해서 올라간다.

 

문제풀이 전략!

d[i] = i번째 에 뭐가 들어갈지 정의해준다.

이제 이러한 d[i]를 어떻게 구할지 생각한다

d[i] = d[i-1] + d[i-2];