파이썬 피보나치 수열 구현하기

 

학습 목표

피보나치 수열에 대한 이해

피보나치 수열

1) 정의

피보나치 수열이란 처음 두 항을 1과 1로 한 후, 그 다음 항부터는 바로 앞의 두 개의 항을 더해 만드는 수열을 말한다.

*문제를 살펴보면 처음 두 항은 다른 경우가 꽤 있다.

 

 

2) 동작 예시 

 

풀이 - 1

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

n=int(input())
print(fibo(n))

가장 기본적인 식으로, x==0과 x==1일 때 fibo(x)는 1을 처리한다.

이 외는 fibo(x-1)+fibo(x-2) 더한 값을 리턴한다.

매번 fibo(x-1), fibo(x-2) .... 계산이 계속해서 돌게 되므로, 연산이 많아지고 결과 도출이 늦어진다.

 

 

풀이 - 2

def fibo(x):
    if x in dictionary:
        return dictionary[x]
    else:
        dictionary[x]=fibo(x-1)+fibo(x-2)
        return dictionary[x]

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

print(fibo(n))

dictionary type에 넣어서 각 피보나치 수열을 적고, 적어 놓은 것을 꺼내오는 방법으로 구성 해 보자.

이 경우 매번 계산을 돌릴 필요는 없고 메모된 값을 꺼내오기만 하면 된다.

 

    if x in dictionary:
        return dictionary[x] - x 값이 dictionary 내에 있는 지 확인한다. 확인하는 기준은 "key" 값이다. 예를 들어 dictionary 내용에 {0:1} 이라면 0이 해당된다.

 

    else:

        dictionary[x]=fibo(x-1)+fibo(x-2)

        return dictionary[x] - dictionary 내에 없는 경우, dictionary[x]에 계산 값을 새로 적어준다. 그리고 해당 값을 리턴한다.