동적 계획법(DP) 코딩테스트 완전 정복: 개념부터 실전 문제까지

동적 계획법이란?

동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 작은 하위 문제들로 분할하여 해결하는 알고리즘 설계 기법입니다. 한 번 계산한 결과를 저장해두고 재사용함으로써 중복 계산을 제거하여 효율성을 극대화합니다.

핵심 아이디어: “이미 풀었던 문제는 다시 풀지 않는다!”

DP vs 분할 정복

DP가 필요한 문제 특징

동적 계획법을 적용하려면 다음 두 가지 조건을 만족해야 합니다:

1. 최적 부분 구조(Optimal Substructure): 전체 문제의 최적해가 부분 문제의 최적해로 구성됨
2. 중복되는 부분 문제(Overlapping Subproblems): 같은 하위 문제가 반복적으로 계산됨

피보나치 수열 예시

피보나치 수열 $F(n) = F(n-1) + F(n-2)$를 재귀로 구현하면:

def fib_recursive(n):
    if n <= 1:
        return n
    return fib_recursive(n-1) + fib_recursive(n-2)

문제점: $F(5)$를 계산할 때 $F(3)$이 2번, $F(2)$가 3번 중복 계산됩니다. 시간 복잡도는 $O(2^n)$으로 폭발적으로 증가합니다.

DP 구현 방식

1. Top-down (메모이제이션)

재귀 함수에 캐싱을 추가하여 이미 계산된 값을 재사용합니다.

def fib_memoization(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n

    memo[n] = fib_memoization(n-1, memo) + fib_memoization(n-2, memo)
    return memo[n]

# 또는 @lru_cache 데코레이터 활용
from functools import lru_cache

@lru_cache(maxsize=None)
def fib_cache(n):
    if n <= 1:
        return n
    return fib_cache(n-1) + fib_cache(n-2)

시간 복잡도: $O(n)$
공간 복잡도: $O(n)$ (재귀 스택 + 메모 테이블)

2. Bottom-up (타뷸레이션)

반복문으로 작은 문제부터 차례대로 해결하며 테이블을 채웁니다.

def fib_tabulation(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]

시간 복잡도: $O(n)$
공간 복잡도: $O(n)$ (재귀 스택 없음)

실무 팁: 코딩테스트에서는 Bottom-up이 스택 오버플로우 위험이 없고 구현이 직관적이어서 선호됩니다.

공간 최적화

현재 값이 직전 2개 값에만 의존하면 배열 없이 변수 2개로 충분합니다.

def fib_optimized(n):
    if n <= 1:
        return n

    prev2, prev1 = 0, 1
    for _ in range(2, n + 1):
        current = prev1 + prev2
        prev2, prev1 = prev1, current

    return prev1

공간 복잡도: $O(1)$

대표 DP 문제 유형

1. 1차원 DP: 계단 오르기

문제: n번째 계단까지 1칸 또는 2칸씩 오르는 방법의 수는?

점화식: $dp[n] = dp[n-1] + dp[n-2]$
여기서 $dp[i]$는 i번째 계단에 도달하는 방법의 수입니다.

def climb_stairs(n):
    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]

2. 2차원 DP: 배낭 문제 (0/1 Knapsack)

문제: 무게 제한 W인 배낭에 가치를 최대화하며 물건을 담으려면?

점화식:
$$dp[i][w] = \max(dp[i-1][w], \; dp[i-1][w – weight_i] + value_i)$$

• $dp[i][w]$: i번째 물건까지 고려했을 때 무게 w 이하에서 얻을 수 있는 최대 가치
• 첫 번째 항: i번째 물건을 선택하지 않는 경우
• 두 번째 항: i번째 물건을 선택하는 경우 (무게 여유가 있을 때만)

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(1, W + 1):
            if weights[i-1] <= w:
                dp[i][w] = max(
                    dp[i-1][w],  # 선택 안 함
                    dp[i-1][w - weights[i-1]] + values[i-1]  # 선택
                )
            else:
                dp[i][w] = dp[i-1][w]

    return dp[n][W]

# 예시
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
print(knapsack(weights, values, 8))  # 출력: 9 (3kg + 5kg)

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

문제: 배열에서 증가하는 순서를 유지하는 가장 긴 부분 수열의 길이는?

점화식:
dp[i] = \max_{j < i, \; arr[j] < arr[i]}(dp[j]) + 1

$dp[i]$는 i번째 원소를 마지막으로 하는 LIS 길이입니다.

def longest_increasing_subsequence(arr):
    n = len(arr)
    dp = [1] * n  # 모든 원소는 최소 길이 1

    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)

print(longest_increasing_subsequence([10, 9, 2, 5, 3, 7, 101, 18]))  # 4: [2,3,7,18]

시간 복잡도: $O(n^2)$
이진 탐색으로 $O(n \log n)$까지 최적화 가능

실전 문제 해결 전략

DP 문제 접근 5단계

1. DP 테이블 정의: dp[i]가 무엇을 의미하는지 명확히 정의
2. 점화식 도출: 현재 상태가 이전 상태들과 어떤 관계인지 수식화
3. 초기값 설정: dp[0], dp[1] 등 기저 사례 처리
4. 계산 순서 결정: Top-down vs Bottom-up 선택
5. 최종 답 도출: dp[n] 또는 max(dp) 등

디버깅 팁

# DP 테이블 중간 출력으로 로직 검증
for i in range(n):
    # ... dp[i] 계산 ...
    print(f"dp[{i}] = {dp[i]}")  # 각 단계 확인

실무 활용 사례

• 경로 탐색: 최단 경로, 최소 비용 경로 (네비게이션, 물류)
• 문자열 처리: 편집 거리(Edit Distance), 최장 공통 부분 수열(LCS)
• 게임 AI: 최적 전략 계산 (체스, 바둑)
• 금융: 주식 매매 최적화, 포트폴리오 관리

마무리

동적 계획법은 중복 계산 제거를 통해 지수 시간 알고리즘을 다항 시간으로 극적으로 개선하는 강력한 도구입니다. 핵심은:

• ✅ 문제 분해: 큰 문제를 작은 부분 문제로 나누기
• ✅ 메모이제이션: 계산 결과 저장 및 재사용
• ✅ 점화식 도출: 현재 상태와 이전 상태의 관계 수식화
• ✅ 구현 방식 선택: Top-down(재귀) vs Bottom-up(반복)

코딩테스트에서 DP 문제는 출제 빈도가 높고 난이도도 다양하므로, 대표 유형(피보나치, 배낭, LIS, LCS)을 반복 연습하여 점화식 도출 감각을 키우는 것이 중요합니다. 처음엔 어렵지만, 패턴이 보이기 시작하면 다양한 문제에 응용할 수 있습니다!