[코딩테스트] 프로그래머스 - 피보나치 수

피보나치 수

문제 설명

피보나치 수는 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은 2 이상 100,000 이하인 자연수입니다.

입출력 예

n	return
3	2
5	5

입출력 예 설명

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

⭐처음에 구현한 코드

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

def calc(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return calc(n-2) + calc(n-1)

🤔오답노트

흠.. 나는 단순하게 recursion을 사용해서 문제를 해결했다. 그러고 보니 시간 초과랑 런타임 에러가.. ㅜㅜ
보니까 파이썬에서 recursion을 사용하면 재귀할수 있는 횟수가 정해져 있고 횟수를 넘어 재귀 호출을 하면 런타임 에러를 내도록 설계되어 있다고 한다.. 힝

해결을 위해서는 for문을 사용해서 구현하라고 한다.

✔수정코드

def solution(n):
    answer = 0
    a,b = 0,1

    for i in range(n):
        a,b = b, a+b

    answer = a % 1234567
    return answer

지시한대로 for문을 써봤다.
이번에 쓰면서 파이썬의 강점을 또 익힌것 같다.
a,b = b, a+b 라고 해도 다 된다는거!
다른 것도 됐었나...

어쨌든 이런 식으로 a는 다음번 숫자인 b로 해주고 그 다음 숫자는 앞의 숫자 두개를 더한거니까 a+b로 해준다.
이렇게 하면 a가 n번째 피보나치 수가 됨!
1234567로 나눈 나머지가 필요하다고 했으니 마지막에 % 로 나눈 나머지를 구해주면 ٩(•̤̀ᵕ•̤́๑)ᵒᵏᵎᵎᵎᵎ

🤓다른 코드

(%1234567이 추가 되기 전인듯)

def fibonacci(num):
    answer=[0,1]
    for i in range(2,num+1):
        answer.append(answer[i-1]+answer[i-2])
    return answer[-1]

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