https://www.acmicpc.net/problem/10129 10129번: 작은 새 문제 경기과학고의 뒤뜰에는 일렬로 된 n개의 나무로 이루어진 숲이 있다. 그 중 첫 번째 나무 위에는 마지막 나무의 위로 올라가고 싶어하는 작은 새가 한 마리 있다. 그 새는 몸집이 매우 작기 때문에 한 번의 비행으로 날아갈 수 있는 거리에 한계가 있다. 만약 새가 i번째 나무 위에 있다면, 이 새는 한 번의 비행으로 i+1, i+2, …, i+k번째 나무 중 하나로 갈 수..

이 문제에서는 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..

https://www.acmicpc.net/problem/13318 13318번: 위험한 해싱 string matching 알고리즘에는 여러 가지가 있다. KMP 알고리즘이나 Boyer­Moore 알고리즘이 그 예시이다. 하지만 지구이는 KMP를 이해할 수 없었고, Boyer­Moore는 시간복잡도가 너무 컸다. 결국 지구이는 틀릴 확률이 있지만, 간단한 방법인 해싱을 즐겨 사용하게 되었다. 해싱은 문자열을 숫자 하나로 바꾸는 해시 함수를 하나 정의한 후, 이 값이 같은지 다른..

원본: 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..

조합론에서의 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}..

Baekjoon Online Judge에는 유용한 문제 난이도 기능 solved.ac 가 있다. 내가 기여한 문제들의 풀이를 간략하게 써보려고 한다. 아마 Gold, Platinum이 주류가 될 것 같고, Diamond 이상은 개별 풀이 포스팅을 할 것 같다. 형식은 문제 번호 (내가 준 티어) 순이다. Gold / Platinum / Diamond 수준의 구분은 신경을 쓰지만, Gold I ~ V의 세부적인 분류는 문제를 푼 직후에 즉흥적으로 내린 경우가 더 많다. 참고 정도만 하자!..

스코어보드는 여기서 볼 수 있다. 5, 6위팀과 페널티 4분이라는 근소한 차이로 전체 4등 / 90팀으로 대회를 마무리했다. 예선 본선 모두 4등이다. 팀원은 imeimi, TAMREF, jhhope1. A Bus With No Drivers 팀처럼 컴공과가 한 명밖에 없는 팀이다 ㅋㅋ 팀 전략, 사전 연습, 팀노트 즈홒(jhhope1)은 풀이를 내는 능력이 뛰어난 데 비해 아직 구현이 익숙하지 않았고, 나는 코딩이 빠른 편이지만 풀이를 잘 못 만들었다. imeimi..

고등학생 때 확률과 통계에서, 빠르면 중학생 때 수학올림피아드에서 접하게 되는 Stirling number \(S(n,k)\)에는 항상 제 2종 이라는 수식어가 붙는다. 교과서에서 보이지도 않는 제 1종 스털링 수가 뭐기에 더 쓸모가 많은 \(S(n,k)\)를 "제 2종"이라고 이름붙인 걸까? Notations & Preliminaries - \([n]\)은 양의 정수 집합 \(\{1,2,\cdots,n\}\)을 의미한다. - Falling factorial \(\displaystyle (x)_{k} := x(x-1)\cdots..