[99클럽 코테스터디 2기][Python/비기너] 20번째 문제: Fibonacci Number

오늘의 주제도 동적계획법

[Fibonacci Number]

문제

입력과 출력

코드

class Solution:
    def fib(self, n: int) -> int:
        F=[0 for i in range(n+1)]

        for i in range(n+1):
            if i==0:
                F[i]=0
            elif i==1:
                F[i]=1
            else:
                F[i]=F[i-1]+F[i-2]
        
        return F[n]

피보나치 수열

F(n) = F(n-1) + F(n-2)

알고리즘

빈 배열을 n+1의 크기로 선언해준다.
먼저 첫번째 항을 0으로, 두번째 항을 1로 지정해준다.
그 뒤부터는 피보나치 수열의 공식을 적용하면 된다.
마지막 항을 return 해주면 끝이다.

회고

코드는 금방 구성할 수 있었다!
당연히 첫번째에 통과할거라고 생각했는데 리스트에서 오류가 났다..

이 오류에 대해서 찾아보니
행렬을 F=[]로 생성했는데, 이렇게 생성하면 빈 리스트가 생성되는 것이기 때문에
현재 리스트가 NULL인데 F[i]=0과 같이 인덱스를 지정해주었으므로 오류가 난 것이다.

-> 해결방법으로는 append를 사용할 수 있는데, 피보나치 공식을 적용할 때 복잡해질 것으로 생각되어서 다른 리스트 선언방식을 알아보았다.

크기를 지정하여 리스트 생성
list = [0 for i in range(n)]
이렇게 하면 크기를 지정해서 생성되므로, 인덱스를 지정할 수 있다.

이 부분만 수정해주니 바로 통과되었다!

오늘 문제는 너무 쉬워서 다른 문제도 풀어보고 싶지만 ㅜㅜ 시험 이틀전이라.. 종강 후를 기약한다.. ㅜㅜ