[파이썬] 피보나치 수열 (2) tabulation로 구현 - 다이나믹 프로그래밍 ★

실습 설명

n번째 피보나치 수를 찾아주는 함수 fib_tab을 작성해 보세요.

fib_tab는 꼭 tabulation 방식으로 구현하셔야 합니다!

실습 결과

def fib_tab(n):
    # 이미 계산된 fib 값들을 담는 리스트
    fib_table = [0, 1, 1]
    
    # n번째 피보나치 수까지 리스트를 하나씩 채워 나간다
    for i in range(3, n+1):
        #print("[%d] fib_table : %s" %(i,fib_table))
        fib_table.append(fib_table[i-1]+fib_table[i-2])
        
    return fib_table[n]

# 테스트 코드
print(fib_tab(10))
print(fib_tab(56))
print(fib_tab(132))

#[3] fib_table : [0, 1, 1]
#[4] fib_table : [0, 1, 1, 2]
#[5] fib_table : [0, 1, 1, 2, 3]
#[6] fib_table : [0, 1, 1, 2, 3, 5]
#[7] fib_table : [0, 1, 1, 2, 3, 5, 8]
#[8] fib_table : [0, 1, 1, 2, 3, 5, 8, 13]
#[9] fib_table : [0, 1, 1, 2, 3, 5, 8, 13, 21]
#[10] fib_table : [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
55
225851433717
1725375039079340637797070384

 

포인트

• Dynamic Programming : 중복된 과정은 1번만 진행하도록 하는 알고리즘 패러다임
• memorization : 재귀
• tabulation : 단순 반복문