[백준][재귀][DP] 2747 - 피보나치 수

개요

재귀 호출 시 반복되는 작업에 대한 결과를 계속 반복 수행하는게 아닌

따로 저장해놓고(캐싱) 갖다 쓰는 방법을 다이나믹 프로그래밍이라 한다. 

 

문제

https://www.acmicpc.net/problem/2747

2747번: 피보나치 수

한 예로 위 문제에 대해 재귀 함수를 사용한다면 금방 제시되는 입/출력을 구현해낼 수 있을 것이다.

하지만 그대로 코드를 제출하면 시간 초과가 나온다.

 

코드 1

n = int(input())

def recursion(n):
  if n <= 1:
    return n
  return recursion(n-1) + recursion(n-2)

print(recursion(n))

 

위에서 말했듯 반복된 계산들을 계속 수행하게되서 그런건데

이미 계산한 결과를 따로 저장해놓고 필요할 때 꺼내 쓴다면 그런 반복 행위를 피할 수 있다.

 

문제에서는 N이 45 이하라는 것으로 힌트를 줬는데,

우리는 여기서 길이 45의 리스트를 사용해 결과 값을 임시저장할 수 있을거라는 걸 알 수 있다.

 

코드 2

n = int(input())
arr = [0] * 46

def recursion(n):
  if n <= 1:
    return n
  if arr[n] != 0:
    return arr[n]
  else:
    temp = recursion(n-1) + recursion(n-2)
    arr[n] = temp
    return temp

print(recursion(n))

1 이하가 아니라면 계속 더하진 값이니 0이 아닐 것이고

만약 0이라면 새로 계산하고선 계산 결과를 넣어놓으면 다른 재귀 호출에서 사용될 것이다.

 

정리

고난이도의 문제에서 재귀를 사용하게 될 때 이렇게 반복 사용되는 부분을 놓치기 쉬운데

항상 과정을 생각하여 재활용 할 수 있는 부분이 있다면 활용할 수 있게끔 기억해놔야겠다.