[프로그래머스] 피보나치 수 - 파이썬

March 17, 2021

문제 설명

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.

예를들어

F(2) = F(0) + F(1) = 0 + 1 = 1 F(3) = F(1) + F(2) = 1 + 1 = 2 F(4) = F(2) + F(3) = 1 + 2 = 3 F(5) = F(3) + F(4) = 2 + 3 = 5 와 같이 이어집니다.

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

제한 사항

• n은 1이상, 100000이하인 자연수입니다.

입출력 예

내 코드

def fibonacci(n):
    if n == 1 or n == 2:
        return 1
    bottom_up = [None] * (n+1)
    bottom_up[1] = 1
    bottom_up[2] = 1
    for i in range(3, n+1) :
        bottom_up[i] = bottom_up[i-1] + bottom_up[i-2]
    return bottom_up[n]

def solution(n):
    return fibonacci(n) % 1234567

일반적인 피보나치 방법인 재귀 방법으로 처음에 시도했더니 n의 범위가 너무 커서 재귀 호출이 허용 범위를 초과해서 에러가 났다. 피보나치를 푸는 방법 중에는 일반적인 1) 재귀호출 방식, 2) 메모이제이션 방식, 3) bottom-up 방식이 있는데, 그 중에서 나는 bottom-up 방식으로 해결했다. 2번째 방법도 결국은 재귀적인 호출을 사용하기 때문에 한계가 있었다. 그래서 처음부터 n까지 값을 구하면서 직접 더해가는 방식으로 풀게 되었다.

다른 사람의 코드

def solution(n):
    a,b = 0,1
    for i in range(n):
        a,b = b,a+b
    return a % 1234567

위 코드가 되게 파이썬스러운 코드이고 간단한 방식이라고 생각했다. 결국 이것도 botton-up방식과 유사하지만 훨씬 간단한 코드였기 때문에 이 방식을 꼭 기억해야겠다고 생각했다.