-
그래프의 간선을 제거할 때 절점의 개수를 세는 효율적인 알고리즘
개요 그래프는 일상생활 뿐만 아니라 대부분의 과학 분야에서 ‘추상화’를 위해 사용하는 아주 강력한 자료 구조이다. 그래프의 중요한 성질로 여러 가지가 있으며, 이 글은 그 중에서 특히 절점과 절선에 대하여 다룬다. 무방향 그래프에서 각 간선을 끊었을 때, 그래프의 절점의 개수를 효율적으로 세는 알고리즘에 대하여 알아보고자 한다. 즉, 이 알고리즘은 다음과 같은 일상생활 속 문제를 해결할 수 있게 도와준다: 사내 서버망에서 어떤 회선이 끊어졌다고(불능이 되었다고) 하자. 여기서, 추가적으로 어떤 서버가 고장나야 서버망이 끊기게 되는가. 즉, 어떤 ‘중요한’...
-
Inequality Solving with CVP
서론 이 글은 제가 CTF 대회에서 자주 사용하는 toolkit인 github.com/rkm0959/Inequality_Solving_with_CVP의 설명서입니다. 이미 README에 많은 설명이 있지만, 설명서라기에는 부실한 점이 많아 이를 보강합니다. 제가 이 글을 작성하는 목적은 이 repository의 존재를 더 많은 사람들에게 홍보하기 위해서 이 repository의 기본적인 아이디어를 CTF를 하지 않는 사람들에게도 알리기 위해서 이 repository가 더 많은 사람들에게 사용되기를 바라기 때문 이 repository의 부족한 점을 보충하기 위해서 입니다. 이 점을 참고하시고 글을 읽어주시면 감사하겠습니다. 이 글에서 모든 나눗셈은 floor function을 거친 결과로 생각하시기...
-
매트로이드에서의 Submodular Maximization에 대한 Deterministic algorithms
이 글에서는 매트로이드 상에서의 submodular maximization과 관련한 여러 연구의 결과들을 소개합니다. 보다 구체적으로는, 매트로이드와 submodular function 등 여러 개념의 정의를 소개하고, 매트로이드 상에서 submodular function을 최적화 하는 것이 실생활의 어떤 문제에 관련이 있는지 먼저 살펴봅니다. 그 후, 이 문제와 관련한 여러 연구 결과들을 살펴봅니다. 특히, 그 중에서도 (이 글에서는) 결정론적인 알고리즘들을 다룹니다. 1. 여러 개념 및 정의 먼저, submodular function 및 그에 대한 marginal gain을 정의합니다. 정의 1. 유한집합 $\mathcal{N}$에 대해 함수 $f : 2^\mathcal{N}...
-
LSM Tree
안녕하세요? 오늘은 데이터베이스 시스템에서, key-value 형태의 데이터를 저장할 때 좋은 성능을 내는 LSM Tree(Log-Structured Merge Tree)에 대해 알아보겠습니다. 보통 key-value 형태의 데이터를 저장할 때는 B-Tree를 많이 사용합니다. 하지만 만약 저장되는 매체가 disk라면, B-Tree는 많은 random access를 발생시켜 저조한 성능을 내게 됩니다. 하지만 이 때 LSM Tree를 사용하면, write를 할 때 append only 방식으로 저장을 하기때문에, write를 sequential하게 처리하여 성능을 향상시킬 수 있습니다. LSM Tree의 기본 구조 LSM Tree는 1996년 Patrick O’Neil의 논문 The Log-Structured Merge-Tree...
-
Gröbner basis
서론 최근 다변수 Coppersmith Method와 관련해 살펴보면서 Gröbner basis, 한국어로는 그뢰브너 기저에 대해서 접하게 되었습니다. 다변수 Coppersmith Method의 과정을 간략하게 설명하자면 다음과 같습니다. 변수 $x_1, x_2, \dots, x_k$에 대한 어떤 modular equation $f(x_1, x_2, \dots, x_k) \equiv 0 \pmod n$을 풀고 싶다. 단, $x_1, x_2, \dots, x_k$는 $n$에 비해서 매우 작다. Howgrave-Graham Theorem과 LLL algorithm을 적용해 $g_1(x_1, x_2, \dots, x_k) = 0, g_2(x_1, x_2, \dots, x_k) = 0, \cdots, g_l(x_1, x_2, \dots, x_k) = 0$...