-
프로그래밍 대회 출제 체크리스트
개요 PS가 보다 대중에게 친숙해지면서 여러 종류의 프로그래밍 대회도 점점 많아지고 있습니다. 특히 기관이나 기업이 아닌 일반인이 주최하는 대회가 부쩍 늘었는데, 대표적인 것이 대학교 대회라고 할 수 있습니다. 모두에게 친숙한 백준 온라인 저지에서도 BOJ Stack을 통해 손쉽게 대회를 준비할 수 있는 플랫폼을 만들어 어느 정도 PS에 경험이 있다면 누구나 쉽게 대회 개최에 참여할 수 있게 되었습니다. 반면에 아마추어가 쉽게 대회를 열 수 있다는 점은 반대로 준비가 덜 된, 낮은 퀄리티의 문제가 쉽게 양산될 수도 있다는...
-
랜덤한 교란 순열을 생성하는 card-based 프로토콜 (1)
1. Introduction Symmetric group $S_n$의 원소, 즉, $[n]$ 상의 순열 가운데 fixed point가 없는 것들을 Derangement(교란 순열)이라고 부른다. 이제, 한 가지 예를 들어, $n$ 명의 학생이 있는 학급에서 마니또 행사를 한다고 가정해보자. 학생 $i$의 마니또가 $p_i$라 할 때, $p_i \neq i$ 여야 하며, $i \neq j$ 이면, $p_i \neq p_j$ 여야 할 것이다. 즉, ${p_i}$ 가 derangement 여야 한다. 또한, 학생 $i$는 $p_i$의 값 외에 다른 정보를 알지 않아야 한다. 이렇듯, 현실에는 각자 자신에게 배정된 수...
-
Operations on Set Power Series
Table Of Contents Introduction Set Power Series Addition Or Convolution Subset Convolution Composition of Set Power Series Exponential General Case Example: ARC105 F Introduction 안녕하세요, Aeren입니다! 이번 글에서는 set power series와 그와 관련된 연산들을 소개하고, combinatorial problem에서 어떻게 활용될 수 있는지 간단하게 소개하겠습니다. Set Power Series 어떤 set $G = \lbrace g _ 0,g _ 1,\cdots ,g _ {N-1} \rbrace$와 commutative ring $R$이 주어질 때, 함수 $p:\mathcal{P}(G) \rightarrow R$를 set power series라고 부릅니다. 그리고 일반적인...
-
Attacking a Variant of the RSA Cryptosystem
서론 이번 글은 저번 달의 글에 이어서 pbctf 2021를 출제하면서 사용한 논문 하나를 리뷰하려고 합니다. 이 논문은 Yet Another RSA라는 문제로 작성하게 되었습니다. 해당 논문의 제목은 Classical Attacks on a Variant of the RSA Cryptosystem인데요, RSA의 변종에 대해 $d$가 작을 경우의 공격법을 다루는 논문입니다. 본론 RSA Variant 이 논문에서 소개하는 RSA의 변종은 정수가 아닌 group 위에서 정의됩니다. 해당 그룹에 대해서 정의하자면 다음과 같습니다. Field $(\mathbb{F}, +, \cdot)$에 대해서 non-cubic integer $r \in \mathbb{F}$를 하나 뽑읍시다....
-
Linear Suffix Array Construction
제가 최근에 작업을 하면서 큰 문자열에서 다른 작은 문자열을 많이 찾을 필요가 있었습니다. 정확히는, 이런 일을 해야 할 필요가 있었습니다. 문자열 $T$가 주어집니다. 문자열 $S_{1}$, $S_{2}$, $\cdots$, $S_{K}$가 $T$에서 등장하는 횟수를 구해야 합니다. 모든 정수 $1 \leq i < K$에 대해, $S_{1}$, $S_{2}$, $\cdots$, $S_{i}$에 대한 답을 구한 이후에야 $S_{i+1}$을 알 수 있습니다. 이 조건은 실제 문제 상황보다는 조금 빡빡한 제한이지만, 이렇게 가정해도 큰 무리는 없습니다. 이 상황이 다른 일반적인 상황과 크게 다른 점은 이렇습니다....