본문 바로가기

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$를 반전시킨 점을 ..