[Algorithm] DP programming

1. 피보나치 수열을 재귀 함수로 구현

import sys
import time


def fibo_recur(x):
    if x <= 1:
        return x
    return fibo_recur(x-1)+fibo_recur(x-2)
    
 
 if __name__ == "__main__":
    print(f"start: {time.time()}")
    start = time.time()
    print(fibo_recur(40))
    end = time.time()
    print(f"end: {end}, total: {end - start:.6f}초")


#### 출력값 ####
start: 1763604540.6283398
102334155
end: 1763604565.0303335, total: 24.401973초

 

 

2. 피보나치 수열을 재귀 함수와 메모이제이션 기법 추가(Top-Down)

import sys
import time

sys.setrecursionlimit(10**8)

dp = [0] * 41

def fibo_memo(x):
    if dp[x] != 0:
        return dp[x]
    if x <= 1:
        dp[x] = x
    else:
        dp[x] = fibo_memo(x-1)+fibo_memo(x-2)
    return dp[x]

if __name__ == "__main__":
    print(f"start: {time.time()}")
    start = time.time()
    print(fibo_memo(40))
    end = time.time()
    print(f"end: {end}, total: {end - start:.6f}초")

#### 출력 ####
start: 1763604814.879065
102334155
end: 1763604814.8791049, total: 0.000021초

 

 

3. 피보나치 수열을 반복문으로 구현(Bottom-Up)

import sys
import time

sys.setrecursionlimit(10**8)

def fibo_iter(x):
    dp[0], dp[1] = 0, 1

    for i in range(2, x+1):
        dp[i] = dp[i-1]+dp[i-2]
    return dp[x]
    

if __name__ == "__main__":
    print(f"start: {time.time()}")
    start = time.time()
    print(fibo_iter(40))    
    end = time.time()
    print(f"end: {end}, total: {end - start:.6f}초")

#### 출력 ####
start: 1763605799.6194804
102334155
end: 1763605799.6195118, total: 0.000013초