동적 계획법 (Dynamic Programming)

동적 계획법 (Dynamic Programming) 설명:

동적 계획법 (Dynamic Programming, DP)은 복잡한 문제를 작은 부분 문제(sub-problems)로 분해하고, 이 작은 문제들의 결과를 저장하며, 이를 활용하여 원래 문제의 결과를 구하는 방법론입니다.

DP는 크게 두 가지 접근 방식으로 나뉩니다:
1. 하향식 (Top-down): 재귀를 사용하여 큰 문제를 작은 문제로 분해하고, 메모이제이션(memoization)을 사용하여 중복 계산을 방지합니다.
2. 상향식 (Bottom-up): 작은 문제부터 시작하여 순차적으로 결과를 빌드업하는 방식. 보통 테이블(tabulation)을 사용하여 값을 저장합니다.

DP의 특징:

1. 중복되는 부분 문제: DP를 적용하기 위해서는 문제가 중복되는 작은 부분 문제들로 구성되어 있어야 합니다.
2. 최적 부분 구조: 큰 문제의 최적해가 작은 부분 문제들의 최적해로부터 구성됩니다.

동적 계획법의 대표적인 예제:

1. 피보나치 수열: 각 숫자가 이전 두 숫자의 합으로 이루어진 수열.
2. 0-1 배낭 문제: 무게 제한이 있는 배낭에 최대 가치를 가지도록 아이템을 선택하는 문제.
3. 동전 거스름돈 문제: 주어진 동전들을 사용하여 주어진 금액을 만드는 최소 동전 수를 구하는 문제.
4. 최장 공통 부분 수열 (LCS): 두 문자열에서 최대 길이의 공통 부분 수열을 찾는 문제.
5. 행렬 곱셈 순서 결정: 여러 행렬을 곱하는 데 필요한 최소 연산 횟수를 결정하는 문제.

예제와 솔루션 (피보나치 수열):

문제:
n번째 피보나치 수를 구하라.

상향식 접근 (Bottom-up):

function fibonacci(n) {
    if (n <= 1) return n;

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

    return fib[n];
}

console.log(fibonacci(9)); // 출력: 34

이 예제에서는 피보나치 수열의 n번째 값을 상향식 방법을 사용하여 구합니다. 작은 문제부터 결과를 저장하며 큰 문제의 해결책을 도출합니다.

동적 계획법은 중복 계산을 피함으로써 효율적인 해결책을 제공합니다. 문제를 잘 분석하고 동적 계획법의 적용 여부를 판단하는 것이 중요합니다.