DP(Dynamic Programming)란?

DPDynamicProgrammingDynamic 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 방식 TabulationTabulation

특징

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

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

 

여기서 가장 중요한것은

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