[프로그래머스] 피보나치 수 (python)

코딩테스트 연습 - 피보나치 수

 

👩🏻‍💻 코드

def fibo(n):
    arr = []
    for i in range(n):
        if i < 2:
            arr.append(1)
        else:
            arr.append(arr[i - 1] + arr[i - 2])

    return arr[n - 1]


def solution(n):
    answer = fibo(n)
    return answer % 1234567

 

📝 정리

처음에 재귀 함수를 사용해, fibo(n) = fibo(n-2) + fibo(n-1) 로 구현했더니 시간 초과와 런타임 에러가 났다.

이는 재귀 함수로 구현하게 되면 불필요한 연산을 반복하고, 재귀 제한에 걸리기 때문이었다.

 

따라서 for문을 통해 arr에 저장하는 방식으로 변경하였고, 테스트에서 통과할 수 있었다.