피보나치(Fibonacci) 수열을 구현하는 7가지 방법 - 파이썬(Python) 피보나치 구현 7선

개발 이야기/Python

by 리치윈드 - windFlex 2018. 3. 3. 02:09

본문 요약 - 피보나치 수열

- 피보나치 수열이란 무엇인가?

- 피보나치 수열을 구현 (python)하는 방법

1) 일반 함수 구현
2) 재귀 함수 구현
3) 제네레이터 (Generator) 방식
4) 메모이제이션 (Memoizatioin) 방식
5) 파이썬 한줄 코딩 (Single Line) 1
6) 파이썬 한줄 코딩 (Single Line) 2
7) 파이썬 행렬 연산 (Numpy)

[관련된 글]

2020.12.16 - [분류 전체보기] - 피보나치(Fibonacci) 수열 구현 7가지 방법 - 파이썬 실습/확인 바로하기

2020.12.05 - [개발 이야기/Python] - [파이썬] IDE 없이 블로그에서 Python 바로 실습/공부

2021.05.18 - [개발 이야기] - 코딩 테스트로 SW 실력을 높여 보자 - 구름레벨(GoormLevel)

2022.05.24 - [개발 이야기/Python] - [코딩 테스트] 파이썬 코딩테스트 핵심 요약 (CheatSheet) - 코테 1시간전에 꼭 보자.

2022.05.08 - [개발 이야기/Python] - [음성인식 - 6라인] 가장 쉬운 음성인식 (STT) 해 보기

2022.04.30 - [개발 이야기] - [코테] 코딩 테스트 플랫폼 4종 - 백준, 리트코드, 프로그래머스, 코드시그널

2021.12.16 - [개발 이야기/Python] - 파이썬 오디오 라이브러리 Top 5종 (Python Audio Library )

2020.05.09 - [개발 이야기] - [개발] 파이썬 문법 5분만에 읽히기 - 파이썬 기본 문법 요약/정리 8 가지

2018.03.03 - [개발 이야기/Python] - 피보나치(Fibonacci) 수열을 구현하는 7가지 방법 - 파이썬(Python) 피보나치 구현 7선

개요 - 피보나치 수열

피보나치 수열

그게 뭔데...?
> 흐음....
> 학교 다닐 때.... 배웠어요.... (잘 생각은 않나지만... ^^;;; )

피보나치 수열은, 현재 값 f(t)를 구함에 있어서, 바로 이전의 값 f(t-1), 그 이전..이전..의 값 f(t-2)을 더하는 방법으로 수를 생성합니다.

다시 말하면, 과거 2개의 값을 더해서, 현재 값을 만드는 방법이고, 이 계산을 계속 반복해 나가면 만드는 숫자들입니다.

그게 뭔말이야??? 쉽게 이야기 해줘~~
쉽게 이야기 하면, 매일마다 그 날 나의 점수를 알고 싶은데, 계산을 어떻게 하냐면,
오늘점수 = 어제점수 + 엊그제점수
이렇게 한다는 이야기야..
여기에서 시간이 흐르니, 날짜는 계속 변하게 되지.

자 이것을 있어보이게 표현을 하면, 현재시간(t)의 함수를 f(t)로 표현합니다.

f(t) = f(t-1) + f(t-2)

실제 숫자의 나열(수열) 예로,

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ..... 입니다.

개념상의 내용은 더 이야기 하면 싫어들... 하실것 같으니, 여기까지 하고요.

우선 Python으로 Coding된 피보나치(Fibonacci) 수 부터 관찰해 보겠습니다.

방법 1. 일반 함수 사용 방식 (Function)

가장 일반적인 함수로 코딩한 경우 입니다. 입력값을 n을 넣어주면, loop문을 통하여 피보나치를 계산하고 결과값을 반환해 주는 방식입니다.

def fib(n):
    a,b = 1,1
    if n==1 or n==2:
        return 1
        
    for i in range(1,n):
        a,b = b, a+b

    return a

5의 피보나치의 수를 구하려면, fib(5)를 실행해 주면 됩니다.

어라? "피보나치수"가 아니라, "피보나치수열"을 구하고 싶은데요?

아래처럼 파이썬(Python) 리스트 표현식 (List Comprehension)을 사용해서 출력해 주면 됩니다.

[ fib(x) for x in range(1,10) ]

피보나치수열의 파이썬 리스트 표현식 (List Comprehension)

실습해 보기

2020/12/16 - [분류 전체보기] - 피보나치(Fibonacci) 수열 구현 7가지 방법 - 파이썬 실습/확인 바로하기

