[수학] 피보나치 수열에 관하여 (코드 구현 방법별 성능 비교)

목차

1. 들어가며

2. 피보나치 수열이란?

3. 코드 구현 및 성능 비교

    3-1. 재귀함수 이용

    3-2. 반복문 이용

    3-3. 수식 이용

4. 마치며

1. 들어가며

프로그래밍과 코딩을 동일한 의미로 이해할 수 있지만 프로그래밍은 문제해결을 위한 코딩이고, 코딩은 단순히 코드를 작성하는 일로 나누고 있는 것 같습니다. 하지만 저는 두 가지의 근본적인 목적이 문제해결이라는 점에서 결국 같은 것이라고 생각합니다. 누구는 프로그래머라 불리고, 누구는 코더라 불리더라도 결국 같은 목표를 가지고 보다 나은 세상을 만들기 위해 노력하시는 분들이라고 생각합니다. 따라서 저는 프로그래밍이든 코딩이든 왜 해야하는지에 대해 항상 생각하는 사람이 되려고 노력하고 있습니다. 때론 프로그래밍이나 코딩이 문제해결을 위한 무조건적인 정답이 아닐 수 있으니까요.

오늘은 알고리즘 공부하며 배웠던 피보나치 수열에 대해서 느낀점과 보충공부한 내용에 대해 포스팅을 하려 합니다. 중고등학교 때에는 수학이 어렵고, 왜 배워야 하는지 잘 몰랐는데, 꿈을 향해 공부하고 업무를 하며 이런 것들이 왜 필요한지를 느끼다보니 지금은 수학이 정말 재밌는 학문인 것 같습니다. 다시 한번 느끼는 것이지만 우리나라 학생들이 주입식 교육보다는 왜 알아야 하는지에 대한 배움을 같이 느껴봤으면 좋겠네요.

2. 피보나치 수열이란?

피보나치 수열은 다들 들어보셨을겁니다. 아래에 나열한 수열과 같이 특정 위치의 숫자는 첫번째 바로 앞의 숫자와 두번째 앞의 숫자를 더한 것이 되는 수열을 의미하죠.

$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, \cdots$

기하학적으로 살펴보자면 아래 그림과 같습니다. 한 변의 길이가 1인 정사각형 2개를 나란히 세워 놓은 후, 이 정사각형들의 변의 합으로 또 하나의 정사각형을 만드는 식으로 반복해서 나가다보면 우리가 알고있는 피보나치의 수열을 그림으로 표현한 것이 됩니다.

<출처>위키백과

피보나치 수열의 개념은 기원전 5세기 인도의 수학자 핑갈라가 쓴 책에 처음 소개되었다고 하고, 이후 유럽에서 레오나르도 피보나치가 자세히 연구하면서 피보나치 수열이라고 이름이 붙게된 것 같습니다. 피보나치는 토끼 개체 수 증가에 관한 이야기를 언급하면서 피보나치 수를 이용하여 토끼 개체 수에 대한 해석 연구를 진행했다고 합니다. 아마도 레오나르도 피보나치는 미래에 토끼 개체 수가 얼마나 될 것인지를 예측하고 싶어했고, 아래와 같이 토끼 개체 수 증가 모델의 가설을 세우면 피보나치 수열로 모델링하여 예측할 수 있겠다고 생각했던 것 같습니다.

· 첫 달에는 새로 태어난 토끼 한 쌍만이 존재한다.
· 두 달 이상이 된 토끼는 번식 가능하다.
· 번식 가능한 토끼 한 쌍은 매달 새끼 한 쌍을 낳는다.
· 토끼는 죽지 않는다.

위 모델의 가설을 보시면 피보나치 수열이 떠오르시나요? 여기서 우리가 수학을 배워야 하는 이유를 말씀드릴 수 있겠네요. 만약 수학을 배우지 않아서 피보나치 수열의 개념을 모르고 있었다면 우리는 문제를 풀지 못했을 것 같아요.

위의 가설 내용을 시각적으로 표현하면 아래와 같겠네요. 태어난 지 2달 이상이 되어야 번식이 가능하므로 2개월 이후부터 새로운 쌍의 토끼가 태어납니다. 이후 새끼 토끼는 두 달간 자라서 또 번식을 하게 됩니다. 이렇게 보고 토끼 개체 수를 확인해 보면 피보나치 수열과 같게 됩니다. 

