동적계획법(Dynamic Programming) - swkim0128/PARA GitHub Wiki

type: Algorithm archive: false

  • 메모이제이션(Memoization) 기법 : 다이내믹 프로그래밍을 구현하는 방법 중 한 종류, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법.

다이나믹 프로그래밍은 다음 조건을 만족할 때 사용할 수 있다.

  1. 큰 문제를 작은 문제로 나눌 수 있다.
  2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

동적 계힉법을 적용하려는 문제는 필히 다음과 같은 요건을 가지고 있어야 한다.

  • 중복 부분문제 구조(Overlapping subproblems)
  • 최적 부분문제 구조(Optimal substructure)

중복 부분문제 구조

  • DP는 큰 문제를 이루는 작은 문제들을 먼저 해결하고 작은 문제들의 최적 해(Optimal Solution)를 이용하여 순환적으로 큰 문제를 해결한다.

    순환적인 관계(recurrence relation)를 명시적으로 표현하기 위해서 동적 계획법에서는 일반적으로 수학적 도구인 점화식을 사용한다.

  • DP는 문제의 순환적인 성질 때문에 이전에 계산되어졌던 작은 문제의 해가 다른 어딘가에서 필요하게 되는데(Overlapping subproblems) 이를 위해 DP에서는 이미 해결된 작은 문제들의 해들을 어떤 저장 공간(table)에 저장하게 된다.

  • 그리고 이렇게 저장된 해들이 다시 피요할 때 마다 해를 얻기 위해 다시 문제를 재계산하지 않고 table의 참조를 통해서 중복된 계산을 피하게 된다.

최적 부분문제 구조(Optimal substructure)

  • 동적 계획법이 최적화에 대한 어느 문에나 적용될 수 있는 것은 아니다. 주어진 문제가 최적화의 원칙(Pricciple of Optimality)를 만족해야만 동적 계획법을 효율적으로 적용할 수 있다.
  • 최적화의 원칙이란 어떤 문제에 대한 해가 최적일 때 그 해를 구성하는 작은 문제들의 해 역시 최적이어야 한다는 것이다. 동적 계획법의 방법자체가 큰 문제의 최적 해를 작은 문제의 최적해 들을 이요아혀 구하기 때문에 만약 큰 문제의 최적해가 작은 문제들의 최적해들로 구성되지 않는다면 이 문제는 동적 계획법을 적용할 수 없다.

탑다운(Top-Down) 방식

큰 문제를 해결하기 위해 작은 문제를 호출, 재귀 함수를 이용하여 다이내믹 프로그래밍 소스코드를 작성하는 방법.
'하향식'

# 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 리스트 초기화
d = [0] * 100

def fibo(x):
    # 종료 조건(1 혹은 2일 때 1을 반환)
    if x == 1 or x == 2:
        return 1

    # 이미 계산한 적 있는 문제라면 그래도 반환
    if d[x] != 0:
        return d[x]

    # 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
    d[x] = fibo(x - 1) + fibo(x - 2)
    return d[x]

print(fibo(99))

보텀업(Bottom-Up) 방식

단순히 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 차근차근 답을 도출하는 방식.
'상향식'
다이내믹 프로그래밍의 전형적인 형태는 보텀업 방식, 저장용 리스트는 'DP 테이블'이라고 불림.

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100

# 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1] = 1
d[2] = 1
n = 99

# 피보나치 함수(Fibonacci Function) 반복문으로 구현(보텀업 다이나믹 프로그래밍)
for i in range(3, n + 1):
    d[i] = d[i - 1] + d[i - 2]

print(d[n])

0-1 Knapsack

배낭 (Knapsack)문제는 n개의 물건과 각 물건 i의 무게 wi와 가치 vi가 주어지고, 배낭의 용량은 W일때, 배낭에 담을 수 있는 물건의 최대 가치를 찾는 문제이다. 단, 배나에 담은 물건의 무게의 합이 W를 초과하지 말아야 하고, 각 물건은 1개씩만 있다.

W = 배냥의 용량
(vi, wi) = 가치(만원) 무게(kg) 물건
K[i, w] = 물건 1 ~ i까지만 고려하고, (임시) 배낭의 용량이 w일 때의 최대 가치
단, i = 1, 2, ..., n이고, w = 1, 2, 3, ... W이다.

  • K[i, w]를 재귀적으로 정리하면