방법2. 재귀함수 사용 방식 (Recursive Function)

자기 자신을 다시 호출하는 자가증식(??) 방식의 코딩입니다. 재귀함수 방식의 가장 중요한 점은 자가증식의 종료를 명시해야 합니다. 재귀함수의 종료 조건이 정확하지 않으면 무한 증식할 수 있습니다.(재귀함수의 가장 중요한 부분이라 하겠습니다.)

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


fib(5)

먼가 코드가 싱거운것 같지요? ^^ㅎ

개인적으로 재귀함수 방식을 좋아하지는 않습니다. 과거에 메모리를 많이 아껴야 하는 시절에는 많이 사용되었습니다만, 메모리가 충분히 성장한 요즘 시대에는 학습차원에서 공부하는 것은 좋지만, 현장에서 사용은 꺼리고 있습니다. 이유는, 재귀함수를 사용하면 가독성이 떨어집니다. 또한, 만약 실수하면 무한루프에 빠지게 되죠. 나중에 디버깅도 쉽지 않습니다. (코딩 인계라도 하는 날이면,,,,, ㅜ_ㅜ)

그러나, 알고리즘 문제는 빠지지 않고 출제되니, 시험을 위해서라면 공부해 두세요~

실습해 보기

2020/12/16 - [분류 전체보기] - 피보나치(Fibonacci) 수열 구현 7가지 방법 - 파이썬 실습/확인 바로하기

방법 3. 제네레이터 구현 방식 (Generator method)

Generator는 단순 반복문(loop)이 아닙니다.

아래 코드에서는 yield를 사용하여, next가 호출 되었을 때만, 한 Step씩 진행하여 결과값을 반환해 주는 방식입니다.

def fibs():
    a,b = 0,1    // generator 출력할 때, next()로 다음것을 출력⇒ 한단계 늦춤
    while True:
        a,b = b, a+b
        yield a

f = fibs()
next(f)

python 2.x 에서는 Generator를 사용할 때, 'generator.next()' 를 사용했었습니다. 즉, 위 예제에서는 f.next()를 사용했었습니다.

그러나, python 3.x 부터 Generator 사용할 때 일부 함수가 변경 되었습니다. next() 공용함수화 되었습니다.

generator의 발생할 때, next(generator) 함수를 사용합니다. 위 예에서, 'next(f)' 를 사용합니다.

기존 python 2.x 스타일로 호출하려면, f.__next__() 입니다.

실습해 보기

2020/12/16 - [분류 전체보기] - 피보나치(Fibonacci) 수열 구현 7가지 방법 - 파이썬 실습/확인 바로하기

방법 4. 메모이제이션 구현 방법 (Memoization Method)

요즈음 데이터의 중요성 때문에, 데이터를 Array에 넣어 놓고 계산하는 방식으로 바뀌고 있습니다. Bigdata를 처리하는 경우가 대부분 이런 경우에 해당됩니다. map / reduce 등의 방식이 대표적입니다. 아래는 피보나치 수열의 각 단계의 결과를 Array로 만들어 반환 하는 방식입니다.

이는 동적계획법 (Dynamic Programming) 접근 방법 중 하나로써, 동적계획법의 대표적인 예로써 피보나치 수열이 자주 등장합니다.

간략하게, "반복되는 수는 메모리에 저장해 두고, 반복 계산 대신 저장해둔 값을 사용한다" 입니다.
Fibonacci(5)를 계산하면, 하위의 fibonacci를 반복적으로 계산하는데, 여러번 계산하지 말고 한번 계산하면 다음에는 그 결과를 재활용 하자는 컨셉 입니다.

다음 이미지 (좌)를 보시면, Fib(5)를 구할 때 반복적인 Fib(2)가 계산이 되고 있습니다. 마찬가지로, Fib(3), Fib(4) ... 계속 반복 계산하는 방식으로 이루어져 있지요. 복잡도를 구하면 O(2^N)에 해당합니다. N이 늘어날 수록 Exponetial하게 연산량이 증가합니다.
효과적인 계산을 위해서, 이것을 한번 계산한 결과를 메모리에 저장해 두고 불러다 사용하는 방식을 취하면, 오른쪽과 같이 연산량이 대폭 감소합니다. 이러한 방식의 복잡도는 O(N)으로 효과적으로 연산량을 줄일 수 있습니다.

피보나치수열의 반복 계산(좌), 동적계획법(Dynamic Programming)을 사용한 피보나치 수열 계산(우)-BottomUp 방식. 출처 : www.baeldung.com

피보나치수열의 동적계획법( Dynamic Programming : Bottom-Up방식)으로 구현하면 아래와 같습니다.

