동적 프로그래밍(Dynamic Programming)

동적 프로그래밍은 하나의 문제를 여러 개의 작은 문제로 나누어 해결하고 해당 결과를 저장한 후에 더 큰 문제를 해결할 때 사용하는 방법론이다. 따라서 알고리즘이라기보다는 문제 해결 방법론으로 보는 관점도 있다.

 

동적 프로그래밍은 개발자의 관점에서 볼 때, '큰 문제'에 중점을 두어야 한다. '큰 문제'가 있어야 동적 프로그래밍의 효율성이 극대화 된다.

 

즉, 동적계획법은 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법이다.

 

특징:

1. 작은 문제의 해결책을 저장(메모이제이션)하여 재사용
2. 중복 계산을 피함으로써 성능 향상
3. 상향식(bottom-up) 또는 하향식(top-down) 방식으로 구현 가능

피보나치 수열을 예로 들어 보면,

// 일반적인 재귀 방식 (비효율적): n이 커질수록 함수가 재귀적으로 수행되며 늘어나게 된다.
function fibRecursive(n) {
    if (n <= 1) return n;
    return fibRecursive(n-1) + fibRecursive(n-2);
}


// DP를 활용한 반복문 방식 (bottom-up)
function fibIterative(n) {
    if (n <= 1) return n;
    
    let dp = [0, 1];
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}


// DP를 활용한 메모이제이션 방식 (top-down)
function fibDP(n, memo = {}) {
    if (n <= 1) return n;
    if (memo[n]) return memo[n];
    
    memo[n] = fibDP(n-1, memo) + fibDP(n-2, memo);
    return memo[n];
}

 

 

예제 : 문자열 일치

문자열이 일치하는지 판단할 때 주로 와일드카드 패턴이라는 것을 사용해 검증한다. 와일드카드 패턴 매칭은 문자열 매칭 문제의 한 종류로, 와일드카드 문자(*, ?등)을 포함한 패턴과 주어진 문자열을 비교하여 패턴과 일치하는지 확인하는 것이다. 와일드카드 문자를 말할 때 "*"만을  생각하는 경우가 많지만 "?"도 와일드카드 문자의 일종이다. 

 

*: 0개 이상의 길이의 문자열과 일치할 때 사용

?: 하나의 문자와 일치할 때 사용

 

function isMatch(pattern, text) {
    const m = pattern.length;
    const n = text.length;

    // dp[i][j]는 pattern의 처음 i 글자와 text의 처음 j글자가 일치하는지를 저장하는 배열
    const dp = Array.from({length: m + 1}, () => Array(n + 1).fill(false));

    // 빈 패턴과 빈 텍스트는 항상 일치
    dp[0][0] = true;

    // 패턴이 *로 시작하는 경우에는 빈 텍스트와도 일치하므로 dp[i][0]을 갱신
    for(let i = 1; i <= m; i++) {
        if(pattern[i - 1] === '*') {  // [i - 1]로 수정 (원래 코드의 [i = 1] 오타 수정)
            dp[i][0] = dp[i - 1][0];
        }
    }

    // 동적 프로그래밍을 통해 dp 배열 갱신
    for(let i = 1; i <= m; i++) {
        for(let j = 1; j <= n; j++) {
            if(pattern[i - 1] === '*') {
                // 와일드카드인 경우
                dp[i][j] = dp[i - 1][j] || dp[i][j - 1] || dp[i - 1][j - 1];
            } else if (pattern[i - 1] === '?' || pattern[i - 1] === text[j - 1]) {
                // ?이거나 현재 패턴 문자와 텍스트 문자가 일치하는 경우
                dp[i][j] = dp[i - 1][j - 1];
            }
        }
    }

    return dp[m][n];
}

// 테스트
console.log(isMatch("g*ks", "geeks")); // true
console.log(isMatch("ge?ks", "geeksforgeeks"));   // true
console.log(isMatch("g*k", "gee"));    // false

 

 

 

