Tan Kim
Blog/develop

dp

동적 프로그래밍 (Dynamic Programming)

부분 문제의 해를 저장해 재사용함으로써 중복 계산을 제거한다.

접근 방식

방식 설명
Top-Down (Memoization) 재귀 + 캐시
Bottom-Up (Tabulation) 반복문으로 작은 문제부터 해결

피보나치

# Top-Down
from functools import lru_cache
 
@lru_cache(maxsize=None)
def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)
 
# Bottom-Up
def fib(n):
    if n <= 1: return 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]

배낭 문제 (0/1 Knapsack)

N개 물건, 각 무게 w[i]와 가치 v[i], 최대 용량 W.

def knapsack(weights, values, W):
    n = len(weights)
    dp = [[0] * (W+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for w in range(W+1):
            dp[i][w] = dp[i-1][w]  # 미선택
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i][w],
                               dp[i-1][w - weights[i-1]] + values[i-1])
    return dp[n][W]

LCS (최장 공통 부분 수열)

def lcs(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

LIS (최장 증가 부분 수열)

# O(n²)
def lis(arr):
    n = len(arr)
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)
 
# O(n log n) — 이진탐색
import bisect
 
def lis_fast(arr):
    tails = []
    for x in arr:
        pos = bisect.bisect_left(tails, x)
        if pos == len(tails):
            tails.append(x)
        else:
            tails[pos] = x
    return len(tails)

편집 거리 (Edit Distance)

두 문자열을 같게 만드는 최소 삽입/삭제/교체 횟수.

def edit_distance(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n+1) for _ in range(m+1)]
    for i in range(m+1): dp[i][0] = i
    for j in range(n+1): dp[0][j] = j
    for i in range(1, m+1):
        for j in range(1, n+1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j],    # 삭제
                                   dp[i][j-1],    # 삽입
                                   dp[i-1][j-1])  # 교체
    return dp[m][n]

동전 교환 (Coin Change)

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

행렬 체인 곱셈

def matrix_chain(p):  # p[i]: i번째 행렬의 행 수
    n = len(p) - 1
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n+1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                cost = dp[i][k] + dp[k+1][j] + p[i]*p[k+1]*p[j+1]
                dp[i][j] = min(dp[i][j], cost)
    return dp[0][n-1]

메모

← develop 목록으로