사전순으로 최소인 최단 경로
문제. 모든 간선의 가중치가 1인 (유향) 그래프 $G = (V, E)$와 시작점 $s$, 끝점 $t$가 주어졌다고 하자. 각 간선 $e \in E$에는 label $\ell(e)$가 있다. $s$에서 $t$로 간선 $e_1, e_2, \cdots, e_k$를 거쳐 이동하는 경로를 경로 튜플 $(\ell(e_1), \ell(e_2), \cdots, \ell(e_k))$로 표현하자. $s$에서 $t$로의 모든 최단 경로 가운데 경로 튜플 이 사전순으로 최소인 경로를 찾아보자. 일단, $s$에서 BFS를 돌리며, $O(|V| + |E|)$ 시간에 shortest path spanning tree를 만들 수 있다. 고로, $d(u) + 1 = d(v)$를 만족하는 $u \to v$ 간선만 남겨두고 생각할 수..
랜덤한 교란 순열을 생성하는 card-based 프로토콜 (1)
1. Introduction Symmetric group $S_n$의 원소, 즉, $[n]$ 상의 순열 가운데 fixed point가 없는 것들을 Derangement(교란 순열)이라고 부른다. 이제, 한 가지 예를 들어, $n$ 명의 학생이 있는 학급에서 마니또 행사를 한다고 가정해보자. 학생 $i$의 마니또가 $p_i$라 할 때, $p_i \neq i$ 여야 하며, $i \neq j$ 이면, $p_i \neq p_j$ 여야 할 것이다. 즉, ${p_i}$ 가 derangement 여야 한다. 또한, 학생 $i$는 $p_i$의 값 외에 다른 정보를 알지 않아야 한다. 이렇듯, 현실에는 각자 자신에게 배정된 수 외의 정보를 알 수 없는 상태에서 derangement를 랜덤하게 생성해야 하는 (암호학적인 ..
2-SAT 및 그의 응용
1. 2-SAT 문제란? 2-SAT 문제란 참/거짓의 값을 가지는 불리언 변수 $n$개 $x_1, x_2, \cdots, x_n$ 와 2-CNF가 있을 때, 2-CNF를 참으로 만들기 위해 $x_i$ 들에 적당한 값을 할당하는 문제이다. 2-CNF란 2개의 변수를 $\lor$ (or)한 식(절) 여러 개에 $\land$ 연산을 취해 만들어지는 식을 의미한다. 예를 들어, $(x_1 \lor x_2) \land (\bar x_3 \lor x_4)$ 는 2-CNF이다. 그리고, $x_1 = true$, $x_2 = false$, $x_3 = false$, $x_4 = false$ 는 이 식을 만족 시키는 하나의 방법이다. 반대로, $(x_1 \lor x_1) \land (\bar x_1 \lor \bar x..
