-
Segment의 개수를 이용하는 순열 경우의 수 문제
소개 특정 조건을 만족하는 순열의 개수를 세는 문제 중에서, segment(이하 구간)의 개수를 이용하는 특이한 꼴의 다이나믹 프로그래밍 문제를 다뤄보려고 합니다. 예시 문제를 통해 살펴봅시다. 문제1. 길이가 $N$, Increasing segment의 개수가 $K$개인 순열의 개수 Increasing segment란, $l+1 \leq i \leq r$인 모든 $i$에 대해 $A_{i-1} < A_i$를 만족하는 $[l, r]$이라고 합니다. 단, 다른 increasing segment에 포함되는 구간은 무시하는 걸로 합시다. 예를 들어, $1\space4\space5\space2\space3\space6\space8\space7$의 increasing segment는 $[1, 3], [4, 7], [8, 8]$로 총 3개입니다. 우리는 길이가 $N$이고...
-
Skew-binary Lifting
Table Of Contents Prerequisite Introduction Implementation Performance Analysis Benchmark Prerequisite Binary Lifting - Tutorial on cp-algorithms Introduction 안녕하세요, Aeren입니다! 이 글에서 소개할 내용은 skew-binary number system을 기반으로 한 skew-binary lifting입니다. 이 글은 An Applicative Random-Access Stack by Eugene W. MYERS을 기반으로 작성되었습니다. 일반적인 binary lifting과의 차이점 중 하나는 각 node $u$가 $O(\log(\textrm{depth}[u]))$ 대신 $O(1)$ 만큼의 공간을 필요로 한다는 것입니다. 표로 정리하면 다음과 같습니다. (Time) / (Additional Space Required) Operation Binary Lifting Skew-binary Lifting Add A...
-
Solving Univariate Polynomial over Finite Field
서론 최근 finite field 위에서는 univariate polynomial을 빠르게 풀 수 있다는 소프트웨어 멤버십 노규민 님의 말씀을 들었습니다. 일반적인 합성수 modulus 위에서 Coppersmith method 등을 통해서 작은 값을 가지는 해를 구하는 방법에 대해서만 접해보았기 때문에, 이 방법에 흥미를 느끼고 한 번 정리해보게 되었습니다. 본론 찾아보니 해를 구하는 것은 Polynomial factorization과 밀접한 관련이 있어서, 유명한 Polynomial factorization 알고리즘인 Cantor–Zassenhaus algorithm을 알아보고, 이를 바탕으로 해를 구하는 방법에 대해서 알아보려고 합니다. Cantor–Zassenhaus algorithm Cantor–Zassenhaus algorithm의 메인 아이디어는 equal-degree factorization,...
-
Top Tree로 Dynamic Tree 관리하기
Top Tree로 Dynamic Tree 관리하기 이 글을 읽기 이전에 동적 계획법을 최적화하는 9가지 방법 (4/4) 의 “Dynamic Tree DP” 단원을 이해하는 것이 좋다. 이 글은 해당 내용을 잘 이해하고 있다고 가정하고 설명한다. 그래프의 특수한 경우인 트리는 PS를 포함한 알고리즘 전반에서 자주 활용되는 구조이다. 트리는 일반적인 그래프에 비해 여러 방면으로 효율적으로 관리할 수 있다. 이러한 방법은 그 자체로도 관심의 대상이 되며, 그래프 문제를 풀 때도 다양하게 응용할 수 있다. 너무나도 중요하다는 사실이 잘 알려져 있으니, 구태여...
-
Quine: 자기 자신의 소스코드를 출력하는 프로그램
우리가 주로 프로그래밍을 하는 목적은 문제를 효율적으로 풀거나, 특정 작업을 편리하게 처리하기 위해서일 것입니다. 그러나 어디서나 재미를 추구하는 것은 사람의 본능이기에, 오직 호기심과 흥미만을 목적으로 전혀 실용적이지 않은 코드를 짜는 경우도 꽤나 있습니다. 얼마나 창의적이게 이상한 C언어 코드를 작성했는지 겨루는 IOCCC라는 대회가 존재할 정도입니다. 이 글에서는, 쓸모는 없지만 신기한 프로그램의 대표적 예시인 ‘콰인(Quine)‘과 그 이론적 배경에 대해 알아보도록 하겠습니다. 콰인이란? 콰인(Quine) 은 실행했을 때 자기 자신의 소스 코드를 출력하는 프로그램을 이르는 말로, 미국의 철학자이자 논리학자인...