Dynamic Programing

dynamic Programming

=> 하나의 문제는 단 한번만 풀도록 하는 알고리즘

 

분할 정복 기법 => 동일한 문제를 다시 푼다. (단, 정렬은 반복x)

fibo => 동일한 문제를 다시 푸는 단점이 있다.

 

1번가정. 큰 문제를 작은 문제로 누눌 수 있다.

2번가정. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일.

 

dp를 사용하지 않은 피보나치 수열

def dp(n):
    if n ==1:
        return 1
    if n==2:
        return 1
    return dp(n-1)+dp(n-2)

print(dp(30))

dp를 사용한 피보나치 수열

d = [0]*100
def dp(n):
    if n ==1:
        return 1
    if n==2:
        return 1
    if(d[n]!=0):
        return d[n]
    d[n] = dp(n-1)+dp(n-2)
    return d[n]

print(dp(30))

자연수 n이 작을때는 상관이 없지만 큰 수가 들어가게 되면 첫 번째의 경우 시간이 오래걸리게 된다.