피보나치 수열 알고리즘 in 파이썬 python 고전 컴퓨터 알고리즘

part.00 메모이제이션을 이용한 피보나치 알고리즘

n = int(input())
memo = {0: 0, 1: 1}

def fibo(n):
    if n in memo:
        return memo[n]
    else:
        ret = fibo(n-1) + fibo(n-2)
        memo[n] = ret
        return ret

print(fibo(n))

일반적인 리스트를 이용하는 것이 아닌, dictionary()를 이용하여 key값으로 value를 빠르게 찾도록 만들었다.

part.01 아래 코드는 해보나치 수열 단일값을 출력하는 코드이다.

from functools import lru_cache

@lru_cache( maxsize = None )

def fib4( n: int ) -> int:
    if n < 2: # 기저조건
        return n
    return fib4(n-2) + fib4(n-1) #재귀조건

if __name__ == "__main__":
    print( fib4(9) )
    # 결과값 34

lru_cache 함수를 사용하여 각각의 값을 저장하여

재귀함수 호출을 수십 혹은 수만번 호출하지 않고

저장크기에 제약을 가하지 않게 설정하여

저장소에서 값을 바로바로 불러와 피보나치 수열 단일값을 계산하는 코드이다.

 

part.02 단일값 피보나치 수열 이전까지의 모든 수를 출력하는 함수 코드

from typing import Generator

def fib6( n: int ) -> Generator[int, None, None]:
    yield 0
    
    if n > 0: yield 1 # 특수조건
    last: int = 0 # fib(0)
    next: int = 1 # fib(1)
    
    for _ in range(1, n):
        last, next = next, last + next
        yield next # 제너레이터 핵심 반환문

if __name__ == "__main__":
    for i in fib6(50):
        print(i)

Generator-yield 함수를 사용하여 

fib6(50) 단일값 뿐만 아니라 그 이전 값들까지 모두 출력하는 코드이다.

결과값은 아래와 같다.

0
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946
17711
28657
46368
75025
121393
196418
317811
514229
832040
1346269
2178309
3524578
5702887
9227465
14930352
24157817
39088169
63245986
102334155
165580141
267914296
433494437
701408733
1134903170
1836311903
2971215073
4807526976
7778742049
12586269025

함수 부분을 따로 놓고 보면.

def fib6( n: int ) -> Generator[int, None, None]:
    yield 0
    
    if n > 0: yield 1 # 특수조건
    last: int = 0 # fib(0)
    next: int = 1 # fib(1)
    
    for _ in range(1, n):
        last, next = next, last + next
        yield next # 제너레이터 핵심 반환문

yield 변수에 값을 저장하면

Generator 함수에 저장을 하게된다.

 

일반적인 재귀함수를 사용하지 않고

고전적인 방법인

last를 이전항

next를 다음항으로 설정하여

 

last <- next를 대입하고

next <- last + next를 대입하여

 

피보나치식

fib(n) = fib(n-2) + fib(n-1) 을 코드로 구현하게 했다.

 

간단하게

 

last == fib(n-2) 이고,

next ==fib(n-1) 라고 보면되겠다.

 

for문을 통해 각 단계마다 계산된

next 변수 값을 yield에 대입하고

Generator 함수에 저장하게 된다.

for i in fib6(50):
	print(i)

위의 코든를 통해 순서대로

fib6(1) 부터 순서대로 출력하게 된다.