본문 바로가기

분류 전체보기

 (54)
2022 ICPC Asia Seoul Regional Contest 스태프 후기 나는 현재 학부를 휴학하고 있어서 ICPC에 참여할 수 없다. 그 와중에 ICPC가 온사이트로 개최될 것이라는 소식을 접했고, 반드시 스태프로 참여해야겠다는 생각을 했다. http://icpckorea.org 의 새 게시물에 대한 알림 설정을 해 놓았기 때문에 공지가 올라오자 마자 지원하여 참여할 수 있었던 것 같다. 나의 첫 온사이트 ICPC를 스태프로 참여했던 것도 나름 뜻 깊은 것 같고, 스태프가 현장에서 어떤 일들을 하는지를 기록해두면 향후 온사이트 대회를 개최하고자 하는 이들에게 큰 도움이 될 것으로 생각해 후기 글을 쓰기로 했다. 스태프 1일차 평소보다 많이 일찍 일어나서 대회장 세팅을 위해 킨텍스로 이동했다. 킨텍스는 생각보다 멀었다. 교대역에서 3호선을 타고 갔는데, 정말 오래 걸렸던 것 ..
Unique Games Conjecture에 대한 노트 본인은 최근 들어 Theoretical Computer Science 분야 중에서도 Computational Hardness에 관련한 결과들을 다루는 스터디에 참여하고 있고, Unique Games Conjecture와 관련하여 발표할 일이 있었다. 나름 의미가 있는 주제임에도 불구하고, 이와 관련한 국문 자료는 (본인이 검색해본 한에서는) 전혀 찾아볼 수 없었어서 이 글을 작성하게 되었다. 이 글은 Unique Games Conjecture가 무엇이고, 이를 통해 어떤 결과들을 얻을 수 있는지에 대해 전달하는 것을 목표로 한다. Unique Games Conjecture에서 어떤 형태로 reduction을 구성할 수 있는지 그 느낌 또한 전달하는 것 또한 목표로 하되, reduction에 대한 form..
The Short-Side Advantage in Random Matching Markets 이 글은 L. Cai와 C. Thomas의 논문 The Short-Side Advantage in Random Matching Markets 의 결과를 간략하게 정리한 것이다. 1. Introduction Stable Matching Problem은 남-여 간의 짝 매칭, 의사와 병원간의 매칭, 학생과 지도교수 간의 매칭 등 여러 상황에서 응용될 수 있는 문제로 다음과 같은 상황을 다룬다. $n$ 명의 의사 $\mathcal{D} = {d_1, d_2, \cdots, d_n}$ 와 $m$ 개의 병원 $\mathcal{H} = {h_1, h_2, \cdots, h_m}$ 이 있다. 각각의 의사는 병원에 대한 선호하는 순서($\prec_d$)가 존재하고, 각각의 병원은 의사에 대한 선호하는 순서($\prec..
[Hardness] 01. Computational Complexity Classes 최근 https://github.com/koosaga/project-hardness 의 스터디에 참여하고 있다. 해당 스터디에서 공부한 내용을 아주 간략히 (주로 informal 하다.) 정리하여 매주 포스트로 올릴 계획이다. P와 NP P와 FP $\mathbb{P}$는 다항 시간(입력 $x$의 크기에 대해 다항식 scale로 bound 됨을 의미)에 풀리는 문제들의 class이다. 유의 사항: 정수 $n$은 $\log_2 n$ 개의 비트로 표현할 수 있으므로 $n$을 입력으로 줄 때 입력의 크기는 $\log_2 n$ 이다. (흔히들 Subset Sum 등을 $\mathbb{P}$라 생각하면서 하는 오해...) $\mathbb{FP}$는 다항 시간에 계산 가능한 함수들의 class이다. 어떤 계산 모델..
Redis는 어떻게 key를 expire 하는가? Redis에서는 key에 timeout을 설정할 수 있다. 이 경우, timeout이 지난 key는 만료(expire) 되어 redis에서 삭제된다. 이전 회사에 다니던 시절에 Redis로 key에 timeout을 걸어줘야 하는 작업을 하면서 이 기능이 어떤 원리로 동작하는지에 대해 의문을 품고 찾아봤던 일이 있었다. 이와 관련하여 지금은 조금 여유가 생겨 간략히 글을 남겨본다. Key가 만료되었는지 확인하고, 삭제할 수 있는 가장 간단한 전략으로는 다음의 두 가지를 생각해 볼 수 있다: eager way: 주기적으로 전체 key들을 살펴보며 timeout에 도달했는지 체크해보고, 도달한 경우 key를 삭제한다. lazy way: 어떠한 key에 대한 접근이 이루어지는 시점에 timeout에 도달했는지 ..
Combinatorial Nullstellensatz 1. Combinatorial Nullstellensatz Theorem. (Combinatorial Nullstellensatz) 체 $\mathbb{F}$와 다항식 $f \in \mathbb{F}[x_1, x_2, \cdots, x_n]$ 이 있다고 하자. $\deg(f) = d = \sum_{i=1}^n d_i$ 이고, $\prod_{i=1}^n x_i^{d_i} \neq 0$ 라면, $\lvert L_i \rvert > d_i$인 $\mathbb{F}$의 부분집합 $L_1, L_2, \cdots, L_n$에 대해 $a_1 \in L_1, a_2 \in L_2, \cdots, a_n \in L_n$이 존재해 $f(a_1, a_2, \cdots, a_n) \neq 0$ 를 만족시킨다. Proof. $..
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) 학부 졸업 전에 군 복무를 마치고 싶었다. 노동에 대해 정당한 대가를 받으며 병역 의무를 수행하는 제도로는 앞의 두 제도가 있고, 학부를 졸업하기 전에 병역 의무를 마칠 수 있는 제도로는 뒤의 두 가지가 있었다. 그래서 두 조건 모두를 만족하는 산업기능요원으로 군 복무를 수행하기로 했다. 산업기능요원이 되는 과정 어떤 것을 준비했나요? 나는 다양한 회사의 채용 공고를 보면서 내가 어떤 회사의 어느 포지션에 지원할 것인지를 먼저 결정했다. 회사의..
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..

티스토리툴바