그래프 에서매칭 = 변집합 로, 상호 끝점을 공유하지 않는다.변 덮개 = 변집합 로, 의 어떤 정점도 적어도 1개의 에 포함된 변에 접속 하고 있다.안정집합 = 점집합 로, 의 어떤 두점도 에 대해 인접하고 있지 않다.점 덮개 = 점집합 로, 의 어떤 변도 적어도 1개의 에 포함된 정점에 접속하고 있다.일때 몇가지 법칙이 성립한다. 1. 고립점이 없는 그래프에서 대해서, |최대매칭| + |최소 변 덮개| = |V|2. |최대 안정 집합| + |최소 점 덮개| = |V| 특히 이분그래프에서는|최대 매칭| = |최소 변 덮개| 가 된다. http://prague.algospot.com/judge/problem/read/TRAPCARD위 문제가 위의 성질을 이용하여 풀수있는 대표적인 문제이다이문제는 갯수만 출..
다이나믹 -- 시작복잡도 줄이기
dynamic programming 문제들중 와 같은 점화식을 가진 문제들에 대해 생각해보자. 실제로 최근 KOI에서도 위와 같은 점화식을 가진 문제가 몇몇 나왔는데2011 전국 중등부3 번이라던가2011 지역 고등부5 번을 예로 들 수 있다. 위와 같은 점화식을 가진 문제는 특수한 경우에 따라 시간복잡도를 에서 으로 바꿔 풀 수 있다. 1. commando (APIO 2010)위 문제의 점화식을 나타내보면여기서 bX항은 그룹을 어떻게 나누는지에는 상관없이 항상 그 값은 과 같게 된다.따라서 위 점화식을 로 두고 마지막에 b*(x1+x2..+xn) 을 더해주면 위와같은 점화식이 된다는것을 확인할 수 있다. 그리고 c는 j값에 상관없이 항상 일정한 값을 가지기 때문에우리는 고정된 i 에 대하여 의 값을만에..
링크 : http://211.228.163.31/pool/coci_traka/coci_traka.php?pname=coci_traka Solution 1) O(NM) D(j) = j번째 사람이 첫번째 작업을 시작할 최소시간 이라 정의하자. 그러면 모든 i에 대하여 D(j) + {T(1)+T(2)+T(3)...+T(i)}*F(j) = D(j) + {T(1)+T(2)+T(3)...+T(i-1)}{F(j)-F(j+1)} + T(i)*F(j) 가 성립해야한다. 즉 D(j+1) = D(j) + max( {T(1)+T(2)+T(3)...+T(i-1)}{F(j)-F(j+1)} + T(i)*F(j) ) 라는 식을 얻어낼수 있다. 따라서 모든j에 대해서 모든 i를 훑으면, O(NM)솔루션을 얻어낼수 있다. 2) O(Nl..