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

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