[알고리즘] DP란?

DP란?

Dynamic Programming(DP, 동적 프로그래밍)은 복잡한 문제를 하위 문제로 나누어 해결한 뒤, 그 결과를 저장하여 중복 계산을 피하는 알고리즘 기법이다.

-> 간단히 말하면, "한 번 계산한 값은 다시 계산하지 않도록 저장해두자"

예를 들어, 친구에게 숙제 답을 알려줬는데, 다른 친구가 또 와서 똑같은 것을 물어본다면?

-> 그냥 기억해두었던 답을 알려주는 게 훨씬 빠른 것과 같다!

핵심 개념

부분 문제(하위 문제)로 나눈다.: 큰 문제를 작은 문제로 나눈다.
중복되는 부분 문제가 발생하는 경우가 많다.: 똑같은 하위 문제를 여러 번 풀게 되는 경우가 많다.
이전에 계산한 결과를 배열(테이블)에 저장해서 재사용한다. (Memorization)

종류

종류	설명	생각 흐름
Top-Down 방식	재귀 + 메모제이션 사용: 문제를 쪼개면서 재귀적으로 풀고, 풀다가 같은 문제가 나오면 저장해둔 값을 재사용한다.	큰 문제 -> 작은 문제 -> 저장 -> 재사용
Bottom-Up 방식	반복문으로 테이블 채우기: 가장 작은 문제부터 차근차근 해결해나가면서, 점점 큰 문제를 푼다.	작은 문제 -> 큰 문제

로직이 재귀적으로 자연스럽게 떠오르면 Top-Down
반복문으로 차근차근 쌓아가는 게 명확하다면 Bottom-Up

-> 실전에서는 Bottom-Up을 많이 사용한다. 재귀 스택 문제가 거의 없고, 코드가 더 안정적이기에 말이다.

왜 사용할까?

중복된 계산을 피할 수 있어서
복잡한 문제를 쉽게 풀 수 있어서
최적의 결과(최소값, 최대값 등)를 구해야 하는 문제에 잘 맞아서
탐색(브루트포스)보다 훨씬 빨라서

예시

1) Top-Down 방식

JavaScript

// Top-Down 피보나치 (재귀 + 메모이제이션)
function fib(n, memo = {}) {
    if (n <= 1) return n;
    if (memo[n]) return memo[n];  // 이미 계산한 값 재사용

    memo[n] = fib(n - 1, memo) + fib(n - 2, memo);  // 저장
    return memo[n];
}

console.log(fib(10));  // 출력: 55

2) 예시 : Bottom-Up 방식

JavaScript

// Bottom-Up 피보나치
function fib(n) {
    const dp = [0, 1];

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

    return dp[n];
}

console.log(fib(10));  // 출력: 55

최근 글