[Algorithm Design Approaches]
1. Brute-Force, Full/Exhaustive Enumeration
2. Divide and Conquer
3. Dynamic programming
Binomial Coefficient (이항계수)
(n, k) = (n-1, k-1) + (n-1, k) (if 0 <k<n)
= 1 (if n == k, k == 0)
B[n, k] = B[n-1, k-1] + B[n-1, k] if 0 < k < n
B[n, k] = 1 if n == k, k == 0
solve B[5,3]
B[5,3] = B[4,2] + B[4,3]
B[4,2] = B[3,1] + B[3,2]
B[4,3] = B[3,2] + B[3,3]
--> linear recurrence
--> multi-dimensional recurrence
--> observe subproblem overlapping
--> like Fibonacci recurrence
--> not D&C recurrence --> inefficient --> New approach
D&C_Bin(n,k)
{
if(n==k or k==0) return 1; // termination
else
left == D&C_Bin(n-1, k-1) // left
right == D&C_Bin(n-1, k) // right
return left + right
}
Problem : subprogram recurrence => D&C처럼 보인다
-> D&C recurrence X -> subprogram overlap -> inefficient (TC grows Exponential !!!)
==> dynamic programming 활용할 수 있다.
Note: Principle of optimality, optimal substructure
- principle of optimality 만족 -> DP가 best인 문제
- D&C recurrence 만족 -> D&C approach가 best인 문제
Dynamic Programming
Design
Step 1: recurrence equation
- Establish a recursive property from the problem
- Identify(Find out, Derive) a recurrence equation from P
- 큰 문제 = 작은 문제 +/* 작은 문제 + ... + 작은 문제
Step 2: (bottom-up) solve + save + reuse
- Solve in a bottom-up fashion programming
cf) D&C: top-down fashion (recursion) programming
- Solve smaller problems first (easy problem first)
- Save them(smaller problems) in arrays (tables, dict...)
- Use them later (from look-up tables)
* 모든 초점을 step1에 맞추어야 함, step2는 구현/분석이 너무 쉬움
example 1
Fibnacci(5) -->
step 1: fib(n) = fib(n-1) + fib(n-2)
step 2: f(0), f(1), f(2), f(3), f(4) ---> f(5) = f(4) + f(3) : for iterative
example 2
Question : solve B[5,3]
B[2,1] = B[1,0] + B[1,1] = 1 + 1 = 2
B[3,1] = B[2,0] + B[2,1] = 1 + 2 = 3
B[3,2] = B[2,1] + B[2,2] = 2 + 1 = 3 ==> local neighbor 계산 활용
- neighbor clever enumeration != brute-force enumeration
- DP = Save and Reuse
Analysis of Dynamic Programming = Time complexity
Design = steps + 기본적 골격 + example
!= detailed algorithmic code
(1) Binomial Coefficient (이항계수)
Design
DP_Bin(n, k):
#iterative(for-loop, while-loop)
for i=0 -> n: // step 2
for j = 0 -> min(i, k):
# K 넘어서까지 구할 필요 없으므로!
if(j == 0 or j == i) B[i, j] = 1
else B[i, j] = B[i-1, j-1] + B[i-1, j] // step 1
return B[n, k]
Time Complexity : T(n, k) = O(?)
D&C Analysis TC = (step1 + step2 + step3)
DP basic opeations = array cell computations = table build-up time
T(n, k) = 1 + 2 + 3 + ... + k + (k+1)*(n-k+1)
= k(k+1)/2 + (k+1)*(n-k+1) = O(nk)
= (2n-k+2)(k+1)/2 = O(nk)
Code Optimization
DP design:
- Find out a recurrence using subprograms
- Save and Reuse using Look-up tables (Bottom-up)
DP Analysis:
- TC = # cell computations = # subproblems * time/sub
(2) CMM (Chained Matrix Multiplication )
Design
Given a ordered sequence of matrices,
Find an optimal order(=min # multiplications) for CMM.
Multiplying Chained Matrices (a sequence of matrices)
- Brute-Force = O(2^n)
- D&C = O(2^n) => T(n)=(n-1)∑(k=1)T(k)⋅T(n−k) ⇒ T(n)=O(2n
Step 0: Exapmples (guessing)
: start with easier subproblems (hand computation)
: insight
A1 X A2 X A3 X A4 X A5 X A6
[5x2] [2x3] [3x4] [4x6] [6x7] [7x8]
-> 가장 쉬운 문제? A1 x A1 = 0
->그 다음 쉬운 문제? A2 x A3, A4A5, A5A6
A4 x A5 = 4x6x7 save M[4,5]
A5 x A6 = 6x7x8 save M[5,6]
-> 그 다음 쉬운 문제는?
A4 x A5 x A6 = min(P,Q)
1) (A4xA5) x A6 = 4x6x7 + 4x7x8 = M[4,5] + 4x7x8 = P
2) A4 x (A5xA6) = 6x7x8 + 4x6x8 = M[5,6] + 4x6x8 = Q
-> 그 다음?
A1 x A2 x A3 x A4 = M[1,4]
= min(M[1,3]+alpha, M[2,4]+beta, M[1,2]+M[3,4] + gamma)
(A1xA2xA3)xA4,
A1x(A2~A4),
(A1xA2)×(A3xA4)
-> Final: M[1,6]
1. A1x(A2...A6) = M[1,1] + M[2,6] + 5*2*8
2. (A1...A2)x(A3...A6) = M[1,2] + M[3,6] + 5*3*8
3. (A1...A3)x(A4...A6) = M[1,3] + M[4,6] + 5*4*8
4. (A1...A4)x(A5...A6) = M[1,4] + M[5,6] + 5*6*8
5. (A1...A5)xA6 = M[1,5] + M[6,6] + 5*7*8
Step 1: Recurrence Equation
M[i, j] = min(M[i,k] + M[k+1,j] + C(i-1)C(k)C(j)) for i <= k <= j-1
M[i, i] = 0
Step 2: save and reuse
DP_CMM(matrices_seq, dimension_row, dimension_col):
for i -> n:
for j -> n:
for-loop(k):
...
M[i,j] <- min()
Time Complexity
DP(CMM) => linear # combinations
Binomial Coefficients: O(nk) => sub problem 하나 푸는 데 상수 시간 걸림
CMM: O(n^2) * time/subproblem => sub problem 하나 푸는 데 걸리는 시간이 상수가 아님
T(n) = # subproblems * time /subproblem = O(n^3) (theoretically)
Code Optimization
(3) APSP (All Pairs Shortest Path) Problem: Floyd-Warshall Algorithm
Problem: Given any pair (u,v), find a SP from u to v
Model: on graph
Solutions:
1) Brute-Force: O(n!)
2) Divide and Conquer: think
3) DP: O(n^3)
-> Step 0: examples (easy small subproblems)
-> Step 1: recurrence equation
What is the easiest (sub)problem?
: a direct path from u to v,
save 2D matrix(array)
D0 -> D1 -> D2 -> ... -> D(n-2)
: D[i.j] = D[u,v] = SP from i to j, u to v.
경유지 개수를 기준으로 테이블 구성하는 방식
D0: input graph info. (given)
D0|2,5] = direct path from 2 t o 5 = inf.
D1[2,5] = min(2-1-5, 2-3-5, 2-4,5)
= min(D0[2,1] + D0[1,5],
D0[2,3] + D0[3,5],
D0|2,4] + D0[4,5] )
=> wrong !
1) too many enumeration
2) 2-1-3-5를
D0[2,1] + D0[1,2] + D0[3,5] 이런 식으로 하면 D1 테이블을 활용하지 않게 됨
D1[2,3] + D0[3,5] 이렇게 하면 2-1-3과 D1[2,3]의 의미가 일치하지 않음
: 다른 approach 필요 !!
- D1[i,j] = i에서 j까지 가는 데 , 1번 도시를 경유 할 수 있다
- D2[i,j] = i -> j: 직접 or 1번 도시 경유 or 2번 도시 경유
D1[5,4] = min(A=D0[5,4], B=D0[5,1]+D0[1,4])
= min(inf, 3+1) = 4
D1[5,2] = min(A, B) = min(D0[5,2]=inf, D0[5, 1] +D0[1,2]=4)=4
D1[2,4] = min(A=D0[2,4]=2, B=D0[2,1]+D0[1,4]=9+1=10)=2
D2[5,4]=min(A=D1[5,4]=4, B=D1[5,2]+D1[2,4)=4+2]=4
D3[5,4] = min(D2(5,4], D2[5,3] +D2[3,4])
Design
Recurrence Equation
DK[i, j] = min(k를 거치지 않는 경우, k를 경유하는 경우)
Dk[I, j] = min(D(k-1)[i, j], D(k-1)[i, k] + D(k-1)[k, j])
k: 경유지
Floyd Recurrence:
D(k)[i, j] = min( D(k-1)[i, j], D(k-1)[i,k] +D(k-1)[k,j] )
procedure Floyd(input: graph D)
for-loop k=1 -> ...
for-loop i ...
for-loop j ..
D(k)[i, j] = min( D(k-1)[i,j], D(k-1)[i,k] +D(k-1)[k,j] )
Time complexity: O(n^3), n = |V|
We need a single D array for the entire calculation?
DO -> D1 -> D2 -> …
- Why D matrix(single) is enough
- instead of DO, D1, D2, D3, .?
k번째 테이블을 업데이트 할 때 테이블의 값은 k-1 이하 경유지들만 거친 경로라서,
테이블을 한 개만 쓰면서 계속 덮어써도 안전하다
[Implementations]
(1) 기존 Floyd-warshall 구현은 shortest path 계산X, shortest distance만 보여줌
-> How to find(print) shortest paths between i -> j.
-> Save the “k” vertex
next[i][j] = j로 가기 위해 i에서 다음으로 가야 하는 노드: 이걸 초기화하고, 업데이트할 때 갱신하면
나중에 경로를 역추적할 수 있다.
# Floyd-Warshall with path saving
for k in range(n):
for i in range(n):
for j in range(n):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
next_node[i][j] = next_node[i][k] # 경유할 경우, i → k 방향의 다음 노드로 갱신
(2) In CMM how to print the optimal matrix multiplication
A에서 i~j를 최적으로 나누는 지점 k를 s[i][j]에 추가로 저장한다
Principle of Optimality == Optimal substructure
- All sub solutions of an optimal solution are optimal
- Optimal sub solutions can build up a global(final) optimal solution
If a problem A satisfies “principle of optimality”(Optimal substructure )
-> then DP provides the best design(optimal results )
-> (not saying that DP is the most efficient design)
정답을 구하면 → Optimal
빠르고 적은 메모리로 구하면 → Efficient
Example
- Floyd-warshall algorithm in APSP satisfies Optimal substructure
- Longest simple path problem does not satisfy Optimal substructure
최종적으로 가장 긴 경로는 1-3-2-4인데, 이것의 substructuredls 1-3은 longest path가 아님(1-2-3이 longest)
- Dynamic Programming (DP):
- Optimal Substructure (최적 부분 구조)
- Overlapping Subproblems (중복 부분 문제)
- Greedy Algorithm:
- Local Optimal → Global Optimal (국소 최적 선택이 전체 최적 해를 이끔)
- Optimal Substructure
- Divide and Conquer (D&C):
- D&C Recurrence (문제를 독립적인 하위 문제로 나누어 풀 수 있음)
- Subproblems are independent (하위 문제들이 서로 겹치지 않고 독립적임) → 이게 중요한 추가 조건입니다.