Dynamic Programming
Dynamic Programming(이하 DP) 은 반복적인 재귀 호출에 대한 최적화 방법을 의미하는 용어입니다. 대체로 DP는 굉장히 어려워서 DP 관련 인터뷰 문제들은 기초적인 것들을 주로 묻는다고 합니다. 이중 대표적인 문제인 피보나치 수열을 여러가지 방식으로 풀면서 DP의 원리를 한번 알아보도록 하겠습니다.
Pibonacci Sequence
피보나치는 재귀로 풀어낼 수 있는 대표적인 문제입니다. 코드는 아래와 같습니다.
def pibonacci(n: int):
if n == 0 or n == 1:
return 1
return pibonacci(n - 1) + pibonacci(n - 2)이렇게 재귀적으로 풀면 굉장히 비효율적인 코드가 나오는데 이유를 아래 그림을 통해 확인해 보겠습니다.
위에서 f(7)은 f(6)과 f(5)의 합입니다. 그리고 f(6)은 f(5)와 f(4)의 합이고 f(5)는 f(4)와 f(3)의 합입니다. 이렇게 쭉쭉 밑으로 내려가면 최종적인 재귀 형태가 위와 같은데 이것은 굉장히 비효율적입니다. 왜냐하면, f(7)을 계산할때도 f(5)를 계산해야 되고 f(6)을 계산할 때도 f(5)를 계산해 주어야합니다. f(2)는 f(7)을 계산하기 위해 함수 호출을 8번하고 계산까지 해주어야합니다. f(7)만해도 이렇게 되는데 f(100)은 정말 엄청난 계산 횟수로 인해 굉장히 과부하를 먹게 됩니다. 이를 파이썬으로 동작시키면 화면이 멈춘것 같이 보입니다.(사실 연산을 하는 중....)
이렇게 피보나치 수열을 재귀로만 동작하게 하면 시간 복잡도가 O(2^n)으로 지수적으로 증가하는 매우 비효율적인 알고리즘이 되어버립니다.
DP로 피보나치 해결하기
그렇다면 DP로 이를 어떻게 해결할 수 있을까요? 첫번째로 memoization을 활용해보겠습니다. 메모이제이션은 반복해서 계산하는 작업을 미리 저장해놓고 다시 그 계산을 하지 않고 미리 저장해놓은 값을 불러와 프로그램 속도를 빠르게하는 방법입니다.
cache = {}
def pibonacci(n):
if n == 0:
return 0
if n == 1:
return 1
if n in cache:
return cache[n]
else:
cache[n] = pibonacci(n - 1) + pibonacci(n - 2)
return cache[n]
print(pibonacci(100))이렇게 딕셔너리를 활용해서 계산된 값들을 저장하고 다시 그 계산이 나오면 미리 저장된 값을 활용해서 속도를 훨씬 높일 수 있습니다. 앞서 그냥 재귀로 풀었을 경우에는 f(7)계산시, f(2)를 8번이나 계산해주어야 했지만 이제는 f(2)를 한번만 계산하고 f(2)가 그 뒤에 다시 나오면 딕셔너리에 캐시해둔 f(2)값을 바로 반환해주기만 하면 됩니다. 아래 그림 처럼 f(100)값이 바로 반환되는 것을 확인하실 수 있습니다.
두번째로는 재귀없이 반복문과 DP의 또다른 주요 개념인 tabulation을 활용해서 풀어보도록 하겠습니다. 테불레이션은 아래에서부터 위로 즉 bottom-up 방식으로 작은 값부터 직접 계산해서 문제를 풀어나가는 방식입니다. f(7)을 계산하기 위해 f(6)과 f(5)을 계산하는 것이 아닌 f(0)과 f(1)을 합친 f(2)를 구하고 그다음 f(1)과 f(2)를 합친 f(3)을 구해나가면서 최종적인 f(7)을 구하는 방식입니다.
def pibonacci(n):
ans = [0, 1]
if n == 0 or n == 1:
return ans[n]
for i in range(2, n + 1):
ans.append(ans[i - 1] + ans[i - 2])
return ans[n]
print(pibonacci(100))tabulation 방식으로 방금 풀었지만 만일 피보나치가 엄청 큰 숫자라면 그 수만큼 리스트의 크기가 되어야 할 것입니다. 그렇다면 공간 복잡도는 O(n)이 되는데 그것보다 훨씬 적게 O(1)으로 공간 복잡도를 낮출 수 있습니다.
우리가 n번째 피보나치 수열을 구한다고 하면 우리에게 필요한 숫자는 n-1번째 수와 n-2번째 수일 것입니다. 그렇다면 그전의 있는 수들을 다 저장할 필요는 없는 것이 됩니다. 3번째 수를 구하기 위해서 1, 2번째 수를 4번째 수를 구하기 위해서 2, 3번째 수를 알고 있으면 됩니다. 아래는 이를 반영한 코드입니다.
def pibonacci(n):
x = 0
y = 1
if n == 0:
return x
if n == 1:
return y
for _ in range(2, n + 1):
current = x + y
x, y = y, current
return current
print(pibonacci(100))이러면 변수 x, y, current만 있으면 되므로 시간복잡도는 이전 코드와 같게 유지하면서 공간 복잡도를 O(n)에서 O(1)으로 줄일 수 있습니다.
