함수를 fibonacci 라고 하면, fibonacci(0):0 fibonacci(1):1 fibonacci(2):1 fibonacci(3):2 fibonacci(4):3 fibonacci(5):5 fibonacci(6):8 fibonacci(7):13 fibonacci(8):21 fibonacci(9):34
def fibo(num):
if num <= 1:
return num
return fibo(num - 1) + fibo(num - 2)
fibo(10)
55
def fibo_dp(num):
cache = [ 0 for index in range(num + 1) ]
cache[0] = 0
cache[1] = 1
for index in range(2, num + 1):
cache[index] = cache[index - 1] + cache[index - 2]
return cache[num]
fibo_dp(10)
55
분할 정복 알고리즘의 예는 별도 챕터에서 다루는 병합 정렬과 퀵 정렬을 통해 이해