[python] 27. 피보나치 수

문제 설명

피보나치 수는 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이하인 자연수입니다.

 

입출력 예

n	return
3	2
5	5

 

입출력 예 설명

피보나치수는 0번째부터 0, 1, 1, 2, 3, 5, ...와 같이 이어집니다.

 

---

 

나의 코드-1 (실패, 정확성: 42.9)

def solution(k):
    if k in [0, 1]:
        return k
    else:
        return (solution(k-2) + solution(k-1)) % 1234567

코드 짜고 돌리면서 들은 생각: 와 이게 된다구?????

하다가 7번 테스트케이스부터 시간초과, 런타임 오류 줄줄이 떠버렸다. 😱

 

 

나의 코드-2

def solution(n):
    answer = []
    for i in range(n+1):
        if i in [0, 1]:
            answer.append(i)
        else:
            answer.append(answer[i-2] + answer[i-1])
    return answer[n] % 1234567

다른 사람들의 풀이를 보면서 왜 위의 코드가 실패한건지 깨닫고 다시 작성해본 코드다.

첫번째 코드에서 f(n) = f(n-2) + f(n-1)라는 수식을 그대로 사용하면서 불필요하게 같은 계산을 두번씩 하게 된 것이다.

list형태로 n번째까지의 피보나치 수를 저장해놓고 계산해주면 훨씬 더 효율성이 좋아진다!