[알고리즘] 동적 계획법(dynamic programming) - 1

오늘은 동적 계획법에 대해서 설명하겠습니다.

동적 계획법은 분할 정복과 유사합니다.

동적 계획법 또한, 문제를 더 작게 나눈 다음에 각 조각의 답을 구한 뒤에 이 답들로부터 원래 문제에 대한 답을 계산하기 때문입니다.

다만, 동적 게획법의 부분 문제는 두 개 이상의 부분 문제를 푸는데 사용될 수 있습니다!

따라서, 해당 부분 문제의 답을 여러 번 계산하는 대신 한 번만 계산하고 계산 결과를 다시 사용해서 속도의 향상을 가져올 수 있습니다.

이를 위해서, 각 부분 문제의 답을 메모리에 저장하는 방식을 취합니다!!

이를 메모이제이션 (memoization) 이라고 합니다.

여담이지만, 메모이제이션을 메모리제이션과 햇갈리는 경우가 굉장히 많습니다! 

실은 저도 최근에서야 메모리제이션이 아니라 메모이제이션인걸 알았습니다..

메모이제이션의 효능을 알아보기 위해 피보나치 수열 예시를 보겠습니다!

자료는 위키피디아에서 가져왔습니다!

피보나치 수열

보통 피보나치 수열을 구하는 함수는 다음과 같이 작성한다.

function fib(n)
 if n = 0
  return 0
 else if n=1
  return 1
 else
  return fib(n-1) + fib(n-2)

이때, fib(5)를 구한다고 한다면 계산은 다음과 같이 이루어진다.

1. fib(5)
2. fib(4) + fib(3)
3. (fib(3) + fib(2)) + (fib(2) + fib(1))
4. ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
5. (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

여기에서 세 번째 줄의 fib(2)가 중복되어 계산되고, 이것은 전체적인 계산 속도를 떨어뜨린다. 이 알고리즘의 시간 복잡도는 지수 함수가 된다.

여기에서 각 함수의 계산값을 저장하는 객체 m을 추가하면, 이 알고리즘은 다음과 같이 바뀐다.

var m := map(0 → 1, 1 → 1)

function fib(n)
 if n not in keys(m)
  m[n] := fib(n-1) + fib(n-2)
 return m[n]

이렇게 각 계산값을 저장하면, 중복 계산이 줄어들고 시간 복잡도는 O(n)이 된다.

이처럼 메모이제이션을 사용하면 중복 계산이 많이 줄기 때문에 동적 계획법은 최적화문제에서 아주 많이 쓰입니다.

그렇다면, 메모이제이션은 언제 사용할 수 있을까요?

메모이제이션은 입력 값에 따라서 그 값을 메모리 공간에 저장하는 형태입니다. 

따라서, 결과의 값이 그 입력 값으로만 결정 될 때 사용합니다! 

참고로, 문제에서 중복값이 많은지 여부를 알고 싶을 때에는, 입력 값으로 만들어 질 수 있는 값의 범위와

실제로 문제를 풀면서 나오는 부분 문제의 수를 비교하면 됩니다. 

예를 들어, 피보나치 풀이의 경우, 5번째 피보나치만 구하고 싶다면, 1부터 5까지의 피보나치만 보면 되지만, 그저 재귀로 풀 때에는 위에서 처럼 엄청나게 많은 부분 문제의 경우가 생깁니다.

따라서, 실제로 중복 문제가 여러번 계산된다는 것을 알 수 있는 것입니다!

(이를 '비둘기집의 원리'라고 합니다.)

메모이제이션의 시간 복잡도는 보통

 - 부분 문제의 개수 * 부분 문제를 계산할 때 걸리는 시간복잡도

로 계산합니다.

하지만, 경우에 따라 중복 계산이 많아지기 때문에 이보다 짧은 시간이 걸릴 수 있습니다.

동적 계획법이 굉장히 긴 파트를 나누고 있어서 다음에 또 다시 업데이트 할 것 같습니다! 우선은 여기까지 하겠습니다!