알고리즘 / 동적 계획법 (Dynamic Programming, DP)

동적 계획법의 배경

 

피보나치 수열

동적 계획법의 등장 배경에는 피보나치 수열이 있다.

피보나치 수열은 제2항까지는 1, 3항부터는 앞의 두 항을 더한 수로 저의 된다.

제 0항은 생략되기도 한다.

(0), 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...

프로그래밍에서 피보나치 수열은 보통 재귀를 통해 표현이 가능하다.

피보나치 수열을 함수로 구현해 보자.

const fibo = (n) => {
  if (n <= 2) {
    return 1;
  }
  else {
    return fibo(n - 1) + fibo(n - 2);
  }
}

 

위의 함수에서 fibo(4)가 어떻게 동작하는지 보자.

DFS와 같이 깊게 탐색하여 fibo(4)와 fibo(3)이 중복되어 연산되는 것을 볼 수 있다.

이미 연산이 됬음에도 불구한데...

 

 

동적 계확법의 등장

위의 예시 처럼 이미 연산된 것을 다시 연산되는 점을 보안하고자 등장한 것이 동적 계획법이다.

동작 원리는 처음 진행된 연산은 기록해 두고, 이미 진행된 연산은 기록되었던 값을 가져오는 것이다.

 

이제 동적 계획법으로 피보나치 수열을 작성해 보자

let fiboData = [0];

const fibo = (n) => {
  if (n <= 2) {
    return 1;
  }
  if (!fiboData[n]) {
    fiboData[n] = fibo(n - 1) + fibo(n - 2);
  }
  return fiboData[n];
}

n이 2이하이면 1을 반납하고, fiboData[n]의 유효성 검사를 하고 없다면

fiboData[n]에 값을 저장하고, 반환한다.

만약, 값이 있다면 fiboData[n]을 반환하게 된다.

재귀와는 다르게 중복되는 연산이 없어진다.

 

 

개념

동적 계획법은 문제를 풀 때 하나의 문제를 여러 하위 문제로 나누어 풀고,

그것들을 결합해서 최종 목적에 도달하는 방식의 알고리즘이다.

 

자료구조의 동적할당(Dynamic Allocation)에서 '동적'은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법' 을 의미한다. 하지만, 알고리즘의 동적 계획법(Dynamic Programming)에서 '동적'은 '기억하기'라 생각하면 편하다. '프로그래밍'은 테이블을 만든다는 뜻이다.

 

DP문제가 성립되는 조건

아래와 같은 상황에서 DP를 사용하면 된다.

1. 최적 부분 구조 (Optimal Substructure)
   
   • 상위 문제를 하위 문제로 나눌 수 있으며, 하위 문제의 답을 모아서 상위 문제를 해결할 수 있다.
2. 중복되는 부분 문제 (Overlapping Subproblem)
   • 동일한 작은 문제를 반복적으로 해결해야 한다.

➡➡ 피보나치 수열은 DP 사용조건에 만족한다.

 

 

메모이제이션(memoization)

이전의 코드에서 하위 문제를 해결할 때 해결책을 저장하고, 같은 문제가 발생할 때

저장해둔 해결책을 갖고와 해결했다.

동일한 문제를 반복해야 하는 경우, 이미 계산된 결과를 저장했다가 사용하는 방식으로

중복 계산을 줄이는 것을 메모이제이션(memoization)이라고 한다.

 

특징

1. 같은 문제를 다시 호출하면 메모했던 결과를 가져온다.
2. 값은 기롷개 놓는 다는 점에서 캐싱(Caching)이라 한다.
3. DP에만 한정된 개념이 아니라 한 번 계산된 결과를 저장하고 다른 방식으로 사용할 수 있다.

 

 

TOP - DOWN

풀이가 위에서 아래로 진행되는 것.

let fiboData = [0];

const fibo = (n) => {
  if (n <= 2) {
    return 1;
  }
  if (!fiboData[n]) {
    fiboData[n] = fibo(n - 1) + fibo(n - 2);
  }
  return fiboData[n];
}

큰 수 부터 작은 수를 호출하며, 가장 작은 수에 도달하는 방식이다.

 

 

BOTTOM - UP

TOP - DOWN 방식과 반대로 아래에서 위로 진행되는 것.

let fiboData = [0];

const fiboBU = (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];
}

fibo(6)을 호출하면 fiboData[2]부터 fiboData[6]까지 진행될 것이다.

위와 같이 하위 값 부터 상위 값의 방향으로 진행하는 것이 BOTTOM - UP 방식이다.

 

동적 계획법의 장단점

모든 해를 구하지 않고 최적의 해를 찾는 방식인 그리디 방식과는 대조된다.

모든 방법을 일일이 검토하여 최적의 해를 찾아내는 방식의 알고리즘이기 때문이다.

 

하지만 동적 계획법은 모든 방법을 검토하기에 그리디 알고리즘 보다는 시간이 오래 걸리지만,

결과적으로 항상 최적의 해를 구할 수 있다는 장점을 갖는다.