동적 계획법(Dynamic Programming) 이란?

생성일: 2023년 1월 16일 오후 5:32
태그: 알고리즘

❔ 동적 계획법 (Dynamic Programming)이 뭔가요?

우리가 아는 DP... ㅋㅋ 포켓몬스터 DP!

이 DP 아닙니다..

 

DP 동적 계획법은 캐시를 사용하는 최적화 기법이다!

*Dynamic Programming은 단지 이름이 멋있어서 지은것이며, 실제의미랑은 관계가 없습니다.*

 

최적화 문제를 연구하는 수학이론에서 왔으며, 처음 주어진 문제를 더 작은 부분 문제들로 나눈 뒤 각 조각의 답을 계산 하고 저장한 뒤에 이 답들로 부터 원래 문제에 대한 답을 계산해 낼 수 있는 최적화 기법입니다.

 

쪼개진 문제가 두 번 이상 계산이 되는 문제를 부분 문제라고 합니다. 이 부분 문제는 두 개 이상의 문제를 푸는데 사용되기 때문에, 이 문제의 답을 여러번 계산하는 대신 한번만 계산하고 계산결과를 재활용해서 속도의 향상을 기대할 수 있습니다. 따라서, 각 부분문제의 답을 메모리에 저장할 필요가 있습나다. 그것을 바로 메모이제이션이라고 합니다.

 

메모이제이션

계산결과를 재활용 하기 위해서는 부분문제에 대한 답을 메모리에 저장할 필요가 있습니다. 부분 문제에 대한 해답을 저장하는 매모리를 캐시(cache)라고 합니다. 또한 한 번 계산한 값을 저장해 뒀다 재활용하는 최적화 기법을 메모이제이션이라고 합니다.

 

메모이제이션을 사용하면 모든 부분문제가 한번씩만 계산된다고 보장할 수 있기 때문에 “총 호출횟수가 엄청나게 감소할 것”이라고 예상 가능합니다.

 

메모이제이션에 대한 예시로 학교 가방을 생각할 수 있습니다. 오늘은 🌞스케치북에 종이를접고 그림을 그려 보는 날입니다. 와! 우리 영희친구👧는 학용품(부분문제)을 미리 책가방(캐시)에 넣어둠으로써 굳이 문방구에 가지(호출) 않아도 바로 책가방에서 스케치북(부분문제에 대한 해답)을 꺼내서 사용할 수 있는 것이죠!

 

분할과 정복 vs 동적 계획법

언뜻보면, 부분문제로 나누는데 있어서 분할과 정복과 별 차이가 없어 보이긴 합니다. 분할과 정복은 나눠진 문제들이 중복되지 않습니다. 하지만 동적 계획법은 부분문제들이 합쳐 더 큰 문제들을 푸는데 사용될 수 있기 때문에 그것을 해결하고 재활용 한다는 점에 있어서 차이점이 있습니다.

 

😒 언제 쓰이는가요?

동적프로그래밍은 문제 해결 패러다임입니다. 따라서 DP를 적용할 수 있는 몇가지 경우를 잘 기억 했다가, 상황에 맞게 써먹어야 합니다.

 

🔧 알고리즘 문제의 단순한 풀이 흐름

1. 재귀 함수, 그리디, 구현, 완전 탐색등 아이디어가 떠오르면 작성한다.
2. 시간 초과등 개선이 어려우면 DP를 고려한다.
3. 큰 문제가 동일한 작은 문제의 해결이 될 때 주로 사용한다.

🛠️ Dynamic Programming 이 사용 될 때

1. Can be divided into sub problem
   큰 문제들이 작은 부분 문제로 나눠질 때 사용가능합니다.
2. Recursive Solution
3. Are There repetitive sub problem
   재귀적인 해결방법은 대부분 큰 문제들이 작은 부분 문제로 나눠집니다. 그 작은 부분 문제들이 큰 문제에 써먹을 수 있는 경우이기 때문에 DP를 고려해 볼 수 있습니다.
4. Memoize “Subproblem”
   부분 문제를 메모이제이션 했다가 큰 문제를 해결 할때 참조해서 사용하면 속도의 향상을 꾀할 수 있습니다.

 

🤕 동적 계획법 적용 과정

구체적으로 어떻게 동적 계획법을 사용하는지 봅시다.

1. 큰 문제에서 반복되는 부분 문제를 찾는다.
2. 부분 문제를 Memoization 을 한다.
   • Cache를 만들었을 때, index의 값이 무엇을 의미 하는지 정해야 합니다.
   • 부분 문제의 초기상태를 정의 해야합니다.
     ⚠️ 현재 상태를 정의해야합니다!
3. 반복되는 수식(점화식)을 찾는다.
   ⚠️ 점화식은 다음 상태를 나타내기 위한 표현식입니다. 말 그대로 이전상태에도 이 점화식을 사 용하고, 다음 상태도 이 점화식을 사용되어 해결되어야 합니다.
