피보나치 수(Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 처음 여섯 항은 각각 1, 1, 2, 3, 5, 8이다. 아래의 구현에서는 편의상 0번째 항을 0으로 두고 계산한다.
1. Iterative
Iterative는 사전적인 정의로 '반복적인' 이라는 뜻을 가지고 있다. 피보나치 수는 이전의 항들이 다음항을 결정하는 구조의 점화식을 이루고 있으므로 반복적인 계산을 통해 구하고자 하는 수를 도출해내는 것이 가장 일반적인 방법이다.
## Iterative
def fibo_iterative(num) :
if num < 0 : print("Input Positive Num")
elif num < 2 : return num
else:
a, b = 0, 1
for i in range(num - 1) :
a, b = b, a + b
return b
a와 b는 각각 0번째와 1번째 항의 값을 의미한다. 피보나치 수는 양의 정수 (+ 0)에서만 정의되어 있기때문에 음수를 입력할 경우를 예외로 처리해준다. 이후엔 간단하게 이전 두 항을 더하여 다음 항을 구하는 식을 반복(for문 사용)한다.
2. Recursive
규칙적인 계산이 반복된다는 점을 활용해 재귀함수로의 구현또한 가능하다. Recursive는 사전적으로 '재귀 : 어떠한 것을 정의할 때 자기 자신을 참조하는 것'를 의미한다.
def fibo_recursive(num) :
if num < 0 : print("Input Positive Num")
elif num < 2 : return num
else:
return fibo_recursive(num - 1) + fibo_recursive(num - 2)
추가 구현의 과정이 줄어들어 코드의 가독성은 올라가지만, n이 커질 수록 시간복잡도가 가파르게 증가하기 때문에 효율면에서 현저히 떨어진다는 단점이 존재한다.
3. Memoization
재귀함수의 시간 복잡도 문제를 해결하기 위해 사용할 수 있는 방법이 Memoization이다. Memoization은 이전에 계산한 값을 저장해두어 계산이 중복되는 것을 방지한다.
## Memorization
fiboMemo = { 0 : 0, 1 : 1 }
def fibo_memoization(num) :
if num < 0 : print("Input Positive Num")
elif num < 2 : return num
else :
if num in fiboMemo :
return fiboMemo[num]
fiboMemo[num] = fibo_memoization(num-1) + fibo_memoization(num-2)
return fiboMemo[num]
전역변수 fiboMemo를 Dictionary로 선언해두어 함수 호출이 끝나더라도 값을 기억하는 방식으로 작성되었다. Dictionary는 Hash의 형태를 띄고 있어 Key값과 Value값을 각각 가지고 있는데 리스트나 튜플처럼 순차적으로(sequential) 해당 요솟값을 구하지 않고 Key를 통해 Value를 얻는다. 예를 들어 위 코드에는 fiboMemo = { 0 : 0, 1 : 1 } 가 선언되어 있는데, fiboMemo[0]을 검색하면 Key값이 0인 곳으로 이동해 그 Value값인 0을 return 한다.
## Memorization (Caching)
@lru_cache
def fibo_memoization(num) :
fiboMemo = { 0 : 0, 1 : 1}
if num < 0 : print("Input Positive Num")
elif num < 2 : return num
else :
if num in fiboMemo :
return fiboMemo[num]
fiboMemo[num] = fibo_memoization(num-1) + fibo_memoization(num-2)
return fiboMemo[num]
전역변수 대신 파이썬의 표준 라이브러리인 functools.lru_cache()를 사용하는 방법도 있다. 데코레이터(@)를 사용해 함수 위에 lru_cache를 넣어주면, fibo_memoization 함수를 재귀 호출 할 때, 중복된 경우 함수 호출이 아닌 캐싱된 결과를 반환하여 실행 시간을 줄인다.
4. Generator
Generator은 iterator를 생성해주는 함수로, yield 키워드를 사용해 함수의 control을 양보하여 중단점을 기억하고, 그 지점에서 재개되는 방식으로 실행이 이어진다. iterable한 순서가 지정되어, 무한한 순서가 있는 객체도 모델링 가능한 함수이다.
## Generator
def fibo_gen_sub(num) :
if num < 0 : print("Input Positive Num")
elif num < 2 : return num
else :
a, b = 0, 1
for i in range(num) :
yield b
a, b = b, a + b
def fibo_generator(num) :
fiboList = []
for i in fibo_gen_sub(num) :
fiboList.append(i)
return fiboList[-1]
사실 Generator는 for문의 조건이 종료될 때까지 yield에서 계속해서 다시 실행되며 1부터 n까지의 결과를 기록하기때문에 정확히 n번째 항을 구하는데에는 적합하지 않은 함수이다. (1부터 n까지 전부 실행후, 다시 n번째 항으로 돌아가는 불필요한 계산이 진행되기 때문) 그럼에도 n번째 항을 찾기 위해서 위 코드에서는 서브함수를 추가로 작성하여 나타냈다.
걸린 시간 측정을 추가하여 실행한 결과는 아래와 갔다. recursive 방식이 눈에 띄게 느린 것을 확인할 수 있다. 결과값은 때에 따라 달라질 수 있기때문에 여러번 측정을 통해 평균치를 활용하는 것이 더 정확하다.
