-
조건을 만족하는 최솟값 혹은 최댓값 구하기
문자열이 주어졌을 때, 재배열하여 원본보다 사전 순으로 느린 문자열 중 사전 순으로 가장 빠른 문자열을 찾는 간단한 문제를 하나 생각해봅시다. 가능한 모든 재배열 방법을 확인하는 건 $N!$에 비례하는 시간이 걸리기 때문에 다른 방법을 찾아보아야 합니다. 이 문제를 해결하기 이 글에서 소개하고자 하는 풀이 방법을 이용해 소개하고자 합니다. 확정되지 않은 가장 앞자리에 a를 넣어본 뒤에 가능한지 확인한 후, 가능하다면 확정 지어주고 불가능하다면 다음 문자인 b로 넘어가고, 이를 확정 짓기까지 계속 반복하는 것입니다. 예를 들어 문제의 입력으로...
-
Matroid Intersection
Matroid Intersection Recall matroid $\mathcal{M} = (S, \mathcal{I})$ 에서 $S$는 유한집합, $ \mathcal{I} \subset 2^S$ 는 독립집합(independent set)들의 collection이다. 이 때, $I$는 다음 세 가지 조건을 만족하여야 한다. $\phi \in \mathcal{I}$ $Y \subset X, X \in \mathcal{I} \Rightarrow Y \in \mathcal{I}$ $X, Y \in \mathcal{I}, \lvert X \rvert < \lvert Y \rvert$ 이면 $X + y \in \mathcal{I}$ 를 만족하는 $y \in Y \setminus X$가 존재 매트로이드는 다양한 집합에서 정의될 수 있다. 그 중 대표적인...