PS 이야기

참고자료: 위키백과 Stern-Brocot 트리는 모든 양의 유리수가 정점과 일대일이 되는 무한한 완전 이진트리다. 또한, 이진탐색트리처럼 왼쪽에서 오른쪽 방향으로 탐색 가능하다. 연분수에 의한 트리 양의 유리수는 $q$ 는 아래와 같은 연분수 꼴로 표현할 수 있고, 이를 수열 $a$로도 표현할 수 있다. $q = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{\ddots + \cfrac{1}{a_k}}}} = [a_0; a_1, a_2, \dots, a_k]$ 여기서 $k$와 $a_0$는 음이 아닌 정수고, 나머지 $a_i$는 양의 정수다. 이러한 표현은 유일하지 않은데 다음과 같이 수열의 맨 끝 $a_k$가 $1$일 때는 중복이 있기 때문이다. $[a_0; a_..

문제: 공식 홈페이지채점: Yandex 1. doll 0번 정점을 시작점이라고 부르고 0번 정점은 나가는 간선이 정확히 1개다. 1번부터 M번까지 번호가 매겨진 나가는 간선이 정확히 1개인 트리거 정점 M개가 존재한다. 그리고 스위치라고 불리는 정점들은 번호가 음수로, 개수가 S개일 때, -1번부터 -S번까지 번호가 매겨진다. 스위치 정점은 나가는 간선이 정확히 2개이며 스위치 상태가 'X'일 때는 'X'로 표시된 간선으로 나가게 되며, 스위치 상태가 'Y'일 때는 'Y'로 표시된 간선으로 나가게 된다. 정점을 나가면서 동시에 스위치 정점의 상태가 뒤집힌다. 초기 0번 정점에서 이동을 시작하며, 이동을 하다가 다시 처음 0번 정점으로 돌아오는 순간 모든 스위치 정점의 상태는 'X'여야하며 트리거 정점은 ..

문제: 공식 홈페이지 채점: Yandex 1. combo 길이가 N인 'A', 'B', 'X', 'Y'로만 이루어진 문자열 S가 있다. 문자열 S의 첫 글자로 나타나는 알파뱃은 오직 한 번만 등장한다. press(p)라는 함수를 문제에서 제공하는데, press(p)에서 p는 길이가 4N 이하인 문자열이며, p의 부분문자열 중 문자열 S의 prefix 중 하나와 동일하며 가장 긴 문자열의 길이를 반환한다. 문제는 적은 횟수의 press(p) 함수 호출을 통해 문자열 S의 내용을 정확하게 알아내는 것이다. 여담으로, p의 부분문자열 중 문자열 S의 prefix 중 하나와 동일하며 가장 긴 문자열의 길이란, 즉, 문자열 S를 패턴이라고 생각하고 p를 전체 문자열이라고 생각했을 때, KMP 알고리즘의 실패 함수..