동적 계획법 | Dynamic Programming

---

내가 볼려고 작성한 알고리즘 공부.

💾 동적 계획법 (Dynamic Programming, DP)

✅ 1. 개념 이해하기

DP(Dynamic Programming)은 큰 문제를 작은 문제로 나누고, 그 작은 문제들의 정답을 저장해두어 같은 계산을 반복하지 않도록 하는 최적화 기법이다.

DP의 핵심 조건

조건	설명
최적 부분 구조	큰 문제의 정답이 작은 문제의 정답으로 구성됨
중복되는 부분 문제	같은 문제를 여러 번 계산하지 않도록 저장함

✅ 2. DP 기본 구조

2.1 메모이제이션 (Memoization)

이미 계산한 결과를 저장해두고, 다시 그 값을 사용하는 방식 (일반적으로 탑다운)

memo = {}

def dp(n):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = dp(n-1) + dp(n-2)
    return memo[n]

2.2 바텀업 (Bottom-Up)

작은 문제부터 차례대로 해결하며 배열에 저장 (일반적으로 반복문)

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

두 방식 모두 동일한 결과를 얻지만, 바텀업은 재귀 호출 오버헤드가 없어 성능이 좋다.

✅ 3. 1차원 DP 예제

3.1 피보나치 수열

피보나치 수열은 f(n) = f(n-1) + f(n-2)의 점화식으로 정의된다. 하지만 단순 재귀로 풀 경우 중복 호출이 매우 많아져 비효율적이다. DP를 사용하면 계산한 값을 저장하여 반복 계산을 피할 수 있다.

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

3.2 계단 오르기 (백준 2579)

한 번에 1칸 또는 2칸을 오를 수 있고, 연속된 3개의 계단은 밟을 수 없다는 제약이 있다. 이전 두 계단까지의 최대값을 기억하며 최적 경로를 찾기 위해 DP를 사용한다.

• 한 번에 1칸 또는 2칸 오를 수 있을 때, n번째 계단까지 가는 경우의 수

dp[0] = 1
dp[1] = 1
dp[2] = 2
for i in range(3, n+1):
    dp[i] = dp[i-1] + dp[i-2]

3.3 최대 연속합 (Kadane’s 알고리즘)

연속된 부분 수열 중 합이 가장 큰 값을 찾는 문제. 현재 원소를 포함한 연속합을 매 순간 계산하며 최댓값을 갱신한다. 음수가 섞인 배열에서도 최적 부분합을 찾을 수 있다.

max_sum = dp[0] = arr[0]
for i in range(1, len(arr)):
    dp[i] = max(arr[i], dp[i-1] + arr[i])
    max_sum = max(max_sum, dp[i])

✅ 4. 2차원 DP 예제

4.1 최장 공통 부분 수열 (LCS)

두 문자열에서 순서를 유지하며 공통으로 등장하는 가장 긴 부분 수열의 길이를 구하는 문제. 2차원 DP를 사용하여 문자 일치 여부에 따라 이전 상태를 참조하여 값을 누적한다.

dp = [[0] * (m+1) for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, m+1):
        if a[i-1] == b[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

4.2 최장 증가 부분 수열 (LIS)

주어진 수열에서 오름차순으로 정렬된 가장 긴 부분 수열을 찾는 문제. 현재 원소보다 작은 이전 원소들의 최장 길이를 누적하여 해결한다.

dp = [1] * len(arr)
for i in range(len(arr)):
    for j in range(i):
        if arr[j] < arr[i]:
            dp[i] = max(dp[i], dp[j] + 1)

4.3 편집 거리 (Edit Distance)

문자열 A를 B로 바꾸기 위해 필요한 최소 편집 횟수(삽입, 삭제, 교체)를 구하는 문제. 2차원 DP를 이용하여 이전 상태에서의 연산 최소 비용을 저장하며 진행한다.

dp = [[0] * (len_b+1) for _ in range(len_a+1)]
for i in range(len_a+1):
    for j in range(len_b+1):
        if i == 0:
            dp[i][j] = j
        elif j == 0:
            dp[i][j] = i
        elif a[i-1] == b[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])

