PS 이야기

Bostan Mori 알고리즘은 2020년 8월 Alin Bostan과 Ryuhei Mori가 작성한 이 논문에 소개되어 있는 선형점화식을 가지는 수열의 $N$ 번째 항을 빠르게 구하는 알고리즘이다. Bostan Mori 알고리즘 이외에 선형점화식을 가지는 수열의 $N$ 번째 항을 빠르게 구하는 방법은 이 글을 참고하자. $D_0, D_1, \cdots, D_{k-1}$과 $c_1, c_2, \cdots, c_k$가 주어졌을 때, $i \ge k$인 $D_i$를 다음과 같은 선형점화식으로 구할 수 있다고 하자. $$D_i = \sum_{j=1}^{k}{c_jD_{i-j}} = c_1D_{i-1} + c_2D_{i-2} + \cdots + c_kD_{i-k}$$ 이러한 선형점화식이 주어졌을 때, $D_N$..

$D_0, D_1, \cdots, D_{k-1}$과 $c_1, c_2, \cdots, c_k$가 주어졌을 때, $i \ge k$인 $D_i$를 다음과 같은 선형점화식으로 구할 수 있다고 하자. $$D_i = \sum_{j=1}^{k}{c_jD_{i-j}} = c_1D_{i-1} + c_2D_{i-2} + \cdots + c_kD_{i-k}$$ 이러한 선형점화식을 가지는 가장 유명한 예시는 피보나치 수열이다. 피보나치 수열은 위 식에서 $k=2$, $D_0 = 1$, $D_1 = 1$, $c_1 = 1$, $c_2 = 2$이다. 이러한 선형점화식이 주어졌을 때, $D_N$을 빠르게 구하는 방법을 알아보자. 1) 행렬 곱셈을 이용한 방법 $$\begin{pmatrix} D_N \\ D_{N-1}\\ D_{N..

차수가 $n$인 다항식 $f(x) = c_0 + c_1x^1 + c_2x^2 + \cdots + c_nx^n (c_n \ne 0)$가 있다. 그리고 차수 $m$인 다항식 $g(x) = d_0 + d_1x^1 + d_2x^2 + \cdots + d_mx^m (d_m \ne 0)$이 있다. 이를 다항식 $q$와 $r$을 이용하여, $f(x) = g(x)q(x) + r(x)$라고 나타내 보자. $r(x)$의 차수가 $m$보다 작은 경우, $f$를 $g$로 나눈 몫을 $q$, 나머지를 $r$이라고 정의한다. 다항식 $q$의 차수는 $n-m$이다. 다항식의 나눗셈을 교과과정에서 배운대로 구현한다면 $O(nm)$ 시간복잡도가 된다. 이를 좀 더 빠르게 하는 방법에 대해서 알아보자. $\textrm{Rev}(f)$를..

1214 A. 조약돌 순서 처음에 $[1, 2, 3, ..., K]$이 적혀있는 크기 $K$인 배열 $A$가 있다. $i = 1$부터 시작하여 $A_i$와 $A_{i+1}$의 값을 바꾼다. 그리고 $i$를 $1$ 증가시킨다. 만약 $i = K-1$이라면 다음 $i$의 값은 $K$가 아니라, $1$이 된다. 바꾸는 작업을 $N$ 번 하였을 때, 최종 배열의 상태를 구하는 문제다. 값을 바꾸는 횟수 $N$이 최대 $10^{18}$로 굉장히 크다. 바꾸는 작업을 $K \times (K-1)$ 번 하면 배열이 원래 상태로 돌아오고, 바꾸는 작업을 $K-1$ 번하면 맨 왼쪽에 있던 값이 맨 오른쪽으로 가는 것을 알 수 있다. 이 점을 이용하여, $O(K)$ 시간복잡도에 해결할 수 있다. 더보기 #include u..

1. 비트문자열 특정 규칙으로 만들어지는 길이 $2^i$인 이진문자열 $S_i$가 있다. 구간 $[s, e]$가 있을 때, $S_i$의 $s$ 번째 문자부터 $e$ 번째 문자까지 문자 중에서 1의 개수를 구하는 문제다. 단, 하나의 입력 파일에 최대 20만 개의 테스트 케이스가 들어올 수 있어서 상당히 빠른 시간 안에 문제를 해결해야 한다. 문제 설명에 적힌 규칙과 다른 방식으로 $S_i$를 설명할 수 있다. $S_0$는 "0"이며, $1$ 이상인 $i$에 대해 $S_i$는 $S_{i-1}$에서 0/1을 뒤집은 것과 $S_{i-1}$을 이어 붙인 문자열이 된다. 즉, $S_1$은 "10"이며, $S_2$는 "10"에서 0/1을 뒤집은 "01"에 "10"을 이어 붙인 "0110"이 된다. $S_3$은 "0..

1. 사진작가 정수로 이루어진 길이 $N$인 배열 $A$가 주어진다. 이 배열의 부분배열 중에서 같은 수를 여러 개 포함하고 있지 않은 부분배열이 있다. 그러한 부분배열 중에서 길이가 가장 큰 부분배열의 길이를 구하는 문제다. 배열을 구성하는 정수의 범위가 $1$ 이상 $1\,000\,000$ 이하이다. 크기가 $1\,000\,000$인 배열을 하나 잡아서 마지막으로 그 수가 등장한 인덱스를 저장하면, 어떤 수 $i$에 대해, $A_i$랑 같은 수 중 왼쪽에 있으면서 가장 오른쪽에 있는 수의 인덱스 $last_i$를 구할 수 있다. 그다음, 오른쪽 끝이 $i$인 부분배열 중에서 문제의 조건을 만족하는 가장 큰 부분배열의 왼쪽 끝은 $\max\limits_{1 \le j \le i}(last_i)+1$이..

글을 쓰는 날짜 기준, 오늘(2022년 7월 1일) 오후 1시 30분부터 5시까지 약 3시간 30분 동안 `22 현대모비스 알고리즘 경진대회 예선에 참가했다. 문제 내용에 대한 언급은 서약 때문에 할 수 없어서 대회 환경에 대한 이야기를 해보려고 한다. 대회는 Goorm Devth(https://devth.goorm.io/)에서 진행됐다. 이 대회에서 가지는 몇 가지 특이 사항과 그로 인한 단점들, 응시하는 입장에서 주의해야 할 것을 적어보겠다. 07/14 추가) 아래 언급된 것 중 일부분은 본선에서 개선이 되었다. 본선에서 개선된 부분들은 별도 표시(*)를 해두었다. 1) 실시간 채점 X (*) 실시간 채점을 지원하지 않는다. 먼저, 다른 대회들의 진행 방식을 알아보자. 첫 번째로, 제일 많은 사람이 ..

오랜만에 풀이 및 후기 글을 적는다. Google Code Jam은 매년 꾸준히 참가해왔다. 그동안 PS 공부할 시간적 여유가 없어서, 참가만 해왔었고, 다행히 최근에는 육아휴직으로 시간이 생겨서 밀린 PS 공부를 했다. 주로 최근에 well-known이 된 알고리즘/자료구조들을 공부하고 익히는 시간이었다. 다만, 최근 Round 2 성적이 최근에 공부한 것을 감안했을 때 아쉬움이 많이 남는 결과라 현재 심경과 풀이를 정리할 겸 포스팅을 시작한다. A. Spiraling Into Control Spiral 모양의 $N \times N$ 크기의 행렬이 있을 때, 원하는 만큼 shortcut을 놓아 정확히 $K$ 번의 이동으로 출발점 $1$에서 도착점 $N^2$으로 가는 문제다. Shortcut이 하나도 없..

유용한 링크: MIT 강의 자료 어떤 문자열이 있고, 각 알파벳에 바이너리를 할당한다. 할당된 바이너리는 어떤 것이 다른 것의 prefix가 되면 안 된다. 문자열을 알파벳에 할당된 바이너리로 표현할 때 바이너리의 크기를 최소화하는 문제가 있다. 이는 매우 일반적인 압축 알고리즘을 필요로 하는 상황이다. Huffman Coding은 이 문제에 대한 최적해를 $O(N \lg N)$ 시간에 구한다. 각색은 다르지만, Huffman Coding과 같은 상황인 문제는 BOJ 13975번 파일 합치기 3이 있다. Huffman coding - Wikipedia From Wikipedia, the free encyclopedia Jump to navigation Jump to search Technique to c..

유용한 링크: 위키백과, Skew heap visualization, NTU 강의자료 Skew heap(혹은 self-adjusting heap)은 이진트리로 구현된 힙 자료구조다. 우리가 배운 기본적인 힙은 완전이진트리이므로 배열과 인덱스를 이용하여 편하게 구현이 가능하다. 그러나, Skew heap은 완전이진트리가 아닌 그냥 이진트리이므로 배열을 이용한 구현을 할 수 없다. 그렇다면, 일반 힙이 아닌 Skew heap이 필요한 순간은 언제일까? 바로, 서로 다른 두 힙을 하나로 빠르게 합치고 싶은 순간에 쓸 수 있다. 서로 다른 두 힙을 하나로 합치는 것을 merge 연산이라고 한다. Skew heap은 merge 연산 중간, 왼쪽 자식과 오른쪽 자식을 무조건적으로 바꿔주어 균형을 유지한다. 이 me..