[알고리즘]동적 계획법(Dynamic Programming/DP)

동적 계획법(Dynamic Programming)

동적계획법이란 복잡한 문제를 간단한 여러개의 문제로 나누어 푸는 방법을 말한다. 

연산이 진행될 때 처음 진행되는 연산은 기억해두고, 이미 진행해서 저장이 되어있는 연산이라면 저장되어 있는 값을 가지고 오는 원리이다.
이렇게 미리 계산해서 저장해둔 결과를 활용해서 중복 연산을 줄이는 방식을 메모이제이션이라고 한다.
메모이제이션을 이용하면 중복되는 하위문제를 조금 더 효율적으로 해결할 수 있다.

모든 방법을 일일이 계산해서 최적의 해를 찾아내는 방식의 알고리즘이다. 그래서 시간이 오래걸린다는 단점이 있지만 최적의 해를 찾는데에 오류가 발생할 수 없다는 장점이 있다.

동적 계획법은 큰 문제를 작은 문제로 쪼개어 해결할 수 있어야 하고, 동일한 부분 문제가 여러번 반복되어 계산되어야 할 때 쓰인다.

정수 삼각형

이를 이용해서 문제를 풀어봤다.

Q. 위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다.
아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다.
예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하시오

이 문제는 어떻게 시작해야할지 감이 잘 안와서 수도코드를 먼저 작성해 봤다.

// 가장 위에서 부터 밑으로 내려가는데, 제일 큰 값을 먼저 찾는다
// 찾은 값 저장
// 저장했다면 밑 칸으로 내려가기
// 반복하며 더해진 값 저장하다가
// 모든 경우를 다 찾으면 max값 찾기

풀이 코드는 아래와 같다.

function solution(triangle) {    
     const height = triangle.length;
    
    // 계산한 값들을 저장하기 위한 Array 만들기 & 값들을 다 0으로 채워둔다
    const dp = new Array(height);
    for (let i = 0; i < height; i++) {
        dp[i] = new Array(i + 1).fill(0);
    }
    dp[0][0] = triangle[0][0]; // 꼭대기의 숫자부터 시작

    // 동적 계획법을 이용하여 최대 합 계산
    for (let i = 1; i < height; i++) {
        for (let j = 0; j <= i; j++) {
            if (j === 0) { // 왼쪽 끝의 경우
                dp[i][j] = dp[i - 1][j] + triangle[i][j];
            } else if (j === i) { // 오른쪽 끝의 경우
                dp[i][j] = dp[i - 1][j - 1] + triangle[i][j];
            } else {
                dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j];
            }
        }
    }
    // 최대 합 중 가장 큰 값 찾기
    const answer = Math.max(...dp[height - 1]);
    return answer;

}

생각보다 풀이가 어려워서 Chat GPT를 이용해서 겨우 풀 수 있었다.

위 풀이에서도 보면 계산한 값을 저장하여 나중에 재계산을 하는 비효율을 막았다.

전에 C언어를 잠깐 배웠을 때 피보나치 수열을 동적계획법을 이용해서 풀이했었는데, 그 때의 기억을 되살려 다시 풀어보고 이해해보려고 하니 금방 이해가 되었던 동적계획법이였던 것 같다.

문제의 난이도가 높아 조금 이해가 되지 않는다면 피보나치 수열을 우선 동적계획법으로 풀이해보는 것을 추천한다.