동적계획법

동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 작은 하위 문제로 나누어 해결한 후, 그 결과를 저장하여 동일한 하위 문제가 다시 발생할 때 계산을 반복하지 않고 저장된 값을 사용하는 문제 해결 기법입니다.

동적 계획법의 핵심 개념
1. 중복되는 하위 문제(Overlapping Subproblems)
• 큰 문제를 작은 문제로 나누었을 때, 동일한 작은 문제가 여러 번 반복해서 등장하는 경우 사용됩니다.
• 예: 피보나치 수열 계산 (F(5) = F(4) + F(3), F(4) = F(3) + F(2) 등)

2. 최적 부분 구조(Optimal Substructure)
• 전체 문제의 최적 해가 부분 문제의 최적 해를 이용해서 구할 수 있는 경우입니다.
• 예: 최단 경로 문제에서, 경유지를 거쳐 가는 최단 경로는 개별 경로도 최단이어야 합니다.

동적 계획법의 해결 방식
1. 메모이제이션(Memoization, Top-Down)
• 재귀(Recursive) 방식으로 문제를 풀면서, 이미 계산된 값은 저장해두고 재사용하는 방식입니다.
• 예: 피보나치 수열을 재귀적으로 구현하면서, 한 번 계산한 값을 배열 등에 저장해서 중복 계산을 방지합니다.

2. 타뷸레이션(Tabulatio, Bottom-Up)
• 작은 문제부터 차례로 해결하며 결과를 테이블(배열)에 저장하는 방식입니다.
• 예: 피보나치 수열을 반복문으로 구현하여 F(1)부터 차례로 F(n)까지 계산하는 방식

예제: 피보나치 수열 (Fibonacci Sequence)
1) 기본 재귀 방식 (비효율적)
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)
• 같은 값이 여러 번 계산되어 비효율적입니다.

2) 메모이제이션 적용 (효율적)
memo = {}
def fibonacci(n):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci(n-1) + fibonacci(n-2)
    return memo[n]
• 이미 계산된 값을 저장하여 중복 계산을 방지합니다.

3) 타뷸레이션 적용 (효율적)
def fibonacci(n):
    dp = [0] * (n+1)
    dp[1] = 1
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]
• 작은 값부터 차례대로 계산하여 메모리를 절약할 수 있습니다.

동적 계획법이 사용되는 대표적인 문제
• 피보나치 수열
• 최단 경로 문제(벨만-포드 알고리즘)
• 배낭 문제(Knapsack Problem)
• 최장 공통 부분 수열(LCS, Longest Common Subsequence)
• 거스름돈 문제

동적 계획법을 이해하는 핵심은 중복 계산을 줄이고, 이전 결과를 저장하여 다시 사용한다는 점입니다. 이 개념을 익히면 다양한 문제를 효율적으로 해결할 수 있습니다.