[프로그래머스_재귀_Lv2] 피보나치 수

피보나치 수

문제 링크

나의 풀이

🙅‍♂️ 재귀를 이용한 풀이

def solution(n):
    if n < 2:
        return n
    else:
        return (solution(n-2) + solution(n-1)) % 1234567

• 처음에 재귀 문제를 풀고싶어서 이 문제를 풀기 시작했기때문에 재귀를 사용하여 코드를 작성하였다.

• 코드를 작성하면서 예상했던 것 처럼 테스트케이스에서 시간 초과로 빨간불의 연속이었다.

• 직접 출력해보았을때 n이 30을 넘어가면 급속도로 출력속도가 느려짐을 체감할 수 있었다. 근데 이 문제에선 n이 100,000 이하의 자연수라고 했으니... 당연히 비효율적인 코드이다.

🙆‍♂️ 정답코드

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

• 재귀를 사용하지 않고 for문을 사용한 풀이이다. 코드를 작성하면서 for문의 range를 (n+1)로 착각하여 오답이 나왔었다. n=2 라면 내가 작성한 코드 기준으로는 for문이 n번 만큼만 돌아야 정답이 나오므로 range(n)을 하는게 맞다.

• recursion의 이론에 대해 공부하면서 정리한바와 같이 역시 메모리 효율측면에선 recursion보다는 iteration이 훨씬 효율적이라는 것을 다시금 느꼈다.