본문 바로가기

랜덤한 교란 순열을 생성하는 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를 랜덤하게 생성해야 하는 (암호학적인 ..
IT 산업기능요원이 되기까지 왜 산업기능요원인가? 나는 병역판정검사에서 보충역을 받았고, 나에게 병역 의무를 수행할 수 있는 선택지는 전문연구요원과 산업기능요원, 그리고 사회복무요원, 이렇게 세 가지 선택지가 있었다. 병역 의무를 수행하면서 1) 노동에 대한 정당한 대가를 받고 싶었고, 2) 학부 졸업 전에 군 복무를 마치고 싶었다. 노동에 대해 정당한 대가를 받으며 병역 의무를 수행하는 제도로는 앞의 두 제도가 있고, 학부를 졸업하기 전에 병역 의무를 마칠 수 있는 제도로는 뒤의 두 가지가 있었다. 그래서 두 조건 모두를 만족하는 산업기능요원으로 군 복무를 수행하기로 했다. 산업기능요원이 되는 과정 어떤 것을 준비했나요? 나는 다양한 회사의 채용 공고를 보면서 내가 어떤 회사의 어느 포지션에 지원할 것인지를 먼저 결정했다. 회사의..
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..