동적 계획법 알고리즘 (Dynamic programming Algorithm)

 

동적 계획법 알고리즘이란

출처: https://www.freecodecamp.org/news/demystifying-dynamic-programming-24fbdb831d3a/

동적 계획법이란 하나의 복잡한 문제를 여러 개의 간단한 하위 문제로 나누어 푼 다음, 이를 결합하여 답을 도출해내는 방법이다. 나누어진 하위 문제들의 결과를 따로 저장해두었다가 이후 동일한 문제가 나왔을 시 저장해둔 결과를 가져다가 쓰면 같은 문제를 반복해서 풀지 않아도 되기 때문에 문제를 해결하는데 시간을 절약할 수 있다. 즉 한번 푼 하위 문제는 중복해서 풀지 않는다. 그렇다면 어떤 문제인 경우에 동적 계획법으로 해결할 수 있을까? 우선 문제를 나누어봤을 때 반복되는 작은 문제들이 나와야 되고, 전체 문제의 최적해가 부분 문제의 최적해들로 구성되는지 확인해야 된다. 이 두 가지 조건 모두 충족한다면 동적 계획법으로 풀 수 있는 문제일 것이다. 지금까지 썼던 내용을 간단히 요약해보겠다.

 

동적 계획법으로 풀 수 있는 문제인지 판별하는 요소 2가지

• 중복되는 부분 문제(Overlapping Subproblem)
  부분 문제에 대해서 한 번만 연산하고 결과를 저장한다. 이 저장한 값을 재활용하면 따로 중복되는 문제에 대해 연산을 할 필요가 없으므로 효율적이다. 이처럼 나중에 사용하기 위해 저장하는 것을 메모이제이션(Memoization)이라 한다

• 최적 부분 구조(Optimal Substructure)
  문제의 최적해가 부분 문제의 최적해들로 구성되는 것을 의미한다

 

동적 계획법과 탐욕법(Greedy Algorithm)의 차이

동적 계획법과 탐욕법 모두 최적해를 구하는 문제에 사용되는 알고리즘이다. 동적 계획법은 작은 문제의 최적해가 전체 문제의 최적해가 되므로 현재 구하는 답이 최적해인 게 보장된다. 반면 탐욕법은 한 수 앞만 보고 진행을 하기 때문에 항상 최적해를 보장하지는 않는다. 정리해보면 동적 계획법은 속도 측면에서는 탐욕법보다 느리지만 확실한 답이 보장되고, 탐욕법은 동적 계획법보다 속도는 빠른 대신 확실한 답이 보장되지 않는다. 그러므로 문제를 풀 때 탐욕법으로 풀릴만한 문제인지 아닌지를 잘 판단하고 적당한 풀이 과정을 세우는 것이 시간을 단축시키는 방법이 될 것이다.

 

메모이제이션

동일한 계산을 반복해야 할 때, 전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 피해 실행 속도를 단축시킬 수 있다. 동적 계획법의 핵심이 되는 기술이다. 피보나치수열을 재귀 함수로 풀었을 때, 메모이제이션 사용 유무에 따른 계산 시간 차이을 확인 해보았다.

// 메모이제이션 사용 안함

let noMemFibo = (count) => {
  if (count < 2) {
    return count;
  } else {
    return noMemFibo(count - 1) + noMemFibo(count - 2);
  }
};

// 메모이제이션 사용함

let memFibo = (count) => {
  // 결과를 저장할 객체 선언
  let mem = {};
  let recur = (num) => {
    if (num < 2) { return num };
    // 객체에 key값이 있으면 가져다 쓰고, 없으면 재귀를 통해 작은 문제로 내려감
    let num1 = mem[num - 1] || recur(num - 1);
    let num2 = mem[num - 2] || recur(num - 2);
    mem[num] = num1 + num2;
    return num1 + num2;
  }
  recur(count);
  return mem[count];
}

noMemFibo는 메모이제이션을 사용하지 않는 함수, memFibo는 메모이제이션을 사용한 함수이다. 두 함수를 각각 이용해 피보나치 수열의 20번째, 30번째, 40번째 항을 구할 때 소요되는 시간을 확인해봤다. 메모이제이션을 사용한 함수는 수가 커져도 소요시간에 큰 변화가 없지만 메모이제이션을 사용하지 않은 함수는 수가 커질수록 기하급수적으로 소요시간이 늘어나는 것을 볼 수 있다.

 

구현 방식

동적 계획법은 Top-down 방식과 Bottom-up 방식으로 구현할 수 있다. 메모이제이션을 했다는 가정하에 두 가지 방식의 시간 복잡도는 같지만, 실제로는 Bottom-up 방식이 좀 더 빠르다고 한다.  차이점을 한눈에 보기 위해 동일한 문제를 각각의 방식으로 풀어보자.

 

Top-down

• 큰 문제를 작은 문제로 쪼개며 풀어나간다. 작은 문제가 풀리지 않았다면, 더 작은 문제로 쪼개어 푼다.
• 재귀로 해결 가능

let memFibo = (count) => {
  let mem = {};
  let recur = (num) => {
    if (num < 2) { return num };
    let num1 = mem[num - 1] || recur(num - 1);
    let num2 = mem[num - 2] || recur(num - 2);
    mem[num] = num1 + num2;
    return num1 + num2;
  }
  recur(count);
  return mem[count];
}

 

Bottom-up

• 작은 문제에서부터 풀어 올라가 큰 문제에 도달한다
• 반복문으로 해결 가능

let buFibo = (count) => {
  let mem = [0, 1];
  count--;

  while(count > 0){
    if(count === 0) return;
    mem.push(mem[mem.length - 2] + mem[mem.length - 1]);
    count--;
  }

  return mem[mem.length - 1];
}

대부분의 문제는 Top-down, bottom-up 양쪽 방식으로 모두 해결 가능하지만 가끔 어떤 문제는 하나의 방식으로만 풀리는 경우도 있다고 한다. 혹시 그런 문제를 만나도 당황하지 않도록 두 개의 방식을 잘 숙지해둘 것...!

 

 

 

 

 

---

참고 자료

• https://ko.wikipedia.org/wiki/%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95
• https://velog.io/@polynomeer/%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming
• https://ko.wikipedia.org/wiki/%EB%A9%94%EB%AA%A8%EC%9D%B4%EC%A0%9C%EC%9D%B4%EC%85%98
• https://www.zerocho.com/category/JavaScript/post/579248728241b6f43951af19
• https://coding-all.tistory.com/2