동적계획법(Dynamic Programming)

DP: 복잡한 문제를 여러문제로 나누고 문제를 해결한 값은 기억했다가 다시 써야할일이 있으면 재사용

      => 문제쪼개기 + 메모이제이션

 

1. DP의 구현 방법 2가지, 차이점
2. DP가 사용하는 핵심 기법의 이름은 무엇이고 그것이 어떤 기법인지 설명

1. 탑다운, 바텀업 / 탑다운: 코드 이해, 작성 쉬움 -) 함수 호출 비용 大, 바텀업보다 느리고 메모리 大

                         바텀업: 빠르고 메모리 小 -) 코드 작성이 조금 어려움

2. 메모이제이션 / 계산한 소문제의 값을 기록했다가, 똑같은 소문제를 계산해야되는 경우 다시 계산하지 않고 기록한 값을 그대로 활용

 

ex) 피보나치 수열에서 recurcive함수로 구현했을 때 계산 중복이 多

    1)전에 계산한 값 기록했다가 필요하면 다시 계산안하고 그 값 사용(memoization)

         ->top-down(큰문제->작은문제)방식 , recursion으로 푼다.

//재귀함수로 구현했을 때 : 시간복잡도 대충 O(2^n)
#include<iostream>
using namespace std;
long long pibo(long long val){
	if (val<=1) return 1;
    else return pibo(val-1) + pibo(val-2);
}

//메모이제이션으로 구현했을 때 : 시간복잡도 O(n)
#include<iostream>
using namespace std;
long long r[91]; //부분문제들의 정보를 저장할 배열 생성
long long pibo(long long val){
	if (val<=1) return 1;
    else if(r[val]) return r[val];
    else return pibo(val-1) + pibo(val-2);
}

//또 다른 코드 예시 (인프런 강의) f배열을 우선 전부 -1로 초기화
int fib(int n){
	if(n==1||n==2) return 1;
	else if (f[n]>-1) return f[n];
    else{
    	f[n]= fib(n-2) + fib(n-1);
        return f[n];
    }
}

//OR

#include<iostream>
using namespace std;
using ll= long long;
ll fib[100],n;
ll fibo(int n){
	if(fib[n] != -1) return fib[n];
    if(n < 2) return fib[n] = n;
    return fib[n] = fibo(n-1) + fibo(n-2);
}
int main(){
	for(int i=0;i<100;i++) fib[i] = -1;
    cin >> n;
    cout << fibo(n);
 
 //초기화는 어떻게 하는가? 반복문? 아니면 fill 함수나 memset 함수?

    2) bottom-up(작은문제->큰문제)방식으로 계산 f[1]부터~f[n]까지 순서대로 계산하여 저장, 반복문으로 구현

    (bottom-up방식은 이미 계산되어있는 값을 가져와서 계산하는 것)

#include<iostream>
using namespace std;
typedef long long ll;
ll arr[91];
int main(){
	int n; cin>>n;
    
    arr[0]=0;
    arr[1]=1;
    for(int i=2; i<=n; i++)
    	arr[i]=arr[i-1]+arr[i-2];
    
    cout<<arr[n];
}

//OR(인프런 강의)

int fib(int n)
{
	f[1] = f[2] =1;
    for( int i=3; i<=n; i++)
    	f[n]= f[n-1] + f[n-2];
    return f[n];
}

  ※memoization vs. DP

  memoization - top-down방식, 실제로 필요한 subproblem만 푼다(계산 결과 저장하여 다른 계산 시 필요할 때 사용)

  DP- bottom-up방식, recursion에 수반되는 overhead X

 

 

ex) 점화식

    1) top-down

 

//boj #13699
#include<iostream>
#define N 35
using namespace std;
typedef long long ll;
ll arr[N+1];

ll dp(int index){
	if(arr[index]) return arr[index];
    for(int i=0; i<index; i++)
    	arr[index]+=dp(i)*dp(index-i-1);
    return arr[index];
}

    2) bottom-up

//boj #13699
#include<iostream>
#define N 35
using namespace std;
typedef long long ll;
ll arr[N+1];

int main(){
	int n; cin>>n;
    arr[0]=1;
    for(int i=1; i<=n; i++){
    	for(int j=0;j<i;j++)
    		arr[i]+=arr[j]*arr[i-j-1];
     }
    cout << arr[n];
}