[2026] DP 패턴 | 동적 프로그래밍 유형별 풀이 전략

· 22분 읽기 · 수정 고급 튜토리얼
[2026] DP 패턴 | 동적 프로그래밍 유형별 풀이 전략

이 글의 핵심

DP 패턴: 동적 프로그래밍 유형별 풀이 전략. 1차원 DP 패턴·2차원 DP 패턴.

들어가며

”DP 문제는 패턴이다”

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

코딩 테스트 준비하며 깨달은 것

알고리즘 문제를 풀다 보면 “이게 실무에 무슨 도움이 될까?” 하는 의문이 들 때가 있습니다. 저도 그랬습니다. 하지만 실제 프로젝트에서 성능 문제에 부딪히면, 알고리즘 지식이 얼마나 중요한지 깨닫게 됩니다. 예를 들어, 사용자 검색 기능이 느려서 고민하다가 해시 테이블을 적용하니 응답 시간이 10초에서 0.1초로 줄어든 경험이 있습니다. 코딩 테스트는 단순히 취업을 위한 관문이 아니라, 문제 해결 능력을 키우는 훈련장입니다. 처음엔 브루트 포스로 풀다가, 시간 복잡도를 개선하는 과정에서 “아, 이렇게 생각하면 되는구나” 하는 깨달음을 얻을 때의 쾌감은 말로 표현하기 어렵습니다. 이 글에서는 단순히 정답 코드만 제시하는 게 아니라, 문제를 어떻게 접근하고 최적화하는지 사고 과정을 함께 공유하겠습니다.

1. 1차원 DP 패턴

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

패턴 1: 이전 값 활용

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

패턴 2: 최대/최소 선택

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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)

2. 2차원 DP 패턴

패턴 1: 격자 경로

아래 코드는 python를 사용한 구현 예제입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

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

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

3. 배낭 문제 패턴

0-1 배낭

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

무한 배낭

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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))  # 120

4. LIS (최장 증가 부분 수열)

O(n²) 풀이

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

O(n log n) 풀이

다음은 python를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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 패턴 인식

아래 코드는 python를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 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 배낭, 동전 문제

정리

핵심 요약

  1. 1D DP: 이전 값 활용, 최대/최소 선택
  2. 2D DP: 격자, LCS, 배낭
  3. LIS: O(n²) 또는 O(n log n)
  4. 패턴 인식: 문제 → 패턴 매칭

추천 문제

백준:

관련 글

... 996 lines not shown ... Token usage: 63706/1000000; 936294 remaining Start-Sleep -Seconds 3