본문 바로가기
사전순으로 최소인 최단 경로 문제. 모든 간선의 가중치가 1인 (유향) 그래프 $G = (V, E)$와 시작점 $s$, 끝점 $t$가 주어졌다고 하자. 각 간선 $e \in E$에는 label $\ell(e)$가 있다. $s$에서 $t$로 간선 $e_1, e_2, \cdots, e_k$를 거쳐 이동하는 경로를 경로 튜플 $(\ell(e_1), \ell(e_2), \cdots, \ell(e_k))$로 표현하자. $s$에서 $t$로의 모든 최단 경로 가운데 경로 튜플 이 사전순으로 최소인 경로를 찾아보자. 일단, $s$에서 BFS를 돌리며, $O(|V| + |E|)$ 시간에 shortest path spanning tree를 만들 수 있다. 고로, $d(u) + 1 = d(v)$를 만족하는 $u \to v$ 간선만 남겨두고 생각할 수..
[퍼즐] 한 변의 길이가 1+ε인 정육각형 이번에 2025 조합론 워크샵에 다녀왔다. 많은 유익한 강연들이 있었고, 다양한 사람들과 이야기를 나누어 볼 기회가 있어서 좋았다. 워크샵에서 한 학교 후배가 알려준 퍼즐이 재밌어서 공유해본다. 한 변의 길이가 1+ε이고, 아랫변과 윗변이 x축에 평행하게 놓인 정육각형을 한 변의 길이가 1이며 세 변 중 하나가 x축에 평행한 단위 정삼각형으로 덮는 상황을 생각해보자. (아래 그림과 같이 두 종류의 정삼각형이 있을 것이고, 반드시 각 정삼각형의 한 변은 x축과 평행해야 한다.) 이 때 최소 몇 개의 정삼각형이 필요할까? (정삼각형 끼리 겹치는 것은 허용된다. 즉, packing이 아닌 covering 문제다.) 아래는 나의 간략한 풀이다. 풀이를 접어 두었으니, 충분히 고민해보고 열어보는 것을 추천한다. ..
구속 240시간 vs. 10일: 전례 없는 판결의 파장 서울중앙지법 지귀연 판사는 내란죄로 기소된 피고인 윤석열에 대해, 구속 기간을 '구속 시작으로부터 10일'이 아닌 '240시간 후'로 계산해야 한다는 전례 없는 해석을 내세워 구속취소 청구를 받아들였다. 이 판결은 지금까지 유지되어 온 구속 기간 산정 방식과 정면으로 배치된다.이 판결을 계기로 변호사들이 나서서, 구속 후 240시간을 초과했지만 10일 이내에 기소된 사례들을 찾아 무료로 구속취소 청구를 도와주면 좋겠다. 더 나아가, 현재 구속기소 되어 실형을 선고받고 복역 중인 사람들 중에서도 이 조건에 해당하는 이들에게는 재심을 청구하도록 도와주기를 바란다. 윤석열씨의 구속 취소와 관련한 판결이 유효하다면, 이들의 공소 또한 피고인의 권리를 침해하는 ‘가짜 구속’에 기반한 구속기소로 이루어졌기에 무효가..

티스토리툴바