다이나믹 프로그래밍 (Dynamic Programming)

동빈나 유튜브 참고

www.youtube.com/watch?v=FmXZG7D8nS4

 

다이나믹 프로그래밍 = 하나의 문제는 단 한 번만 풀도록 하는 알고리즘

 

다이나믹 프로그래밍을 사용할 수 있는 조건!

1. 큰 문제를 작은 문제로 나눌 수 있다. (분할-정복의 개념)
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. (핵심!!)

 

예시 : 피보나치 수열 f(n) = f(n-1) + f(n+1)

 

이미 계산한 결과를 배열에 저장하는 메모이제이션(Memoization)이 분할-정복 기법과 다른 점이다.

 

어떤 조건일 때 종료되는지도 알아둬야 함!

#include <stdio.h>

int dp(int x){
	//언제 끝나는지 명시해주는 역할
	if(x==1) return 1;
    if(x==2) return 1;
    return dp(x-1) + dp(x-2);
}

int main(void){
	printf("%d", dp(10));
}

 

피보나치(N)의 경우

N = N-1 + N-2;

높이는 대충 N. 그리고 단계마다 두배씩 증가함

==> 2^N 번 연산해야 함 (시간복잡도 : 2^n)

따라서 이를 개선해야 함~

 

한번 구한 값은 그 값을 저장해서 그 값을 요구하면 반환하기만 하면 됨 (Memoization)

#include <stdio.h>

int d[100];

int dp(int x){
	//언제 끝나는지 명시해주는 역할
	if(x==1) return 1;
    if(x==2) return 1;
    
    //0이 아니라는 것은 값을 저장해뒀다는 뜻
	if(d[x]!=0) return d[x];
	
    return d[x] = dp(x-1) + dp(x-2);
}

int main(void){
	printf("%d", dp(10));
}

시간 복잡도 : O(n)

이미 구했던 값으로 연산하기 때문

N → N-1 → N-2 → ...