def fib(n):
    fibList=[1, 1]
    if n==1 or n==2:
        return 1
    for i in range(2,n):
        fibList.append( fibList[i-1] + fibList[i-2] )
    return fibList

fib(5)

실습해 보기

2020/12/16 - [분류 전체보기] - 피보나치(Fibonacci) 수열 구현 7가지 방법 - 파이썬 실습/확인 바로하기

방법 5. 파이썬 람다를 사용한 한줄 코딩 1 (Single Line Code with lambda)

파이썬의 lambda 함수를 이용하면, 다음과 같이 한줄로 표현이 가능합니다. 내부적으로는 재귀함수 호출을 람다 함수로 단순화 한것입니다.

fib = lambda n: 1 if n<=2 else fib(n-1) + fib(n-2)

fib(5)

실습해 보기

2020/12/16 - [분류 전체보기] - 피보나치(Fibonacci) 수열 구현 7가지 방법 - 파이썬 실습/확인 바로하기

방법 6. 파이썬 람다를 사용한 한줄 코딩 2 (Single Line Code with lambda)

파이썬 Lambda 함수 이용방법중 또다른 방법입니다. 재귀호출되는 함수의 인자값에 넣어줄 때 원하는 계산을 수행 후 입력하는 방식입니다.

fib = lambda n, a=0, b=1 : a if n<=0 else fib(n-1,b, a+b)

fib(5)

실습해 보기

2020/12/16 - [분류 전체보기] - 피보나치(Fibonacci) 수열 구현 7가지 방법 - 파이썬 실습/확인 바로하기

방법 7. 행렬 연산 (Matrix Operational method) 구현 방식

지금까지는 직관적으로 피보나치를 계산하는 방식이 었습니다. 또다른 방식으로는 행렬연산 방식이 있습니다.

최근 중/고등 과정에서 행렬 연산과정을 제외한다는 소식을 들었는데요.

행렬 연산식 방식은 현대 IT기술의 근간이라고 할 수 있습니다.

최근에 유행하고 있는, AI / Bigdata / 영상분석 / 자율주행 / 음성인식 등 대부분이 행렬연산과 Algebra 를 근간으로 하고 있습니다.

(물론 인문계열에는 불필요할 수 있는데, 이과계에게는 필수적인 기초학문 입니다. )

제 개인적인 사견으로는 "앞으로 우리나라는 AI / IT기술을 포기하겠다..."라고 들립니다. ^^;;;;;;

실습해 보기

2020/12/16 - [분류 전체보기] - 피보나치(Fibonacci) 수열 구현 7가지 방법 - 파이썬 실습/확인 바로하기

[ 행렬 연산 ]

사실 행렬이 어려보이지만, 여러개의 식을 귀찮아서 하나의 묶음으로 계산하는 것이라고 보면 됩니다.

행력의 표기 자체도 대괄호( [ ] )로 묶음 표기 이잖아요??

일종의 "계산들의 패키지" 라고 보면 됩니다.

피보나치를 위한 행렬 연산식은 아래와 같습니다.

뭔가 굉장히 난해해 보이지만,

행렬을 잘 살펴봅시다. ( 앞으로 요렇게 표기 합니다 : [ [1, 1] , [1, 0] ] )

이 행렬을 곱하면 어떻게 되는지? 원소가 1 아니면 0 이잖아요?

위의 행렬을

어떤 행렬A에 행렬[ [1,1], [1,0] ] 을 곱하는 것은,

각각을 더하거나, 원소를 그대로 가져오가나 등의 기능이라고 볼 수 있습니다.

Step이 하나 더 진행되었을 시점임을 고려해야 합니다. 곱하는 시점의 n은 다음 스텝의 n-1입니다.

예를 들어, 결과행에서 1행 2열의 값은, 1* F(n) + 1* F(n-1)이다.

이것은, 결과행 시점에서, n-1번째 결과 + n-2번째 결과 이다.

A = np.matrix( [ [1,1], [1,0] ] )

(A**5)[0,1]

* 여기에서 np는 numpy 입니다. 파이썬에서는 Array연산을 위하여 Numpy 라이브러리를 주로 사용합니다.

import numpy as np

형태로 import 하여 사용합니다.

numpy를 사용하는 주된 이유는,

python 기본 라이브러리에서 배열(Array)를 연산이 행렬(Matrix) 연산이 아니기 때문입니다.

예를 들면, A = [ 1,1] 배열이 있고, 다음과 같은 연산을 진행 한다면,

A * 2

Python 기본 라이브러리는 [ 1, 1, 1, 1 ] 이라는 결과를 보일것입니다.

