백준 1932 정수 삼각형을 풀며 알아보는 DP (다이나믹 프로그래밍)

들어가며

• 알고리즘과 자료구조는 여전히 어렵다. 최근까지도 dp를 멀리하고 있었다. 어느날 아는 동생이 면접에서 dp를 맞닥뜨리고 어려워했다는 이야기를 들었다. 이 놈, 얼마나 어려우려고? 하는 생각에 문제를 보니.. 처음엔 뭔소린가 했다.
• 처음 몇 문제는 다른 사람의 풀이를 보며 이해하려 노력했다. 계속 dp문제만 골라 풀다 보니 대략적인 감이 왔다.
• 그렇게 백준의 1932번 문제는 dp문제를 스스로 풀게 된 첫 dp 문제였다. 기록하며 어떻게 풀었는지 공유하는 글을 작성해보려 한다.

dp (동적계획법)

• 다이내믹 프로그래밍은 한국말로 동적 계획법이라한다. 여러 글을 살펴보며 왜 dp라는 방법을 쓸까 찾아보았다.
• 동적계획법은 bfs, dfs 처럼 수많은 경우의 수를 따져봐야 하는데 그 경우의 수가 너무 많아서 속도가 느려지는 문제를 개선하고자, 그래서 수행시간을 단축하고자 만들어진 알고리즘이다.

  한줄로 말하자면, 메모리를 사용하여 (ex. dp 배열이나 자료구조를 추가로 만드는 것) 중복 연산을 줄이고 (연산 결과를 저장), 중복 연산을 줄여 수행 속도를 개선하는 것이다.

dp로 풀 수 있는 문제인지에 대한 구분

1. dfs,bfs로 풀 수 있는데 경우의수가 너무 많은 경우
2. 경우의 수들에 중복 연산이 많은 경우

• 나는 분류에서 dp로 들어가 푸니 dp로 풀지만, 실제 알고리즘 테스트가 있을때면 dp로 풀어야되나? 싶은 생각이 들 것 같다..

정수 삼각형

문제
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력
첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

출력
첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

풀이

• 몇몇 dp 문제를 보다보니 대부분 중요하게 보는 것은 바로 반복되는 내용을 식으로 바꾸는 점화식 이었다.
• 일정 부분까지는 그냥 대입하고 그 이후 점화식을 반복문에 대입하여 풀던가, 가능하다면 처음부터 점화식으로 풀던가 하는 식이었다.
• 전체적인 코드를 먼저 보자.

const path = process.platform === "linux" ? "/dev/stdin" : "input.txt";
const fs = require("fs");
const [testCase, ...arr] = fs.readFileSync(path).toString().trim().split(`\n`);

const numberArray = arr.map((i) => i.split(" ").map(Number));

for (let i = 1; i < testCase; i++) {
  for (let j = 0; j < numberArray[i].length; j++) {
    if (!numberArray[i - 1][j - 1]) {
      numberArray[i][j] += numberArray[i - 1][0];
    } else if (!numberArray[i - 1][j]) {
      numberArray[i][numberArray[i].length - 1] +=
        numberArray[i - 1][numberArray[i - 1].length - 1];
    } else {
      numberArray[i][j] += Math.max(
        numberArray[i - 1][j - 1],
        numberArray[i - 1][j]
      );
    }
  }
}

console.log(Math.max(...numberArray[testCase - 1]));

• 나는 먼저 else부분인 식을 생각했다.

numberArray[i][j] += Math.max(
        numberArray[i - 1][j - 1],
        numberArray[i - 1][j]
      );

풀면서 어려웠던 점

• 그러다 예를들면 2번째줄인 [ 8, 1, 0 ] 에서 8은 numberArray[2][0]인 친구인데, numberArray[i - 1][j - 1] 로 보자면 numberArray[1][-1]이 되어 비교가 안되게 되는 것이다.
• 마찬가지로 2번째줄인 [ 8, 1, 0 ] 에 0은 numberArray[2][2]인 친구인데, numberArray[i - 1][j]로 보자면 numberArray[1][2]가 된다. numberArray[1]은 numberArray[1][0],numberArray[1][1] 까지만 있어 또 오류가 발생한다.
• 이러한 오류는 각 단계 배열의 0번째와 배열의 마지막 값에서 나는 오류이기에, 조건문을 통해 해당 상황일 때는 다르게 동작하도록 식을 추가하였다.

마치며

• 막상 식을 보면 엄청 간단해보이지만, 그 식을 생각하기까지가 어려운 것 같다. 오늘도 다른 dp 문제를 푸는데, 어느정도 풀다 막혀서 다른 사람 풀이를 보고 이해했다^^..
• dp를 스스로 5~10개 내외로 풀 수 있게 되면 다음 알고리즘/자료구조 로 넘어가보려 한다.