[Python]3 - Fibonacci Sequence 피보나치 수열

N번째의 피보나치 수열 원소를 반환하는 프로그램을 만들어 보자.

 

 

피보나치 수열이란?

출처:

위키피디아 - ko.wikipedia.org/wiki/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98_%EC%88%98

나무위키 - namu.wiki/w/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98%20%EC%88%98%EC%97%B4#s-1

"피사의 레오나르도로 널리 알려진 레오나르도 피보나치가 1202년 토끼의 번식을 언급하면서 이 수에 대하여 연구했다. 하지만, 피보나치가 최초로 연구한 것은 아니고 인도의 수학자가 최초란 기록이 남아있다. 기원전 450년 핑갈라가 쓴 책에서 최초로 이 패턴이 언급되었고 이후 인도의 수학자들이 이 수에 대하여 연구한 흔적들이 발견되었다. 그 때문에 피보나치도 동방쪽에서 넘어온 정보를 접한 적이 있지 않았을까 생각하는 무리들도 있긴 하나 공식적인 연관성은 불명. 어쨌든 서유럽에서 이 수열을 연구하고 체계화할 수 있는 업적을 세운 것은 피보나치였기 때문에 피보나치 수열이란 이름이 붙게 됐다. 다만 피보나치수열이란 이름은 19세기가 되어서야 붙여졌다."
- 나무위키

 

여기서 토끼 번식 규칙은,

"첫 달에는 새로 태어난 토끼 한 쌍이 존재한다.
두 달 이상 된 토끼는 번식이 가능하다.
번식 가능한 토끼 한 쌍은 매달 암수 토끼 한 쌍을 낳는다.
토끼는 죽지 않는다.
일 년 뒤 토끼는 모두 몇 쌍이 될까?"
- edujin

라는 규칙이다. 토끼 쌍 수를 Fn이라 하고, n이 달일 때,

 

F0 = 0, F1 = 1, F2 = 1, F3 = 2, F4 = 3, F5 = 5, F6 = 8, F7 = 13, F8 = 21, F9 = 34, F10 = 55, F11 = 89, F12 = 144, ...,

혹은 F(n+2) = F(n+1) + Fn

의 수열을 얻을 수 있는 것이다.

 

 

파이썬 구현

입력 number의 validation은 패스했다. (코드 리뷰를 하다 보니 assert nth_number >0 으로 쉽게 할 수 있는 것 같다. 다만 이는 바로 프로그램의 종료를 일으키므로 while loop등을 통해 valid input을 어떻게든! 받게 하는 게 개인적으로는 더 좋아 보인다.)

'''
Fibonacci_sequence program
12/8/2020
'''

def fibonacci(nth_number):
     fibonacci = [0,1]
     for x in range(2,nth_number+1):
          fibonacci.append(fibonacci[x-2] + fibonacci[x-1])
   
     return fibonacci[nth_number]

def main():
     nth_number = int(input("n = ?: "))
     print(fibonacci(nth_number))

if __name__ == '__main__':
     main()

메모

- 재귀함수 말고 리스트로 접근했다. 입력받은 input number까지 각 항을 계산하여 리스트에 append하고 (이전 두 개의 원소들을 용이하게 찾기 위해), 마지막에 계산한 값을 리턴했다.

- 재귀함수를 이용하면 프로그램 자체는 더 간단해 질 수 있다.

# 재귀함수 이용시
# 나머지 부분 동일
def fibonacci(nth_number):
     if nth_number in (0,1):
          return nth_number
     else:
          return fibonacci(nth_number-2) + fibonacci(nth_number-1)

 

하지만 나무위키에서 친절히 말해줘서 알았는데, 재귀함수에 메모이제이션 (Memoization)을 사용하지 않으면 실행시간이 너무 길어질 수 있다고 했다. 링크를 타고 가서 메모이제이션을 봤더니, 피보나치 수열이 예로 나오네!

"메모리라는 동적 자원을 투자해 시간 자원을 아끼는 것"이라는 설명이 잘 들어온다.

namu.wiki/w/%EB%A9%94%EB%AA%A8%EC%9D%B4%EC%A0%9C%EC%9D%B4%EC%85%98

메모이제이션 - 나무위키

 

Udemy 추천 코드들

을 읽으며 이해해보려 했다!

 

1. github.com/MrBlaise/learnpython/blob/master/Numbers/fibonacci.py

- assert n>0 으로 입력값의 validation을 현명하게 했다.

assert [condition]

  은 condition이 True일 때만 실행이 진행되고, 아니면 AssertionError를 리턴한다.

- list를 사용하고, n번째 원소까지의 수열 전체를 리턴한다.

 

2. github.com/timkaboya/cached_fibo/blob/master/cached_fibo.py

- 메모이제이션을 사용한다!

  cached_execution은, cache = {}라는 dictionary 안에 이미 값이 저장되어 있으면 그 값을 읽어 쓰고,

  아니면 cached_fibo값을 새로 저장한다.

- proc(proc_function)부분이 조금 헷갈렸는데, 결국 변수를 받아쓰니 cached_fibo(number)값을 반환하는 것이다!

- cached_fibo는 피보나치 원소를 구하는 재귀함수 부분이다. 다만 cached_fibo를 바로 recursively 부르는 것이 아니라,

  cached_execution에서 찾는 값이 없으면 부른다 (결국은 전체적으로 한 index 당 한 번만 수행)

 

- 근데 말이 메모이제이션이지 저장해서 끌어쓰는 것은 리스트 이용법이랑 같네...?!

메모이제이션을 처음 접해서 생소했는데, 빠른 수행을 위해 메모리를 더 쓰는 것 으로 기억하면 될 것 같다.

 

 

3. github.com/whoshuu/Projects/blob/master/Numbers/fibonacci.py

- 이 분은 재귀함수를 이용, 원소가 2개인 리스트를 계속 덮어쓰면서 값을 구한다. 메모이제이션 없는 재귀함수여서 인덱스가 높아지면 느려질 듯 하다.