물론 이렇게 모델링을 한다고 토끼 개체 수를 완전 정확하게 예측할 수는 없을거에요. 우리는 학교에서 100%의 정답이 아니면 틀렸다는 식의 교육을 많이 받는 것 같습니다. 사실 현업에 종사하다 보면 완벽한 100%는 만들기가 거의 불가능한 것 같아요. 하지만 때론 70%만 맞춰도 잘한 것일 수 있거든요. 아예 시도를 안해서 0%보단 70% 훨씬 낫지 않나요?

 

아무튼 돌아가서 레오나르도 피보나치가 "특정 시점에서 지구에 있는 토끼 개체 수는 얼마나 존재할까?"란 문제를 해결하기 위해 피보나치 수열로 모델링 해보겠다는 아이디어는 정말 대단한 것 같아요. 저도 수학을 꾸준히 공부해서 부딪치는 문제를 다양한 시각에서 해결해 보고 싶다는 열망이 생기네요.

 

그러면 피보나치 수열로 토끼 개체 수를 예측할 수 있다는 것까지 알았다고 합시다. 그러면 "특정 시점에서 토끼 개체 수가 얼마나 돼?"라는 질문에 우리는 처음부터 숫자를 더해 나가면서 계산하면 구할 수 있을까요? 물론 가능하겠지만 만약 몇 십년 이후의 값을 계산하기 위해 매번 처음부터 더해 나가는 것은 매우 힘든 일이 될 겁니다. 그래서 컴퓨터가 없던 과거에는 대부분의 사람들이 계산 결과를 기록하여 필요할 때 열어 보거나, 추가의 계산 결과가 필요하면 또 계산하여 기록하는 일을 했을 것 같습니다.

아마도 기록 작업이 매우 불편하게 느꼈을 수학자들도 있었을 것 같네요. 그래서 불편함이 세상의 기술을 발전시켰듯이 수학자들은 피보나치 수열을 공식과 같이 풀 수 없을까를 고민했고, 결국 피보나치 수열의 일반항 공식이 세상 밖으로 나오게 되었죠.

 

피보나치 수열 일반항 공식 유도

공식을 외워서 필요할 때 사용해도 되겠지만 나중에 풀어야할 어떤 문제를 다른 모델로 해결해야 할 일이 생길 것 같아 이참에 다시 공부를 했습니다. 그래서 공부하며 정리한 부분을 간략히 포스팅하려고 해요.

피보나치 수열의 점화식

공부하다 보니 "점화식이 뭐였지?"란 생각에 처음부터 당황했네요. 수학 공부를 놓은지 진짜 오래된 것 같아요. 간단한 정의를 찾아보니 "수열에서 숫자들의 관계들을 정의한 식"이라고 하네요. 즉, $a_{n+1} = a_{n} + n$의 수식이나 $a_{n+1} = r\cdot a_{n}$ 수식과 같이 2개 이상의 수열 항의 관계로 표현된 식을 의미한답니다.

만약 $a_{n+1} = n + 1$과 같이 찾고자 하는 수열의 항이 다른 항의 관계로 표시가 되지 않으면 점화식이 아니라고 하네요.

그럼 점화식에 대한 개념 이해는 했으니 아래와 같이 피보나치 수열의 점화식을 작성할 수 있습니다.

 

$a_{n+2} = a_{n+1} + a_{n}\;(a_{1}=1, \; a_{2}=1)$

 

그럼 위 식을 어떻게 만들어야 될까요? 우리의 목표는 $n$이 몇이 되었든 그냥 바로 수식에 넣어서 $a_{n+2}$를 구하는 것입니다. 허나 현재 위의 점화식으로는 $a_{n+2}$번째의 값을 구하기 위해선 $a_{n+1}$, $a_{n}$의 값을 알아야 하네요. 그리고 또 $a_{n+1}$와 $a_{n}$을 알려면 똑같은 절차를 거쳐야 하므로 $a_{n+1}$과 $a_{n}$이 없으면 좋겠네요.

 

피보나치 수열의 일반항을 구하는 공식에 대해 검색을 하다 보니 특성방정식, 생성함수 등의 다양한 방식이 있다는 것을 알게 되었습니다. 본 포스팅에서는 특성방정식을 이용하여 풀어보려고 합니다.

 

특성방정식은 명쾌하게 설명해 놓은 곳을 찾지 못해서 개인적으로 해석하여 말씀드립니다. 특성방정식은 우리가 가진 복잡한 수식을 조금 더 풀기 쉬운 형태의 수식으로 변형할 수 있게 보조해 주는 방정식인 듯 합니다. 

 

