1. 피보나치 수열?
다음 문제들을 살펴보고 공통점을 생각해봅시다.
한번에 한 칸 또는 두 칸의 계단을 올라갈 수 있습니다.
이 때, n칸을 올라가는 경우의 수는 몇 가지일까요?
n개의 육각형이 두 줄로 그림과 같이 배치되어 있습니다.
인접한 칸으로 이동이 가능하고, 현재 칸보다 숫자가 더 큰 칸으로 이동할 수 있습니다.
1에서 n까지 이동하는 경우의 수는 몇 가지일까요?
첫번째 달에는 어린 암수 토끼 한 쌍이 있습니다.
어린 암수 토끼 한 쌍은 한 달이 지나면 다 큰 암수 토끼 한 쌍이 됩니다.
다 큰 암수 토끼 한 쌍은 한 달이 지나면 어린 암수 토끼 한 쌍을 낳습니다.
n번째 달에는 토끼가 몇 쌍일까요?
문제는 모두 다르지만, 모든 문제의 공통점은 n번째의 수가 (n-1)번째와 (n-2)번째를 더한 수가 된다는 것입니다.
이렇게 첫째항과 둘째항이 1이며, 그 뒤의 모든 항이 바로 앞 두 항의 합인 수열을 피보나치 수열이라고 합니다.
편의상 0번째 항을 0으로, 첫번째 항을 1로 두기도 합니다.
2. 재귀로 피보나치 수열 구하기
def fibo(n):
if n == 0 or n == 1:
return n
return fibo(n-1) + fibo(n-2)
for i in range(10):
print(i+1, fibo(i+1)) # 1 ~ 10
# 1 1
# 2 1
# 3 2
# 4 3
# 5 5
# 6 8
# 7 13
# 8 21
# 9 34
# 10 55재귀 함수로 피보나치 수열을 구하는 코드입니다.
가장 직관적이고 코드가 간결하다는 장점이 있습니다.
하지만 함수가 한 번 실행될 때마다 재귀적으로 두 번을 호출하므로, 시간복잡도가 \(O(2^n)\)으로 굉장히 느립니다.
처음에 n으로 시작해서 점점 작은 값으로 쪼개어 해결하는 방식으로, 이런 방식을 탑다운(Top-down, 하향식) 방식이라고 합니다.
3. 반복문으로 피보나치 수열 구하기
def fibo(n):
if n == 0 or n == 1:
return n
a, b = 0, 1
i = 1
while i < n:
a, b = b, a+b
i += 1
return b
for i in range(10):
print(i+1, fibo(i+1)) # 1 ~ 10
# 1 1
# 2 1
# 3 2
# 4 3
# 5 5
# 6 8
# 7 13
# 8 21
# 9 34
# 10 55반복문을 통해 순차적으로 n까지 값을 만들어 갑니다.
재귀 함수보다 코드가 다소 길어졌지만, 어렵지 않습니다.
파이썬의 특징 중의 하나인 다중 할당(Multiple Assignment)도 살펴볼 수 있습니다.
순차적으로 n까지 진행되므로 시간복잡도는 \(O(n)\)이며, 재귀를 사용한 코드보다 훨씬 빠릅니다.
작은 값부터 구해가며 점점 n까지 큰 값을 구해가는 과정으로, 이런 방식을 바텀업(Bottom-up, 상향식) 방식이라고 합니다.
4. 동적 계획법(재귀)으로 피보나치 수열 구하기
def fibo(n):
memo = [-1] * (n+1)
memo[0], memo[1] = 0, 1
def recur(n):
if memo[n] == -1:
memo[n] = recur(n-1) + recur(n-2)
return memo[n]
recur(n)
return memo
print(fibo(10))
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]재귀 함수를 사용한 코드에 동적 계획법을 적용하였습니다.
한번 계산한 결과를 저장해놓고 다시 계산할 필요가 있을 때 가져다 쓰므로 계산 횟수를 줄여주는 방식입니다.
큰 문제를 해결하기 위해 작은 문제로 쪼개어 가며 계산하므로 탑다운(Top-down, 하향식) 방식입니다.
문제가 점차 해결되어 가며 memo 변수에 할당된 배열의 값들이 채워지게 되는데, 이렇듯 탑다운 방식으로 채워지는 방식을 메모이제이션(Memoization)이라고 합니다.
길이가 n인 배열을 채워가며 계산 과정이 진행되므로 시간복잡도는 \(O(n)\)입니다.
5. 동적 계획법(반복문)으로 피보나치 수열 구하기
def fibo(n):
memo = [-1] * (n+1)
memo[0], memo[1] = 0, 1
for i in range(2, n+1):
memo[i] = memo[i-1] + memo[i-2]
return memo
print(fibo(10))
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]반복문을 사용한 코드에 동적 계획법을 적용하였습니다.
작은 값을 구해가며 그 결과를 이용해 점차 큰 값을 구하므로 바텀업(Bottom-up, 상향식) 방식입니다.
앞서 살펴본 메모이제이션과는 다르게 단순하게 memo 변수에 할당된 배열의 앞에서부터 차례대로 값을 채워갑니다.
이런 방식을 표를 채워가는 것과 같다고 하여 타뷸레이션(Tabulation)이라고 합니다.
길이가 n인 배열을 차례대로 채워가므로 시간복잡도는 \(O(n)\)입니다.
6. 분할 정복으로 피보나치 수 구하기
피보나치 수열은 그 정의에 의해 다음을 만족합니다.
\(a_{n} = a_{n-1} + a_{n-2}\)
그러면 당연히 다음도 만족합니다.
\(a_{n-1} = a_{n-2} + a_{n-3}\)
따라서 두 식을 합치면 다음과 같이 됩니다.
\(a_{n} = (a_{n-2} + a_{n-3}) + a_{n-2} = 2a_{n-2} + a_{n-3}\)
계속해서 반복하면 다음과 같이 됩니다.
\(a_{n} = 2(a_{n-3} + a_{n-4}) + a_{n-3} = 3a_{n-3} + 2a_{n-4}\)
\(a_{n} = 3(a_{n-4} + a_{n-5}) + 2a_{n-4} = 5a_{n-4} + 3a_{n-5}\)
\(a_{n} = 5(a_{n-5} + a_{n-6}) + 3a_{n-5} = 8a_{n-5} + 5a_{n-6}\)
...
과정을 통해 살펴보니, 계수가 피보나치 수열을 이루는 것을 볼 수 있습니다.
따라서 다음과 같이 일반화 할 수 있습니다.
\(a_{n} = a_{i+1} \cdot a_{n-i} + a_{i} \cdot a_{n-(i+1)}\)
n에 2i와 2i+1을 대입해보면 다음과 같은 식을 도출해낼 수 있습니다.
\(a_{2i} = a_{i+1} \cdot a_{i} + a_{i} \cdot a_{i-1}\)
\(a_{2i+1} = {a_{i+1}}^{2} + {a_{i}}^{2}\)
첫 번째 식을 이해해보면, 피보나치 수열에서 i 번째 항과 그 앞, 뒤 항을 알면 2i 번째 항도 바로 알 수 있다는 뜻입니다.
두 번째 식을 보면, 피보나치 수열에서 i 번째 항과 그 다음 항을 가지고 2i+1 번째 항을 구할 수 있습니다.
그리고 두 번째 식의 i에 (i-1)을 대입하면 다음과 같은 식을 구할 수 있습니다.
\(a_{2i-1} = {a_{i}}^{2} + {a_{i-1}}^{2}\)
이 식으로 피보나치 수열에서 i 번째 항과 그 이전 항을 가지고 2i-1 번째 항을 구할 수 있습니다.
더 쉬운 방법으로 2i+1 번째에서 2i 번째를 빼면 2i-1 번째를 구할 수 있습니다.(이전 값 두 개를 더하면 다음 값이 되므로...)
이제 구하고자 하는 n 번째에서 반으로 나누어 가며, 탑다운(Top-down, 하향식) 방식으로 분할 정복하면 해결됩니다.
주의할 점은 반으로 나눌 때, 1이 남는다면 i번째를 통해 (2i-1 번째, 2i 번째, 2i+1 번째)가 아닌 (2i 번째, 2i+1 번째, 2i+2 번째)를 구하면 됩니다.
2i+2 번째는 2i 번째와 2i+1 번째의 합으로 구할 수 있습니다.
이 방식은 반으로 나누어 가며 계산되기 때문에 시간복잡도가 \(O(\log_{2}{n})\)입니다.
또 이것을 행렬을 이용해 간단하게 표현하면 다음과 같습니다.
\(\begin{pmatrix}a_{n+1} & a_{n} \\ a_{n} & a_{n-1}\end{pmatrix} = \begin{pmatrix}a_{2} & a_{1} \\ a_{1} & a_{0}\end{pmatrix}^{n} = \begin{pmatrix}1 & 1 \\ 1 & 0\end{pmatrix}^{n} \)
코드는 다음과 같습니다.
def fibo(n):
if n == 1:
return (0, 1, 1)
a, b, c = fibo(n//2)
B = a*b + b*c
C = b*b + c*c
if n % 2 == 0:
return (C-B, B, C)
return (B, C, B+C)
print(fibo(100))
# 99, 100, 101 번째 값을 반환
# (218922995834555169026, 354224848179261915075, 573147844013817084101)7. 일반항으로 피보나치 수 구하기
피보나치 수열도 일반항을 구할 수 있습니다.
피보나치 수열의 일반항은 다음과 같습니다.
\(
a_{n} = \dfrac {1} {\sqrt{5}} \Bigg( \bigg(\dfrac {1 + \sqrt{5}} {2}\bigg)^{n} - \bigg(\dfrac {1 - \sqrt{5}} {2}\bigg)^{n} \Bigg)
\)
이 일반항을 어떻게 구하는지 차근차근 살펴봅시다.
먼저 더하면 1, 곱하면 -1이 되는 두 수를 \(\alpha\), \(\beta\)라고 해봅시다.(\(\alpha + \beta = 1\), \(\alpha\beta = -1\))
그러면 피보나치 수열의 점화식을 다음과 같이 바꿀 수 있습니다.
\(
\begin{align*}
a_{n} &= a_{n-1} + a_{n-2} \\
\\
a_{n} - a_{n-1} &= a_{n-2} \\
\\
a_{n} - (\alpha + \beta)a_{n-1} &= -\alpha \beta a_{n-2}\\
\\
a_{n} - \beta a_{n-1} &= \alpha (a_{n-1} - \beta a_{n-2})
\end{align*}
\)
이 식은 좌변의 n이 1 작아진 값에 \(\alpha\)를 곱하면 우변이 되므로, 다음과 같이 거듭해서 n을 줄여갈 수 있습니다.
\(a_{n} - \beta a_{n-1} = \alpha (a_{n-1} - \beta a_{n-2}) \)
\(\qquad \qquad \quad = \alpha^{2} (a_{n-2} - \beta a_{n-3}) \)
\(\qquad \qquad \quad = \alpha^{3} (a_{n-3} - \beta a_{n-4}) \)
\(\qquad \qquad \quad ... \)
\(\qquad \qquad \quad = \alpha^{n-1} (a_{1} - \beta a_{0}) \)
\(\qquad \qquad \quad = \alpha^{n-1} \)
피보나치 수열의 1 번째 항과 0 번째 항은 각각 1과 0이므로 위와 같은 식이 만들어집니다.
\(\alpha\)와 \(\beta\)를 서로 바꾸어도 같으므로, 다음과 같은 두 식이 만들어지고 n을 n+1로 바꾼 후 두 식을 빼면 아래의 식이 나옵니다.
\(a_{n} - \beta a_{n-1} = \alpha^{n-1} \)
\(a_{n} - \alpha a_{n-1} = \beta^{n-1} \)
\(
\begin{align*}
a_{n+1} - \beta a_{n} &= \alpha^{n} \\
- \quad a_{n+1} - \alpha a_{n} &= \beta^{n} \\
\hline
(\alpha - \beta) a_{n} &= \alpha^{n} - \beta^{n}
\end{align*}
\)
\( a_{n} = \dfrac {\alpha^{n} - \beta^{n}} {\alpha - \beta} \)
이제 \(\alpha\)와 \(\beta\)의 값만 구해서 대입하면 됩니다.
\(\alpha\)와 \(\beta\)는 이차방정식 \((x-\alpha)(x-\beta) = 0\) 의 해입니다.
즉, 이차방정식 \(x^{2} -(\alpha + \beta)x + \alpha \beta = 0\) 의 해입니다.
\(\alpha\)와 \(\beta\)는 더해서 1, 곱해서 -1이 되는 두 수이므로, 이차방정식 \(x^{2} -x -1 = 0\) 의 해가 됩니다.
근의 공식을 이용해 해를 구하면, \( x = \dfrac {1 \pm \sqrt{5}} {2}\) 가 되고 위 식의 \(\alpha\)와 \(\beta\)에 대입하면 다음과 같은 일반항을 구할 수 있습니다.
\(a_{n} = \dfrac {1} {\sqrt{5}} \Bigg( \bigg(\dfrac {1 + \sqrt{5}} {2}\bigg)^{n} - \bigg(\dfrac {1 - \sqrt{5}} {2}\bigg)^{n} \Bigg)\)
피보나치 수열은 모두 정수로만 이루어져 있습니다.
그런데 일반항에는 무리수가 들어가는 것이 참 신기합니다.
또한 피보나치 수열의 이웃한 두 수의 비의 극한값을 이 일반항을 통해 구할 수 있는데, 그 값이 황금비가 됩니다.
이 일반항을 파이썬 코드로 구현하면 다음과 같습니다.
import math
def fibo(n):
sqrt_5 = math.sqrt(5)
res = (1 / sqrt_5) * (((1 + sqrt_5) / 2)**n - ((1 - sqrt_5) / 2)**n)
return round(res)
print(fibo(100))
# 354224848179263111168
# 오차 발생!이렇게 구한 값은 n이 커지면 오차가 발생합니다.
무리수를 계산하는 과정에서 부동소수점 연산의 한계로 인해 오차가 발생하게 됩니다.
이 코드의 시간복잡도는 n만큼의 지수 연산이 필요하므로 \(O(\log{n})\)입니다.
