Dynamic Programming

Knapsack problem 이라는 배낭 채우기 문제는 워낙 유명하고 DP를 처음 접할 때 대부분 이것으로 접하게 된다.

knapsack problem

배낭의 최대 용량은 W이며, 이를 초과해서 보석을 담으면 배낭이 찢어진다.
각 보석들의 무게와 가격은 알고 있다.
배낭이 찢어지지 않는 선에서 가격 합이 최대가 되도록 보석을 담는 방법을 return 해라.

여기에는 두 가지 종류의 문제가 있다. 보석을 자를 수 있는 fractional knapsack problem과 자를 수 없다고 가정하는(덩어리로) 0-1 knapsack problem이 있다. 동적계획법은 후자의 문제를 다룰 때 사용된다.

DP는 큰 문제를 작은 문제로 쪼개서(Devide-and-Conquer), 이전 계산 결과를 저장해서 반복을 줄이는(Memorization) 이 두 가지를 활용해서 문제를 해결한다. 워낙 유명한 피보나치 수열문제는 재귀함수를 이용하는 dp를 사용해서 풀 수 있다.

memo = {1:1, 2:1}
def fibo(n):
    # initialize
    if n == 0:
        return 0
    elif n == 1:
        return 1

    # recursive memo
    if n not in memo:
        memo[n] = fibo(n-1) + fibo(n-2)
    return memo[n]

그냥 memo를 안해도 풀 수 있긴 하지만, 이렇게 재귀적으로 앞의 계산 결과를 뒤에서 활용하는 문제는 저장을 하냐 안하느냐에 따라서 n이 커질 경우에 압도적으로 시간복잡도가 줄어든다. 이러한 DP를 0-1 knapsack problem에 적용하려면 최적의 원리(principle of optimality)가 성립하는지 확인해야한다. 최적의 원리란

Principle of Optimality

어떤 문제의 입력 사례의 최적해가 그 입력 사례를 분할한 부분 사례에 대한 최적해를 항상 포함하고 있으면, 그 문제에 대하여 최적의 원리가 성립한다.

결국 다이나믹 프로그래밍이란 것은 문제를 작은 문제들로 나누고(최적 부분구조 optimal substructures), 하위 문제가 반복되는(overlapping subproblems) 것이다. DP가 효과적이라면 해당 두 가지 조건이 만족되어야만 한다. 이 조건이 성립되지 않으면 적용되지 않거나, 효율이 떨어질 수 있다.

비교

재귀 분할정복(Divide and Conquer)

DP는 중복된 부분 문제를 해결할 때 중복 계산을 중리기 위해 결과를 메모라이즈한다. 반면, 분할 정복은 문제를 독립적인 하위 문제로 나누고, 그 결과를 합쳐서 전체 문제를 해결한다. 하위 문제들이 중복되지 않는 경우 DP < 분할정복이다. 적합한 문제 : 퀵 정렬, 병합 정렬, 이진 탐색. 해당 경우들은 하위 문제가 중복되지 않는다. 독립적인 부분문제들은 분할정복이 좋다.

탐욕(Greedy)

탐욕 알고리즘은 매 단계에서 최선 선택, 이러한 과정의 결론이 결국 최적해로 도달한다. 반면 DP는 문제 최적화를 위해 가능한 모든 하위 문제의 결과를 고려한다. 적합한 문제 : 최단 경로 문제 - 다익스트라 알고리즘은 탐욕적 접근이 유효하지만, 가중치가 음수인 경우 탐욕적 접근이 최적해를 보장하지 못한다. 때문에 벨만-포드 알고리즘 같은 DP 기법이 필요해진다.

브루트포스(Brute Force)

DP는 중복된 부분 문제의 결과를 저장해 시간 복잡도를 줄이는 반면, 브루트포스는 모든 경우를 확인하기 때문에 연산량이 당연히 많아 질 수 밖에 없다.

백트래킹(Backtracking)

backtracking은 모든 가능한 경로를 탐색하되, 조건을 만족하지 않는 경우 미리 배제하는 방식으로 경우의 수를 줄여서 탐색한다. DP는 주로 상태 저장을 통해 중복 계산을 방지하고, 백트래킹은 불필요한 경로를 가지치기하여 효율성을 높인다. 적합한 문제 : 경로 탐색에서 제약 조건이 있어, 모든 경로를 탐색하지 않아도 되는 경우 백트래킹이 효과적이다. 백트래킹은 최적 부분 구조가 성립하지 않는 경우에도 사용할 수 있다. N-Queen, 부분 집합의 합 문제 등이 있다.

