본문 바로가기

동적 프로그래밍 기초

동적 프로그래밍(DP)은 코딩테스트에서 출제 비중(약 6%)은 낮지만, Lv3 이상의 고난도 문제에서 자주 등장합니다. 기초적인 DP 유형만 익혀도 많은 문제를 해결할 수 있습니다. 이 챕터에서는 코딩테스트에 자주 나오는 기초 DP 패턴만 다룹니다.

1. 동적 프로그래밍이란?

동적 프로그래밍(Dynamic Programming, DP)은 큰 문제를 작은 문제로 나누어 해결하고, 작은 문제의 결과를 저장해두었다가 재활용하는 기법입니다.

1.1 DP가 필요한 이유

피보나치 수열을 재귀로 구현하면 같은 계산을 반복합니다.

// 비효율적인 재귀 (O(2^n))
function fibRecursive(n) {
    if (n <= 1) {
        return n;
    }
    return fibRecursive(n - 1) + fibRecursive(n - 2);
}

// fib(5)를 계산하면:
// fib(3)이 2번 호출
// fib(2)가 3번 호출
// fib(1)이 5번 호출

DP를 사용하면 이미 계산한 값을 저장해두고 재사용합니다.

1.2 DP의 두 가지 조건

  1. 최적 부분 구조 (Optimal Substructure)

    • 큰 문제의 최적해가 작은 문제의 최적해로 구성됨
    • 예: fib(n) = fib(n-1) + fib(n-2)

  2. 중복되는 부분 문제 (Overlapping Subproblems)

    • 동일한 작은 문제가 반복적으로 등장
    • 예: fib(3)이 여러 번 필요

2. DP 구현 방식

2.1 탑다운 (Top-Down, 메모이제이션)

재귀 + 저장 방식입니다. 큰 문제에서 시작해서 작은 문제로 내려갑니다.

// 메모이제이션 (탑다운)
function fibTopdown(n, memo = {}) {
    if (n in memo) {
        return memo[n];
    }
    if (n <= 1) {
        return n;
    }

    memo[n] = fibTopdown(n - 1, memo) + fibTopdown(n - 2, memo);
    return memo[n];
}

console.log(fibTopdown(50));  // 12586269025 (빠르게 계산)

// 클로저를 활용한 메모이제이션
function memoize(fn) {
    const cache = {};
    return function(...args) {
        const key = args.toString();
        if (key in cache) {
            return cache[key];
        }
        cache[key] = fn.apply(this, args);
        return cache[key];
    };
}

const fibCached = memoize(function(n) {
    if (n <= 1) return n;
    return fibCached(n - 1) + fibCached(n - 2);
});

console.log(fibCached(50));  // 12586269025

2.2 바텀업 (Bottom-Up, 타뷸레이션)

반복문 + 테이블 방식입니다. 작은 문제부터 시작해서 큰 문제로 올라갑니다.

