ICPC를 마무리하면서 2020의 PS 일정은 사실상 마무리되었다. 11/12 solve 3등으로 전체 대회를 마무리했다. 굉장히 좋은 성적을 거뒀지만, 제 역할을 못한 것 같아서 많이 아쉽다. 기대한 것도 있었고... 대회 준비 팀 구성은 작년과 같이 imeimi / jhhope1 / TAMREF로 구성된 3인팀이었다. 사실 예선 때까지만 해도 거의 기대를 하지 않았다. 학기 일정을 소화하기에도 많이 벅찼고 PS를 거의 손도 대지 않았다. 그런데 솔직히 팀원이 imeimi인데ㅋㅋㅋㅋ 월파 욕심이 안 나기 어렵다. 폼이 많이 떨어진 상태에서 예선을 봤는데 생각보다 가능성이 보여서(??) jhhope1이 실력을 좀 키우자는 이야기를 했다. 결국 내가 아는 문제들을 즈홒한테 던져주고, 즈홒은 풀이를 짜고, ..

고3 때를 포함해서 3번째 UCPC. ICPC멤버 그대로 (imeimi2000, jhhope1, TAMREF) 완전탐색 원툴 16등 도전합니다팀으로 참가했다. 최종 성적은 10 / 12 solve 5등으로, 역대 UCPC 중에서는 제일 좋은 성적이 나왔다. 팀연습이라고는 UCPC 예선밖에 없었는데 결과는 별로 나쁘지 않았다 ㅋㅋ 기억나는대로 타임라인을 재구성해본다. 약한 스포일러가 있으니 주의. 초반 (0~1시간) 내가 앞, 이멘이 중간, 즈홒이 뒤를 맡았다. A에 후원사 로고가 붙어있는 걸 발견했지만 뭔가 "제일 쉬운 문제"로 불릴 정도는 아닌 것 같아서 B랑 C를 보고 있었다. 한창 복잡한 지문을 읽고 있는데 스코어보드에 초록색 A들이 쫙 깔리기 시작했다. 정신 차리고 보니 쉬운 문제더라. 트리에서 ..

https://www.acmicpc.net/problem/10129 10129번: 작은 새 문제 경기과학고의 뒤뜰에는 일렬로 된 n개의 나무로 이루어진 숲이 있다. 그 중 첫 번째 나무 위에는 마지막 나무의 위로 올라가고 싶어하는 작은 새가 한 마리 있다. 그 새는 몸집이 매우 작기 때문에 한 번의 비행으로 날아갈 수 있는 거리에 한계가 있다. 만약 새가 i번째 나무 위에 있다면, 이 새는 한 번의 비행으로 i+1, i+2, …, i+k번째 나무 중 하나로 갈 수 있으며 그보다 멀리 떨어진 나무로는 가지 못한다. 또한, 작은 새에게 지금 있는 www.acmicpc.net 더보기 가장 먼저 드는 생각은 \(dp[i]\)를 "\(i\)번 나무에 도달하기 위해 느끼는 피로감의 횟수"로 정의하는 것이다. 점화식..

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

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의 결정 문제..