동적계획법/다이나믹 프로그래밍(Dynamic Programming)

동적 계획법: 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법

*이미 했던 계산은 재활용하여 사용하기

 

 

-Top-down 형식

재귀로 구현, 큰 문제를 작은 문제로 쪼개나가면서 해결(memoization 활용)

 

아래 코드는 피보나치를 구하는 함수를 top down 형식으로 구현한 것이다. 

int fib(int n){
	if (n==1 || n==2)
    return 1;
    else if(f[n] > -1) //배열이 초기화 된 경우=이미 계산을 한 경우
    	return f[n];
    else
   		return f[n] = fib(n-2) + fib(n-1);
}

Top down 형식은 재귀 오버헤드가 발생할 수 있다.

 

 

 

-Bottom up 형식

반복문으로 구현, 작은 문제부터 구해서 큰 문제를 해결

 

아래 코드는 피보나치를 구하는 함수를 bottom up 방식으로 구한 것이다. 

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

Bottom up 방식은 재귀를 array로 풀어낸 것이다.