6. Dynamic Programming

동적 계획법을 알아보자.

6.1. Shortest paths in dags, revisited

방향 비순환그래프의 최단 경로들은 동적 계획법을 이용해 선형 시간에 풀 수 있다.

6.2. Longest increasing subsequences

최장 증가 부분순열은 동적 계획법을 이용해 O(n \log n)에 풀 수 있다.

6.3. Edit distance

단어의 수정 거리는 동적 계획법을 이용해 O(mn)에 풀 수 있다.

6.4. Knapsack

이산 배낭 문제는 O(nW)에 풀 수 있다. n에 대한 다항식으로 푸는 것은 불가능하다.

6.5. Chain matrix multiplication

최적의 행렬곱 순서 판정은 O(n^{3})에 풀 수 있다.

6.6. Shortest paths

All-pairs shortest paths

모든 쌍 최단 경로는 플로이드-와샬로 O(V^{3})에 풀 수 있으며 이도 동적 계획법의 일부이다.

The traveling salesman problem

순회하는 외판원 문제는 O(n^{2} 2^{n})에 풀 수 있다.

6.7. Independent sets in trees

트리 내 최대 독립적 집합의 수는 O(V + E)에 풀 수 있다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중