군대에서 갑자기 PS 공부에 흥미를 느껴 야금야금 공부하기 시작했다 (물론 전역이 다가오며 더 이상 아무것도 할 수 없는 지경에 이르러 잠시 손을 놓았다.) 올해 전역을 하고서는 멈추었던 PS를 다시 시작했다. 서서히 실력이 올라가는 것이 체감되며 재미를 느꼈다.
대학 졸업 마지막 학기를 남겨두고 대학에서만 할 수 있는 활동을 하고 싶었다. 6월에 에브리타임에 글을 올렸다. UCPC/ICPC 팀원 모집. 학교에 PS를 관심있어하는 사람이 별로 없을 것 같아 불안했지만 생각보다 몇몇 분들이 연락해주셨다. 원래 같이 대회에 나가기로 했던 holywater2, 먼저 연락을 주셨고 이제까지 푼 문제에서 비범함이 돋보였던 invrtd-h와 함께 팀을 꾸리게 되었다.
무언가를 일방적으로 가르치는 방식은 어울리지 않는다 생각해서 각자 자신이 공부한 알고리즘, 그리고 알려주고 싶은 문제를 준비해서 일주일에 두 번 디스코드를 통해 모였다. 서로가 공부하는 방향도 달랐고 접해보지 못한 특이한 컨셉도 있어 재미있게 시간을 보냈다.
아쉽게도 UCPC는 예선에서 떨어졌다. 말을 정정하자면 사실 아쉽지는 않았다. 예선을 치르며 든 생각은 확실히 우리가 대회 자체는 별로 연습하지 않았다는 점이었다. 쉬운 문제들도 많았지만 어려운 문제를 붙잡고 시간을 허비하기도 했고 심지어 무조건 풀어야 하는 문제들도 시간안에 풀지 못했다. 충분히 예선에 떨어질만 했다. 그냥 이 경험을 교훈삼아 ICPC는 더 철저히 준비해야겠다 다짐했다.
여름 방학에는 기업 인턴, 랩실 인턴 등으로 각자 바빴지만 그런 와중에도 짬을 내서 일주일에 두 번 무조건 디스코드로 공부한 것들을 공유하였다.
2학기에는 모두가 학교에 모였다. 처음에는 기존과 동일한 방식으로 한 장소에서 만나 진행하였고 ICPC 예선이 다가오며 방식을 바꾸어 과거 대회 set을 가져와 풀었다. 2시간이라는 짧은 시간동안 연습을 진행했기 때문에 문제를 최대한 빨리 해결해야 했으며 컴퓨터 한 대를 함께 사용했기 때문에 컴퓨터를 잡고 있는 시간을 줄이려고 자신의 해답을 어떻게 구현할지 생각해놓아야 했다. 개인적으로 이런 연습이 꽤나 많은 도움이 되었다고 생각한다.
ICPC 신청을 하면서는 나이 제한과 대학 졸업으로 인해 정말 마지막 ICPC라는 사실을 다시금 깨닫기도 했다.
그렇게 ICPC 예선을 치렀다.
UCPC 결과가 너무 좋지 않았기 때문에 우려하며 치렀던 대회였다. 초반에 문제를 하나도 풀지 못하고 있어서 분위기가 좋지 않았는데 슬슬 풀리는 문제들이 생기기 시작했고 6솔을 하고 남은 문제들을 보았을 때 이 정도면 본선은 가겠다라는 생각이 들었다. (우리가 푼 여섯 문제와 그 외 문제들의 난이도 차이가 상당히 심했다.) (문제 A에 대한 해석을 이상하게 하면서 너무 늦게 풀게되어 등수가 많이 밀렸다.)
나중에 올라온 공지를 통해 본선 진출 팀들을 확인하였고, 우리 팀이 본선에 나간다는 것을 알게되었다. 6솔을 가장 빨리한 팀이 21등이었기에 조금만 더 잘하면 수상을 노릴 수 있지 않을까하는 희망회로를 돌리며 본선을 기다렸다.
처음 가본 오프라인 대회는 신기했다. 여기 있는 사람들이 대학을 졸업하고 어떤 미래가 기다리고 있을지도 괜히 궁금했고 실제 대회에서 문제를 풀었을 때 풍선을 달아주는 것도 신기했다. PS 관련 활동으로 처음 티셔츠를 받은 것도 기뻤다. 대회가 진행되는 5시간동안 열심히 머리를 굴렸고 6솔을 해 28등으로 처음이자 마지막인 ICPC 본선을 마무리했다. 우리 팀의 실력을 생각하였을 때 5시간이라는 시간 안에서 5~7솔이 최대라고 생각했기에 그냥 덤덤하게 결과를 받아들일 수 있었다.
조금 더 빨리 PS에 관심을 가졌다면 어땠을까 하는 아쉬움은 항상 있는 것 같다.
함께 대회준비를 열심히 하였고 대회에서도 역할을 잘 해준 holywater2, invrtd-h 에게 고마운 마음이다.
D. Folding Sticks
\( N \) 개의 segment가 이어진 스틱이 있을 때, 특정 조건을 만족하며 스틱을 접어 일자로 이루어진 segment 최대 합의 최소를 구하는 문제이다.
길이에 대한 prefix sum을 구해준다. 접을 수 있는 관절들에 대해 왼쪽에서 오른쪽으로 numbering을 해주고 이 관절을 접었을 때의 최소 maximum 길이를 구해줄 것이다.
처음으로 관찰해야 하는 점은 문제에 제시된대로 관절을 접기 위해서는 왼쪽에서 오른쪽으로 가며 길이가 증가 함수 형태를 띈다는 점이다 (마지막 짜투리는 상관없다.) 현재 접을 관절을 i번째라고 했을 때, i와 가장 가까우며 그 곳을 접었을 때 i도 접을 수 있는 (j를 접었을 때 최대 길이보다 j - i 사이의 길이가 더 길거나 같음) j를 구할 수 있다면 (j < i) 우리는 i를 접었을 때의 최소 최대 길이를 구할 수 있다.
대회에서는 이상한 그리디 특성을 가정해서 온갖 방법을 다 사용하다가 지나가는 팀원의 말에 priority queue를 이용해 문제를 풀었다. (O(N log N)으로 풀었지만 O(N)도 가능하다.)
I. Palindrome Type
\( N \) 길이의 문자열에서 최대 문자 3개를 지워 펠린드롬을 만들 수 있는지를 묻는 문제다 (가능한 방법이 여러가지라면 지우는 문자의 최소 개수를 리턴.)
현재의 오른쪽 문자가 s_i, 왼쪽 문자가 s_j라고 했을 때 s_i와 s_j가 같다면 i + 1, j - 1을 검사해준다. 만약 다르다면 i를 옮기거나 j를 옮겨주고 검사한다. 최대 지울 수 있는 문자의 개수가 3개기 때문에 depth가 3밖에 되지 않아 이를 고려하여 불가능한 branch를 끊어주고 재귀적으로 탐색해주면 된다.
K. Shuffle Game
문자열 \( A \), \( B \), \( C \)가 있을 때, \( B \), \( C \)를 순차적으로 잘 조합하여 \( A \)와의 LCS를 구하는 문제이다.
3차원 배열을 사용해서 풀 수 있다. 혹시나 메모리가 터지면 어떡하지라는 마음에 2차원으로 만들어서 풀었다.
E, F, J는 팀원들이 쓱싹했다.
마지막 L을 시도하다 끝이 나버렸다.
'이것저것' 카테고리의 다른 글
| 2022년 마지막 날 (0) | 2023.01.01 |
|---|---|
| 오늘의 일기 (0) | 2022.12.25 |
| '22 상반기? 기록 (0) | 2022.06.01 |
| 어제오늘 (0) | 2022.03.21 |
| ['22.03.03 - '22.03.07] 제주 (1) | 2022.03.15 |
댓글