서론

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

• 점화식 꼴 : $\displaystyle D(i) = \min_{1 ≤ j < i}{D(j) + C(j, i)}$
• 조건 : $i < j$인 임의의 $i, j$에 대해 다음을 만족하는 지점 $cross(i, j)$가 존재
  • $cross(i, j) > k$이면 $D(i) + C(i, k) < D(j) + C(j, k)$
  • $cross(i, j) ≤ k$이면 $D(i) + C(i, k) > D(j) + C(j, k)$

서론

DP 최적화를 공부하다보면 monge array라는 것이 많이 보이지만, 정작 monge array에 대한 설명은 많이 없습니다.
이 글에서는 monge array의 정의와 몇 가지 성질의 증명을 다룹니다.

문제 링크

• http://icpc.me/17439

PS 실력을 키우기 위해 3월 13일부터 4월 10일까지 총 4주동안 적절한 문제들을 골라서 연습했습니다.
이 글에서는 연습에서 사용한 문제들과 문제에 관한 후기와 몇 가지 스포를 포함하고 있으니 주의 바랍니다.

문제 링크

• http://icpc.me/18596

문제 링크

• http://icpc.me/13145

문제 링크

• http://icpc.me/3319

서론

이 글은 독자가 MCMF와 Dinic’s Algorithm을 알고 있다고 간주하고 설명합니다.
Min Cost Max Flow(MCMF) 문제를 해결하는 방법은 잘 알려져 있습니다.
이 글에서는 이 MCMF를 구하는 알고리즘에서 수행하는 몇 가지 비효율적인 작업 최적화하는 방법을 다룹니다.

문제 링크

• http://icpc.me/16002

서론

알고리즘 문제를 풀 때 랜덤을 사용해 문제를 해결하는 경우가 있습니다.
최악의 시간 복잡도와 평균 시간 복잡도가 많이 차이나는 알고리즘을 사용하는 경우에 최악의 상황을 피할 때 사용하기도 하고, 무작위 선택을 여러 번 시도하는 것으로 틀릴 확률을 줄이는 용도로 사용하기도 합니다.
이 글에서는 랜덤을 이용해 여러가지 문제를 통해 문제 풀이에 랜덤을 적용하는 방법을 다룹니다.