본문 바로가기
2022-06-05 Problem Solving 최근에 여러 문제를 해결하였다. 최근에 해결해 본 문제들의 풀이를 간략하게 정리해보았다. 4230. 사랑과 전쟁 편의상 0번 남편을 위쪽에 앉히자. 남편과 아내가 같은 편에 앉을 수 없다는 조건과 각 불륜 쌍 중 최소 한 쪽은 아래 쪽에 앉아야 한다는 조건은 typical한 2-SAT 조건 식으로 만들어줄 수 있다. 2-SAT을 구하는 알고리즘을 돌려서 문제를 해결할 수 있다. 21065. Friendship Circles 문제에서 물어보는 것은 $p_0$ 에 대해 점들을 반전시켜 생각해보면 간단하다. $p_0$ 와 $p_i$ 만을 포함하는 원이 있는 것은 $p_i$를 반전 시킨 점을 지나는 직선이 존재해 나머지 점들을 한쪽 반평면에만 놓이게 할 수 있음과 동치이다. 따라서, $p_i$를 반전시킨 점을 ..
랜덤한 교란 순열을 생성하는 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) 학부 졸업 전에 군 복무를 마치고 싶었다. 노동에 대해 정당한 대가를 받으며 병역 의무를 수행하는 제도로는 앞의 두 제도가 있고, 학부를 졸업하기 전에 병역 의무를 마칠 수 있는 제도로는 뒤의 두 가지가 있었다. 그래서 두 조건 모두를 만족하는 산업기능요원으로 군 복무를 수행하기로 했다. 산업기능요원이 되는 과정 어떤 것을 준비했나요? 나는 다양한 회사의 채용 공고를 보면서 내가 어떤 회사의 어느 포지션에 지원할 것인지를 먼저 결정했다. 회사의..

티스토리툴바