[ Python ] 파이썬 피보나치 수열(Fibonacci)코드

 

 

이 포스팅은 구름edu 의 파이썬으로 배우는 알고리즘 강의를 기반으로 코드를 작성했음을 밝힙니다.

edu.goorm.io/learn/lecture/22654/%ED%8C%8C%EC%9D%B4%EC%8D%AC%EC%9C%BC%EB%A1%9C-%EB%B0%B0%EC%9A%B0%EB%8A%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B8%B0%EC%B4%88

파이썬으로 배우는 알고리즘 기초 - 구름EDU

 

 

 

 

 

피보나치수열은 아래 그림을 보면 단박에 이해가 가실 겁니다!

제가 피보나치 수열을 접한 것은 분명 초딩 때,,, 스펀지라는 프로그램을 보면서

꽃잎 수의 비밀이 이런 거구나,,, 하고 감탄했을 때인데,,,,,,,,

 

지금와서 파이썬으로 코딩하니까 새롭네요 하하 재밌네

 

 

 

 

 

이미지 출처 : https://news.samsungdisplay.com/23402

 

 

 

피보나치 수열은 재귀를 활용하여 코딩을 할 수 있습니다.

만약 4개의 항을 출력하고 싶다면,

 

마지막으로 출력되는 4번째 항의 수는 3번째 항과 2번째 항이 더해진 것이고,

3번째 항은 2번째 항과 1번째 항이 더해진 수입니다.

 

 

 

 

 

 

[ Code ]

 

 

 

def fibonacci(n):
    if(n<=1):
        return n
    else:
        return fibonacci(n-1)+ fibonacci(n-2)

for i in range(10):
    print(fibonacci(i), end=' ')

 

 

 

 

 

 

위와 같이 코딩하면 원하는 값은 정상적으로 얻어낼 수 있습니다.

하지만 비효율적인 방법이겠죠.

 

했던 연산을 하고, 또하고, 또하고,,,

 

fibonacci(6) 을 구하기 위해 전에 했던

fibonacci(0),fibonacci(1),fibonacci(2),fibonacci(3),fibonacci(4),fibonacci(5) 를 다시 연산해야합니다.

 

다시 fibonacci(5)를 구하려 fibonacci(0), fibonacci(1) .... 효율적이지 못하죠.

 

 

따라서 우리는 했던 연산을 저장해놓고, 이를 필요할 때마다 불러오는 식으로 다시 코딩해야합니다!

 

 

 

 

 

[ Code ]

 

 

 

def fibonacci2(n):
    f = [0]*(n+1)
    if(n>0):
        f[1]=1
        for i in range(2,n+1):
            f[i]= f[i-1] + f[i-2]
    return f[n]

for i in range(10):
    print(fibonacci2(i), end=' ')

 

 

 

 

 

 

 

 

편-안