-
Stack 자료구조와 실습
Stack Stack이란 스택 자료구조란 항상 한쪽 방향에서만 자료의 입력 및 출력이 가능한 형태의 선형 자료구조입니다. 책상 위에 책을 무더기로 쌓아놓은 상태를 생각하면 스택 구조를 이해하기 쉽습니다. 여러 개의 책이 쌓인 상태에서, 우리는 가장 위에 놓여져 있는 책만 쉽게 들어올릴 수 있으며, 가장 위에만 새롭게 책을 놓는 것이 쉽습니다. 물론 중간에 있는 위치에 책을 넣거나 빼는 것도 가능하지만, 이를 위해서는 그보다 위에 있는 책들을 들어야 하죠. 여기서 가장 위에 있는 책이라는 의미는, 책들이 쌓이기 시작했을 때...
-
다양한 생성함수와 그 응용 (2)
개요 본문은 아래의 포스트와 내용이 이어지며, 다음 포스트의 내용을 부가적인 설명 없이 서술한다. 다양한 생성함수와 그 응용 (1) 이번에는 생성함수를 어떻게 실제 PS 문제에 적용할 수 있는지 살펴본다. 다변수 생성함수 이항계수의 생성함수 이항계수 $\displaystyle \binom{n}{k}$의 OGF를 유도하자. 먼저, 이항계수와 같은 값을 가지는 함수 $f(n, k)$를 귀납적으로 정의하자. 다음은 이항계수의 일반적인 귀납적 정의이다: 다음을 만족하는 함수 $f : \mathbb{Z}_{\ge 0}^2 \rightarrow \mathbb{R}$은 모든 음이 아닌 정수 $n$, $k$에 대하여, $\displaystyle f(n, k) =...
-
Zero-Knowledge from MPC
1. Introduction 드디어 Zero-Knowledge에 도달했습니다. 암호학에 그다지 관심이 없었다고 하더라도 최근 Zero-Knowledge가 모네로, 지캐시와 같은 프라이버시 코인에 쓰임으로 인해 Zero-Knowledge라는 단어 혹은 간단한 개념 정도는 익숙한 분이 그럭저럭 있을 것으로 보입니다. 맨 처음에는 게시글 하나를 할애해 Zero-Knowledge에 대한 설명을 하려고 했으나 evenharder님이 작성하신 대화형 증명 시스템과 영지식 증명에 설명이 잘 되어있어서 자세한 설명은 저 글로 대신하고 간단한 요약만 작성하겠습니다. 먼저 $\text{SHA256}(x) = 0^{256}$을 만족하는 $x$를 증명자가 알고 있고, 알고 있다는 사실을 검증자에게 증명하면서도 $x$ 자체는...
-
Stoer-Wagner Algorithm
안녕하세요? 오늘은 Stoer-Wagner 알고리즘에 대해 살펴보겠습니다. Stoer-Wanger 알고리즘은 그래프의 Global Minimum Cut을 찾는 알고리즘입니다. Introduction 그래프를 두 집합 $S$, $T$로 나누는 것을 그래프의 cut이라고 합니다. 간선에 weight가 있는 그래프에서, 두 점 $s$와 $t$가 주어졌을 때 $s \in S$, $t \in T$를 만족하도록 그래프를 cut하는 상황을 생각해봅시다. 한 쪽 노드는 집합 $S$에, 다른 한 쪽은 $T$에 포함된 모든 edge들의 weight의 합을 cut의 크기라고 합니다. 이 때 크기가 가장 작은 최소 cut은 최대 유량과 같다는 사실(Min-cut Max-flow...
-
Deterministic Mincut in Almost-Linear Time
Introduction 지난 3월 포스팅 “Minimum Cuts in Near Linear Time”에서 Weighted min-cut을 near-linear time에 구해주는 Karger의 Monte-Carlo algorithm을 소개한 적이 있었습니다. 이 글에서는 Karger의 알고리즘을 almost-linear complexity로 유지하며 derandomize하는 데 성공한 Jason Li의 2021년 논문 Determinstic Mincut in Almost Linear Time을 리뷰합니다. 논문 자체가 기술적으로 복잡한 부분이 많은 만큼, 깊숙한 디테일을 모두 다루기보다는 특별한 경우에 대해 이 논문에서 소개한 방법론이 어떻게 적용되는지를 다루어보도록 합니다. Terminologies 일부는 3월 포스팅과 동일하지만, Li (2021)의 문법을 대체로 따르면서 변화한...