[알고리즘] 동적계획법(Dynamic Programming, DP) 이란?

동적계획법(Dynamic Programming)은

큰 문제를 작은 문제로 나누어 푸는 알고리즘이다.

dp의 핵심은 "메모이제이션" 기법인, 이미 계산된 결과를 별도의 메모리에 저장하여 필요한 경우 다시 계산하지 않고 사용하는 방식이다.

작은 문제들이 계속 반복되고, 그 작은 문제의 결괏값은 항상 같을 때 DP 알고리즘 적용할 수 있다.

 

가장 대표적인 예로 피보나치 수열을 들 수 있다.

피보나치 수열

피보나치 수열을 살펴보자. 피보나치 수열은 아래와 같다.
1,  1,  2,  3,  5,  8,  13,  21,  34,  55,  89,  144 ...

피보나치 수열을 구할 때는 재귀를 쓴다. 다음과 같이 이전 결과와 전전 결과의 합으로 계속 구해나가는 방식이다.

return f(n) = f(n-1) + f(n-2)

그런데, 100번째 피보나치 수를 구할 경우 함수 호출은 기하급수적으로 증가한다.

5번째 피보나치 수를 구할 때, f(3), f(2), f(1) 와 같이 같은 연산을  여러번 반복하게 된다.

여기서, dp를 사용한다면 O(n^2) → O(f(n)) 로 시간복잡도가 줄어들게 된다. (다항식 수준으로, 문제에 따라 다르다.)

 

DP 적용조건

dp를 적용하기 위해서는 다음과 같이 2가지 조건을 만족해야 한다.

• Overlapping Subproblems (겹치는 부분 문제)
• Optimal Substructure (최적 부분 구조)

 

1. Overlapping Subproblems

DP는 기본적으로 문제를 나누고 그 문제의 결과 값을 재활용해서 전체 결과를 구한다.

그래서 동일한 작은 문제들이 반복하여 나타나는 경우에 사용 가능하다.

 

2. Optimal Substructure

부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우를 의미한다.

 

파보나치 수열을 동적계획법으로 구하는 두 가지 방법이 있다.

1. Top-down

문제 풀이가 위에서 아래로 진행된다.

let fiboData = new Array(100).fill(0);

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

2. Bottom-up

문제 풀이가 아래에서 위로 진행된다. 재귀함수를 사용하지 않고, for문 내에서 반복된다.

let fiboData = new Array(100).fill(0);

function fibo(n)
{
  fiboData[0] = 0;
  fiboData[1] = 1;
  for (let i=2; i<=n; i++)
    fiboData[i] = fiboData[i - 1] + fiboData[i - 2];
  return fiboData[n];
}

 

결론

동적 계획법은 모든 방법을 일일이 검토하여 최적의 해를 찾아내는 방식의 알고리즘이다.

여기서 그리디 알고리즘(탐욕 알고리즘)과 대비된다. 그리디 알고리즘은 모든 해를 구하지 않고 그 순간에서의 최적의 해를 찾는 방식이다. 그리디 알고리즘은 닥치는 순간만을 고려해서 해를 구하기 때문에 도출된 값이 항상 최적의 해라고 할 수 없다.

하지만 동적 계획법은 모든 방법을 검토해 보고 결과적으로 효율적인 값을 택하기 때문에 그리디 알고리즘에 비해 시간이 오래 걸리지만, 결과적으로는 항상 최적의 해를 구할 수 있다는 이점을 가지고 있다.