DP 패턴 정리: 1차원·2차원 DP, 배낭 문제, LIS 점화식 세우는 법

시리즈 안내

#13 | 📋 전체 목차 | 이전: #12 DP 기초 · 다음: #14 DP 문제

---

들어가며

대부분의 DP 문제는 몇 가지 패턴의 변형입니다. 패턴을 익히면 새로운 문제도 쉽게 풀 수 있습니다.

DP를 푸는 과정은 거의 항상 같은 네 단계입니다. ① dp[...]가 무엇을 뜻하는지 한 문장으로 정의하고, ② 그 값을 더 작은 부분 문제로 표현하는 점화식을 세우고, ③ 가장 작은 경우(초기값)를 채우고, ④ 참조하는 값이 먼저 계산되도록 순회 순서를 정합니다. 이 중 가장 어렵고 중요한 것은 ①입니다. 상태 정의가 모호하면 점화식이 맞는지 판단할 수 없고, 정의가 명확하면 점화식은 대부분 “마지막에 무엇을 선택했는가”를 경우로 나누는 것만으로 나옵니다. 아래 패턴들은 결국 자주 쓰이는 상태 정의의 목록이라고 보면 됩니다. DP의 기본 개념(중복 부분 문제, 최적 부분 구조, 메모이제이션)은 #12 DP 기초에서 다뤘습니다.

---

1차원 DP 패턴

1차원 DP에서 dp[i]는 보통 “첫 번째부터 i번째까지” 또는 “길이 i인 부분 문제의 최적값”을 뜻합니다. 아래 두 예는 이전 칸의 값만으로 다음 칸을 채우는 대표 패턴입니다.

패턴 1: 이전 값 활용

def climb_stairs(n):
    """
    계단 오르기 (1칸 또는 2칸)
    dp[i] = dp[i-1] + dp[i-2]
    """
    if n <= 2:
        return n
    
    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 2
    
    for i in range(3, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]
print(climb_stairs(5))  # 8

dp[i]는 “i번째 계단에 도착하는 방법의 수”입니다. i번째 계단에 도착하기 직전의 한 걸음은 1칸이거나 2칸이므로, i-1번째에서 오는 방법과 i-2번째에서 오는 방법을 더하면 됩니다. 결과가 피보나치 수열과 같은 이유입니다. 이렇게 마지막 한 걸음을 경우로 나누는 방식이 1차원 DP 점화식의 기본형이며, 한 번에 1·2·3칸을 오를 수 있다면 dp[i-3]을 더하는 것으로 자연스럽게 확장됩니다.

점화식이 dp[i-1]과 dp[i-2]만 참조하므로 배열 전체를 둘 필요 없이 변수 두 개로 O(1) 공간에 풀 수 있습니다. 다만 n이 커지면 경우의 수가 기하급수적으로 커져서, C++이나 Java라면 long으로도 넘치고 문제에서 “1,000,000,007로 나눈 나머지”를 요구하는 이유가 여기 있습니다. Python은 정수 크기에 제한이 없어 오버플로는 없지만 큰 수 연산이 느려지므로 나머지 연산을 매 단계 적용하는 편이 좋습니다.

패턴 2: 최대/최소 선택

def rob(houses):
    """
    집 털기 (인접한 집은 털 수 없음)
    dp[i] = max(dp[i-1], dp[i-2] + houses[i])
    """
    if not houses:
        return 0
    if len(houses) == 1:
        return houses[0]
    
    dp = [0] * len(houses)
    dp[0] = houses[0]
    dp[1] = max(houses[0], houses[1])
    
    for i in range(2, len(houses)):
        dp[i] = max(dp[i-1], dp[i-2] + houses[i])
    
    return dp[-1]
# 테스트
print(rob([2, 7, 9, 3, 1]))  # 12 (2+9+1)

dp[i]는 “0번부터 i번 집까지만 고려했을 때 훔칠 수 있는 최대 금액”입니다. i번 집에 대해서는 털지 않거나(dp[i-1] 그대로), 털거나(인접한 i-1번은 못 털었으니 dp[i-2] + houses[i]) 둘 중 큰 쪽을 고릅니다. 계단 오르기와 구조는 같지만 더하기 대신 max라는 점이 “경우의 수” DP와 “최적값” DP의 차이입니다.

