85번: 피보나치 수

재귀와 다이나믹 프로그래밍을 동시에 물어볼 수 있는 문제.

문제

입력

출력

풀이

• 만일 N=5라면

1. 재귀를 이용한 풀이 (15번 연산)

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

1. 다이나믹 프로그래밍

# a. 하향식: 메모이제이션 (9번 연산)
def fib(n):
	if n <= 1:
		return n
	
	if self.dp[n]:
		return self.dp[n]
	self.dp[n] = self.dp[n-1] + self.fib(n-2)
	return self.dp[n]

# b. 상향식: 타뷸레이션 (n번 연산) → O(n)
def fib(n):
	self.dp[0] = 0
	self.dp[1] = 1
	
	for i in range(2, n+1):
		self.dp[i] = self.dp[i-1]+self.dp[i-2]

	return self.dp[n]

1. 두 변수만 이용해 공간절약

def fib(n):
	x,y = 0,1
	for i in range(0, n):
		x,y = y, x+y
	return x

새로운 개념