가장 널리 알려진 알고리즘 중의 하나인 피보나치(Fibonacci) 알고리즘에 대해서 알아보겠습니다.
피보나치 수열
피보나치 수열에서는 첫 번째 항은 0, 두 번째 항은 1, 그 다음부터는 바로 전 두 항의 숫자의 합이 현재 항의 값이 됩니다. 따라서 피보나치나 수열은 다음과 같은 모습을 가지게 됩니다.
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...]재귀 알고리즘
피보나치 수열을 구현하는 가장 흔한 알고리즘은 재귀(recursion)를 사용하는 것입니다.
재귀 알고리즘에 대한 일반적인 설명은 별도 글에서 자세히 다루고 있습니다.
def fib(n):
if n == 0:
return 0
if n == 1:
return 1
return fib(n - 1) + fib(n - 2)
if __name__ == "__main__":
for n in range(20):
print(fib(n), end=", ")0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181,이 재귀 알고리즘의 시간과 공간 복잡도는 모두 O(2^N)으로 매우 비효율적입니다.
즉, 재귀 함수의 인자로 넘기는 숫자가 커지면 실행 시간이 비약적으로 증가하게 됩니다.
프로그램을 실행하는 컴퓨터마다 다르겠지만, 이 재귀 함수에 30 이상의 값을 넘기면 실행 속도가 현저히 느려질 것입니다.
재귀 함수가 어떻게 호출이 되는지 트리로 그려보면, 중복 계산이 상당히 많이 일어나는 것을 알 수 있습니다.
예를 들어, fib(5)를 호출하면 fib(3)는 두 번, fib(2)는 세 번, fib(1)은 다섯 번이나 반복해서 호출됩니다.
fib(5) => 3 + 2 = 5
fib(4) => 2 + 1 = 3
fib(3) => 1 + 1 = 2
fib(2) => 1 + 0 = 1
fib(1) => 1
fib(0) => 0
fib(1) => 1
fib(2) => 1 + 0 = 1
fib(1) => 1
fib(0) => 0
fib(3) => 1 + 1 = 2
fib(2) => 1 + 0 = 1
fib(1) => 1
fib(0) => 0
fib(1) => 1반복 알고리즘
재귀 알고리즘으로 작성된 프로그램은 많은 경우 스택(stack)을 이용하면 반복 알고리즘으로 전활할 수 있습니다.
def fib(n):
total = 0
stack = [n]
while stack:
n = stack.pop()
if n < 2:
total += n
else:
stack.append(n - 1)
stack.append(n - 2)
return total위 코드의 시간/공간 복잡도는 맨 처음에 작성한 재귀 함수와 동일하지만 스택오퍼플로우(stack overflow)를 방지할 수 있는 이점이 있습니다.
메모이제이션
위 재귀 트리를 관찰해보면 결국 fib(5)를 계산하기 위해서 필요한 것은 fib(4), fib(3), fib(2), fib(1)의 결과 값이라는 것을 알 수 있습니다.
따라서, 이 결과 값을 어딘 가에 저장해놓고 재활용할 수 있다면 중복 계산을 피할 수 있을 것 입니다.
흔히 이러한 프로그래밍 기법을 메모이제이션(memoization)이라고 합니다.
def fib(n):
memo = {0: 0, 1: 1}
def helper(n):
if n not in memo:
memo[n] = helper(n - 1) + helper(n - 2)
return memo[n]
return helper(n)위 코드는 memo 변수에 사전(dictionary)을 할당해놓고, 각 숫자의 계산 결과를 저장해고 있습니다.
주어진 숫자의 계산 결과가 사전에 저장되어 있지 않은 경우에만 재귀 호출을 하기 때문에 훨씬 효율적입니다.
이 알고리즘은 시간과 공간 복잡도는 모두 O(N) 입니다.
왜냐하면 함수 호출 횟수와 저장 데이터의 크기가 주어진 숫자에 비례하기 때문입니다.
동적 계획법
메모이제이션을 사용한 알고리즘의 성능도 나쁘지는 않지만 추가적인 공간 최적화를 해보도록 하겠습니다. 피보나치 수열을 어떻게 계산되는지를 유심히 생각해보면 굳이 모든 수에 대한 계산 결과를 저장해둘 필요가 없다는 사실을 깨닫게 됩니다. 왜냐하면 실제로 매 단계 필요한 것은 단지 전 단계와 바로 전전 단계의 계산 결과이기 때문입니다. 결국, 두 개의 변수만 있다면 계속해서 매 단계 저장된 값을 바뀌가면서 재사용할 수 있습니다.
이렇게 더 적은 입력에 대한 답을 먼저 구해서 저장해놓고, 더 큰 입력에 대한 답을 구할 때 활용하는 풀이 기법을 동적 계획법 (Dynamic Programming)이라고 하죠.
def fib(n):
p2, p1 = 0, 1
for i in range(n):
p2, p1 = p1, p2 + p1
return p2이 알고리즘은 고정된 크기의 메모리만 사용하므로 공간 복잡도가 O(1)이 됩니다.