Coding StudyRoom

Nonserial Polyadic DP : next level의 optimal solution 계산을 위해 바로 이전 level의 optimal subsolution 이외에 다른 것도 필요할 수 있으며 + functional equation에 재귀 식이 여러 개 인 경우. 예제 문제1) Optimal Matrix-Parenthesization Problem (Matrix Chain Multiplication) 문제 설명 : - A1, A2 ... Ai matrix 가 존재하고 순서대로 곱했을 때 행렬 곱 연산이 가능 (row와 columm 크기가 매칭된다는 의미) 이 때 행렬 곱을 위해 행렬을 괄호로 묶었을 때 최소 연산 횟수를 찾는다. functional equation C[i, j] : A i 행렬부..

Serial Polyadic DP : next level의 optimal solution 계산을 위해 이전 level의 optimal subsolution을 사용하고, functional equation에 여러 재귀 함수가 필요한 경우. 예제 문제1) Floyd's All-Pairs Shortest-Paths Algorithm 문제 설명 : 모든 노드 간의 쌍에 대해서 최단 거리를 구하는 문제. >> 결과는 행렬로 나오고 0번 노드부터 n번 노드까지 각 노드까지 경유를 고려했을 때 최단거리를 계산해 나가면서 계산한다. functional equation 좌항 : k는 노드 번호, 0번 노드 부터 k - 1 노드 까지 고려해서 경유한 경우 최단 거리를 저장하고 있다. (각 level 마다 n^2 계산이 필..

Serial Monadic DP : next solution의 최적 해를 구하기 위해 바로 이전 level의 subproblem의 최적 해의 값이 사용되고, 이러한 DP 식에서 재귀식이 한 개인 경우. 예제 1) The Shortest-Path Problem (최단 경로 문제) : 시작 노드(S)에서 끝 노드(R) 까지의 최단 경로를 구하는 문제이다. 문제설명 : - weighted multistage graph(다단계 그래프) 이고 r + 1 개의 levels로 구성되었다. 예시 그림) - level i의 모든 노드들은 level i + 1 의 모든 노드들과 연결되어 있다. (그림과는 다름) - level 0 은 시작 노드(S), level r 은 끝 노드(R)로 노드가 1개 뿐이다. functiona..

Dynamic Programming : Discrete optimization(이산 최적화) 문제들을 풀기 위해 일반적으로 사용됨. >> Discrete optimization : 문제의 해가 연속적이지 않다. 즉, 이산적이다. ex) 해 = [1, 2, 3, 4]