“큰 집부터 고르는” 그리디는 여기서 통하지 않습니다. [2, 7, 9, 3, 1]에서 가장 큰 9를 먼저 고르면 7과 3을 못 쓰게 되어 9+2+1=12로 우연히 정답이지만, [5, 6, 5]처럼 가장 큰 6을 고르는 순간 5+5=10이라는 더 나은 답을 놓칩니다. 현재의 선택이 뒤의 선택지를 바꾸는 문제는 그리디보다 DP를 먼저 의심해야 하는 신호입니다. 초기값 dp[1] = max(houses[0], houses[1])을 houses[1]로 잘못 두는 실수도 흔한데, 두 번째 집이 더 싸면 첫 번째 집만 터는 것이 최선이기 때문입니다. 집이 원형으로 배치되어 첫 집과 마지막 집이 인접한 변형은 “첫 집을 제외한 경우”와 “마지막 집을 제외한 경우”를 각각 풀어 큰 값을 고릅니다.

---

2차원 DP 패턴

패턴 1: 격자 경로

def unique_paths(m, n):
    """
    m×n 격자에서 경로의 수
    dp[i][j] = dp[i-1][j] + dp[i][j-1]
    """
    dp = [[1] * n for _ in range(m)]
    
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    
    return dp[m-1][n-1]
print(unique_paths(3, 7))  # 28

오른쪽이나 아래로만 움직일 수 있다면 (i, j)에 도착하는 직전 칸은 위(i-1, j)나 왼쪽(i, j-1) 둘뿐입니다. 첫 행과 첫 열은 한 방향으로만 갈 수 있어 경로가 1개이므로 전체를 1로 채우고 시작했습니다. 순회를 위에서 아래, 왼쪽에서 오른쪽으로 하는 이유는 참조하는 두 칸이 항상 먼저 계산되도록 하기 위해서입니다. 이 순서를 바꾸면 아직 계산되지 않은 값을 읽어 틀린 답이 나옵니다.

이 문제는 사실 조합 공식 C(m+n-2, m-1)로 바로 계산할 수 있지만, DP로 푸는 방식은 장애물이 있는 격자(프로그래머스 “등굣길”)나 칸마다 비용이 있는 최소 경로 합 문제로 그대로 확장된다는 장점이 있습니다. 장애물 칸은 dp[i][j] = 0으로 두면 되는데, 이때 “첫 행·첫 열은 전부 1”이라는 초기화가 더 이상 성립하지 않습니다. 첫 행에 장애물이 있으면 그 뒤 칸들은 도달할 수 없어 0이어야 하기 때문입니다. 장애물 문제에서 초기화를 이 예제처럼 해 두고 오답을 받는 경우가 많습니다. 파이썬에서 [[1] * n] * m으로 2차원 리스트를 만들면 모든 행이 같은 리스트를 공유하므로, 예제처럼 리스트 컴프리헨션으로 행마다 새 리스트를 만들어야 합니다.

패턴 2: LCS (최장 공통 부분 수열)

def lcs(s1, s2):
    """
    Longest Common Subsequence
    "ABCDGH", "AEDFHR" → "ADH" (길이 3)
    """
    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]
# 테스트
print(lcs("ABCDGH", "AEDFHR"))  # 3

두 문자열을 다루는 DP는 dp[i][j]를 “s1의 앞 i글자와 s2의 앞 j글자에 대한 답”으로 정의하는 것이 표준입니다. 마지막 글자가 같으면 그 글자를 공통 수열에 포함하고 둘 다 한 글자씩 줄인 문제(dp[i-1][j-1] + 1)로 가고, 다르면 둘 중 한쪽의 마지막 글자를 버린 두 경우 중 나은 쪽을 고릅니다. 같은 틀에서 점화식만 바꾸면 편집 거리(삽입·삭제·교체 비용), 최장 공통 부분 문자열(연속이어야 하므로 다르면 0), 두 문자열을 섞어 세 번째 문자열 만들기 같은 문제가 풀립니다.