4. 구현한다.
   1. 큰 문제에서 부터 해결되는 Top-Down 구현방식이 있고,
   2. 작은 문제에서 부터 해결하는 Bottom-Up 구현방식이 있습니다.

말로만 들으면 무슨 소리인지 하나도 모릅니다. 어디 한번 예시를 통해 구체적인 코드를 봅시다.

 예시 : 피보나치 수열

수학에서 피보나치 수(영어: Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 처음 여섯 항은 각각 1, 1, 2, 3, 5, 8이다. 편의상 0번째 항을 0으로 두기도 한다.

이때 n 번째항에 있는 피보나치 수를 구하는 코드를 작성 하라.

 

 피보나치 수열은 점화식이 있습니다. 보통 피보나치 수열은 재귀로 많이 해결하는 문제입니다.  반복되는 문제로 이루어져 있는 셈이죠. 이 문제를 재귀 방식으로 먼저 해결해 보겠습니다.

피보나치 수열 점화식

 

1 : 재귀로 해결하는 방식

피보나치 수는 재귀적인 방식으로 해결이 가능합니다. 왜냐하면 5번째 항은 3,4번째 항의 합이기 때문이죠. 이를 그림으로 나타내면 다음과 같습니다.

 

재귀 호출 과정

fib(5)에서 fib(3) + fib(4) 를 호출하고, fib(4)에서는 fib(2) + fib(3)를 호출하고 쭉 내려가다 보면 어느샌가 1까지 찍고 다시 스택에 쌓은 순서대로 답을 끌어와서 답이 나올겁니다. 이를 코드로 구현해보겠습니다.

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

console.log(fibo(30)); //1346269

하지만 이 fibo( ) 함수에는 치명적인 문제가 있습니다. N이 늘어날 수록 시간복잡도가 급격하게 늘어나는 문제입니다.

fibo( )는 O(2^n)으로 N이 커질 수록 급격하게 시간 복잡도가 늘어납니다. 이를 동적 계획법으로 해결할 수 있습니다.

 

2 : 동적 계획법으로 해결하는 방식

피보나치 수열은 점화식으로 나타낼 수 있습니다. 따라서 우리가 굳이 상태를 정의 하지 않아도 초기상태와 cache에 들어갈 정의가 이미 다 정해져 있는 셈입니다. 이를 Cache를 이용한 계산을 그림으로 표현 하자면, 다음과 같습니다.

엄청난 최적화가 이루어짐

 

이렇게 캐시에 넣어두게 되면 Fibo(5)를 구하기 위해서 Fibo(3) [Fibo(1) Fibo(2)] , Fibo(4) [Fibo(2) ,Fibo(3)] 위로 재귀호출을 하지 않고 바로 캐시에 접근해서 계산하므로 속도의 향상을 얻을 수 있습니다. 이를 코드로 표현 하면 다음과 같습니다.

 

Top-Down 방식

const fibonacci = () => {
    // js closure를 이용한 Cache 정의
  const fibboTable = {};

  return function fib(n) {
    if (n in fibboTable) {
      return fibboTable[n];
    } else {
      if (n < 2) {
                //초기 상태 2이하는 1
        fibboTable[n] = 1;
        return fibboTable[n];
      } else {
        fibboTable[n] = fib(n - 2) + fib(n - 1);
        return fibboTable[n];
      }
    }
  };
};

 

얼마나 속도가 향상 될까요?

각각 함수를 호출 횟수와 연산 시간을 통해서 직접한번 비교해 보겠습니다.

const t0 = performance.now();
console.log("피보나치 수열 30번 째 수", fibo(30));
const t1 = performance.now();
console.log("재귀 호출 시간 : ", t1 - t0, "milliseconds");
console.log("재귀 호출 횟수 : ", recursionCount, "회");

const t2 = performance.now();
console.log("피보나치 수열 30번 째 수", fiboDP(30));
const t3 = performance.now();
console.log("DP 호출 시간 : ", t3 - t2, "milliseconds");
console.log("DP 호출 횟수 : ", DPCount, "회");

결과 콘솔 창

속도가 엄청 빨라 졌다는 것을 볼 수 있습니다. 호출횟수 4만5천배 차이가 납니다. ㄷㄷ…

후기

오늘은 동적 계획법에 대해서 포스팅을 해봤습니다. 매우 어려운 알고리즘 패러다임인 만큼 이 방식을 적용하기 위해서는 많은 연습이 필요할것 같습니다. 특!히! 문제를 잘 볼 줄 알아야 앞뒤 상관 관계 정의를 잘 세울 수 있고, 그제서야 비로소 DP를 적용할 수 있을 테니까요! 작성자도 여러 문제를 한번 풀어보고 한 번더 꿀팁을 전해줄 수 있게 실력을 기르도록 하겠습니다 !

 

 

출처 : 알고리즘 문제 해결 패턴 , Udemy js 알고리즘 + 자료구조 강의