예제2 동전교환

/**
 * 주어진 동전들을 사용하여 특정 금액을 만들 수 있는 최소 동전 개수를 계산하는 함수
 * @param {number[]} coins - 사용 가능한 동전의 종류 배열
 * @param {number} amount - 만들어야 하는 목표 금액
 * @returns {number} - 최소 동전 개수 (불가능한 경우 -1 반환)
 */
function coinChange(coins, amount) {
    // dp 배열 초기화: 각 인덱스는 해당 금액을 만들기 위한 최소 동전 개수를 저장
    // 초기값으로 Infinity를 설정하여 아직 해당 금액을 만들 수 없음을 표시
    let dp = new Array(amount + 1).fill(Infinity);
    
    // 0원을 만드는데 필요한 동전 개수는 0개
    dp[0] = 0;

    // 각 동전에 대해 반복
    for(let coin of coins) {
        // 현재 동전부터 목표 금액까지 반복
        for(let i = coin; i <= amount; i++) {
            // 현재 금액을 만드는 최소 동전 개수는
            // 이전에 계산된 값(dp[i])과
            // 현재 동전을 사용했을 때의 값(dp[i - coin] + 1) 중 최소값
            dp[i] = Math.min(dp[i], dp[i - coin] + 1);
        }
    }

    // 목표 금액을 만들 수 없는 경우(Infinity)는 -1 반환
    // 가능한 경우는 해당 금액을 만드는데 필요한 최소 동전 개수 반환
    return dp[amount] === Infinity ? -1 : dp[amount];
}

// 테스트 예시
console.log(coinChange([1, 2, 5], 11));  // 결과: 3 (5 + 5 + 1)
console.log(coinChange([2], 3));         // 결과: -1 (불가능)
console.log(coinChange([1, 2, 5], 15));  // 결과: 3 (5 + 5 + 5)
console.log(coinChange([1, 4, 5], 8));   // 결과: 2 (4 + 4)

// dp 배열의 변화 과정을 보여주는 예시 (amount = 5, coins = [1, 2, 5])
function showDpProcess(coins, amount) {
    let dp = new Array(amount + 1).fill(Infinity);
    dp[0] = 0;
    
    console.log("초기 dp 배열:", [...dp]);
    
    for(let coin of coins) {
        for(let i = coin; i <= amount; i++) {
            dp[i] = Math.min(dp[i], dp[i - coin] + 1);
        }
        console.log(`${coin}원 동전 처리 후 dp 배열:`, [...dp]);
    }
}

console.log("\nDP 배열 변화 과정:");
showDpProcess([1, 2, 5], 5);

/*

DP 배열 변화 과정:
초기 dp 배열: [ 0, Infinity, Infinity, Infinity, Infinity, Infinity ]
1원 동전 처리 후 dp 배열: [ 0, 1, 2, 3, 4, 5 ]
2원 동전 처리 후 dp 배열: [ 0, 1, 1, 2, 2, 3 ]
5원 동전 처리 후 dp 배열: [ 0, 1, 1, 2, 2, 1 ]
*/

 

예제3: 도둑질

/**
 * 트리 구조의 마을에서 도둑질을 통해 얻을 수 있는 최대 골드를 계산하는 프로그램
 * 인접한 집은 동시에 도둑질할 수 없다는 제약 조건이 있음
 */

// 입력값 정의
const N = 7; // 집의 개수
const gold = [6, 7, 4, 8, 2, 9, 5]; // 각 집에 보관된 골드의 양

// 트리 구조 정의 (인접 리스트 방식)
const tree = [
    [1,2],      // 집 0과 연결된 집들
    [0, 3, 4],  // 집 1과 연결된 집들
    [0, 5, 6],  // 집 2와 연결된 집들
    [1],        // 집 3과 연결된 집들
    [1],        // 집 4와 연결된 집들
    [2],        // 집 5와 연결된 집들
    [2],        // 집 6과 연결된 집들
];

