[algorithms] ch6. Dynamic programming (shortest paths in dags, longest increasing subsequences)

(23.03.29)

algorithms  S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani (2008) 책 읽고 정리하기

http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf

 

 

정리한 내용

6.1 Shortest paths in dags, revisited

6.2 longest increasing subsequences

 

---

 

Dynamic Programming

- dynammic programming의 핵심은 문제를 한 번만 풀도록 하는 것이다.

- 하나의 problem을 sub-problem으로 계속해서 쪼개고, 가장 작은 sub-problem부터 해결함으로써 더 큰 sub-problem을 해결하는 방식이다. 

 

 

 

 

Shortest paths in dags, revisited

- 최단경로 문제는 directed acyclic graph 의 형태로 쉽게 풀 수 있었는데, 이를 통해 dynammic programming을 좀 더 쉽게 이해할 수 있다.

- dag는 nodes들을 linearlized 할 수 있다.

 

 

이를 바탕으로 dist(D)를 구해보면 아래와 같다. 

 

 

이 알고리즘은 아래와 같이 해결한다고 정리해볼 수 있다. 

 

 

 

 

 

longest increasing subsequences (LIS)

- input: a sequence of numbers

- output: greatest length

- increasing subsequence of greatest length 를 찾는 것이 해당 task의 목표!!

 

 

LIS의 예시는 아래와 같다.

 

- L(j) 부분이 위의 shortest paths in dag와 동일한 알고리즘이다.

- min이 max로 바뀐 것이며, edge weight가 모두 1이다. 

 

 

알고리즘대로 풀어본 예시이다.

(교재에서 말한 알고리즘과는 살짝 다른 방식으로 풀어보았다)