DP(Dynamic Programming)

한 번 계산한 결과를 저장해두고, 다시 계산하지 않도록 하여 효율성을 높이는 알고리즘 기법입니다.

Dynamic Programming 의 의미

한국어로 하면 “동적 계획법” 혹은 “동적 프로그래밍”이라고 하는데, 그냥 봐서는 이게 무슨 뜻인지 이해가 잘 안 갔습니다.

여기서의 “Dynamic”이나 “Programming”이라는 단어가 흔히 쓰이는 뜻과는 조금 다르기 때문입니다.

우선, DP라는 이름은 1950년대 미국의 수학자 리처드 벨먼(Richard Bellman)이 지었습니다. 당시 그는 군사 최적화 문제를 연구하면서 국방부에서 싫어하는 단어(수학, 최적화, 계획 등)를 피해 정치적으로 중립적이고, 거부감 없는 이름을 일부러 만들었습니다. 이게 Dynamic Programming 입니다.

"Dynamic이라는 단어는 그럴싸하게 들리고, Programming은 어떤 계획 절차를 의미할 수 있어서 좋았다."

— 리처드 벨만

각 단어가 기존 의미인 ‘역동적인’, ‘프로그래밍’ 이라는 뜻이 아니라, ‘계산이 진행되면서 상태가 계속 바뀐다’와 ‘최적의 계획을 세우다’라는 의미를 가집니다. 즉, 계산이 진행되면서 바뀌는 상황에서, 최적의 전략이라는 의미를 가집니다.

이러한 최적의 전략이 바로, 계산했던 걸 저장해서 재사용하자입니다. 따라서 DP는 단지 코드, 알고리즘이 아닌 ‘어떻게 문제를 풀지에 대한 사고방식’으로 전략에 해당합니다.

DP가 필요한 이유

가장 흔하게 드는 예시가 “피보나치 수열”입니다.

피보나치 수열을 재귀로 풀면 다음과 같습니다.

function fibo(n) {
  if (n <= 2) return 1;
  return fibo(n - 1) + fibo(n - 2);
}

<aside> 🔗

재귀에 관해서는 다음 게시글을 참고해주세요.

</aside>

쉽게 작성했지만, 위 방식은 O(2ⁿ)의 시간복잡도를 가지고, 중복 계산이 아주 많습니다.

예를 들면, fibo(5)를 구하는 경우,

위 그림과 같이 fibo(1)과 fibo(3)은 2번, fibo(2)는 3번이나 반복 수행합니다. 사실 fibo(4) 쪽 트리의 계산만 해도 오른쪽 트리는 전부 중복이라 계산할 필요가 없습니다. 이런 중복을 없애서 성능을 최적화 하는 기법이 DP입니다.

function fiboDP(n, memo = {}) {
  if (n <= 2) return 1;
  if (memo[n]) return memo[n];

  memo[n] = fiboDP(n - 1, memo) + fiboDP(n - 2, memo);
  return memo[n];
}

이렇게, 한 번 계산한 값은 memo 객체에 n을 키로 하여 값을 저장하고, 같은 값이 필요하면 계산하지 않고 꺼내서 바로 사용할 수 있습니다.