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

피보나치 수

-풀이

def solution(n):
    first, second = 0, 1
    for _ in range(n):
        first, second = second, first + second
    return first%1234567

-풀이 설명

피보나치 수를 들어는 봤는데 어떤식으로 사용하는지 몰라서 어느정도 공식 느낌으로 있을 것 같아서 20분 정도 고민 후 구글링하여 피보나치를 나타내는 법을 참고하여 풀게 되었다. 피보나치 수를 구하는 방법은 반복문 ,제네레이터, 재귀 함수, 메모이제이션 등이 있었는데, 재귀 함수는 코드는 간결하고 보기 좋지만 재귀 함수의 단점은 n이 증가하면 시간 복잡도(O(2n))가 가파르게 증가한다는 점이다. 그래서 이러한 문제를 해결하기 위해 메모이제이션을 많이 사용한다고 한다. 메모이제이션은 이전에 계산한 값을 저장해서 중복된 계산을 피하는 방법이다.

from functools import lru_cache

@lru_cache(maxsize=None)

 

functools의 lru_cache를 통해 간단하게 메모이제이션을 구현할 수 있다.

간단하게 @lru_cache 데코레이터를 추가해서 이미 연산된 값을 모두 저장한다.

출처 : 파이썬(Python)으로 피보나치(Fibonacci) 수 구하기https://psychoria.tistory.com/770

그래서 웬만하면 풀이에 올린 코드처럼 직관적이면서 가장 효율적인 방법인 반복문을 사용하여 피보나치 수를 자주 활용해봐야겠다.