[프로그래머스 Level2][Python] 피보나치 수

[프로그래머스 Level2] 피보나치 수

https://programmers.co.kr/learn/courses/30/lessons/12945

문제설명 📖

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

입출력 예

문제접근 💡

1. 먼저 피보나치 수열에 대한 이해가 필요하다.

피보나치 수란, 다음 그림과 같다. F(n) = F(n-1)+F(n-2) (단, n은 1 이상이며 F(0)=0, F(1)=1)
문제에 나와있는 것처럼
ex) F(3) = F(2)+F(1) = {F(0)+F(1)}+F(1)= 1 + 1 = 2
2. 직관적인 이해는 끝났다. 코딩을 하기 위해 규칙에 대한 이해가 좀 더 필요하다.
F(2) = F(1) + F(0)
F(3) = F(2) + F(1)
F(4) = F(3) + F(2)
F(5) = F(4) + F(3)
F(6) = F(5) + F(4)
F(7) = F(6) + F(5)
3. answer = 0, num = 1이라는 변수를 정해두고, answer = num, num = answer+num으로 n-1만큼 반복한다.
예를 들어, F(5)일 경우
i = 0일 때 answer = 1, num = 0+1
i = 1 일 때 answer = 1, num = 1+1
i = 2 일 때 answer = 2, num = 1+2
i = 3 일 때 answer = 3, num = 2+3
i = 4 일 때 answer = 5, num = 3+5
F(5) = 5
여전히 어렵다면, 직접 손으로 변수에 넣어가면서 풀어보시길...

문제풀이 💡

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

처음에는 재귀를 썼으나, 효율성 문제로 실패..
재귀함수는 코딩테스트에서 메모리 효율에 좋지 않다고 한다.
규칙성을 간단하게 하기 위해 손으로 계속 적어보며 변수를 어떻게 활용해야하는지 감을 잡았다.
어렵다면, 그렇게 해보길 추천한다.

다른 풀이는 리스트로 추가해서 하는법이 있으나 근본적으로 같은 풀이이므로 올리지 않겠다😃