그래프와 관련된 심화 알고리즘을 알아보기 전에, 그래프의 간선을 몇 가지의 종류로 구분하는 방법을 알아봅시다.

문제 링크

• http://icpc.me/13262

문제 링크

• http://icpc.me/13261

서론

Divide and Conquer Optimization은 점화식이 아래 조건을 만족할 때 사용할 수 있습니다.

• 점화식 꼴 : $\displaystyle D(t, i) = min_{1 ≤ j < n}{D(t-1, j)+C(j, i)}$
• 조건 : $D(t, i) = D(t-1, j) + C(j, i)$을 만족하는 가장 작은 $j$를 $P(t, i)$이라고 할 때 $P(t, i) ≤ P(t, i+1)$을 만족

문제 링크

• http://icpc.me/13260

문제 링크

• http://icpc.me/13974

문제 링크

• http://icpc.me/11066

수정 예정

monotone stack은 몇몇 문제들의 시간 복잡도를 O(n)정도로 줄어주는 강력한 테크닉입니다.

최악의 경우

이전 글 마지막 부분을 다시 가져와봅시다.