[알고리즘 - 이론] DP

1. DP의 정의

DP(Dynamic Programming)란, 복잡한 문제를 작은 문제로 나누어 해결하는 알고리즘 기법 중 하나이다. 작은 문제들의 답을 계산하고 저장해놓은 다음, 큰 문제에서 필요한 작은 문제의 답을 이용해 전체 문제를 해결하는 방식이다. 즉, 중복되는 연산을 줄여서 효율적으로 문제를 해결하는 것이 핵심이다.

2. DP의 장점

• 코드가 간결하고 이해하기 쉽다.
• 중복되는 연산을 최소화해 실행 시간을 단축시킬 수 있다.
• 계산한 값을 저장해둘 수 있기 때문에, 필요할 때 매우 빠르게 값을 구할 수 있다.

3. DP의 단점

• 메모리 사용량이 크다. 이미 계산한 값을 저장해둬야 하기 때문이다.
• 문제를 작은 문제로 나누는 것이 쉽지 않을 수 있다.
• 모든 문제가 DP를 사용해 효율적으로 해결될 수 있는 것은 아니다.

4. DP 사용 예시

피보나치 수열

n번째 피보나치 수를 계산하는 문제는 다음과 같은 재귀함수로 표현될 수 있습니다.

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

하지만 이 함수는 n이 커질수록 중복 계산이 많아져서 시간 복잡도가 지수 시간에 가까워집니다. 이때 DP를 사용하면 중복 계산을 피하고 선형 시간에 해결할 수 있습니다.

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

최장 증가 부분 수열

주어진 수열에서 원소를 일부 선택해 만들 수 있는 증가 부분 수열 중 가장 긴 것의 길이를 계산하는 문제입니다. 이 문제는 다음과 같은 DP 점화식으로 표현할 수 있습니다.

def lis(seq):
    n = len(seq)
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if seq[j] < seq[i]:
                dp[i] = max(dp[i], dp[j]+1)
    return max(dp)

배낭 문제

주어진 무게와 가치를 가진 물건들 중에 주어진 무게 이하의 배낭에 최대 가치를 가지는 물건들을 넣는 문제입니다. 이 문제는 다음과 같은 DP 점화식으로 표현할 수 있습니다.

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, capacity+1):
            if j < weights[i-1]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1])
    return dp[n][capacity]

5. DP방식 구체화

• 문제에서 구하고자 하는 값을 머릿속에 구체화하고, 이를 작은 부분 문제들로 쪼개는 것이 중요하다.
• 작은 부분 분제를 해결해가며 전체 문제를 해결하는 Bottom-up방식과, 전체 문제를 재귀적으로 풀어가는 Top-down방식 중 하나를 선택해서 풀이를 진행하면 된다.
• Overlapping Subproblems (중복되는 부분 문제)
• 문제를 작은 부분 문제들로 쪼개면서, 각각의 작은 문제들이 서로 중복될 수 있다.
• 이 경우 중복 계산을 피하기 위해 메모이제이션을 사용하는 것이 좋다.
• Optimal Substructure (최적 부분 구조)
• 전체 문제의 최적해가 부분 문제의 최적해들로 구성될 수 있는 경우
• 이 경우, 부분 문제들의 최적해들을 이용하여 전체 문제의 최적해를 계산할 수 있다.
• 점화식
• 작은 부분 문제들을 해결해 나가면서, 부분 문제들 간의 관계를 나타내는 점화식을 도출할 수 있다.

DP 문제

• BOJ 1463번 1로 만들기
• BOJ 2156번 포도주 시식
• 프로그래머스 정수 삼각형
• 프로그래머스 등굣길