2) tubulation 방식의 피보나치 함수

2) tubulation 방식

테이블을 그려놓고 하나씩 진행하며 저장하는 방식

제일 최소의 단위부터 문제의 값을 테이블에 저장해 나가며,

제시된 문제를 해결할 수 있으면 거기서 해당 값을 리턴한다. 

 

문제를 해결할 때 아래에서부터 위로 올라간다.

(작은 값 부터 큰 값으로)

이를 Bottom-up-approach라고 한다.

 

주로 반복문을 활용한다.

 

 

 

tubulation 방식의 피보나치 함수

def fib_tab(n):
    # 이미 계산된 피보나치 수를 담는 리스트
    fib_table = [0, 1, 1]

    # n번째 피보나치 수까지 리스트를 하나씩 채워 나간다
    for i in range(3, n + 1):
        fib_table.append(fib_table[i - 1] + fib_table[i - 2])

    # 피보나치 n번째 수를 리턴한다
    return fib_table[n]

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

결과

55

225851433717

1725375039079340637797070384