배열 크기를 (m+1) × (n+1)로 한 칸 크게 잡고 인덱스를 s1[i-1]로 쓰는 이유는, dp[0][*]과 dp[*][0]을 “빈 문자열과의 LCS = 0”이라는 초기값으로 쓰기 위해서입니다. 덕분에 i-1이 음수가 되는 경계 처리를 따로 하지 않아도 됩니다. 이 방식에서 dp[i]와 s1[i]의 인덱스가 한 칸 어긋난다는 점을 잊고 s1[i] == s2[j]로 비교하는 실수가 가장 흔합니다.

이 함수는 길이만 돌려줍니다. 실제 공통 수열(“ADH”)이 필요하면 dp[m][n]에서 출발해 글자가 같으면 대각선으로, 다르면 값이 큰 쪽으로 거슬러 올라가며 글자를 모은 뒤 뒤집으면 됩니다. 문자열 길이가 각각 수만이면 O(nm) 표가 수억 칸이 되어 메모리가 부족하므로, 길이만 필요하다면 이전 행 하나만 유지하는 2행 배열로 줄입니다.

---

배낭 문제 패턴

0-1 배낭

def knapsack_01(weights, values, capacity):
    """
    각 물건을 0개 또는 1개만
    """
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(capacity + 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][capacity]
# 테스트
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 8
print(knapsack_01(weights, values, capacity))  # 10

dp[i][w]는 “앞의 i개 물건만 고려하고 용량이 w일 때 얻을 수 있는 최대 가치”입니다. i번 물건을 넣지 않으면 앞의 i-1개로 용량 w를 쓰는 것과 같고, 넣으면 i번 물건의 무게만큼 용량이 줄어든 상태에서 앞의 i-1개로 만든 최선에 i번의 가치를 더합니다. 넣는 경우에도 dp[i-1] 행을 참조한다는 것이 “각 물건은 한 번만”이라는 조건을 보장합니다. 예제의 답 10은 무게 3(가치 4)과 무게 5(가치 6)를 고른 결과입니다.

가치 대비 무게 비율이 높은 물건부터 담는 그리디는 여기서 틀린 답을 냅니다. 비율로 고르면 무게 2(1.5)와 3(1.33)을 먼저 담고 남은 용량 3에 넣을 물건이 없어 7에 그칩니다. 그리디는 물건을 쪼갤 수 있는 “분할 가능 배낭”에서만 최적입니다.

2차원 표는 이전 행만 참조하므로 1차원 배열 하나로 줄일 수 있습니다. 이때 FAQ에서 설명하듯 용량을 큰 쪽에서 작은 쪽으로 돌아야 합니다. for w in range(capacity, weights[i] - 1, -1): dp[w] = max(dp[w], dp[w - weights[i]] + values[i])처럼 쓰면 dp[w - weights[i]]가 아직 이번 물건으로 갱신되지 않은 “이전 행” 값이라 같은 물건이 두 번 들어가지 않습니다. 시간 복잡도는 O(n × capacity)라 용량이 10^9처럼 크면 쓸 수 없고, 그런 문제는 가치를 축으로 바꾸거나 다른 접근이 필요합니다.

무한 배낭

def knapsack_unbounded(weights, values, capacity):
    """
    각 물건을 무한대로
    """
    dp = [0] * (capacity + 1)
    
    for w in range(capacity + 1):
        for i in range(len(weights)):
            if weights[i] <= w:
                dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    
    return dp[capacity]
# 테스트
weights = [1, 3, 4]
values = [15, 50, 60]
capacity = 8
print(knapsack_unbounded(weights, values, capacity))  # 130 (무게 3×2 + 무게 1×2)

무한 배낭은 같은 물건을 여러 번 쓸 수 있으므로 “몇 번째 물건까지 고려했는가”라는 축이 필요 없고, dp[w] = “용량 w로 얻을 수 있는 최대 가치”만으로 충분합니다. dp[w - weights[i]]에는 이미 i번 물건을 넣은 경우가 포함되어 있을 수 있고, 그것이 바로 “여러 번 넣기”를 허용하는 부분입니다. 예제의 답은 가치 50짜리(무게 3) 두 개와 15짜리(무게 1) 두 개를 담은 130입니다. 가치 60짜리(무게 4)를 두 개 담으면 120이라 직관적으로 고를 법한 답보다 크다는 점에서, 사람이 어림으로 푼 값과 DP 결과를 비교해 보는 것이 좋은 검증이 됩니다.

