[수학] 피보나치 수 구현하는 여러 방법

1. 피보나치 수

 

첫 번째 항을 0, 두 번째 항을 1로 한 후, 이후의 항들은 이전의 두 항을 더한 값으로 이루어진 수열

 

 

2. 재귀함수 이용하기 => 비효율

n = int(input())

def fibo(n):
  if n == 0 or n == 1:
    return n
  else:
    return fibo(n-1) + fibo(n-2)

print(fibo(n))

 

3. 행렬 이용하기

n = int(input())

def fibo(n):
	f1 = 0
	f2 = 1
	for i in range(2, n+1):
		f3 = f1 + f2
		f1 = f2
		f2 = f3
	return f2

print(fibo(n))

 

4. list 이용하기

n = int(input())

def fibo(n):
  arr = [0,1]

  for i in range(2,n+1):
    arr.append(arr[i-1] + arr[i-2])
  return arr[n]

print(fibo(n))

 

 

5. 두 개의 변수 이용하기

n = int(input())

def fibo(n):
  a,b = 0,1
  for i in range(2,n+1):
    a,b = b, a+b
  return b

print(fibo(n))

 

아으 DP의 기초 중 기초인 파보나치 수,, DP 넘나리 어려워~