동적 계획법

복잡한 문제를 더 간단한 하위 문제로 나누어 해결하는 방법론이다. DP는 하위 문제의 해결 결과를 저장하여 동일한 하위 문제가 다시 나타날 때 재사용함으로써 계산을 반복하지 않아 효율성을 높이는 방법을 사용한다.

일반적으로 다음 두 가지 조건을 만족할 때 유용하다.

최적 부분 구조 (Optimal Substructure)
문제의 최적 해결 방법이 하위 문제의 최적 해결 방법으로 구성될 수 있는 경우.

중복 부분 문제 (Overlapping Subproblems)
동일한 작은 문제들이 반복적으로 해결되는 경우.

🔍 접근 방식

DP는 복잡한 문제를 해결하는데 있어 두 가지 주요 접근 방식을 사용한다.

1. 탑다운(Top-Down) 접근 방식

탑다운 방식은 문제를 큰 문제에서 작은 문제로 재귀적으로 쪼개면서 해결하는 방법이다. 각 하위 문제의 결과를 메모이제이션(memoization)을 통해 저장하여 동일한 하위 문제를 반복해서 해결하지 않도록 한다.

# 피보나치 수열
def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n == 0:
        memo[n] = 0
    elif n == 1:
        memo[n] = 1
    else:
        memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

print(fib_memo(10))  # Output: 55

2. 바텀업(Bottom-Up) 접근 방식

바텀업 방식은 작은 하위 문제부터 차례대로 해결해 나가면서 점차적으로 큰 문제를 해결하는 방법이다. 반복문을 사용하여 구현되며, 메모리 상에 배열을 사용해 하위 문제의 결과를 저장한다.

# 피보나치 수열
def fib_bottom_up(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    dp = [0] * (n + 1)
    dp[0] = 0
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

print(fib_bottom_up(10))  # Output: 55

🔍 문제 접근

1. 문제 정의 및 구조 이해

주어진 문제를 여러 하위 문제로 나누어 생각한다.
하위 문제들이 겹치는지 확인한다.

2. 상태 정의

DP 테이블을 정의하고, 각 상태가 무엇을 의미하는지 명확히 한다.
ex) 피보나치 수열에서는 dp[i]가 i번째 피보나치 수를 의미.

3. 초기 조건 설정

가장 작은 하위 문제(기저 사례)를 정의한다.
ex) 피보나치 수열에서는 dp[0] = 0, dp[1] = 1이 초기 조건.

4. 점화식(Transition) 정의

각 상태에서 다음 상태로의 전이를 정의한다.
ex) 피보나치 수열에서는 dp[i] = dp[i-1] + dp[i-2]가 점화식.

5. 최적해 결정

최종적으로 구하고자 하는 문제의 해를 결정한다.
ex) 피보나치 수열에서는 dp[n]가 최적해.

✅ 탑다운 (하향식 접근)과 바텀업 (상향식 접근) 비교

탑다운 방식은 재귀를 사용하는 방식이고, 바텀업 방식은 반복문을 사용하는 방식이다.
바텀업 방식이 더 직관적이고, 스택 오버플로우의 위험이 없다.

특징	탑다운(Top-Down)	바텀업(Bottom-Up)
정의	큰 문제를 작은 문제로 재귀적으로 분할	작은 문제부터 해결하여 큰 문제로 확장
방법	메모이제이션(Memoization)을 사용한 재귀 방식	반복문을 사용한 반복적 방식
재귀	예	아니요
메모리 사용	스택을 사용하여 재귀 호출이 많아질 수 있음	주로 배열을 사용
구현 난이도	비교적 직관적이고 구현이 쉬움	구현이 다소 복잡할 수 있음
성능 최적화	불필요한 호출을 줄이기 위해 메모이제이션 사용	반복적 계산으로 오버헤드가 적음
초기화	기저 사례만 초기화	모든 하위 문제의 초기값 설정
예제 코드	피보나치 수열, 각종 최적화 문제	피보나치 수열, 최장 공통 부분 수열(LCS)

💻 빈출 예제

1. 피보나치 수열
피보나치 수열은 앞 두 항의 합이 다음 항이 되는 수열이다.
DP를 통해 중복 계산을 피할 수 있다.

2. 최장 증가 부분 수열 (Longest Increasing Subsequence, LIS)
수열에서 일부 항을 제거하여 얻을 수 있는 가장 긴 증가하는 부분 수열을 찾는다.

3. 배낭 문제
정해진 무게 한도 내에서 최대 가치를 얻도록 물건을 담는 문제.

4. 최소 비용 경로
격자(grid)에서 왼쪽 상단에서 오른쪽 하단으로 이동할 때 최소 비용을 찾는다.

5. 문자열 편집 거리
두 문자열을 같은 문자열로 만들기 위해 수행해야 하는 편집 작업의 최소 횟수 구하기.