K[i, w] =
{ 0 if i = 0 or w = 0
K[i - 1, w] if wi > w
max(vi + K[i - 1, w - wi], K[i - 1, w]) if > 0 and wi ≤ w

  • i번째 물건을 고려 할 때

    case 1 : 최적해는 물건 i를 포함하지 않는다.

    • 전체 가치는 그 전(물건 1 ~ (i - 1)까지 고려한 상황)과 동일하다.

    case 2 : 최적해는 물건 i를 포함한다.

    • 전체 가치는 물건 i의 가치 + 물건 1 ~ (i - 1)까지 고려하여 배낭의 용량이 (w - wi)인 경우의 최대 가치
FOR i in 0 -> n : K[i, 0] <- 0
FOR w in 0 -> W : K[0, w] <- 0

FOR i in 1 -> n
	FOR w in 1 > W
		if wi > w
			K[i, w] <- K[i - 1, w]
		else
			K[i, w] <- max(vi + K[i - 1, w - wi], K[i - 1, w])
return k[n, W]

최장 증가 수열(Longest Increasing Subsequence)

어떤 수열이 나열되 있을 때 순서를 유지하면서 크기가 점진적으로 커지는 가장 긴 부분 수열의 길이는?

어떤 수열이 왼쪽에서 오른쪽으로 나열돼 있으면, 그 배열 순서를 유지하면서 크기가 점진적으로 커지는 가장 긴 부분수열을 추출하는 문제

ex ) 3, 2, 6, 4, 5, 1 → 3, ==2==, 6, ==4==, ==5==, 1
최장 증가 수열은 2, 4, 5이다. 길이는 3이다.

  • brute-force 접근 방법

    수열의 모든 부분 집합을 구하여 그 부분 집합이 증가 수열인지 판별한다. 증가 수열 중 가장 길이가 긴 값을 구한다.

  • DP 접근 방법 1

    LIS(i) : a1, a2, ..., ai에서 최장 부분 수열의 길이

    case1 : LIS(i)가 ai를 포함하지 않는다면, LIS(i) = LIS(i - 1)

    case2 : LIS(i)가 ai를 포함한다면, LIS(i) = ?

    • 증가 수열의 관계인 aj < ai인 aj를 찾는다.
    • j값을 알 수 없으므로 모두 검색해야 한다.
    • 그 중 최대값을 찾아 1 증가시켜 LIS(i)에 저장한다.
    • LIS() 중에서 최대값을 찾는다.
    for i in 1 -> n
	LIS[i] = 1
	for j in 1 -> i - 1
		if aj < ai and LIS[i] < 1 + LIS[j]
			LIS[i] = 1 + LIS[j]
return max LIS[]

  • DP 접근 방법 2

    이진 검색을 이용한 보다 효율적인 방법

    C[k]: 길이 k의 증가 수열에 대하여 가장 작은 값을 C[k]에 저장.

    각 위치에서 C[]를 갱신하기 위해 이진 검색을 수행한다. O(nlonn)

    arr[]
LIS[]
 
LIS[0] = arr[0]
idx = 0

for i in 1 -> n
	if LIS[idx] < arr[i]
		LIS[++idx] = arr[i]
	else
		ii = lower_bound(LIS, idx, arr[i])
		LIS[ii] = arr[i]
return;

lower_bound(LIS[], end, n)
	start <- 0
	
	while start < end
		mid = (start + end) / 2
		
		if LIS[mid] >= n
			end = mid
		else
			start = mid + 1
	
	return end

모든 쌍 최단 경로

다음 각 정점 사이의 최단 경로는 얼마인가? 1에서 2까지의 최단 경로 값은 1이며, 1에서 5까지의 최단 경로 값은 4이다. 다른 정점 사이의 최단 경로 값들은 얼마인가?

한 도시에서 다른 도시로 가장 빨리 갈 수 있는 경로를 찾는 문제

가중치 포함, 방향성 그래프에서 최단 경로 찾기

최적화 문제(optimization problem)

