[CodeWars] 5Kyu : Memoized Fibonacci

https://www.codewars.com/kata/529adbf7533b761c560004e5/train/python

Codewars - Achieve mastery through coding practice and developer mentorship

 

 

월요일 아침, 뇌가 제일 피로하지 않을때 한문제 슥 풀어보려고 rank up에서 5kyu 짜리 하나 가져와봤다.

 

저번에 푼 5kyu는 실패했었고, 이번엔 어떨지 모르겠다.

 

이번 카타는.. 피보나치 함수를 리팩토링 하는 것 이다. 

 

지금 보면, n이 50을 넘어가면 너무 오래 걸린다 등등의 이유다.

 

피보나치 수열은 첫번째에 들어오는 숫자와, 두번째에 들어오는 숫자가 세번째가되고, 세번째+ 네번째 = 다섯번째, 이렇게 n번째에 어떤 숫자가 나오는지 찾는거다.

 

https://devkevin0408.tistory.com/entry/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98-%EC%88%98%EC%97%B4%EC%9D%B4%EB%9E%80

피보나치 수열이란

 

메모이제이션을 추천했으니, 값을 저장하고 넘기는 식으로 해봐야겠다

def fibonacci(n, memo = {}):
    if n in memo: 
        return memo[n]
    if n in [0, 1]:
        return n
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]

 

나는 파라미터로 memo값을 보내주는 방법을 사용했다.

 

처음에 n에 3이 들어올 경우, 

memo[3]일단 딕셔너리를 사용하고, 배열이 아닌 이유는, 배열은 크기를 미리 잡아야해서 메모리 낭비가 된다.
memo = {} 으로 딕셔너리를 사용했고, key값으로 빠르게 조회도 가능하다.

data가 10일 경우를 계산해보면,

일단 첫줄 memo안에 10이 없어서 지나간다.

memo[10] = fibonacci(9) + fibonacci(8)
memo[9] = fibonacci(8) + fibonacci(7)
...

이런식으로 memo[0]까지 저장이 되고, 

memo = {
    0: 0,
    1: 1,
    2: 1,
    3: 2,
    4: 3,
    5: 5,
    6: 8,
    7: 13,
    8: 21,
    9: 34,
    10: 55
}

이렇게 memo[10]까지 계산해서 반환한다.

 

다른 정답을 보니, 이런 라이브러리를 사용하는것도 있었다.

from functools import lru_cache

@lru_cache(None)
def fibonacci(n):
    if n in [0, 1]:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

 

이 캐시 라이브러리는 함수의 결과를 캐시해준다고 한다. 파이썬이 확실히 편리하긴 하다.