예를들어 $a_{n} = a_{n-1} + a_{n-2}$ 점화식에 있는 항들을 어떻게든 쪼개고 이동해서 $a_{n+2} - \alpha \cdot a_{n+1} = \beta (a_{n+1} - \alpha \cdot a_{n})$의 형태로 만들어 줄 수만 있다면 아래와 같이 급수를 나열할 수 있습니다. 

 

$a_{n+2} - \alpha \cdot a_{n+1} = \beta (a_{n+1} - \alpha \cdot a_{n})$   $\cdots$  수식 (n)

$a_{n+1} - \alpha \cdot a_{n} = \beta (a_{n} - \alpha \cdot a_{n-1})$  $\cdots$  수식 (n-1)

$a_{n} - \alpha \cdot a_{n-1} = \beta (a_{n-1} - \alpha \cdot a_{n-2})$  $\cdots$  수식 (n-2)

$\cdots$

$a_{5} - \alpha \cdot a_{4} = \beta (a_{4} - \alpha \cdot a_{3})$  $\cdots$  수식 (3)

$a_{4} - \alpha \cdot a_{3} = \beta (a_{3} - \alpha \cdot a_{2})$  $\cdots$  수식 (2)

$a_{3} - \alpha \cdot a_{2} = \beta (a_{2} - \alpha \cdot a_{1})$  $\cdots$  수식 (1)

 

그리고 수식 (1)부터 (n)까지를 모두 곱하여 식을 정리하면 왼쪽 항과 오른쪽 항의 동일한 부분을 모두 지워줄 수 있고, 수식의 결과는 $a_{n+2} - \alpha \cdot a_{n+1} = \beta^{n} (a_{2} - \alpha \cdot a_{1})$ 만 남게되죠.

 

그럼 남은 일은 $a_{n+2}$나 $a_{n+1}$ 둘 중에 하나를 없애고, $\alpha$, $\beta$ 값만 알게되면 우리는 피보나치 수열의 일반항 값을 단순한 공식으로 표현할 수 있습니다.

 

돌아가서 특성방정식은 우리가 문제를 풀기 쉬운 꼴로 바꾸어 주는 보조 도구라고 했습니다. 그러면 점화식을 풀기 쉬운 형태로 바꾸어 주는 $\alpha$, $\beta$ 값들은 어떻게 찾으면 될까요? 일단 우리가 만들고 싶어하는 형태의 $\alpha$, $\beta$로 이루어진 공식을 풀어서 써보겠습니다.

 

$a_{n+2} - \alpha \cdot a_{n+1} = \beta (a_{n+1} - \alpha \cdot a_{n})$

$a_{n+2} = (\alpha + \beta) a_{n+1} - \alpha \beta a_{n}$

 

풀어쓴 위의 식과 우리가 알고 있는 피보나치 수열의 점화식을 비교해 보면 $\alpha + \beta = 1$, $\alpha \beta = -1$이라는 것을 알 수 있습니다. 그러면 $\alpha$와 $\beta$의 합이 1이고, 곱은 -1인 $\alpha$, $\beta$를 찾으면 되는데 이를 찾을 수 있게 세우는 식이 특성방정식이다로 이해를 했습니다. 

 

만약 특성방정식의 두 근이 $\alpha$, $\beta$이고, 2차식으로 구성된다고 하면 우리는 중학교 때 배운 "근과 계수와의 관계"를 통해 2차식을 완성할 수 있습니다.

 

"근과 계수와의 관계"는 $ax^2 + bx + c$라는 2차식이 있고 2개의 해를 각각 $\alpha$, $\beta$라 한다면, $\alpha + \beta = -{b \over a}$이고, $\alpha \beta = {c \over a}$이다는 것입니다. 따라서 우리는 아래와 같이 두 근의 합이 1이고, 곱이 -1 인 특성방정식을 만들 수 있고, 근의 공식을 통해 두 근인 $\alpha$와 $\beta$를 구할 수 있습니다.

 

$x^2 - x - 1$

$\therefore \alpha = {1 - \sqrt{5} \over 2}, \; \beta = {1 + \sqrt{5} \over 2}$

 

이제$\alpha$와 $\beta$는 구했고, $a_{n+2}$나 $a_{n+1}$ 둘 중에 하나를 없애는 일만 남았습니다.  

