[코테] 피보나치 수

문제링크

프로그래머스

<로직 고민/>

• 피보나치 수를 구하는 방법을 보니 재귀함수를 써야 하는 건가...!! 싶군
• 일단 피보나치 수를 구하는 함수 fibonacci를 만들어서 n이 0일 때 0, 1일 때 1, 2보다 크거나 같을 때 fibonacci(n-2) + fibonacci(n-1)을 리턴하는 로직을 짜보자 

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1 or n == 2:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)
    
def solution(n):
    answer = fibonacci(n) % 1234567
    return answer

• 이렇게 해서 예시는 다 통과하고, 채점 했더니 1~6번 테스트는 통과, 7~14번은 런타임에러 또는 시간초과가 뜬다
• 재귀함수를 쓰는 거라 뭔가 숫자가 커지면 시간이 오래 걸리겠단 생각은 했는데...통과가 안 되는군
• 그럼 재귀함수를 쓰는 게 정답은 아닌가보다
• 검색해봤는데 누가 이미 연산된 값들을 저장하는 메모제이션을 써보라고 해서 fibonacci 함수 위에다 아래 코드를 추가했는데 7~14번에서 9번만 통과하고 나머지는 런타임에러 뜬다,,

from functools import lru_cache

@lru_cache(maxsize=None)

• 일반함수로 피보나치 수를 구하니까 통과...! 10점!!

---

<완성된 풀이/>

def fibonacci(n):
    if n == 0:
        return 0
    
    elif n == 1 or n == 2:
        return 1
    
    a, b = 1, 1
    for _ in range(1, n):
        a, b = b, a + b
    return a
    
def solution(n):
    answer = fibonacci(n) % 1234567
    return answer

n이 클수록 시간이 오래 걸린당,,

---

<다른 사람 풀이/>

- 풀이1

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

• 오 이렇게 짧게도 되는 건데...나는 괜히 함수를 하나 더 만들었구나

• 근데 실행시간은 내 풀이보다 더 걸리네