qwerasdfzxcl의 ps 블로그 qwerasdfzxcl의 ps 블로그

오일러 경로를 구하는 알고리즘은 다음과 같다.void dfs(int now){ for(int nxt=1; nxt 0){ g[now][nxt]--; g[nxt][now]--; dfs(nxt); } } printf("%d ", now);} 나는 이 코드와 알고리즘에 대한 설명을 읽고 이해를 할 수 없었다. "dfs하면서 사이클을 찾으면 끼워 넣는다"로 보통 설명하는 것 같은데, 어떤 사고를 거치면 저런 코드가 나오는 것일까? 이에 대해 오랜 시간 고민해봤지만 아직도 잘 모르겠다. 그래도 다행인 점은 적어도 내가 납득할 수 있는 설명을 찾았다는 것이다. dfs(now)를 호출하면 현재 그래프에 남아있는 간선을 사용해서 now로 끝나는 오일러 경로를 출력하게 된다. 정확히는, 기존에 출력했던 경로 ..

당연한 말이지만 $\mathbb{Z}_p$에서 생각한다. Lagrange interpolation 구하려는 식은 $n$에 대한 $k+1$차 다항식이라는 사실이 알려져 있다. 따라서, $k+2$개의 함숫값만 알고 있으면 Lagrange interpolation을 통해 값을 계산할 수 있다. 함숫값을 구하는 건 거듭제곱을 해야 하기 때문에 $O(k \log k)$의 시간이 걸리고, $f(n)$을 계산하는 것은 역원을 나이브하게 계산할 경우 $O(k \log p)$의 시간이 걸린다. 사실 이 정도면 충분히 빠르다. TLE가 난다면 쓰레기 문제라는 뜻이기 때문에 풀지 않는 것을 권장한다. Linear sieve 사실 $i^k$를 $i=0, 1, \ldots, k+1$에 대해 계산하는 것은 $O(k)$에 가능하다..

문제0 이상 1 이하인 분모가 $N$이하의 기약분수를 크기 순으로 나열한 수열을 $N$번째 페리 수열 (Farey Sequence)라고 한다. $N$과 $K$가 주어졌을 때, $N$번째 페리 수열의 $K$번째 원소를 구하여라. BOJ 1882와 동일한 문제고, 올해 ICPC 예선에도 출제된 문제이다. 이 글에서는 $N$이 고정이고 $K$가 쿼리로 주어질 때 전처리 $O(N^{\frac{2}{3}})$, 쿼리 $O(\sqrt{N} \log^{1.5}{N})$ 시간에 이 문제를 해결하는 방법에 대해 다룬다. 문제 변형하기$n$번째 페리 수열의 길이는 $\Theta(n^2)$임이 널리 알려져있다. (서로소인 쌍의 개수의 비율이 $\frac{6}{\pi^2}$에 수렴한다.) 따라서, 페리 수열을 직접 구하는 방..

(2023.06.11 online IHT with linear memory 문단 추가) 이 글에서는 imos법을 확장한 imos-Hanbyeol Trick (IHT)의 개념과 응용에 대해 설명한다. imos법 imos법이란 구간 덧셈 업데이트를 빠르게 처리하는 테크닉이다. 다음과 같은 문제를 생각해보자. 0으로 초기화된 $N \times N$ 크기의 $2$차원 배열 $A$가 주어진다. 다음 연산을 $Q$개 처리한 후 배열을 출력하여라. $x_1$ $y_1$ $x_2$ $y_2$ $z$: $A[x_1:x_2][y_1:y_2]$에 $z$를 더한다. (앞으로 모든 : notation은 닫힌 구간이다.) 나이브하게 했을 때 시간복잡도는 최악의 경우 $O(QN^2)$이지만, imos법을 사용하면 $O(Q+N^2)..

길이가 각각 $N$, $M$인 두 문자열 $A$, $B$의 LCS (Longest Common Subsequence)을 구하는 문제는 매우 유명한 문자열 비교 문제이며, 이는 간단한 dp로 $O(NM)$에 해결할 수 있음이 알려져 있다. 또한, 이를 더 빠르게 하기 힘들다는 것도 알려져 있다. 이 글에서는 $A$와 $B$의 substring의 LCS를 구하는 문제인 semi-local LCS에 대한 빠른 알고리즘을 설명한다. 내용이 매우 길고 복잡하기 때문에, 이 글에서는 핵심적인 내용만 요약해서 설명할 것이며, 자세한 증명은 모두 생략할 것이다. 목차 1. ALCS algorithm 2. Seaweed braids 3. Unit-Monge matrix distance multiplication 4. P..

서론다음과 같은 문제를 생각해봅시다. "좌표평면에 $N$개의 선분이 있고, 이들 중 서로 교차하는 선분 쌍이 존재하는지 판별하라." 이 문제를 푸는 가장 간단한 방법은 모든 선분 쌍에 대해 서로 교차하는지 판별하는 것입니다. 선분 쌍은 $O(N^2)$개이고, 두 선분이 교차하는지는 $O(1)$에 판정할 수 있기 때문에 시간복잡도는 $O(N^2)$이 됩니다. 이 글에서는 위 문제를 $O(N\log{N})$에 풀 수 있는 샤모스-호이 알고리즘에 대해 설명하겠습니다. 가정알고리즘을 소개하기에 앞서, 몇 가지 가정을 하도록 하겠습니다. 1. $y$축에 평행한 선분이 존재하지 않는다.2. 한 선분의 끝 점이 다른 선분이나 끝 점 위에 있는 것도 교차하는 것이다.3. 세 선분이 한 점에서 교차하는 경우는 존재하지 ..