다이나믹 프로그래밍(DP) 마스터하기: 코딩테스트 완벽 가이드

개발 문서/코딩테스트

다이나믹 프로그래밍(DP) 마스터하기: 코딩테스트 완벽 가이드

copg 2025. 3. 24. 18:28

728x90

안녕하세요! 오늘은 코딩테스트에서 가장 중요한 알고리즘 패러다임 중 하나인 다이나믹 프로그래밍(Dynamic Programming, DP)에 대해 자세히 알아보겠습니다. DP는 처음 접하면 어렵게 느껴질 수 있지만, 개념을 제대로 이해하고 충분히 연습한다면 코딩테스트의 강력한 무기가 될 수 있습니다.

다이나믹 프로그래밍이란?

다이나믹 프로그래밍은 복잡한 문제를 여러 개의 작은 부분 문제로 나누어 해결하고, 그 결과를 저장해두었다가 재활용하는 알고리즘 설계 기법입니다. 이러한 접근법은 같은 계산을 반복하는 것을 피하게 해주어 시간 복잡도를 크게 개선할 수 있습니다.

DP가 적용 가능한 문제의 특징은 다음과 같습니다:

최적 부분 구조(Optimal Substructure): 큰 문제의 최적해가 작은 부분 문제들의 최적해를 포함하는 구조
중복되는 부분 문제(Overlapping Subproblems): 동일한 작은 문제가 여러 번 반복되는 경우

DP의 핵심 원리

1. 상태 정의하기

DP의 첫 번째 단계는 상태(state)를 정의하는 것입니다. 상태란 부분 문제의 해를 저장하기 위한 변수로, 대개 DP 테이블의 인덱스로 사용됩니다.

예를 들어, 피보나치 수열에서는 dp[i]가 i번째 피보나치 수를 의미합니다.

2. 점화식 세우기

다음으로 상태 간의 관계를 나타내는 점화식(recurrence relation)을 세웁니다. 이는 현재 상태의 값을 이전 상태의 값으로 어떻게 계산할 수 있는지를 나타냅니다.

피보나치 수열의 점화식: dp[i] = dp[i-1] + dp[i-2]

3. 초기값 설정하기

DP 알고리즘을 시작하기 위한 초기값(base case)을 설정합니다.

피보나치 수열의 초기값: dp[0] = 0, dp[1] = 1

DP 접근 방법: Top-down vs Bottom-up

DP 문제는 크게 두 가지 접근 방식으로 해결할 수 있습니다:

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

재귀 함수를 사용하며, 계산 결과를 메모리에 저장(메모이제이션)하여 중복 계산을 방지합니다.

def fib(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]

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

반복문을 사용하여 작은 부분 문제부터 차례대로 해결해 나가는 방식입니다.

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

일반적으로 Bottom-up 방식이 메모리 사용량이 더 예측 가능하고 스택 오버플로우의 위험이 없어 권장됩니다. 그러나 Top-down 방식이 문제를 더 직관적으로 이해하기 쉬운 경우도 있습니다.

대표적인 DP 문제 유형과 풀이

1. 피보나치 수열 (기본)

위에서 이미 다루었으므로 다음으로 넘어가겠습니다.

2. 최장 증가 부분 수열 (LIS: Longest Increasing Subsequence)

문제: 주어진 수열에서 오름차순으로 정렬된 가장 긴 부분 수열의 길이를 찾는 문제

접근법:

dp[i]: arr[0...i] 중에서 arr[i]로 끝나는 최장 증가 부분 수열의 길이

def lis(arr):
    n = len(arr)
    dp = [1] * n

    for i in range(1, n):
        for j in range(i):
            if arr[i] > arr[j]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

3. 배낭 문제 (Knapsack Problem)

문제: 최대 무게 제한이 있는 배낭에 가치가 다른 여러 물건을 넣을 때, 최대 가치를 구하는 문제

접근법:

dp[i][w]: 처음 i개의 물건만 고려하고 배낭 무게가 w일 때의 최대 가치

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i-1] <= w:
                dp[i][w] = max(values[i-1] + dp[i-1][w-weights[i-1]], dp[i-1][w])
            else:
                dp[i][w] = dp[i-1][w]

    return dp[n][capacity]

4. 편집 거리 (Edit Distance)

문제: 한 문자열을 다른 문자열로 변환하기 위해 필요한 최소 편집 횟수를 구하는 문제

접근법:

dp[i][j]: str1의 첫 i글자를 str2의 첫 j글자로 변환하는 데 필요한 최소 편집 횟수

def edit_distance(str1, str2):
    m, n = len(str1), len(str2)
    dp = [[0 for _ in range(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 str1[i-1] == str2[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]

DP 문제 해결 전략

1. 상태 정의하기

문제의 변수가 무엇인지 파악합니다.
부분 문제의 해를 어떻게 표현할 수 있는지 고민합니다.

2. 점화식 도출하기

현재 상태와 이전 상태의 관계를 수식으로 표현해 봅니다.
작은 예시로 시작해서 패턴을 찾아보세요.

3. 초기값 설정하기

가장 작은 부분 문제의 해는 무엇인지 생각해 봅니다.

4. 계산 순서 정하기

Top-down 또는 Bottom-up 중 어떤 방식이 더 적합한지 고려합니다.

5. 공간 복잡도 최적화하기

필요한 경우 1차원 배열로 압축하거나, 필요한 상태만 저장하는 방법을 고려합니다.

연습 문제 추천

다음은 DP 실력을 향상시키기 위한 추천 문제들입니다:

기초 단계
- 계단 오르기 (백준 2579)
- 1, 2, 3 더하기 (백준 9095)
- RGB 거리 (백준 1149)
중급 단계
- 정수 삼각형 (백준 1932)
- 가장 긴 바이토닉 부분 수열 (백준 11054)
- 동전 1 (백준 2293)
고급 단계
- 행렬 곱셈 순서 (백준 11049)
- 외판원 순회 (백준 2098)
- 내리막 길 (백준 1520)

마무리

다이나믹 프로그래밍은 확실히 처음에는 어렵게 느껴질 수 있습니다. 하지만 기본 개념을 이해하고 다양한 문제를 접하면서 패턴을 익히다 보면, 점점 DP 문제를 해결하는 직관이 생기게 됩니다.

중요한 것은 많은 문제를 풀어보는 것입니다. 각 문제마다 상태를 어떻게 정의하고, 점화식을 어떻게 세우는지 집중적으로 연습하세요. 특히 처음에는 문제를 이해하고 접근법을 생각하는 데 시간을 충분히 투자하는 것이 좋습니다.

DP는 코딩테스트에서 빈번하게 등장하는 중요한 알고리즘 기법이므로, 시간을 들여 마스터한다면 큰 도움이 될 것입니다. 코딩테스트 준비 화이팅하세요! 🚀

티스토리