동적프로그래밍

동적 프로그래밍(Dynamic Programming, DP)은 복잡한 문제를 여러 개의 간단한 하위 문제로 나누어 풀고, 그 결과를 저장하여 중복 계산을 피하는 방법을 말합니다.

전이와 완화

동적 프로그래밍에서 하위 문제를 통해 해결해 나가는 방식은 다음 두 가지의 방식이 있습니다.

• 전이 - 이 전의 문제에서 부터 전이해 나갑니다.
• 완화 - 가장 마지막 문제에서 부터 완화해 나갑니다.

핵심

동적 프로그래밍 에서의 핵심은 하나의 큰 문제를 여러개의 작은 문제로 나누고 작은 문제를 해결하고 이를 메모이제이션 한 후 전이 혹은 완화 해 나가면서 문제를 해결한다는 것 입니다.

동적 프로그래밍은 대부분 문제가 데이터의 흐름으로 봤을 때 규칙성을 가지는 경우가 많습니다. 프로그래머스의 정수 삼각형 문제를 보며 말씀 드리겠습니다.

정수 삼각형

이 문제에서 삼각형의 한 노드의 위치를 i, j라 했을때 노드(i, j)에 도달할 수 있는 경로는 노드(i-1, j) 또는 노드(i-1, j-1) 로 부터 파생됩니다.

그렇게 생각하고 위에서 부터 삼각형의 각 배열을 한 단계씩 내려 갑니다. 각 단계에 속하는 각 삼각형을 구축하는 노드로 가는데 최대 가질 수 있는 비용은 바로 위 삼각형 노드 (i-1, j) 또는 (i-1, j-1) 둘 중 최댓값 + 현재 삼각형 노드의 비용 입니다.

이를 통해서 다음 점화식을 만들 수 있습니다.
dp[i][j] = max(dp[i - 1][j] + triagle[i][j], dp[i - 1][j - 1] + triangle[i][j])

이를 토대로 문제를 풀면

function solution(triangle) {
  var answer = 0;

  const dp = [[triangle[0][0]]];

  for (let i = 1; i < triangle.length; i++) {
    dp.push([]);
    const isLastDepth = i === triangle.length - 1;
    const rowLength = triangle[i].length;
    for (let j = 0; j < rowLength; j++) {
      dp[i][j] = 0;
      if (j < rowLength - 1) {
        dp[i][j] = triangle[i][j] + dp[i - 1][j];
      }
      if (j > 0) {
        dp[i][j] = Math.max(dp[i][j], triangle[i][j] + dp[i - 1][j - 1]);
      }

      if (isLastDepth) {
        answer = Math.max(answer, dp[i][j]);
      }
    }
  }
  return answer;
}