/**
 * DFS를 사용하여 각 노드에서의 최대 골드값을 계산하는 함수
 * @param {number} node - 현재 처리중인 노드
 * @param {number} parent - 부모 노드
 * @param {Array<Array<number>>} tree - 트리 구조
 * @param {Array<number>} gold - 각 집의 골드 양
 * @param {Array<Array<number>>} dp - 동적 프로그래밍 배열
 */
function dfs(node, parent, tree, gold, dp) {
    // dp[node][0]: 현재 노드를 선택하지 않았을 때의 최대 골드
    // dp[node][1]: 현재 노드를 선택했을 때의 최대 골드
    dp[node][0] = 0;  // 현재 노드를 선택하지 않는 경우 초기화
    dp[node][1] = gold[node];  // 현재 노드를 선택하는 경우 해당 노드의 골드값으로 초기화

    // 현재 노드와 연결된 모든 이웃 노드에 대해 처리
    for(let neighbor of tree[node]) {
        // 부모 노드는 이미 처리했으므로 건너뛴다
        if(neighbor === parent) continue;

        // 이웃 노드에 대해 재귀적으로 DFS 수행
        dfs(neighbor, node, tree, gold, dp);

        // 현재 노드를 선택하지 않는 경우:
        // 이웃 노드를 선택하거나 선택하지 않는 경우 중 큰 값을 더함
        dp[node][0] += Math.max(dp[neighbor][0], dp[neighbor][1]);

        // 현재 노드를 선택하는 경우:
        // 이웃 노드는 선택할 수 없으므로 이웃 노드를 선택하지 않는 경우의 값을 더함
        dp[node][1] += dp[neighbor][0];
    }
}

/**
 * 전체 트리에서 얻을 수 있는 최대 골드를 계산하는 함수
 * @param {number} N - 집의 개수
 * @param {Array<number>} gold - 각 집의 골드 양
 * @param {Array<Array<number>>} tree - 트리 구조
 * @returns {number} - 훔칠 수 있는 최대 골드량
 */
function getMaxGold(N, gold, tree) {
    // dp[i][j]: i번 집에서 j상태(0:미선택, 1:선택)일 때의 최대 골드
    const dp = Array.from(Array(N), () => Array(2).fill(0));
    
    // 루트 노드(0번 집)부터 DFS 시작
    dfs(0, -1, tree, gold, dp);
    
    // 루트 노드를 선택한 경우와 선택하지 않은 경우 중 큰 값 반환
    return Math.max(dp[0][0], dp[0][1]);
}

// 결과 출력
console.log(getMaxGold(N, gold, tree)); // 결과: 30

/**
 * 예시 설명:
 * 최대 골드 30을 얻는 방법:
 * - 선택한 집들: [8(집3) + 9(집5) + 5(집6) + 2(집4) + 6(집0)] = 30
 * - 인접한 집들은 선택되지 않았음
 */

 

 

동적프로그래밍은 크게 두 가지 특징을 가지고 있다.

 

1. 최적 부분 구조(Optimal Substructure)를 가진다.

전체를 한 번에 해결하기보다는 부분을 해결하는 최적해를 찾아내면 이를 사용해 전체를 해결하는 데 효율적일 수 있다.

 

2. 중복 부분 문제(Overlapping Subproblems)를 해결하는 데 유리하다.

전체 문제에서 일정 부분이 동일한 부분 문제로 구성돼 있다면 동적 프로그래밍은 훌륭한 접근법이 되 수 있다. 이 과정에서 동일한 부분 문제(또는 하위 문제)의 연산값을 재활용하여 성능을 높이는 전략을 사용할 수 있다.

 

위의 두 가지 상황에 해당할 수 있는 문제를 만났을 때 동적 프로그래밍을 사용하기에 적합하다고 할 수 있다. 피보나치 수열과 같은 최장 공통부분 수열(Longest Common Subsequence), 최단경로 문제 등이 동적 프로그래밍을 적용해 볼 만한 문제이다.