0-1 배낭의 1차원 버전과 비교하면 차이는 순회 방향 하나입니다. 용량을 작은 쪽에서 큰 쪽으로 돌면 앞에서 갱신한 값을 다시 참조해 같은 물건이 누적되고(무한 배낭), 큰 쪽에서 작은 쪽으로 돌면 갱신 전 값만 참조해 한 번씩만 들어갑니다(0-1 배낭). 코드 한 줄의 방향이 문제의 의미를 바꾸기 때문에, 어떤 배낭인지 먼저 확인하지 않고 외운 코드를 붙여 넣으면 오답이 나기 쉽습니다. 동전 거스름돈의 “최소 동전 개수”는 무한 배낭의 최솟값 버전이고, “만드는 방법의 수”를 셀 때는 바깥 반복을 물건(동전), 안쪽을 용량으로 두어야 순서만 다른 조합이 중복으로 세어지지 않습니다. 이 예제처럼 바깥이 용량이면 1+3과 3+1을 다른 방법으로 세는 “순열” 개수가 됩니다.

---

LIS (최장 증가 부분 수열)

O(n²) 풀이

def lis_n2(arr):
    """
    Longest Increasing Subsequence
    [10, 9, 2, 5, 3, 7, 101, 18] → 4 ([2,3,7,18])
    """
    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)
# 테스트
arr = [10, 9, 2, 5, 3, 7, 101, 18]
print(lis_n2(arr))  # 4

dp[i]는 “i번째 원소로 끝나는 가장 긴 증가 부분 수열의 길이”입니다. “0~i번째 중 가장 긴 증가 수열”로 정의하면 점화식을 세울 수 없는데, 다음 원소를 붙일 수 있는지 판단하려면 수열의 마지막 값을 알아야 하기 때문입니다. 끝 원소를 고정하면 “i 앞에 있는 j 중 arr[j] < arr[i]인 것 뒤에 i를 붙인다”는 점화식이 자연스럽게 나옵니다. 이 정의 때문에 답은 dp[-1]이 아니라 max(dp)입니다. 가장 긴 수열이 마지막 원소로 끝난다는 보장이 없으므로, dp[-1]을 반환하는 실수는 흔한 오답 원인입니다. 빈 배열에서는 max(dp)가 ValueError를 내므로 입력이 비어 있을 수 있다면 따로 처리합니다.

O(n log n) 풀이

import bisect
def lis_nlogn(arr):
    """
    이진 탐색 활용
    """
    dp = []
    
    for num in arr:
        pos = bisect.bisect_left(dp, num)
        
        if pos == len(dp):
            dp.append(num)
        else:
            dp[pos] = num
    
    return len(dp)
# 테스트
arr = [10, 9, 2, 5, 3, 7, 101, 18]
print(lis_nlogn(arr))  # 4

이 풀이의 dp[k]는 앞 풀이와 의미가 전혀 다릅니다. “길이가 k+1인 증가 부분 수열들 중 마지막 값의 최솟값”입니다. 같은 길이라면 끝 값이 작을수록 뒤에 더 많은 수를 붙일 수 있으므로 가장 작은 끝 값만 기억하면 충분하고, 이 배열은 항상 오름차순이라 이진 탐색으로 위치를 찾을 수 있습니다. 새 수가 모든 끝 값보다 크면 가장 긴 수열을 한 칸 늘리고, 아니면 자기 이상인 첫 끝 값을 자신으로 교체해 “같은 길이를 더 작은 끝 값으로” 개선합니다.

예제를 따라가면 dp는 [10] → [9] → [2] → [2, 5] → [2, 3] → [2, 3, 7] → [2, 3, 7, 101] → [2, 3, 7, 18]로 바뀝니다. 마지막 dp가 우연히 실제 LIS 중 하나지만, 일반적으로 dp 배열은 실제 부분 수열이 아닙니다. [3, 4, 1]이면 결과가 [1, 4]가 되는데 원래 순서상 1은 4보다 뒤에 있습니다. 길이만 정확하므로, 실제 수열이 필요하면 각 원소가 들어간 위치와 직전 원소를 따로 기록해 역추적해야 합니다.