원하는 결과가 [2, 2] 라면, 어떻게 해야 하는가??? 에 대한 해답이 Numpy를 사용하는 것입니다.

[관련글 참조]

( * Numpy에 대한 내용은 다른 포스팅 https://windflex.tistory.com/1을 참조)

2018/03/03 - [개발 이야기/Python] - [파이썬-Python] Numpy는 왜 필요할까?

파이썬 문법 요약

2020/05/09 - [개발 이야기] - 파이썬 문법 5분만에 읽히기 - 파이썬 기본 문법 요약/정리 8 가지

2020/03/10 - [IT 이야기] - 파이썬 Pandas x Excel

2020/03/10 - [IT 이야기] - Python x Jupyter Notebook 사용하기

2020/03/10 - [개발 이야기/Python] - [Python] 파일 해쉬 (hash) 및 Strings 기능

2020/03/10 - [개발 이야기/Python] - [Python] 딕셔너리를 데이터 프레임으로 (Dict to DataFrame)

2018/03/03 - [개발 이야기/Python] - [Python] Py2Exe - Python 스크립트를 Exe로 배포하자 !!

2020/05/09 - [개발 이야기] - 온라인 IDE - 개발 환경 구축 없어 어디서나 웹브라우저로 개발하기

2020/04/30 - [개발 이야기] - 웹 IDE(구름IDE)로 개발(Coding)환경을 구축해 보자.

2021.05.18 - [개발 이야기] - 코딩 테스트로 SW 실력을 높여 보자 - 구름레벨(GoormLevel)

2022.05.24 - [개발 이야기/Python] - [코딩 테스트] 파이썬 코딩테스트 핵심 요약 (CheatSheet) - 코테 1시간전에 꼭 보자.

2022.05.24 - [IT 이야기] - [ 인터뷰 후기 ] 몰로코 코딩테스트 및 인터뷰 후기

도움이 되었다면, 좋아요와 구독 부탁 드립니다.

'개발 이야기 > Python' 카테고리의 다른 글

[Python] 파일 해쉬 (hash) 및 Strings 기능 (0)	2020.03.10
[Python] 딕셔너리를 데이터 프레임으로 (Dict to DataFrame) (0)	2020.03.10
Python Numpy 추천 문서 및 유의점 (0)	2020.03.09
[Python] Py2Exe - Python 스크립트를 Exe로 배포하자 !! (0)	2018.03.03
[파이썬-Python] Numpy는 왜 필요할까? (0)	2018.03.03

리치윈드 (RichWind)

고정 헤더 영역

메뉴 레이어

메뉴 리스트

검색 레이어

검색 영역

상세 컨텐츠

본문 제목

본문

본문 요약 - 피보나치 수열

개요 - 피보나치 수열

피보나치 수열

방법 1. 일반 함수 사용 방식 (Function)

방법2. 재귀함수 사용 방식 (Recursive Function)

방법 3. 제네레이터 구현 방식 (Generator method)

방법 4. 메모이제이션 구현 방법 (Memoization Method)

방법 5. 파이썬 람다를 사용한 한줄 코딩 1 (Single Line Code with lambda)

방법 6. 파이썬 람다를 사용한 한줄 코딩 2 (Single Line Code with lambda)

방법 7. 행렬 연산 (Matrix Operational method) 구현 방식

[관련글 참조]

'개발 이야기 > Python' 카테고리의 다른 글

관련글 더보기

댓글 영역

추가 정보

인기글

최신글

티스토리툴바

리치윈드 (RichWind)

고정 헤더 영역

메뉴 레이어

메뉴 리스트

검색 레이어

검색 영역

상세 컨텐츠

본문 제목

본문

본문 요약 - 피보나치 수열

개요 - 피보나치 수열

피보나치 수열

방법 1. 일반 함수 사용 방식 (Function)

방법2. 재귀함수 사용 방식 (Recursive Function)

방법 3. 제네레이터 구현 방식 (Generator method)

방법 4. 메모이제이션 구현 방법 (Memoization Method)

방법 5. 파이썬 람다를 사용한 한줄 코딩 1 (Single Line Code with lambda)

방법 6. 파이썬 람다를 사용한 한줄 코딩 2 (Single Line Code with lambda)

(adsbygoogle = window.adsbygoogle || []).push({});

방법 7. 행렬 연산 (Matrix Operational method) 구현 방식

[관련글 참조]

'개발 이야기 > Python' 카테고리의 다른 글

관련글 더보기

댓글 영역

추가 정보

인기글

최신글

티스토리툴바