[알고리즘] 동적 프로그래밍 - 저장 가능 재귀 알고리즘

동적 프로그래밍

 

큰 문제의 답이 작은 문제의 답이 포함되어 있다.

 

분할 정복 알고리즘과 비슷하지만 속도가 빠르다,

다른점은 부분 문제의 정답을 저장한뒤 동일 문제에서 저장한 정답을 바로 계산해서 이용한다

 

피보나치 수의 정의

전 값과 전전 값을 더하는 피보나치 수

f(n) = f(n - 1) + f(n - 2)

f(1) = f(2) = 1

 

f(1) = 1

f(2) = 1

f(3) = f(1) + f(2) = 2

f(4) = f(2) + f(3) = 3

 

그냥 재귀 알고리즘 유사코드

fib(n) {
	if(n == 1 or n == 2)
		then return 1;
		else return (fib(n - 1) + fib(n - 2));
}

 

재귀 알고리즘 사용시, 중복 호출이 굉장히 많이 발생한다 -> 비효율

 

중복되는 호출의 결과를 저장해 놓았다가 다시 사용

 

재귀 호출 이용 동적 프로그래밍 유사코드

fib(n) {
	if(f[n] != 0) then return f[n];
    else {
    	if( n == 1 or n == 2)
        	then f[n] = 1;
            else f[n] = fib(n - 1) + fib(n - 2);
        return f[n];
    }
}

 

파이썬 코드

def fib_dynamic2(n, f):
    if f[n] != 0:
        return f[n]
    else:
        if n==1 or n==2:
            f[n] = 1
        else:
            f[n] = fib_dynamic2(n-1, f) + fib_dynamic2(n-2, f)
        return f[n]


if __name__ == '__main__':
    n = 7
    f = [0] * (n + 1)
    fib2 = fib_dynamic2(n, f)
    print(fib2)

 

 

 

for문 이용 동적 프로그래밍 유사코드

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

 

파이썬 코드

def fib_dynamic1(n,f):
    f[1] = 1
    f[2] = 1
    for i in range(3, n + 1):
        f[i] = f[i - 1] + f[i - 2]
    return f[n]

if __name__ == '__main__':
    n = 7
    f = [0] * (n + 1)
    fib1 = fib_dynamic1(n, f)
    print(fib1)