2019-10-04_atari.md

DP 알고리즘

피보나치 수 구하는 함수 비교(수행 시간 차이가 납니다)

# 재귀 함수로 구현
fibo(n) 
     IF n < 2 : RETURN n
     ELSE     : RETURN fibo(n - 1) + fibo(n - 2)

# DP 알고리즘으로 구현
fibo1(n) 
 IF n >= 2 AND memo[n] == 0
  memo[n] ← fibo1(n-1) + fibo1(n-2)
 RETURN memo[n]

Atari 소개

논문 링크