피보나치 수열 5가지 풀이법

1. 피보나치 수

피보나치 수는 레오나르도 피보나치 가 수의 규칙에 대해 연구하여 토끼🐰 수의 증가를 예시로 들어 설명하였습니다.

피보나치 수는 자연계뿐만 아니라, 과학, 건축, 예술에 이르기까지 아름답거나 질서정연한 어떤 형식이 있는 곳이면 빠지지 않고 등장하고 있으며, 수열에서 두 수 사이의 비를 통해 황금비 를 구할 수 있습니다.

피보나치 수는 첫번째와 두번째 숫자가 1 이고, 그 뒤의 모든 항은 바로 앞 두 수의 합 으로 나타나는 수열입니다. (편의상 0번째 숫자를 0으로 두기도 해요.)

2. 피보나치 수열 5가지 알고리즘

피보나치 수열을 다양한 방식으로 구현할 수 있습니다.

Sol.1 재귀

1
2
3
4
def fibo(n):
    return fibo(n-1) + fibo(n-2) if n > 1 else n

fibo(6) # 8

재귀를 배울 때 주로 팩토리얼이나 피보나치 수열을 사용하는데, 피보나치 수열에서 이 방식대로 구현하면 중복 호출 이 많아져 Recursion Error를 쉽게 만날 수 있다는… 시간복잡도가 \(O(2^n)\) 으로 가장 비효율적입니다.

Sol.2 반복

1
2
3
4
5
6
7
8
def fibo(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b

    return a

fibo(6) # 8

이 방식은 함수 호출없이 n번 반복을 통해 구현하였으므로 시간 복잡도 \(O(N)\) 으로 1번 풀이법보다 효율적입니다.

ㅤ

Sol.3 DP

1
2
3
4
5
6
7
8
def fibo(n):
    memo = [0, 1]
    for _ in range(n-1):
        memo.append(memo[-1] + memo[-2])

    return memo[n]

fibo(6) # 8

DP(동적계획법)는 피보나치 수열을 구할 때 가장 많이 사용됩니다.

이 방식에는 Memoiztion이 사용되었는데, Memoization이란 중복을 피하기 위해 저장 해두는 방식입니다.

Sol.4 lambda

1
2
3
4
5
6
def fibo(n):
    fib = lambda n: n if n < 2 else fib(n-1) + fib(n-2)

    return fib(n)
    
fibo(6) # 8

Sol.5 수식

\(F_n = \cfrac{1}{\sqrt{5}} \left( \left( \cfrac{1+\sqrt{5}}{2} \right)^n - \left( \cfrac{1-\sqrt{5}}{2} \right)^n \right)\)

1
2
3
4
5
def fibo(n):
    root_5 = 5**0.5
    return int(1 / root_5 * (((1 + root_5) / 2) ** n - ((1 - root_5) / 2) ** n))

fibo(6) # 8

알고리즘에 대한 일반식을 모른다면 문제를 풀면서 예외까지 고려한 수식 찾기란 하늘의 별따기..⭐ 그리고 피보나치 일반식의 경우 무리수 가 나오기 때문에 프로그래밍을 할 때 적합한 방식이 아니라고 합니다.

개인적으로 DP 가 다른 알고리즘에 적용하기 좋고 효율적이기 때문에 가장 추천하는 방식이에요 ㅎㅎ

잘못된 내용이 있거나 조언이 있다면 언제든지 환영입니다^.^