// 타뷸레이션 (바텀업)
function fibBottomup(n) {
    if (n <= 1) {
        return n;
    }

    const dp = new Array(n + 1).fill(0);
    dp[0] = 0;
    dp[1] = 1;

    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

console.log(fibBottomup(50));  // 12586269025

// 공간 최적화 (변수 2개만 사용)
function fibOptimized(n) {
    if (n <= 1) {
        return n;
    }

    let prev = 0;
    let curr = 1;
    for (let i = 2; i <= n; i++) {
        [prev, curr] = [curr, prev + curr];
    }

    return curr;
}

console.log(fibOptimized(50));  // 12586269025

2.3 탑다운 vs 바텀업

특성탑다운 (메모이제이션)바텀업 (타뷸레이션)
구현재귀 + 캐시반복문 + 테이블
순서큰 문제 → 작은 문제작은 문제 → 큰 문제
필요한 부분만 계산OX (모든 부분 계산)
스택 오버플로우 위험OX
코딩테스트 추천직관적일 때안정적

3. 코딩테스트 필수 DP 유형

3.1 계단 오르기 (1차원 DP)

function climbStairs(n) {
    // 계단을 오르는 방법의 수
    // 한 번에 1칸 또는 2칸 오를 수 있음

    if (n <= 2) {
        return n;
    }

    const dp = new Array(n + 1).fill(0);
    dp[1] = 1;  // 1칸: 1가지
    dp[2] = 2;  // 2칸: 2가지 (1+1, 2)

    for (let i = 3; i <= n; i++) {
        // i번째 계단 = (i-1)에서 1칸 + (i-2)에서 2칸
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

console.log(climbStairs(5));  // 8
// 1+1+1+1+1, 1+1+1+2, 1+1+2+1, 1+2+1+1, 2+1+1+1,
// 1+2+2, 2+1+2, 2+2+1

점화식: dp[i] = dp[i-1] + dp[i-2]

3.2 동전 교환 (최소 개수)

function minCoins(coins, amount) {
    // 주어진 동전으로 amount를 만들기 위한 최소 동전 개수
    // 만들 수 없으면 -1 반환

    // dp[i] = i원을 만들기 위한 최소 동전 개수
    const dp = new Array(amount + 1).fill(Infinity);
    dp[0] = 0;  // 0원은 동전 0개 필요

    for (let i = 1; i <= amount; i++) {
        for (const coin of coins) {
            if (coin <= i && dp[i - coin] !== Infinity) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }

    return dp[amount] !== Infinity ? dp[amount] : -1;
}

console.log(minCoins([1, 2, 5], 11));  // 3 (5+5+1)
console.log(minCoins([2], 3));         // -1 (불가능)

점화식: dp[i] = min(dp[i], dp[i - coin] + 1) for each coin

3.3 최장 증가 부분 수열 (LIS)

function longestIncreasingSubsequence(arr) {
    // 가장 긴 증가하는 부분 수열의 길이
    // 예: [10, 20, 10, 30, 20, 50] → [10, 20, 30, 50] → 4

    const n = arr.length;
    if (n === 0) {
        return 0;
    }

    // dp[i] = arr[i]로 끝나는 LIS의 길이
    const dp = new Array(n).fill(1);

    for (let i = 1; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (arr[j] < arr[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }

    return Math.max(...dp);
}

console.log(longestIncreasingSubsequence([10, 20, 10, 30, 20, 50]));  // 4
console.log(longestIncreasingSubsequence([3, 1, 4, 1, 5, 9, 2, 6]));   // 4

점화식: dp[i] = max(dp[j] + 1) where arr[j] < arr[i] and j < i

3.4 배낭 문제 (0/1 Knapsack)

function knapsack(weights, values, capacity) {
    // 배낭의 용량 내에서 가치의 합이 최대가 되도록
    // 물건을 선택할 때의 최대 가치
    // 각 물건은 한 번만 선택 가능

    const n = weights.length;

    // dp[i][w] = i번째 물건까지 고려했을 때, 용량 w에서의 최대 가치
    const dp = Array.from({ length: n + 1 }, () => new Array(capacity + 1).fill(0));

    for (let i = 1; i <= n; i++) {
        for (let w = 0; w <= capacity; w++) {
            // i번째 물건을 넣지 않는 경우
            dp[i][w] = dp[i - 1][w];

            // i번째 물건을 넣는 경우 (넣을 수 있다면)
            if (weights[i - 1] <= w) {
                dp[i][w] = Math.max(dp[i][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            }
        }
    }

    return dp[n][capacity];
}

const weights = [2, 3, 4, 5];
const values = [3, 4, 5, 6];
const capacity = 5;
console.log(knapsack(weights, values, capacity));  // 7 (물건 1, 2 선택)

점화식: dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])

3.5 2차원 격자 경로

function uniquePaths(m, n) {
    // m x n 격자에서 좌상단에서 우하단까지
    // 오른쪽 또는 아래로만 이동할 때의 경로 수

    const dp = Array.from({ length: m }, () => new Array(n).fill(1));

    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            // 위에서 오거나 왼쪽에서 오는 경우의 합
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }

    return dp[m - 1][n - 1];
}

console.log(uniquePaths(3, 3));  // 6
console.log(uniquePaths(3, 7));  // 28

점화식: dp[i][j] = dp[i-1][j] + dp[i][j-1]

3.6 최소 경로 합

function minPathSum(grid) {
    // 격자에서 좌상단에서 우하단까지
    // 경로 합이 최소가 되는 값

    const m = grid.length;
    const n = grid[0].length;

    // dp[i][j] = (0,0)에서 (i,j)까지의 최소 경로 합
    const dp = Array.from({ length: m }, () => new Array(n).fill(0));
    dp[0][0] = grid[0][0];

    // 첫 행: 왼쪽에서만 올 수 있음
    for (let j = 1; j < n; j++) {
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    }

    // 첫 열: 위에서만 올 수 있음
    for (let i = 1; i < m; i++) {
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }

    // 나머지: 위 또는 왼쪽 중 작은 값 + 현재 값
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
        }
    }

    return dp[m - 1][n - 1];
}

const grid = [
    [1, 3, 1],
    [1, 5, 1],
    [4, 2, 1]
];
console.log(minPathSum(grid));  // 7 (1→3→1→1→1)

4. DP 문제 접근법

4.1 DP 문제 판별

4.2 DP 문제 풀이 단계

  1. 상태 정의: dp[i]가 무엇을 의미하는지 정의
  2. 점화식 도출: dp[i]를 이전 상태로 표현
  3. 초기값 설정: 가장 작은 문제의 답 설정
  4. 계산 순서: 작은 문제부터 큰 문제 순서로

DP 문제 키워드

  • "~의 최솟값/최댓값"
  • "~의 경우의 수"
  • "~가 가능한가?"
  • "가장 긴/짧은 ~"
  • "연속된 ~"

4.3 자주 사용하는 상태 정의

유형상태 정의예시
1차원dp[i]: i번째까지의 최적해계단 오르기, 피보나치
부분 배열dp[i]: i에서 끝나는 최적해LIS, 최대 부분 합
2차원 격자dp[i][j]: (i,j)까지의 최적해경로 수, 최소 비용
배낭dp[i][w]: i번째까지, 용량 w0/1 배낭 문제
문자열dp[i][j]: s1[0:i], s2[0:j]LCS, 편집 거리

5. DP 심화 문제

5.1 숫자로 목표값 만들기

function minUses(n, target) {
    // 숫자 n을 사칙연산으로 조합하여 target을 만들 때
    // n을 최소 몇 번 사용해야 하는지 반환합니다.
    // 8번 초과면 -1 반환
    //
    // 예: n=5, target=12 → (55+5)/5=12 → 4번 사용

    if (n === target) {
        return 1;
    }

    // dp[i] = n을 i번 사용해서 만들 수 있는 모든 수
    const dp = Array.from({ length: 9 }, () => new Set());

    for (let i = 1; i <= 8; i++) {
        // n을 i번 연속 사용 (예: 5, 55, 555, ...)
        dp[i].add(parseInt(String(n).repeat(i), 10));

        // j번 사용 + (i-j)번 사용 조합
        for (let j = 1; j < i; j++) {
            for (const a of dp[j]) {
                for (const b of dp[i - j]) {
                    dp[i].add(a + b);
                    dp[i].add(a - b);
                    dp[i].add(a * b);
                    if (b !== 0) {
                        dp[i].add(Math.floor(a / b));
                    }
                }
            }
        }

        if (dp[i].has(target)) {
            return i;
        }
    }

    return -1;
}

console.log(minUses(5, 12));   // 4
console.log(minUses(2, 11));   // 3

5.2 삼각형 경로 최대합

function maxTrianglePath(triangle) {
    // 삼각형 형태의 숫자 배열에서 꼭대기부터 바닥까지
    // 이동하며 거쳐간 숫자의 최대 합을 구합니다.
    // 각 단계에서 바로 아래 또는 오른쪽 아래로만 이동할 수 있습니다.

    const n = triangle.length;

    // 바닥부터 올라가기 (바텀업)
    const dp = [...triangle[n - 1]];  // 마지막 행 복사

    for (let i = n - 2; i >= 0; i--) {  // 아래에서 두 번째 행부터
        for (let j = 0; j < triangle[i].length; j++) {
            // 아래 두 값 중 큰 값 선택
            dp[j] = triangle[i][j] + Math.max(dp[j], dp[j + 1]);
        }
    }

    return dp[0];
}

const triangle = [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]];
console.log(maxTrianglePath(triangle));  // 30

6. 연습문제

동적 프로그래밍 기초 - 코딩 테스트 에센셜 with 자바스크립트 | 위니버시티