본문 바로가기

분류 전체보기

 (57)
최근 일주일간 마신 위스키 최근 일주일간 꽤나 다양한 위스키를 마셨다. 야마자키 싱글 캐스크 (1996 증류, 2009 병입): 병에 마지막 남은 하프 샷 정도를 마셔 볼 기회를 얻게 되었다. 에어링이 너무 많이 되었을까봐 다소 걱정했지만, 뚜껑을 여는 순간 향긋한 향이 너무나도 기대를 하게 만들었고, 역시나 그 기대에 부응하는 맛이었다. 스프링뱅크 15년: 역시나 스프링뱅크 스러움을 가장 잘 살린건 15년인 것 같다. 로즈뱅크 21년 CS: 내가 너무 사랑해 마다하지 않는 로즈뱅크. 마실 수 있을 때 마셔놔야 한다고 생각한다(?) CS라기에 다소 뭔가 때리는게 적다고 느낄 수도 있을 법 하다만, 부드럽고 향긋하고 역시 매력 있다고 느꼈다. 글렌알라키 10년 배치#7, #8: #8은 아직 에어링을 좀 더 해서 좀 더 열려야 맛있을..
합정 ㅁㅅㅂ(무스비) 수현님이 예약 잡아주신 덕에 경훈님과 셋이서 방문했다. 음식의 맛도 정말 감동적이었고, 모든 손님이 함께 식사를 즐긴다는 컨셉 자체도 내 취향에 잘 맞았다. 사장님의 입담 덕에 식사 시간이 더 재밌었던 것 같기도 하다. 위치는 합정역에서 조금 걸으면 나오는데, 주택가라 그런지 "여기가 맞나..." 싶은 위치다. 스스로가 가는 길에 믿음을 가지고 가라는 삶의 교훈일수도...(아무말) 여튼 믿음을 가지고 가면 된다. 처음 들어갔을 때 테이블의 세팅은 위 사진과 같았다. 사장님께서 코스 설명 해주시면서 페어링할 와인도 몇 개 추천해주시는데, 이 날 모두가 풀-컨디션은 아니었던 만큼, 추천 받은 와인 세 바틀 중 샴페인을 제외한 나머지 두 바틀을 주문했다. 이 날 페어링 한 와인은 다음과 같았다: San Zop..
2022년을 마무리 하며 2022년 한 해는 정말 다사다난 했던 것 같습니다. 단순히 많은 활동을 한 것을 넘어서 학업, 커리어, 인간관계 등 여러 측면에서 많은 고민을 했고, 또 많은 것을 얻을 수 있었습니다. 그 외로도 스스로를 돌보고, 챙기는 법을 배울 수 있었던 한 해였습니다. 올 한 해도 많은 분들 덕분에 무사히 마무리하는 것 같습니다. 여느 때와 같이, 올해에도 알고리즘 문제해결 커뮤니티에서 여러 활동을 한 것 같습니다. 신년 대회인 Hello, BOJ 2022!를 개최하며 한 해를 시작했습니다. 제가 지금까지 이룬 자그마한 성취들 뒤에는 알고리즘 문제해결 커뮤니티의 도움이 있었다고 생각하고, 그런 만큼 단순히 개인 대회를 개최하는 것 외에도 이 커뮤니티에 기여를 하고 싶다는 생각이 꾸준히 있었습니다. 그래서 한국정보..
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$를 반전시킨 점을 ..

티스토리툴바