[Python] 피보나치 수열과 Dynamic Programming 기초

1. 피보나치 수열

피보나치 수는 첫째 항과 둘째 항이 1이고 뒤에 나오는 모든 항이 앞 두 항의 합인 수열이다.

피보나치 수열의 점화식

앞의 두항의 합만 구하면 다음 항을 구할 수 있으므로 코드로 구현하면 다음과 같이 간단하게 표현할 수 있다.

N = int(input())

def fibo(x):
	if x == 0:
    	return 0
    if x == 1:
    	return 1
    return fib(x - 1) + fib(x - 2)
print(fibo(N))

하지만 이 코드에는 큰 문제점이 있는데...

앞서 구했던 피보나치 수의 값을 기억하질 못한다...

N=5라고 할 때 피보나치 수를 구하면 위와 같다.

동일한 계산을 여러 번하는데 전에 이미 값을 구했는데도 하위 연산을 하면서 값을 다시 구한다.

값이 하나 증가할 때마다 연산의 횟수가 2배씩 커져 시간복잡도 O(2^N)이라는 기적의 시간복잡도가 나오게 된다.

또 함수를 계속해서 호출하기 때문에 스택에도 계속 함수가 쌓여 스택 오버플로우가 발생하게 된다.

 

2. DP(Dynamic Programming)

이런 문제는 DP(Dynamic Programming)로 해결할 수 있다. DP는 이전에 구한 값을 저장했다가 다시 활용하는 방법이다.

앞선 풀이법에서는 값을 계산한 후 기억을 하지 않기 때문에 동일한 계산이 나오면 다시 계산을 한다. 

하지만 값을 저장한다면 동일한 계산이 나오면 계산하지 않고 저장한 값을 반환하기만 하면 된다.

값을 저장하는 것뿐이지만 계산을 다시 할 필요가 없어져 시간복잡도는 O(N)으로 엄청나게 줄어든다.

이런 DP는 Memoization( Top-Down) 방식과 Tabulation(Bottom-Up) 2가지 방법이 있는데 하나씩 살펴보자

 

1) Memoization

Memoization은 Top-Down 방식으로 구하려 하는 값부터 시작해서 점차 내려오며 하위값을 구하는 방식이다.

위에서 피보나치 수열을 구하는 방법과 비슷한데 함수를 호출할 때마다 계산한 값을 저장하는 방식이다.

N = int(input())
seq = [0, 1, 1] + [0] * (N - 2)

def fibonacci(x):
    if seq[x]:
        return seq[x]
    seq[x] = fibonacci(x - 1) + fibonacci(x - 2)
    return seq[x]
print(fibonacci(x))

(계산의 편의성을 위해 0번 인덱스에 0을 채워넣었다.)

 

seq라는 리스트를 만들어 피보나치 수열의 값을 계산하고 저장한다. 

 

2) Tabulation(Bottom-Up)

Tabulation은 하위값부터 시작하여 차근차근 표를 채워나가며 구하려는 값에 접근하는 방식이다.

가장 아래값부터 구하여 저장한 후 다음값을 구하는 방식이다.

N = int(input())
seq = [0, 1, 1] + [0] * (N - 2)

def fibonacci(x):
    for i in range(3, x+1):
        seq[i] = seq[i-1] + seq[i-2]
    return seq[x]
print(fibonacci(x))

 

3) 일반 함수와 DP 방식의 함수 실행시간 비교

import time

N = int(input())
seq = [0, 1, 1] + [0] * (N - 2)

def fibonacci(x):
    if seq[x]:
        return seq[x]
    seq[x] = fibonacci(x - 1) + fibonacci(x - 2)
    return seq[x]

def fib(x):
    if x == 0:
        return 0
    if x == 1:
        return 1
    return fib(x-1) + fib(x-2)


start = time.time()
print(fib(N))
print('memory 저장 x: ', time.time() - start)

start = time.time()
print(fibonacci(N))
print('memory 저장 o: ', time.time() - start)

N값이 35만 됬는데도 메모리에 저장하지 않고 그냥 구하는 경우 6초에 가까운 시간이 걸린 것을 볼 수 있다.

반면에 메모리에 값을 저장하면서 구하면 시간이 비약적으로 줄어든다.

 

값을 저장한 것뿐이지만 시간복잡도를 엄청나게 줄일 수 있다.

DP 문제는 메모이제이션이나 타뷸레이션 둘 다 사용해서 풀 수 있는 문제도 있지만 어느 하나를 사용하는 방법이 더 쉬운 문제들도 있기 때문에 문제를 많이 풀면서 감각을 익히는게 좋을 것 같다.