피보나치(Fibonacci)

피보나치 알고리즘

피보나치 수열은 앞 두개 항의 값을 더한 것이 뒤 항의 값이 되는 수열이다.

[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...]

 

이런 형태의 피보나치 수열에서 n번째 항의 값을 찾는 알고리즘을 만들어보자.

 

재귀 알고리즘 사용

  피보나치 문제는 재귀 알고리즘을 이용하여 간략한 형태의 코드를 짤 수 있다. 재귀 알고리즘을 사용하기 위해서는 두 가지가 정의되어야 한다. 문제 정의, 탈출 요건이다.

  피보나치 수열은 'n번째 항의 값은 n - 1항과 n - 2 항의 값과 같다' 로 정의할 수 있다. 즉, f(n) = f(n-1) + f(n -2)로 정의할 수 있다. 다만 첫째항, 두번째항의 경우 n - 1항과 n - 2항이 없어 조건이 충족되지 않는다. 따라서 더이상 위 식을 사용할 수 없고 이 두 항의 값은 1로 고정한다. 이것이 곧 재귀함수의 탈출요건이 된다.

 

이를 코드로 구현해보면 아래와 같다.

def fib(n):
    if n < 3:
        return 1
    return fib(n - 1) + fib(n - 2)


if __name__ == "__main__":
    print(fib(10)) #55

n이 3보다 작다면 1을 return하고 재귀호출에서 탈출한다.

n이 3보다 크거나 같다면 다시 fib함수를 호출한다.

 

재귀 알고리즘을 사용하면 코드 단 세 줄로 피보나치 수열에서 n 번째 요소를 찾는 함수를 만들 수 있다.

 

하지만 효율은 좋지않다. 재귀용법을 이용해 구현한 피보나치수열 알고리즘의 시간 복잡도는 O(2ⁿ)이다.

 

 

 

위 그림과 같이 fib(n)는 fib(n-1), fib(n-2)로 구성되기 때문에 fib(n-1)을 구하기 위해 또다시 재귀 호출을 시작하고 f(n-2) 또한 재귀호출을 시작한다. 그리고 내부의 재귀호출은 또다시 재귀호출을 시작하고 이 모든 호출이 탈출할 때까지 반복된다.

 

fib(100)까지만 호출해봐도 결과 출력이 굉장히 느려짐을 알 수 있다.

 

 

메모이제이션

  메모이제이션을 이용하면 재귀호출 없이도 간략하고 성능이 좋은 알고리즘을 만들 수 있다. 

f(n) = f(n-1) + f(n -2)에서 f(n-1)은 결국 f(n-2) + f(n-3)으로 구성되는데, 다시말해 f(n) = (f(n-2) + f(n-3)) + f(n -2)과 같다는 뜻이다. 여기서 f(n-2)이 두번 사용되는데, 재귀호출에서는 이 f(n-2)의 값을 구하기 위한 재귀호출을 두 번 따로 수행한다. 하지만 그럴 필요 없이 한번만 f(n-2)의 값을 구하고 기억해두었다가 다시 f(n-2)이 필요해지면 그 값을 재활용하면 된다. 이것이 메모이제이션의 개념이다.

 

p1은 n-1의 값, p2는 n-2의 값을 나타낸다. 고정된 개수의 변수만 사용하므로 공간복잡도는 O(1), 시간 복잡도는 O(N)이 된다.

def fib(n):
    p2, p1 = 0, 1
    for i in range(n):
        p2, p1 = p1, p2 + p1
    return p2
    
if __name__ == "__main__":
    print(fib(10)) #55

 

 

 

참고

https://www.dalecoding.com/algorithms/fibonacci

피보나치 (Fibonacci) 알고리즘 | 달레코딩