피보나치 수열 (1)
Fibonacci Number(피보나치 수열)은 0과 1로 시작하며, 다음 피보나치 수는 바로 앞의 두 피보나치 수의 합이 되는 수열이다. 피보나치 수열은 점화식으로 표현할 수 있기 때문에 재귀함수로 구현할 수 있다. 그리고 재귀적 호출이 2번 일어나기 때문에 동적 프로그래밍 기법을 사용하면 더 효율적으로 구현하는 것이 가능하다.
Fibonacci Number
피보나치 수열은 아래 점화식1으로 쉽게 설명할 수 있다.
피보나치 수열의 n번째 항은 n-1, n-2번째 항의 합이다. 재귀함수 기법으로 파이썬으로 구현하면 아래와 같다.
def fibonacci(index):
if index < 2:
return index
return fibonacci(index - 1) + fibonacci(index - 2)
가독성이 좋은 깔끔한 코드이다. 하지만 재귀함수를 2번이나 호출하기 때문에 시스템에 부하가 많이 걸린다. 게다가 n번째 항의 피보나치 수를 계산하기 위해서 2^n번의 피보나치 함수를 호출해야 한다. 즉, 시간복잡도가 O(2^n)이라는 소리다. 이는 O(n^2)보다도 나쁜 시간복잡도이다.
피보나치 수열의 최적화를 위해서 동적 프로그래밍 기법을 사용해보았다.
Dynamic Algorithm
동적 알고리즘의 아이디어를 한마디로 정리하면 아래와 같을 것이다.
이미 계산된 값이 있다면 2번 계산하지 말고 메모리에 저장해놓았다가 꺼내 쓰면 어떨까?
동적 프로그래밍은 이미 계산한 결과를 별도의 메모리에 저장해 둔다. 그리고 나중에 그 결괏값을 다시 사용해야 할 때 연산하는 과정 대신 메모리 접근을 통해 값을 얻는다. 이렇게 하면 상수항 시간 내에 연산을 할 수 있게 된다.
이를 위해 위 코드를 함수 호출에 따라 정리해보자.
위 그래프대로 6번째 피보나치 수를 구하기 위해서 f(5)부터 f(0)까지 재귀함수가 호출된다. 그런데 자세히 보면 f(5)부터 f(0)까지의 함수들이 반복해서 호출됨을 알 수 있다. 이 함수의 결괏값을 별도로 저장해놓았다가 사용하면 어떻게 될까?
아래 코드를 확인해보자.
mem = [0] * 19 # memory for dynamic algorithm
def fibonacci_dynamic(index):
if index < 2:
return index
mem_index = index - 2
if mem[mem_index]:
return mem[mem_index]
else:
mem[mem_index] = fibonacci(index - 1) + fibonacci(index - 2)
return mem[mem_index]
피보나치 수열의 결괏값을 mem이라는 이름의 리스트에 저장하기 위해 리스트를 선언해두었다. 그리고 피보나치 수열을 계산하기 전에 먼저 해당 mem 리스트 인덱스2에 값이 존재하는지 검사한다. 만약 값이 없을 경우에만 피보나치 수열을 재귀적으로 계산한다. 계산 후에는 해당 인덱스에 계산 결괏값을 저장하고 리턴한다.
이렇게 하면 피보나치 수열을 계산하기 위해서 피보나치 함수는 n번만 수행하면 된다. 즉, 시간복잡도가 O(n)이 된다. 이전 함수에 비해 매우 효율적으로 바뀌었음을 알 수 있다.