PS 이야기

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

1. 계단 $1$ 층부터 $M$ 층까지 총 $M$ 개의 층이 있는 건물이 있다. 건물의 $F$ 층에서 시작하여 계단을 통해 한 층을 올라가거나, 엘리베이터를 타고 원하는 층으로 이동할 수 있다. 정확히 $N$ 번 계단을 통해 층을 오르면서 엘리베이터를 적절히 타서 $F$ 층으로 돌아오고 싶다. 이때, 엘리베이터를 타는 횟수의 최솟값을 구하는 문제다. 문제에서 $F$가 입력으로 주어지지만, $F$는 답에 영향을 미치지 않는다는 것을 알 수 있다. 답은 $\left\lceil\frac{N}{M-1}\right\rceil$이다. 더보기 #include using namespace std; int M, F, N; int main() { cin >> M >> F >> N; cout

길이가 $n$인 문자열 $s$가 있다. $1 \leq i \lt n$인 $i$에 대해 $z[i]$를 $i$에서 시작하는 suffix와 $s$의 가장 긴 common prefix의 길이라고 정의하자. 편의상 $z[0] = 0$이다. 이러한 $z$ 배열을 문자열 $s$의 Z-function이라고 부른다. 예를 들어, 문자열 "aaaaa"의 경우, $z = [0, 4, 3, 2, 1]$이 되며, 문자열 "aaabaab"의 경우, $z = [0, 2, 1, 0, 2, 1, 0]$이 되고, 문자열 "abacaba"의 경우, $z = [0, 0, 1, 0, 3, 0, 1]$이 된다. Z-function을 $O(n^2)$ 시간복잡도로 naive 하게 구하면 아래와 같이 코딩할 수 있다. vector z_functio..