[백준-2747] 피보나치 수 파이썬, 재귀함수 시간초과 메모이제이션 방법사용

# 문제

# 풀이

 피보나치 수열 문제는 재귀함수를 배울때 가장 먼저 접하게 된다. 대부분의 수열 관계는 재귀함수로 짤 수 있다. 그러나 재귀함수는 1000번 이하로 호출이 가능하다. 그러나 이전에 계산했던 값에 대해서 다시 계산하기 때문에 자원낭비가 크다. 기본적으로 메모이제이션 기법을 사용해서 풀 수 있다.

# 코드

# 재귀 이용했더니 시간초과 뜸
def fibo(n):
  if n <= 1:
    return n
  return fibo(n-1) + fibo(n-2)

def solve():
  n = int(input())
  print(fibo(n))


def solve2():
  n = int(input())
  memo = [0,1]
  for index in range(2,n+1):
    memo.append(memo[index-1] + memo[index-2])
  print(memo[n])

if __name__ == '__main__':
    solve2()

 

# 마치며