알고리즘	적합 조건	주요 차이점
다이나믹 프로그래밍 (DP)	최적 부분 구조 + 중복된 부분 문제	중복 계산을 줄이기 위해 이전 계산을 저장.
분할 정복 (Divide and Conquer)	독립된 하위 문제로 나눌 수 있는 경우	중복된 계산이 없고 각 하위 문제가 독립적이면 적합. DP보다 간단.
탐욕 알고리즘 (Greedy)	각 단계의 최선 선택이 전체 최적해로 이어질 수 있는 경우	매 단계 최적 선택만 함. 최적해 보장이 필요하면 DP가 더 적합.
브루트포스 (Brute Force)	문제의 규모가 작아 모든 경우를 시도할 수 있는 경우	가능한 모든 경우를 탐색. 중복 계산 줄이기가 필요하면 DP.
백트래킹 (Backtracking)	조건을 통해 불필요한 탐색 가지치기가 가능할 때	가지치기 활용. DP는 상태 저장을 통해 효율성 개선, 백트래킹은 조건을 만족하지 않으면 미리 배제.
A* 알고리즘 (A)*	경로 탐색에서 휴리스틱을 통해 효율성을 높일 수 있을 때	비용과 휴리스틱을 모두 고려해 특정 방향 탐색. DP는 모든 하위 문제를 고려해 최적화.

방법론

해당 방법을 해결하는 방법론에는 두 가지가 있다. 하나는 탑다운 방식이고, 다른 하나는 바텀업 방식이다.

탑다운

문제를 재귀적으로 풀되, 메모라이제이션 기법으로 저장해두고, 다시 계산할때는 저장된 값을 사용하는 방식이다. 재귀적으로 접근하기 때문에 함수 호출 스택에 값을 저장하는 구조이며, 메모라이제이션을 통해 중복 계산을 피할 수 있다.

def fibonacci(n, memo={}):
    if n in memo:  # 이미 계산된 값이 있다면 그 값을 반환
        return memo[n]
    if n <= 1:  # 기본 조건
        return n
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)  # 메모이제이션
    return memo[n]

바텀업 방식

작은 하위 문제를 반복문으로 사용해 점진적으로 큰 문제를 해결하는 방식이다. 하위 문제의 해결 결과를 테이블에 저장하고, 이를 점차 상위 문제 해결하여 나가며 최종적으로 원하는 문제를 해결한다.

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

최적 부분집합 성립 알아보기

• \(A\) : \(n\)개의 보석들 중 최적으로 고른 부분집합

• \(A\)가 \(n\)번째 보석을 포함하고 있지 않다면, \(A\)는 \(n\)번째 보석을 뺀 나머지 \(n-1\)개의 보석들 중에서 최적으로 고른 부분집합과 같아. \(\to\) 최적의 원리 적용가능

• \(A\)가 \(n\)번째 보석을 포함하고 있다면, \(A\)에 속한 보석들의 총 가격은 \(n-1\) 개의 보석들 중에서 최적으로 고른 가격의 합에다가 보석 \(n\)의 가격을 더한 것과 같다.

• \(P[i,w]\)란 i개의 보석이 있고 배낭의 무게 한도가 w일때 최적의 이익

\[\begin{split} P[i,w] = \begin{cases} P[i-1,w] &\text{if } w_i > w\\ \max\{v_i+P[i-1,w-w_k],P[i-1,w]\} &\text{else} \end{cases} \end{split}\]

i번째 보석이 배낭의 무게 한도보다 무거우면 넣을수 없음으로 i번째 보석을 뺀 i-1개의 보석들을 가지고 구한 전 단계의 최적값을 유지한다. 그렇지 않을 경우 i번째 보석ㅇ르 위해 i번째 보석만큼의 무게를 비웠을 때의 최적값에 i번째 보석의 가격을 더한 값 or i-1개의 보석들을 가지고 구한 전 단계의 최적값중 max를 취한다.

12865 : 평범한 배낭

아주 클래식하고 그냥 맨 처음 만나는 배낭 문제다. 이름처럼 그래도 평범한 배낭 문제이다. 다른 배낭 문제 짱많으니깐 백준 배낭문제 문제집 여기 들어가서 구경해보자.

import sys
input = sys.stdin.readline

def knapsack(n,k,items):
    dp = [[0]*(k+1) for _ in range(n+1)]

    for i in range(1,n+1): # 물건 개수 늘리기
        w,v = map(int, items[i-1])
        for j in range(1,k+1): # 최대무게 늘리기
            if w <= j: # 물건무게가 여유용량보다 작으면
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)
            else: # 이전 최적값 유지
                dp[i][j] = dp[i-1][j]
    print(dp[n][k])

referances

• 메시에 - dynamic programming:배낭채우기 문제(knapsack problem)