이 문제에서는 SEERC '19 Game on a Tree와 CERC '11 Racing Car Trail의 풀이를 다룬다. 풀이의 첫 단어부터 강력한 스포일러가 될 수 있으니 충분한 고민을 해보고 오는 것을 권한다. 풀이 설명 또한 두 문제의 context에 의존하는 경향이 강하니 지문을 숙지하고 오자. https://www.acmicpc.net/problem/17962 17962번: Game on a Tree In a single line, print “Alice” (without quotes), if Alice wins. Otherwise, print “Bob”. www.acmicpc.net https://www.acmicpc.net/problem/3419 3419번: Racing Car Trail..

https://www.acmicpc.net/problem/13318 13318번: 위험한 해싱 string matching 알고리즘에는 여러 가지가 있다. KMP 알고리즘이나 Boyer­Moore 알고리즘이 그 예시이다. 하지만 지구이는 KMP를 이해할 수 없었고, Boyer­Moore는 시간복잡도가 너무 컸다. 결국 지구이는 틀릴 확률이 있지만, 간단한 방법인 해싱을 즐겨 사용하게 되었다. 해싱은 문자열을 숫자 하나로 바꾸는 해시 함수를 하나 정의한 후, 이 값이 같은지 다른지를 통해 문자열이 같은지 판별하는 방법이다. 지구이는 해시 함수를 다음 www.acmicpc.net 풀이 두 해시값을 뺀 다항식을 생각하면, 그 다항식은 아래와 같은 조건을 만족해야 한다. \(\deg f < 300000\) \(..

원본: https://codeforces.com/blog/entry/61205 Blogewoosh #1 - Codeforces codeforces.com Radewoosh의 블로그에 올라온 신기한 트릭을 리뷰한다. 해결해야 할 원본 문제는 여기서 볼 수 있다. https://szkopul.edu.pl/problemset/problem/wTy-sxQCIKry0Ml-6RvM0L78/site/?key=statement Zadanie Różne słowa (slo) - Problemset - SZKOpuł Congratulations, you solved it! The problemset isn't perfect, but we always aim to make it better. To do that we nee..

조합론에서의 Cayley's theorem은 완전그래프 \(K_{n}\)의 서로 다른 spanning tree가 \(n^{n-2}\)개라는 정리이다. 일반적으로는 그 쓰임보다도 아름다운 증명에 가치를 둔다. Functional graph를 알고 있다는 전제 하에 글을 작성했다. Reference : Miklos Bona - [A Walk through Combinatorics] cf : \([n] := \{1,\dots,n\}.\) Proof (By A. Joyal) \(K_{n}\)의 spanning tree의 개수를 \(t_{n}\)이라고 두고, \(n^{2}t_{n} = n^{n}\)임을 보인다. Definition. 정점 \(n \ge 1\)개의 트리 \(T\)에서 정점 \(a, b\)를 골라 \..

Baekjoon Online Judge에는 유용한 문제 난이도 기능 solved.ac 가 있다. 내가 기여한 문제들의 풀이를 간략하게 써보려고 한다. 아마 Gold, Platinum이 주류가 될 것 같고, Diamond 이상은 개별 풀이 포스팅을 할 것 같다. 형식은 문제 번호 (내가 준 티어) 순이다. Gold / Platinum / Diamond 수준의 구분은 신경을 쓰지만, Gold I ~ V의 세부적인 분류는 문제를 푼 직후에 즉흥적으로 내린 경우가 더 많다. 참고 정도만 하자! BOJ 1762. 평면그래프와 삼각형 (Gold II) 불러오는 중입니다... BOJ 2026. 소풍 (Gold III) Last update 19.12.16. 더보기 Maximal clique problem의 결정 문제..