[파이썬] 9009.피보나치[백준_S1] - By @Memoizaiton

"""
 *packageName    : 
 * fileName       : 9009_피보나치_S1
 * author         : qkrtk
 * date           : 2022-03-19
 * description    :
 * ===========================================================
 * DATE              AUTHOR             NOTE
 * -----------------------------------------------------------
 * 2022-03-19        qkrtk       최초 생성
 """
import sys
from functools import lru_cache



def Solution(test_data):
      x = 0
      result_list = []
      while fibo(x) <= test_data:
            x += 1

            if fibo(x) > test_data:
                  x -= 1
                  result_list.insert(0, fibo(x))
                  test_data -= fibo(x)
                  x = 0

                  pass
            if test_data <= 0:
                  for num in result_list:
                        print(num, end=" ")
                  print()
                  return


@lru_cache(maxsize=None)
def fibo(x):
      if x == 0:
            return 0
      elif x == 1 or x == 2:
            return 1
      else:
            return fibo(x - 1) + fibo(x - 2)



T = int(sys.stdin.readline())

for _ in range(T):
      a = int(sys.stdin.readline())
      Solution(a)

- 파이썬 메모이제이션 활용한 첫번째 문제입니다

-재귀 함수( O(n) ) 이기에 연산이 길어질수록 부하 생김

- 그래서 재귀의 경우 이미 계산한 값이 존재하는 경우 별도의 함수의 결과값을 캐싱해서 데이터를 저장해서 불러오는 과정이 필요합니다

- dp 의 경우 재귀적인 호출이 잦기에 이러한 lru_cache 활용이 필수적입니다.