피보나치수열_Fibonacci Sequence

피보나치 수열이란?

수학에서, 피보나치 수(Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 단조 증가 수열이다. 

처음 여섯 항은 각각 1, 1, 2, 3, 5, 8이다. 편의상 0번째 항을 0으로 두기도 한다.

 

피보나치 수열의 점화식(이곳에서 사용)

---

반복(Iterative)

1. 코드

def fibo(x):
	if x<=2:
		return 1
	
	a, b = 0,1
	for i in range(x-1):
		a, b = b, a+b
	return b

2. 시간 복잡도

T(n) = n+1  --> O(n)

 

3. 특징

• 불필요한 연산을 계속 수행해야 한다.

---

재귀(Recursive)

1. 코드

def fibo(x):
	if x<=2:
		return 1
	else:
		return fibo(x-1)+fibo(x-2)

2. 시간 복잡도

T(n) = T(n-1) + T(n-2) + c --> O(2^n)

함수가 한 번 호출되면 2번씩 호출되기 때문에 2^n

 

3. 특징

• 코드 구성이 간단하다.
• 시간 복잡도가 크다. 
• 재귀의 특징에 따라 Stack Overflow가 발생할 수 있다.
• 불필요한 연산을 계속 수행해야 한다.

 

---

동적계획법(Dynamic Programming)

1. 코드

########피보나치 수열########
########1. 탑다운 방식(memoization)########

#한 번 계산된 결과를 메모이제이션하기 위한 리스트 초기화
d = [0] * 100

#피보나치 함수를 재귀함수로 구현(탑다운)
def fibo(x):
	#종료 조건(1 혹은 2일 떄 1을 반환)
	if x == 1 or x ==2:
		return 1
	#이미 계산한 적이 있는 문제라면 그대로 반환
	if d[x]!=0:
		return d[x]
    #아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환   
	d[x] = fibo(x-1) + fibo(x-2)
	return d[x]
 
########2, 바텀업 방식########

 d = [0] * 100

#첫번째 피보나치 수와 2번쨰 피보나치 수는 1
 d[1] = 1
 d[2] = 1
 n = 99

#피보나치 함수 반복문으로 구현(바텀업 다이나믹 프로그래밍)
 for i in range(3, n+1):
 	d[i] = d[i-1] + d[i-2]

2. 시간 복잡도

O(n)

 

3. 특징

 

출처: 나무위키

동적계획법의 사용 이유

• 기존의 재귀적인 방법과, 반복을 이용한 방법은 매우 비효율적이다.
• 부분 문제가 너무 많이 중복 된다. 예를 들면 fib(0)과 fib(1)은 많은 중복이 발생한다. 그때마다 연산을 계속 하기란 시간낭비!
• 단, 추가적인 메모리 공간이 필요하다.

 

 

반복적 동적계획법(바텀업) VS 재귀적 동적계획법(탑다운)

• 재귀적 동적계획법은 함수를 계속 호출하는 데에 따르는 오버헤드가 발생할 수 있어서 반복적 동적계획법보다는 느리다. 
• 하지만 그 차이는 미세하여서 무시 가능

 

---

 

출처

https://shoark7.github.io/programming/algorithm/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%84-%ED%95%B4%EA%B2%B0%ED%95%98%EB%8A%94-5%EA%B0%80%EC%A7%80-%EB%B0%A9%EB%B2%95.html

https://ko.wikipedia.org/wiki/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98_%EC%88%98

https://www.youtube.com/channel/UChflhu32f5EUHlY7_SetNWw

https://ssu-gongdoli.tistory.com/29