bisect_left는 같은 값이 이미 있으면 그 자리를 교체하므로 순증가 수열(같은 값 불가)의 길이를 구합니다. 같은 값을 허용하는 비감소 수열이라면 bisect_right로 바꿔야 하며, 이 한 글자 차이가 백준 “가장 긴 증가하는 부분 수열” 변형 문제들에서 오답의 흔한 원인입니다. n이 10^5 이상이면 O(n²)은 시간 초과이므로 이 풀이가 필수가 됩니다.

---

문제 문장에서 DP 패턴 알아보기

# 1. 1D DP
# - 이전 값 활용: dp[i] = f(dp[i-1], dp[i-2])
# - 예: 피보나치, 계단 오르기
# 2. 2D DP
# - 격자: dp[i][j] = f(dp[i-1][j], dp[i][j-1])
# - 문자열: dp[i][j] = f(s1[i], s2[j])
# - 예: LCS, 편집 거리
# 3. 배낭
# - 선택/비선택: dp[i][w] = max(안넣음, 넣음)
# - 예: 0-1 배낭, 동전 문제

문제를 보고 패턴을 고를 때는 문제 문장에서 신호를 찾습니다. “n번째”, “i칸까지”처럼 한 방향으로 진행하는 문제는 1차원, “두 문자열”, “격자”, “구간 [i, j]“가 나오면 2차원, “무게·비용 한도 안에서 고른다”면 배낭입니다. 경우의 수를 묻는지(더하기) 최적값을 묻는지(max/min)도 점화식의 연산을 결정합니다.

처음 DP 문제를 풀 때 흔히 겪는 어려움은 점화식은 떠올렸는데 테스트에서 틀리는 경우입니다. 대부분 초기값과 경계 조건 문제라서, n = 0, 1, 2 같은 아주 작은 입력을 손으로 계산한 값과 dp 배열을 출력해 비교해 보면 원인이 금방 드러납니다. 점화식이 떠오르지 않을 때는 재귀와 메모이제이션(functools.lru_cache)으로 먼저 풀어 보는 것도 좋은 방법입니다. 재귀 함수의 매개변수가 곧 상태이고 반환값이 dp 값이라, 동작하는 재귀 풀이를 반복문으로 옮기면 표 방식 DP가 됩니다. 다만 Python의 기본 재귀 한도는 1000이라 깊은 재귀는 sys.setrecursionlimit을 늘리거나 반복문으로 바꿔야 합니다. 실전 문제 적용은 #14 DP 문제에서 이어집니다.

---

추천 문제와 배낭 반복 방향 함정

배낭 패턴을 1차원 배열로 줄일 때 반복 방향이 답을 바꿉니다. 0-1 배낭(물건을 한 번씩만 쓰는 경우)은 용량을 큰 쪽에서 작은 쪽으로 돌아야 같은 물건이 두 번 담기지 않고, 개수 제한이 없는 배낭(동전처럼 여러 번 쓰는 경우)은 작은 쪽에서 큰 쪽으로 돌아야 합니다. 방향을 반대로 쓰면 에러 없이 틀린 값이 나오기 때문에, 2차원 표로 먼저 맞힌 뒤 1차원으로 줄이는 순서가 안전합니다.

백준:

• 11053번: 가장 긴 증가하는 부분 수열
• 9251번: LCS

프로그래머스:

• 등굣길
• 정수 삼각형

---

같이 보면 좋은 글

• 동적 프로그래밍(DP)
• 알고리즘 시리즈 전체 목차
• 배열과 리스트
• 스택과 큐
• DP 실전 문제 | 코딩 테스트 DP 문제 풀이 전략
• DP Patterns | Dynamic Programming Problem-Solving Strategies

---

자주 묻는 질문 (FAQ)

Q. 0-1 배낭과 무한 배낭은 점화식에서 정확히 어디가 다른가요?

A. 0-1 배낭은 물건 i를 넣을 때 dp[i-1][w - 무게], 즉 아직 i번 물건을 고려하지 않은 이전 행을 참조하므로 같은 물건이 두 번 들어가지 않습니다. 무한 배낭은 1차원 dp[w - 무게]를 그대로 참조하는데, 이 값에는 같은 물건을 이미 넣은 경우가 포함될 수 있어 여러 개 선택이 자연스럽게 허용됩니다. 0-1 배낭을 1차원 배열로 줄일 때 용량을 큰 쪽에서 작은 쪽으로 도는 이유도 이전 행 값을 덮어쓰기 전에 읽기 위해서입니다.

---