$a_{n+2} - \alpha \cdot a_{n+1} = \beta^{n} (a_{2} - \alpha \cdot a_{1})$ 식에서 변수는 2개인데 식은 하나이므로 수학적 트릭을 써서 비슷한 식을 하나 더 만들어 보겠습니다. 이렇게 트릭을 쓸 수 있는 이유는 $\alpha$와 $\beta$의 위치를 바꾸어도 우리가 원하는 형태의 수식으로 변형 가능하기 때문일 것 같아요. 만약 불가능하다면 아래와 같이 변형된 수식을 추가해서 연립하더라도 해가 구해지지 않을 것 같아요. (수학 전공이 아니라 맞는지는 모르겠네요.)

 

$a_{n+2} - \alpha \cdot a_{n+1} = \beta^{n} (a_{2} - \alpha \cdot a_{1})$ 

$a_{n+2} - \beta \cdot a_{n+1} = \alpha^{n} (a_{2} - \beta \cdot a_{1})$

 

위 식을 연립했을 때, 남는 항이 $a_{n}$이 되도록 하고 싶기에 아래와 같이 보정을 한번 해줄게요.

 

$a_{n+1} - \alpha \cdot a_{n} = \beta^{n-1} (a_{2} - \alpha \cdot a_{1})$   $\cdots$ 수식 (a)

$a_{n+1} - \beta \cdot a_{n} = \alpha^{n-1} (a_{2} - \beta \cdot a_{1})$   $\cdots$ 수식 (b)

 

위에 수식 (1)~(n)개를 나열한 부분에서 수식 (n)만 지우고 계산한 결과라 생각하시면 편합니다. 그럼 식이 1개가 줄어든 것이니까 $\beta$는 n-1개만 곱해진 결과가 되겠죠.

 

이제 "수식 (a) - 수식 (b)"를 통해 $a_{n}$만 남기고 정리해 보겠습니다.

 

$ ( \beta - \alpha ) \cdot a_{n} = \beta^{n-1} \cdot ( a_{2} - \alpha a_{1} ) - \alpha^{n-1} \cdot ( a_{2} - \beta a_{1} )$

 

$\alpha \ne \beta$이므로 왼쪽 항의 $\beta - \alpha$는 0이 아니라 나눠줄 수 있습니다.

 

$ a_{n} = {\beta^{n-1} \over ( \beta - \alpha ) }\cdot ( a_{2} - \alpha a_{1} ) - { \alpha^{n-1} \over ( \beta - \alpha ) }\cdot ( a_{2} - \beta a_{1} )$

 

그리고 우리는 위에서 $a_{1} = 1, \; a_{2} = 1$로 초기 조건을 설정한 바 있습니다. 넣어서 정리하면 아래처럼 됩니다.

 

$ a_{n} = {\beta^{n-1} \over ( \beta - \alpha ) }\cdot ( 1 - \alpha ) - { \alpha^{n-1} \over ( \beta - \alpha ) }\cdot ( 1 - \beta  )$

 

이제 우리가 구한 $\alpha$, $\beta$를 위 식에 넣고, n번째의 피보나치 수열항을 구할 수 있지만 식이 아직 깔끔하지가 않아 조금 더 만지고 싶네요. $\alpha + \beta = 1$ 이니까 $ 1 - \alpha = \beta$,  $ 1 - \beta = \alpha$가 되네요. 그러면 아래와 같이 마저 식을 정리할 수 있습니다.

 

$ a_{n} = {\beta^{n-1} \over ( \beta - \alpha ) }\cdot ( \beta ) - { \alpha^{n-1} \over ( \beta - \alpha ) }\cdot ( \alpha  )$

$ a_{n} = {\beta^{n} \over ( \beta - \alpha ) } - { \alpha^{n} \over ( \beta - \alpha ) }$

$ a_{n} = {1 \over {\beta - \alpha}} \cdot ( \beta^{n} - \alpha^{n})$

 

이제 모두 다 끝났습니다. 근의 공식을 통해 구한 $\alpha$, $\beta$를 넣고 정리하면 $\beta - \alpha = \sqrt{5}$이므로 아래와 같이 피보나치 일반항 공식 유도를 마칠 수 있습니다.

 

$ { \frac{1}{\sqrt{5}} }  ( ( {1 + \sqrt{5} \over {2} } )^{n} - ( {1 - \sqrt{5} \over {2} } )^{n} ) $

 

그럼 피보나치 수열에 대한 공식 유도는 마치고, 코드로 살펴 보아요~

3. 코드 구현 및 성능 비교

3-1. 재귀함수 이용

