[백준 9184번][Javascript][NodeJs] 동적 계획법 (DP; Dynamic Programming)

DP란?

동적 계획법(DP)이란 복잡한 문제를 부분적인 문제(subproblem)로 나누어 푸는 방법을 말한다

최적 부분구조(Optimal Substructure) 라고 하는 큰 문제와 세부 문제와의 관계를 설정

 

예를 들어,

1번 줄에서부터 10번 줄까지의 어떤 조건에 따라 계산을 하는데

2번 줄에서의 계산 방식과 7번 줄에서의 계산 방식이 동일하다고 할 때, 생각해볼 수 있다

 

동적 계획법은 분할 정복과 비슷하나,

분할 정복은 계산한 부분 문제를 한 번만 쓰기 때문에 메모이제이션이 필요하지 않다는 차이점이 있다

 

---

 

메모이제이션이 무엇인가 ?

 

function DFS(n) {
  if(n == 1 || n == 2) {...}
  
  if(memo[n] === 0) {
    ...
    DFS(n-1);
    DFS(n-2);
    memo[n] = memo[n-1] + memo[n-2];
    ...
  }
}

 

위의 코드에서 재귀함수를 활용하여 1~n까지의 경우를 확인하는데,

memo 배열에 이미 확인한 부분을 Memo 하여 같은 계산을 반복하지 않도록 하는 것이다

 

재귀호출은 기본적으로 시스템에 대한 부하가 크며
같은 함수를 여러 차례 호출하는 단점을 보여 시스템의 낭비가 예상되므로
동적 계획법을 사용하여 알고리즘의 실행 성능을 높인다

 

[Fig. 1] 재귀호출

 

---

 

위와 같은 예시를 n에서 1까지 내려왔다고 하여 TOP - DOWN 방식이라고 하고

BOTTOM - UP 방식은 다음과 같다

 

function fib(n) {
  memo[0] = 0;
  memo[1] = 1;
    
  for(int i = 2; i <= n; i++)
    memo[i] = memo[i - 1] + memo[i - 2];
        
  return memo[n];
}

 

피보나치 수열을 DP를 적용하여 구사한 코드이다

0에서 n까지 올라가며 값을 구하는 것을 볼 수 있다

시간 복잡도는 같지만 TOP - DOWN 방식의 시간이 좀 더 길다고 일반적으로 알려져 있다

 

---

주의해야 될 점?

 

1. 초기화

첫 번째 코드를 보면, DP[n] === 0의 조건으로 판단을 하는 경우가 있다

이는 DP 배열을 0으로 초기화 하였기때문에 가능한 조건문임을 알아야 한다

만약 0의 값을 쓰는 메모이제이션이라면 통상 -1로 초기화를 하곤 한다

 

2. 가이드라인

메모이제이션을 몇 차원으로 할 것인가?

변수와 값의 의미는 무엇인가?

이를 생각하여 점화식으로 재귀 또는 for문 계산을 하면 된다

 

---

문제 풀이

단순한 풀이 흐름은 다음과 같다

 

1. 재귀 함수, 그리디, 구현, 완전 탐색 등 아이디어가 떠오르면 작성
2. 시간 초과 등 코드 개선이 어려우면 DP를 고려
3. 위에서 언급했던 것과 같이, 큰 문제가 동일한 작은 문제의 반복적인 해결이 될 때 주로 사용된다

 

문제

https://www.acmicpc.net/problem/9184

9184번: 신나는 함수 실행

 

풀이

"use strict";

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = fs.readFileSync(filePath).toString().trim().split("\n");

let output = "";

let dp = [];

for (let i = 0; i < 21; i++) {
  dp[i] = [];
  for (let j = 0; j < 21; j++) {
    dp[i][j] = [];
    for (let k = 0; k < 21; k++) {
      dp[i][j][k] = 0;
    }
  }
}

function w(a, b, c) {
  if (a <= 0 || b <= 0 || c <= 0) return 1;
  if (a > 20 || b > 20 || c > 20) return w(20, 20, 20);

  if (dp[a][b][c]) return dp[a][b][c];

  if (a < b && b < c) {
    return (dp[a][b][c] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c));
  } else {
    return (dp[a][b][c] =
      w(a - 1, b, c) +
      w(a - 1, b - 1, c) +
      w(a - 1, b, c - 1) -
      w(a - 1, b - 1, c - 1));
  }
}

for (let i = 0; i < input.length; i++) {
  const [a, b, c] = input[i].split(" ").map(Number);

  if (a == -1 && b == -1 && c == -1) break;

  output = output.concat(`w(${a}, ${b}, ${c}) = ${w(a, b, c)}\n`);
}

console.log(output);

 

 

---

풀 만한 문제 (boj)

10844, 11057, 9465, 2156 / 11053, 11055, 11722, 11054, 1912 / 2133, 2225, 2011, 11052

 

---

- https://snupi.tistory.com/37 (C언어)

- https://mehee.tistory.com/16 (공댕이의 개발블로그)