DP( Dynamic Programing)

동적프로그래밍 DP

큰 문제를 한번에 해결하기 힘들 때 작은 여러 개의 문제로 나누어서 푸는 기법으로

작은 문제들을 매번 재계산 하지 않고 값을 저장해두었다가 재사용하는 기법이다.

 

 

조건 

1.  Problem이 더 작은 Subproblem으로 쪼개질 수 있어야 한다.
2.  Subproblem 의 솔루션으로 더 큰 Subproblem의 솔루션을 구할 수 있어야 한다.
3.  Subproblem이 겹칠때(memorization을 통해 필요한 계산수를 줄일 수 있다)
   

   

   출처 : https://www.youtube.com/watch?v=eJC2oetXaNk 

백준 피보나치 수열 2

#bottom up방식
fib_array = [0, 1]

def fib_dp(n):
    if n==0:
        return 0
    elif n==1:
        return 1
    for i in range(2, n+1):
        num =  fib_array[i-2]+fib_array[i-1]
        fib_array.append(num)
    
    return print(fib_array[n])

n = int(input())
fib_dp(n)


# reculsive DP 
# 큰 숫자가 들어갈경우 recursion depth exceeded 에러가 뜬다. 
#n=10000이라면 재귀적으로 call stack의 리밋을 초과한다. 
# 탑다운방식
"""  
def fib_recur_dp(n):
    if n<len(fib_array):
        return fib_array[n]
    else:
        fib = fib_recur_dp(n-1) + fib_recur_dp(n-2)
        fib_array.append(fib)
        return print(fib)

 """

# naive한 방식 직관적이나 느리다.

""" 
def fib_naive(n):
    if n == 0:
        return 0
    elif n==1:
        return 1
    else :
        fib = fib_naive(n-1) + fib_naive(n-2)
        return fib
 """