[백준] 1003번-(Python 파이썬) - memoization

문제링크 : https://www.acmicpc.net/problem/1003

이번 문제는 단순한 피보나치 수열의 재귀함수를 이용한 문제이다.
재귀함수의 단점인 값이 커지면 연산이 너무나도 많아지는걸
해결하는 메모이제이션을 이용하여 푸는게 이 문제의 출제의 의도이다.

메모이제이션이란 재귀함수의 중복호출 문제를 보완할 수 있는 방법으로
말 그대로 함수의 결과값을 다른 자료구조에 메모해 두는 것이다.

이미지로 보면 쉽게 알 수 있듯이 메모이제이션을 이용하면 중복호출을 줄일 수 있다.

import sys
read = sys.stdin.readline

dp ={
  0 : 0,
  1 : 1,
  2 : 1
}

def f(n):
  if n not in dp:
    dp[n] = f(n - 1) + f(n - 2)
  return dp[n]

t = int(read())
for _ in range(t):
  num = int(read())
  if not num:
    print('1 0')
  else:
    f(num)
    print(dp[num - 1], dp[num])

이번 피보나치 수열 문제는 많이 쉬운 편이었지만
DP문제의 특징은 메모이제이션을 하는건 쉽지만
재귀 규칙 찾는게 헬이라고 할 수 있다.
귀납법을 잘 찾는게 관건이다.