주어진 문제에 대하여 하나 이상의 많은 해답이 존재할 때, 이 가운데에서 가장 최적인 해답(optimal solution)을 찾아야하는 문제

  • brute-force 접근 방법

    한 정점에서 다른 정점으로 모든 경로를 구한 뒤, 그들 중에서 최단 경로를 찾는다.

    그래프가 n개의 정점을 가지고 있고, 완전 그래프라고 가정하면

    한 정점 i에서 어떤 정점 j로 가는 경로들을 다 모아 보면, 그 경로들 중에서 나머지 모든 정점을 한번씩은 꼭 거쳐서 가능 경로들을도 포함되어 있는데, 그 경로들의 수만 우선 계산해보자.

    i에서 출발하여 처음에 도착할 수 있는 정점의 가지 수는 n - 2개이고, 그 중에 하나르 선택하면, 그 다음에 도착할 수 있는 정점의 가지 수는 n - 3개이고, 이렇게 계속하여 계산해보면, 총 경로의 개수는 (n - 2)(n -3)...1 = (n - 2)!이 된다.

    이 경로의 개수만 보아도 지수보다 훨씬 크므로, 이 알고리즘은 절대적으로 비효율적이다.

  • DP 접근 방법

    이 문제를 해결하려면, 각 점을 시작점으로 정하여 다익스트라(Dijkstra)의 최단 경로 알고리즘을 수행하면 된다.

    이때의 시간 복잡도는 인접 행렬을 사용하면 O(n3)이다. 단 n은 정점의 수이다.

    Warshall은 그래프에서 모든 쌍의 경로 존재 여부(transitive closure)를 찾아내는 동적 계획 알고리즘을 제안했고, Floyd는 이를 변형하여 모든 쌍 최단 경로를 찾는 알고리즘을 고안하였다.

    따라서 모든 쌍 최단 경로를 찾는 동적 계획 알고리즘을 플로이드-워샬 알고리즘이라 한다.

    플로이드 알고리즘의 시간복잡도는 O(n3)으로 다익스트라의 시간복잡도와 동일하다.

    그러나 플로이드 알고리즘은 매우 간단하여 다익스트라 알고리즘을 사용하는 것보다 효율적이다.

    부분문제 정의 :

    $D_{ij}^k$ = 정점 {1, 2, ..., k} 만을 경유 가능한 정점들로 고려하여, 정점 i로부터 정점 j까지의 모든 경로 중에서 가장 짧은 경로의 거리

    여기서 k ≠ i, k ≠ j이고, k = 0인 경우, 정점 0ㅇ은 그래프에 없으므로 어떤 정점도 경유하지 않는다는 것을 의미한다. 따라서 $D_{ij}^0$은 입력으로 주어지는 선분 (i, j)의 가중치이다.

    $D_{ij}^1$은 i에서 정점 1을 경유하여 j로 가는 경로와 i에서 j로 직접 가는 경로, 즉, 선분 (i, j) , 중에서 짧은 거리이다.

    따라서 모든 쌍 i와 j에 대하여 $D_{ij}^1$을 계산하는 것이 가장 작은 부분 문제들이다. 단, i ≠ 1, j ≠ 1이다.

    그 다음엔 i에서 정점 2를 경유하여 j로 가는 경로의 거리와 $D_{ij}^1$중에서 짧은 거리를 $D_{ij}^2$로 정한다. 단, 정점 2를 경유하는 경로의 거리는 $D_{i2}^1 + D_{2j}^1$이다.

    모든 쌍 i와 j에 대하여 $D_{ij}^2$를 계산하는 것이 그 다음으로 큰 부분 문제들이다.

    정점 i에서 정점 k를 경유하여 j로 가는 경로의 거리와 $D_{ij}^{k-1}$ 중에서 짧은 것으로 정한다. 단, 정점 k를 경유하는 경로의 거리는 $D_{ik}^{k-1} + D_{kj}^{k-1}$이다.

    k가 1에서 n이 될 때까지 $D_{ij}^{k}$를 계산해서, $D_{ij}^n$, 즉 ==모든 정점을 경유 가능한 정점들로 고려한 모든 쌍 i와 j의 최단 경로의 거리==를 찾는 방식이 플로이드의 모든 쌍 최단 경로 알고리즘이다.

    D[i][j] = 정점 i에서 정점 j로의 최소 비용
AllPairsShortest(D[][])
	for k in 1 -> n
		for i in 1 -> n      (단, i ≠ k)
			for j in 1 -> n    (단, j ≠ k, j ≠ i)
				D[i][j] <- min(D[i][k] + D[k][j], D[i][j])
⚠️ **GitHub.com Fallback** ⚠️