Dynamic Programming 이란

 

 

 

It is "programming" that is "dynamic"!
- Richard Bellman

 

 

 

 

복잡한 문제를 여러개의 간단한 문제로 나누어 푸는 방법. 반복적인 문제가 많고 최적의 방법을 찾아야 하는 경우 사용된다.

참고로 Dynamic (동적)이라는 단어의 뜻과 이 알고리즘과는 크게 연관성이 없다. 점화식을 사용한다는 것이 큰 특징.

 

 

 

 

기준:

1. There are only a polynomial number of subproblems

2. The solution to the larger problem can be efficiently calculated from the subproblems.

3. Natural ordering of the subproblems from "smallest" to "largest"

 

 

 

 

 

 

 

1. Weighted Interval Scheduling

기존 인터벌 스케줄링과는 달리 각각의 스케줄에 가치가 부여되어 가장 최대의 가치를 갖게 스케줄 하는 것이 목표이다.

참고) 기존 인터벌 스케줄링: https://gamercat.tistory.com/6 

 

 

 

Q1. What is the value of FF heuristic?: 2

Q2. What is the optimal value?: 3 

 

 

 

 

a) Recursive Solution: Find the optimal value in sorted σ of first j items:

• 1) Find largest i<j such that f_i <= s_j
• 2) OPT(j) = max(OPT(j-1), OPT(i)+v_j (Bellman Equation)
• Require too many repetition.     

Recusion Visualization: O(2^n)

• Step:

DP solution

 

 

 

 

b) Memoizing the Recursion: Store the value in array and retrieve for future calls (iterative)

- 반복되는 작은 문제들을 저장해놓고 다시 사용하는 것

    (피보나치 수 문제를 재귀적으로 풀었을 때와의 차이?

       -n이 증가함에 따라 호출되는 함수의 양이 급격하게 증가하기때문에 스택에 좋지 않다)

 

 

WeightIntDP

 

 

 참고) https://www.techiedelight.com/ko/weighted-interval-scheduling-problem-using-lis/

가중 간격 스케줄링 – 동적 프로그래밍 솔루션

 

 

 

 

 

 

 

 

2. LIS(Longest Increasing Subsequence)

배열 A[1..n] 이 있을 때 가장 긴 increasing subsequence를 찾는 알고리즘: A[i_k] < A[i_k+1] for all k

 

Subsequence 란? - For a sequence A, a subsequence S is a subset of A that maintains the same relative order.

• Ex: I like watching the puddles gather rain. 
• puddles: subsequence, substring (contiguous)
• late train: subsequence, not substring (not contiguous)
• For an array of length n, there are 2^n subsequences

 

 

 

Recursive Approach)

LIS pseudo (Recursive Approach)

 

 

 

 

Dynamic Approach)

1. Prepare 2D array L, where L[i,j] is the maximum LIS of A[j..n] with every item > A[i], i<j
2. Build Bellman Equation 
3. Solution in L[0][1]; add A[0] = -inf. Populate j from n to 1; i from 0 to j-1 or j-1 to 0.

 

 

참고) 백준 11053번: https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

 

 

 

 

 

 

 

 

 

3. Simple dichotomy Game

 

많은 게임이론에서, 다이나믹 프로그래밍은 최적 전략을 찾는데 가장 널리쓰이는 방법 중 하나이다.

 

 

 

 

 

 

 

 

 

 

 

 

4. Subset & Knapsack

 

 

 

 

 

참고) 백준 냅색 문제: https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

 

 

 

 

 

 

 

 

 

5. Shortest Path - Dijkstra's

Bellman-Ford 알고리즘: 

 

 

 

 

 

 

 

 

6. Edit Distance

최소의 문자개수로 string A[1..m] 를 string B[1..n]으로 바꾸는 것.

• Insertions: adding a letter
• Deletions: removing a letter
• Substitutions: replacing a letter

 

 

 

ex) TUESDAY->THUESDAY->THURSDAY

 

 

 

Recursive Approach)

 

Recursive approach

 

 

 

Dynamic Approach)

1. Prepare 2D array E, where E[i,j] is the edit distance for A[1..i] and B[1..j]
2. Build Bellman Equation
3. Solution in E[m,n], Set E[0,j] = j; E[i,0] = i, populate from 1 to n, 1 to m.

DP, bellman equation

 

Insertion: E[i,j-1]+1

Deletion: E[i-1,j]+1

Substitution: E[i-1,j-1]+A[i]!=B[j]

 

 

 

 

 

참고) 관련 백준 문제 https://www.acmicpc.net/problem/15483

15483번: 최소 편집

 

 

 

 

 

 

 

 

 

7. Max Subarray

정수 배열 A가 주어졌을 때, 최대 합의 비어있지않은 연속적인 부분배열을 구하는 알고리즘

 

 

 

 시간복잡도 O(n^2)의 해결 방법 

 

 

 

 

 

 

시간복잡도 O(nlogn)의 해결 방법 (Divide and Conquer)

 

 

 

시간복잡도 O(n)의 해결 방법 (Dynamic Programming)

1. Prepare 1D array s, where s[i] contains the value of the max subarray ending at i. (O(n) cells)
2. Build Bellman Equation: s[i] = max(s[i-1]+A[i], A[i]). (O(1) time) *s[i-1]+A[i]는 기존 부분배열을 지속, A[i]는 새로운 것
3. Solutions is: max_j{s[j]}. (O(n) time)