1. 피보나치 수열
수학적인 개념에서 피보나치 수(Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열을 말한다. 즉 처음 여섯 항은 1, 1, 2, 3, 5, 8이며 그 뒤로 쭉 이어진다. 또한 프로그래밍에서 인덱스가 0부터 시작하는 것과 함께 0번째 항을 0으로 두기도 한다.
피보나치 수를 표현하는 식으로 아래와 같이 정의할 수 있다.
F(1) = F(2) = 1
F(n) = F(n-1) + F(n-2)
그리고 0번째 항부터 시작할 경우는 아래와 같이 정의할 수 있다.
F(0) = 0, F(1) = 1
F(n) = F(n-1) + F(n-2)
2. 피보나치 수열 파이썬 구현
피보나치 수의 개념에 따라 파이썬 코드로 구현을 해본다. 피보나치 수를 구현하는 방법은 여러 방법이 존재한다. 그중 반복문을 사용하는 방법, 재귀함수를 사용하는 방법, 재귀함수에 메모이제이션 기법을 적용한 방법을 알아보며 각 구현 방식의 성능 차이점에 대해 알아보도록 하겠다.
2.1. 피보나치 수열 반복문 함수 - fibonacci for loop function
파이썬에서 반복문을 사용해 피보나치 수열을 구할 때는 튜플 패킹(packing)과 언패킹(unpacking)을 이용해 두 값을 반복문에서 지속적으로 변경하며 피보나치 수를 구한다.
반복문으로 피보나치 수열 함수를 구현할 경우 수학에서의 점화식과는 약간 다른 모습으로 코드를 작성해 가독성이 떨어지나 가장 효율적인 연산을 한다.
fibo_for(n)은 n번의 연산을 한다.
예제 코드
# fibonacii for loop function (반복문 함수)
# 변수 정의
count = 0 # 계산 카운트
fibo = 7 # fibonacci 7번째 값
# 함수 정의
def fibo_for(n):
global count
_cur, _next = 0, 1
for i in range(n):
count += 1
print(f'for loop[{i}] _cur: {_cur}, _next: {_next}, count: {count}')
_cur, _next = _next, _cur + _next
return _cur
# 결과 출력
print('-'*10+f'\nfibo_rec({fibo}): {fibo_for(fibo)} 계산에 활용된 반복 횟수는 {count}번입니다.\n'+'-'*10)
print()
코드 실행 결과
for loop[0] _cur: 0, _next: 1, count: 1
for loop[1] _cur: 1, _next: 1, count: 2
for loop[2] _cur: 1, _next: 2, count: 3
for loop[3] _cur: 2, _next: 3, count: 4
for loop[4] _cur: 3, _next: 5, count: 5
for loop[5] _cur: 5, _next: 8, count: 6
for loop[6] _cur: 8, _next: 13, count: 7
----------
fibo_rec(7): 13 계산에 활용된 반복 횟수는 7번입니다.
----------
2.2. 피보나치 수열 재귀함수 - fibonacci recursive function
재귀함수(Resursive Function)란 프로그래밍에서 함수를 정의할 때 자기 자신을 재귀호출(Recursive Call) 하는 함수이다.
재귀함수로 피보나치 수열을 구현할 경우 수학에서의 점화식과 비슷한 형태로 코드를 작성할 수 있기 때문에 가독성이 높아진다. 그러나 재귀함수의 특성상 연산 효율이 떨어진다는 것이 단점인데, 이것은 인덱스 숫자(피보나치 수 몇 번째 값)가 높아질수록 연산 효율이 급격하게 떨어진다는 것이 가장 큰 문제점이다.
예를 들어 fibo_rec(10)은 109번의 연산, fibo_rec(11)은 177번의 연산을 한다. 이렇게 되는 이유는 피보나치 수열의 점화식인 f(n) = f(n-1) + f(n-2)를 구하기 위해 f(1) = 1, f(2) = 1라는 정해진 값까지 도달해서 그 값들을 더한 값이 결과가 되기 때문에 이미 구해진 값이더라도 불필요한 연산을 수행하게 되기 때문이다.
재귀라는 말을 처음 듣는 경우 잘 이해가 안 될 수도 있기 때문에 간단한 예를 들자면 화면 녹화 프로그램에서 녹화 프로그램을 출력할 경우 작은 화면이 무한히 들어가며 출력되는 것을 생각하면 이해하기 쉽다.
# fibonacii recursive function (재귀 함수)
counter = 0
fibo = 7
# 함수 정의
def fibo_rec(n):
global count
count += 1
print(f'fibo_rec({n}) 호출, count: {count}')
if n == 1:
return 1
if n == 2:
return 1
else:
return fibo_rec(n-1) + fibo_rec(n-2)
# 결과 출력
print('-'*10+f'\nfibo_rec({fibo}): {fibo_rec(fibo)} 계산에 활용된 함수 호출 횟수는 {count}번입니다.\n'+'-'*10)
print()
코드 실행 결과
fibo_rec(7) 호출, count: 1
fibo_rec(6) 호출, count: 2
fibo_rec(5) 호출, count: 3
fibo_rec(4) 호출, count: 4
fibo_rec(3) 호출, count: 5
fibo_rec(2) 호출, count: 6
fibo_rec(1) 호출, count: 7
fibo_rec(2) 호출, count: 8
fibo_rec(3) 호출, count: 9
fibo_rec(2) 호출, count: 10
fibo_rec(1) 호출, count: 11
fibo_rec(4) 호출, count: 12
fibo_rec(3) 호출, count: 13
fibo_rec(2) 호출, count: 14
fibo_rec(1) 호출, count: 15
fibo_rec(2) 호출, count: 16
fibo_rec(5) 호출, count: 17
fibo_rec(4) 호출, count: 18
fibo_rec(3) 호출, count: 19
fibo_rec(2) 호출, count: 20
fibo_rec(1) 호출, count: 21
fibo_rec(2) 호출, count: 22
fibo_rec(3) 호출, count: 23
fibo_rec(2) 호출, count: 24
fibo_rec(1) 호출, count: 25
----------
fibo_rec(7): 13 계산에 활용된 함수 호출 횟수는 25번입니다.
----------
2.3. 피보나치 수열 재귀함수 메모이제이션 - fibonacci recursive function memoization
메모이제이션(memoization)이란 재귀함수에서 이미 연산했던 값은 더 이상 연산하지 않아 불필요한 연산을 제거하여 연산을 효율적으로 하며 재귀함수 형식을 따라 가독성이 높은 코드를 작성하기 위한 기법이다.
메모이제이션 기법을 사용한 코드의 연산 효율을 살펴보면 n번째 피보나치 수를 구하는 함수의 연산 횟수는 (n * 2 - 3) 번이다. 예시로 fibo_memo(10)의 경우 (10 * 2 - 3) = 17번의 연산, fibo_memo(11)의 경우 (11 * 2 - 3) = 19번의 연산을 한다.
# fibonacci recursive function memoization (재귀함수 메모화)
# 변수 정의
count = 0 # 계산 카운트
fibo = 7 # fibonacci 7번째 값
dictionary = { # 이미 계산한 값을 저장할 딕셔너리
1: 1,
2: 1
}
# 함수 정의
def fibo_memo(n):
global count
count += 1
print(f'fibo_memo({n}) 호출, count: {count}')
if n in dictionary:
return dictionary[n]
else:
dictionary[n] = fibo_memo(n-1) + fibo_memo(n-2)
print(dictionary)
return dictionary[n]
# 결과 출력
print('-'*10+f'\nfibo_memo({fibo}): {fibo_memo(fibo)} 계산에 활용된 함수 호출 횟수는 {count}번입니다.\n'+'-'*10)
print()
코드 실행 결과
fibo_memo(7) 호출, count: 1
fibo_memo(6) 호출, count: 2
fibo_memo(5) 호출, count: 3
fibo_memo(4) 호출, count: 4
fibo_memo(3) 호출, count: 5
fibo_memo(2) 호출, count: 6
fibo_memo(1) 호출, count: 7
{1: 1, 2: 1, 3: 2}
fibo_memo(2) 호출, count: 8
{1: 1, 2: 1, 3: 2, 4: 3}
fibo_memo(3) 호출, count: 9
{1: 1, 2: 1, 3: 2, 4: 3, 5: 5}
fibo_memo(4) 호출, count: 10
{1: 1, 2: 1, 3: 2, 4: 3, 5: 5, 6: 8}
fibo_memo(5) 호출, count: 11
{1: 1, 2: 1, 3: 2, 4: 3, 5: 5, 6: 8, 7: 13}
----------
fibo_memo(7): 13 계산에 활용된 함수 호출 횟수는 11번입니다.
----------
3. Summary
본문에서 피보나치 수열을 구현하는 세 가지 방식에 대해 살펴봤다. 각 방법마다 장단점이 존재하는데 '어떤 코드 구현 방식이 최고다' 또는 '무조건 이런 방식으로만 구현해야 한다'라는 것이 아니라 필요에 따라 적재적소에 맞는 코드를 구현하고 활용할 수 있어야 한다고 생각한다.
아래 표는 세 가지 방법의 연산 횟수 차이점을 비교한 것이다.
| 15번째 피보나치 수 구현 방식 | 연산 횟수 |
| fibo_for(15) | 15 |
| fibo_rec(15) | 1219 |
| fibo_memo(15) | 27 |
이와 같이 같은 기능을 하는 코드를 구현할 때 다양한 방식이 존재하고 차이점을 이해하며 개발자로서의 안목을 넓혀가는 것이 개발자로서 자신의 실력과 가치를 높이는 방법이라고 생각한다.
