Dynamic Programming - 1

피보나치 수열

문제: 피보나치 수열에서 n번째 오는 값을 구하시오.

e.g. n이 6일 때, 1, 1, 2, 3, 5, 8 ... 이므로 답은 8

재귀로 아래처럼 간단하게 풀 수 있으나, 이 방법은 O(2^n) 시간 복잡도를 가진다.

def fib(n):
  if n == 1 or n == 2:
    return 1
  return fib(n-2) + fib(n-1)

시간 복잡도를 생각하는 방법은, 아래와 같은 예시를 생각해보면 된다. 위의 피보나치 수열을 구하는 재귀와 밑의 코드의 시간복잡도는 비슷하리라 짐작할 수 있다. 하나의 n에서 두 개의 가지를 뻗어서 자기 자신을 재호출하고 있는 구조이기 때문이다. -1씩 깎이는 거나 -2씩 깎이는거는 나중에 가면 상수값이 되어서 빅오표기법에서는 의미가 없다. (이 영상 의 20분 쯤을 참조)

def recursive(n):
  if n <= 1:
    return
  recursive(n-1)
  recursive(n-1)

하나의 노드에서 가지를 두 개씩 뻗어나간다는 것은 트리의 높이가 한 단계 길어질 때마다 현재 노드 수의 * 2씩 된다는 소리이다. 처음에 루트 노드는 1개이니까 1 * 2 * 2 * 2 ... 이렇게 단계가 깊어질 수록 반복될 거고, 즉 트리의 높이가 n이라면 2^n이 될 것이다. (곱하기 2가 n번 반복되니까)

그래서 시간복잡도는 exponential time complexity O(2^n) 가 되는 것이다.

이렇게 되면 n이 50 만 되어도 엄청난 연산 비용이 든다. 이 비용을 줄이기 위해서 memoization을 사용한다.

n이 6일 때 피보나치 수열이 진행되는 모습을 보면, 똑같은 서브트리가 반복되고 있음이 보인다. 루트노드가 3인 서브트리, 루트노드가 4인 서브트리 등이 반복된다. n이 커질 수록 반복되는 서브트리는 더 많아질 것이다. 이렇게 반복될 때마다 계산을 반복하는 것은 매우 비효율적이므로, 어떤 자료구조에다 한 번 연산을 하면 그 결과를 저장해놓기로 한다. 예를 들어 n이 4일 때를 한 번 계산했다면, 오른쪽의 서브트리를 돌 때에는 또 다시 계산하지 않고 저장해놓은 fib(4)의 값을 갖다쓰는 것이다.

딕셔너리를 쓰면 원하는 값을 읽어올 때 O(1) 이므로 딕셔너리에 n을 key로 두고 계산 결과인 fib(n)을 value로 두자.

memo = dict() # memoization을 줄여서 memo
def fib(n, memo):
  if n in memo:
    return memo[n]
  if n == 1 or n == 2:
    return 1
  memo[n] = fib(n-2, memo) + fib(n-1, memo)
  return memo[n]

메모이제이션을 거치면 트리가 이렇게만 뻗어나간다. 대략 2n개 정도의 노드만 거치므로 시간 복잡도는 상수를 무시하고 O(n)이 된다.

Ref

• freeCodeCamp Dynamic programming lecture