아래 코드는 함수를 재귀적으로 만들었습니다. 즉 40번 째의 피보나치 행의 값을 구하기 위해서 n에 40을 넣고 그러면 return 하는 곳에서 함수 인자가 각각 n=39, n=38이 들어가는 같은 함수를 추가로 돌립니다. 그리고 n=39는 n=38, n=37인 함수를 또 호출하며, n=38는 n=37, n=36인 함수를 또 호출하게 되죠. 이러면 속도 측면에서 엄청난 성능 저하가 발생하게 됩니다.

이를 Big-O 표기법에선 O($N^{2}$)이라 하고, 우리가 다소 피해서 프로그래밍해야 할 부분인 것 같네요.

아래에서 40번째의 피보나치 수열 값을 구할 때 소요된 시간은 약 28초 정도였습니다.

import time

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

start_time = time.time()

print(recursive_fibonacci(40))

elapsed_time = time.time() - start_time

print("총 소요시간: {}초".format(elapsed_time))

>>> 102334155
>>> 총 소요시간: 28.366228818893433초

3-2. 반복문 이용

피보나치 수열을 또 다른 방식으로 구하기 위해 함수를 반복문으로 만들었습니다. 이렇게 구하는 방식은 for 문 1개 밖에 없으므로 O($N$)인 복잡도를 가질 것입니다. 즉 n의 크기에 따라 계산 속도가 선형적으로 비례하는 함수이죠. 재귀함수보다 코드도 이해하기 쉽고, 속도도 매우 빨라 이렇게 하는 방식으로 구현하는게 좋을 것 같네요.

import time

def iter_fibonacci(n):
    a, b = 1, 1
    if n < 2:
        return 1
    else:
        for i in range(n-2):
            c = a + b
            a, b = b, c
        return c   
  
start_time = time.time()

print(iter_fibonacci(40))

elapsed_time = time.time() - start_time

print("총 소요시간: {}초".format(elapsed_time))

>>> 102334155
>>> 총 소요시간: 0.0초

3-3. 수식 이용

아래 방식은 위에서 유도한 공식을 통해 피보나치의 일반항을 구한 것입니다. 계산 결과는 소수점이 나오긴 하지만 정수로 바꾸면 위에서 구한 코드들과 동일한 값이 나오게 됩니다. 공식으로 계산하는 것이다 보니 소수점이 나올 수 밖에 없죠. 이 방식도 속도가 좋아서 재귀함수보단 이렇게 구현하는 것을 것 같아요.

import time

def equation_fibonacci(n):
    root_5 = 5 ** (1/2)
    return (1 / root_5) * ( ( (1 + root_5) / 2)**n - ( (1 - root_5) / 2)**n )

start_time = time.time()

print(equation_fibonacci(40))

elapsed_time = time.time() - start_time

print("총 소요시간: {}초".format(elapsed_time))

>>> 102334155.00000013
>>> 총 소요시간: 0.0초

4. 마치며

재귀함수, 반복문, 수식 이용 방법 중에서는 반복문을 사용하는 것이 제일 좋은 것 같습니다. 일단 속도 측면에서 재귀함수 방법은 무조건 버리고, 반복문, 수식 방법에서는 속도 측면에서는 차이가 거의 없었으나 n이 약 1,500 이상에서는 수식으로 계산할 때 OverflowError: (34, 'Result too large') 오류가 발생하네요. 아마도 큰 수를 한 방에 계산해야 하므로 컴퓨터 메모리에 부하가 걸리는 것 같아요.

반면, 반복문 방법을 확인한 결과, n이 20,000을 넘어서도 약 0.005초 정도의 시간만 소요되며 계산이 잘되네요.

아직은 컴퓨터 구조에 대해서 잘 모르다 보니 "반복문"과 "수식" 방식이 컴퓨터에서 어떻게 돌아가는지 모르겠어서 왜 저런 결과가 발생하는지는 앞으로 알아봐야 할 숙제인 것 같아요.

사실 성능은 수식으로 푼 것이 가장 좋을 것으로 기대했고, 그래서 우리가 수학을 배워야 한다고 말하고 싶어서 기획한 포스팅인데 제 생각과는 다른 결과가 나와서 알쏭달쏭하면서도 재밌네요. 역시 무엇이든 직접해봐야 많이 배우는 것 같습니다.

 

긴 내용 읽어주셔서 감사드립니다. 내용이 도움되셨다면 "좋아요" 버튼 부탁드립니다.
문의사항과 잘못된 정보에 대한 지적은 언제든지 환영입니다. ^^