DP(Dynamic Programming)란?

DP(Dynamic Programming)란?

Dynamic Programming(동적 계획법)은
하위 문제의 정답을 저장해두고 그것을 활용해
전체 문제를 효율적으로 푸는 알고리즘 설계 기법입니다.

DP는 언제 쓰는가?

다음 두 조건을 동시에 만족할 때 DP로 풀 수 있습니다.

1. Overlapping Subproblems (부분 문제 중복)

→ 동일한 계산을 여러 번 반복함

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

→ 전체 문제의 최적해가 부분 문제의 최적해로부터 구성됨

---

전통적인 재귀 vs DP 방식 비교

예: 피보나치 수열

• 재귀 방식 (중복 계산 발생)

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

시간복잡도: O(2ⁿ) - 거의 지수 시간

 

• 메모이제이션 방식 (Top-down DP)

memo = [-1] * 100
def fib(n):
    if memo[n] != -1:
        return memo[n]
    if n <= 1:
        memo[n] = n
    else:
        memo[n] = fib(n-1) + fib(n-2)
    return memo[n]

시간복잡도: O(n)
→ 중복 계산 제거, 저장 후 재활용

---

Bottom-up 방식 (Tabulation)

특징

• 반복문으로 아래부터 계산
• 재귀 없이 구현
• 메모이제이션보다 공간 최적화가 쉬움

def fib(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]

 

O(n)시간, O(n)공간
→ 공간도 아끼고 싶다면?

---

공간 최적화 기법

def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

공간복잡도: O(1)

---

점화식 세우는 법

1. 상태 정의

• dp[i]: i번째 문제까지 고려했을 때의 최적 해

2. 점화식 설계

• 문제를 작은 subproblem으로 쪼갬
• 중복되는 계산을 식으로 일반화

3. 초기값 세팅

• base case부터 dp 테이블 채우기

예제

# dp[n] = dp[n-1] + dp[n-2]
def climb_stairs(n):
    dp = [0] * (n+1)
    dp[0] = dp[1] = 1
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

---

자주 나오는 DP 문제 유형 패턴

유형	핵심 점화식 구조
피보나치	dp[n] = dp[n-1] + dp[n-2]
배낭 문제 (0/1 Knapsack)	dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt[i]] + val[i])
최소 비용 경로	dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + cost[i][j]
문자열 비교 (LCS)	dp[i][j] = dp[i-1][j-1] + 1 or max(dp[i-1][j], dp[i][j-1])
팰린드롬 서브스트링	dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]

---

실전 적용

• 반복되는 재귀 호출이 있다면 → DP로 변경해보자
• 탐색 기반 문제를 table로 바꾸면 → 효율성 개선 가능
• DFS + memoization (Top-down)도 DP의 일종임
• DP는 단순 구현보다 문제 해석력이 더 중요

---

결론

DP는 어려운 개념처럼 느껴지지만,
"작은 문제부터 큰 문제로 확장하는 사고방식"만 익히면
다양한 문제에 응용할 수 있습니다.

 

여기서 가장 중요한것은

점화식을 세우고 사고를 반복적으로 훈련하는 것!!