✅ 5. 고급 DP: 상태 압축 & 비트마스크

5.1 상태 압축 DP

보통 2차원 이상으로 커지는 상태를 비트마스크(정수로 압축) 하여 1차원 배열로 표현하는 기법

# 예: 방문한 도시를 비트마스크로 표현 (TSP)
visited = 1 << start
memo = {}

def tsp(city, visited):
    if visited == (1 << n) - 1:
        return dist[city][start]
    if (city, visited) in memo:
        return memo[(city, visited)]

    min_cost = float('inf')
    for next_city in range(n):
        if not visited & (1 << next_city):
            new_visited = visited | (1 << next_city)
            cost = dist[city][next_city] + tsp(next_city, new_visited)
            min_cost = min(min_cost, cost)

    memo[(city, visited)] = min_cost
    return min_cost

✅ 6. DP 연습 문제 추천

난이도	문제 링크
⭐	백준 9095 - 1,2,3 더하기
⭐⭐	백준 1149 - RGB 거리
⭐⭐⭐	백준 11053 - 가장 긴 증가하는 부분 수열
⭐⭐⭐⭐	백준 2098 - 외판원 순회

✅ 7. 문제 풀이

• 백준 9095 - 1,2,3 더하기

g = [1,2,4]
for j in range(3,11):
    g.append(g[j-1] + g[j-2] + g[j-3])
n = int(input())
t = [int(input()) for _ in range(n)]
for i in t:
    print(g[i-1])

• 백준 1149 - RGB 거리

import sys
input = sys.stdin.readline

n = int(input())
g = [list(map(int,input().split())) for _ in range(n)]
d = [[0] * 3 for _ in range(n)]

d[0][0] = g[0][0]
d[0][1] = g[0][1]
d[0][2] = g[0][2]

for i in range(1,n):
    d[i][0] = g[i][0] + min(d[i-1][1],d[i-1][2])
    d[i][1] = g[i][1] + min(d[i-1][0],d[i-1][2])
    d[i][2] = g[i][2] + min(d[i-1][0],d[i-1][1])

print(min(d[-1]))

• 백준 11053 - 가장 긴 증가하는 부분 수열

n = int(input())
l = list(map(int,input().split()))
d = [1] * n

for i in range(1,n):
    for j in range(i):
        if l[j] < l[i]:
            d[i]= max(d[i],d[j]+1)
print(max(d))

-백준 2098 - 외판원 순회(실패)

import sys
from functools import lru_cache

input = sys.stdin.readline
n = int(input())
g = [list(map(int,input().split())) for i in range(n)]

@lru_cache(None)
def tsp(c, v):
    if v == (1 << n) - 1:
        return g[c][0] if g[c][0] > 0 else float('inf')
    min_cost = float('inf')
    for next in range(n):
        if not v & (1 << next) and g[c][next] != 0:
            cost = tsp(next, v | (1 << next)) + g[c][next]
            min_cost = min(min_cost, cost)
    return min_cost
print(tsp(0, 1))

비트 연산자 (<<, &, |)

• 1 << i : 2의 i제곱, i번째 도시를 나타내는 비트 생성
• visited & (1 << i) : i번째 도시를 방문했는지 확인
• visited | (1 << i) : i번째 도시를 방문했다고 표시
• 비트마스크를 쓰는 이유: 메모리 절약 + 빠른 방문 체크 (O(1))

@lru_cache란?

• lru_cache는 Least Recently Used cache의 약자
• 같은 인자에 대해 함수 호출 시 결과를 자동 저장(메모이제이션)
• 다음에 똑같은 호출이 들어오면 함수 실행 없이 캐시 반환 → 속도 UP