[Dynamic Programing] 피보나치 수열 Tabulation

실습 설명

n번째 피보나치 수를 찾아주는 함수 fib_tab을 작성해 보세요.
 
fib_tab는 꼭 tabulation 방식으로 구현하셔야 합니다!
- Tabulation(Table 방식으로 정리, 상향식 접근)
 

def fib_tab(n):
    # 여기에 코드를 작성하세요
    # tabulation
    fib_table = [0, 1, 1]
    
    if n > 2:
        for i in range(3, n+1):
            fib_sum = fib_table[i-1] + fib_table[i-2]
            fib_table.append(fib_sum)
            
        return fib_table[n]
    
    return fib_table[n]
            
        

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

해결과정
 
Memoization vs Tabulation
- 공통점 : 둘 다 중복되는 부분 문제의 비효율을 해결
- 차이점 : Memoization -> 일반적으로 재귀함수 사용 / Tabulation -> 일반적으로 반복문 사용
Memoization(재귀 호출이 너무 많이 일어나면 스택(stack)이 계속 쌓이고 결국에 과부하가 걸려서 오류가 날 수도 있지만 위에서부터 필요한 계산이 뭔지 요구를 하기 때문에, 필요 없는 계산은 안 해도 된다.)
Tabulation(반복문을 사용하기 때문에 과부하의 문제점은 없지만, n번째 값을 구하기 위해서 처음부터 모두 계산하고 중간에 필요 없는 것들까지 계산하게 될 수 있다.)
 
1번 피보나치 수는 1이고, 2번 피보나치 수도 1이기 때문에 fib_table의 값을 먼저 정의한다. fib_table = [0, 1, 1]
fib_table을 인덱스 3부터 인덱스 n까지 채워 나간 후에 리스트의 n번째 항목을 리턴
 
처음에 반복문 안에 fib_table[i] = fib_table[i-1] + fib_table[i-2]라고 정의를 했지만 계속 오류가 나서 왜 안되는지 계속 고민했다.
빈 리스트는 index가 없기 때문에 위와 같이 할 수 없다는 사실을 깨달았다.
 
나름 기본적인 코드에 지식이 있다고 생각했지만, 이런 기본적인 사실을 모르다니... 아직 갈길이 한참 남았다는 생각도 들었다...
 
세상에 버려지는 노력은 없다라는 생각을 갖고 더 열심히해야겠다! 화이팅 국나뇽🫡