피보나치 수열
def solution(n):
memo = [0]*(n+1)
def fibo(num):
if num in (0, 1):
return num
if memo[num] > 0:
return memo[num]
val = fibo(num-1) + fibo(num-2)
memo[num] = val
return val
memo[0] = 0
memo[1] = 1
fibo(n)
# print(memo)
ans = memo[-1] % 1234567
return ans
Python
복사
n은 2 이상 100,000 이하인 자연수입니다.
재귀는 런타임 에러를 일으킬 수 있음
def solution(n):
if n < 2:
return n
memo = [0]*(n+1)
memo[0] = 0
memo[1] = 1
for i in range(2, n+1):
memo[i] = memo[i-1] + memo[i-2]
# print(memo)
ans = memo[-1] % 1234567
return ans
Python
복사
반복문 기반의 memoization을 수행하면 됨