2022 ICPC 이야기

작성일 | In

요약

  1. ICPC 서울 리저널 5등, 대학 3등!
  2. 높은 확률로 월드 파이널 진출
  3. 드디어 무관 탈출 ㅠㅠ
  4. 중요한 건 꺾이지 않는 마음
  5. 응원해 주신 모든 분들 감사합니다.

문제 푸는 과정은 글로 쓰면 너무 지루하고 궁금한 분들도 별로 없을 것 같아서, 문제와 관련 없는 이런저런 이야기나 해보려고 합니다.

팀

팀 결성

2020년과 2021년에 엄청난 퍼포먼스를 보여줬던 181920(LongestPathToWF)의 팀원 중 한 명이 졸업을 하면서 팀이 깨졌습니다. 저는 남은 두 명(edenooo, kyo20111)과 함께 ICPC에 참가하는 상상을 했지만 kyo20111이 휴학을 해서 팀원을 한 명 더 구해야 하는 상황이었습니다.
먼저 작년에 저와 함께 ICPC에 참가했던 팀원 두 분께 연락을 드렸지만 이런저런 이유로 바쁘셔서 ICPC는 하기 힘들 것 같다고 하셨습니다. 결국 합을 맞춰보지 않은 사람들과 팀을 짜야 하는 상황이 왔습니다.

edenooo와 제가 각각 코드포스 레드와 오렌지이기 때문에 최소한 퍼플 이상인 팀원을 찾아보기로 했고, 실력이 퍼플 정도 되는 22학번 새내기 2명을 찾았습니다. 많은 고민을 한끝에, 작년에 제가 잠깐 (무상으로) 가르쳤던 chansol과 함께 참가하기로 했습니다. 팀워크가 중요하기 때문에 더 잘 알고 있는 후배를 선택했습니다.

팀명

고등학교 입학 이후로 팀 이름을 정해야 하는 일은 매년 한 번씩은 꼭 있었지만 아직도 너무 어렵습니다. UCPC는 팀 채팅방에서 주고받은 대화 내용 일부를 발췌해서 정했습니다. 팀 이름은 우리 팀 이름 머함, 팀원 닉네임은 각각 진짜 이걸로 해요?, ㅇㅇ, 팀원 이름 추천 받음으로 정했습니다.

ICPC는 UCPC처럼 이상한 이름으로 나갈 수 없기 때문에 다시 고민을 해야 됐습니다. 일단 다른 채팅방에서 이름을 추천받았는데 좋은 아이디어가 나오지 않았습니다.

  • huidak (나정휘 닥치라는 뜻)
  • choi soongsil (최고 숭실이라는 뜻)

결국 팀원들끼리 팀명을 정해야 하는 상황이었고, 다양한 아이디어가 나왔지만 결국 NLP로 결정했습니다. 팀원 3명의 성(나, 이, 박)을 따서 만들었습니다.
작년 AC-Complete 처럼 전산학과 관련된 이름으로 하고 싶어서 Traveling SCCC President 같은 것도 생각했었는데, 전산학과 관련 있으면서 훨씬 깔끔한 이름이 나와서 만족스러웠습니다.

경쟁 상대

ICPC 서울 리저널 수상, 더 나아가 월드 파이널에 진출하기 위해서는 다른 학교 팀들과 경쟁을 해야 합니다. ICPC 서울 리저널은 대부분 서울대학교와 카이스트가 대학 1/2위를 두고 경쟁하고, 다른 학교들이 3등 티켓을 두고 경쟁하는 형태입니다. 올해는 코드포스 레드와 IOI 국가대표 출신이 있는 고려대학교 LaSt Chance, 코드포스 레드와 계절학교 계속반 출신이 있는 한양대학교 OReO, 그리고 코드포스 레드와 BOJ 5등이 있는 숭실대학교 NLP가 3등 티켓을 두고 박 터지게 싸울 것으로 예상했습니다.

평소 대회 성적은 고려대학교와 한양대학교 구성원들이 우리 팀보다 훨씬 좋았기 때문에, 운이 좋거나 문제 셋을 잘 만나야 이길 수 있다고 생각했습니다. 또한 두 팀의 강점이 서로 다르기 때문에 두 팀 모두 이기는 것은 매우 어려워 보였습니다. 따라서 월드 파이널 진출 생각은 접어두고 팀 기준 14등 안에 들어서 수상하는 것을 목표로 준비했습니다.

UCPC 예선

대회

UCPC 예선은 10문제로 구성되어 있고 쉬운 문제 2~3개가 앞쪽에 배치되어 있습니다. 따라서 구현이 빠른 제가 ABCD를 잡고 edenooo가 EFG, chansol이 HIJ를 잡기로 했습니다.

저는 대회 시작하고 36분 동안 ABDF 4문제를 해결한 이후로 아무것도 못했습니다. 다행히 edenooo가 CEG, chansol이 J를 해결해서 17등으로 본선에 진출했습니다. 8문제를 해결한 팀 중에는 패널티가 가장 적었습니다.

H를 못 푼 것이 굉장히 아쉬웠습니다. 경쟁 상대로 생각했던 고려대학교 팀과 한양대학교 팀은 모두 H까지 9문제를 해결해서 각각 16등과 10등을 차지했습니다. 그래도 핵심적인 관찰은 한 상태였기 때문에 사실상 풀었다고 정신 승리를 하며 본선을 기약했습니다.

여담으로, 저는 작년 UCPC 예선과 UCPC 본선에 이어 3번 연속으로 17등을 차지했습니다.

UCPC 본선

대회

예선과 동일하게 제가 ABCD, edenooo EFGH, chansol이 HIJK를 잡았습니다. 앞쪽에 쉬운 문제가 많을 줄 알았지만 전부 어려운 문제였습니다. 문제를 읽으면서 숨이 턱턱 막히는 느낌이 들었고, 내색은 하지 않았지만 오늘은 쉽지 않을 거라는 예감이 들었습니다.

제가 DJL, edenooo가 H, chansol이 K를 해결해서 21등을 기록했습니다. 이번에도 푼 문제 수가 같은 팀 중에서는 패널티가 가장 적었습니다.

F와 I 모두 아쉬운 점이 많았습니다.
F는 $O(N \log^2 N)$ 풀이를 작성했고 시간 초과를 받았었는데, 이때 $O(N \log N)$ 풀이를 생각하지 않고 상수 커팅을 시도한 것이 잘못된 선택이었던 것 같습니다.
I는 쉬운 문제인데 너무 늦게 읽은 것이 가장 큰 문제였고, 그 외에도 시간이 부족해서 문제를 대충 읽고 너무 급하게 코딩한 점이 안 좋게 작용했습니다. 두 문제 모두 풀어야 하는 문제였는데 못 풀어서 아쉬웠습니다.

뒷풀이

대회가 끝나고 16명을 모아서 링고에 갔고, 이후 3명이 더 와서 총 19명이 링고에 모이게 되었습니다. 다 같이 노란 티셔츠 입고 수상 판넬(?)을 들고 가는 모습이 굉장히 우스꽝스러웠을 것 같습니다… 제가 앉은 테이블에서는 4명 중 3명이 술을 못 마셔서 맥주 1잔과 오렌지 주스 5잔을 시키는 어이없는 일도 있었습니다.
19명 중 5명만 초면인 걸 보면 실력을 키우는 것보다 친목질에 더 많은 노력을 쏟은 것 같습니다. 반성하고 열심히 공부하겠습니다.

중간 리뷰

최근에 문제를 많이 안 풀어서 구현 속도가 예전만큼 안 나왔고, 어려운 문제를 많이 안 풀어서 그런지 풀이를 고민하는 능력도 많이 떨어졌습니다. UCPC 이후로 푸는 문제의 난이도를 조금 올리고, BOJ Open Contest에 꾸준히 참가하면서 대회 감각도 끌어올리기 위해 노력했습니다.

팀 연습을 한 번도 안 해서 팀워크가 잘 안 맞았던 것도 UCPC의 실패 요인 중 하나인 것 같습니다. ICPC 전까지는 팀 연습도 열심히 하자고 다짐했습니다. 하지만 놀랍게도 2달 동안 팀 연습을 단 한 번도 하지 않은 채로 ICPC 예선에 참가했습니다. 그래도 UCPC 이후로 각자 정말 열심히 공부했고, 대회 전에 팀 전략에 대해 어느 정도 의논하고 대회에 참가했습니다.

ICPC 예선

대회

ICPC 예선은 가장 쉬운 4문제 정도만 한글 지문을 제공해 줍니다. 따라서 먼저 한글 문제를 모두 해결하고, 그 이후에 남은 문제를 적절히 분배하기로 했습니다.

대회 초반 1시간 동안 한글 문제 4문제(ACEK)와 쉬운 영어 문제 2문제(FG)를 해결했습니다.

쉬운 문제는 다 푼 것 같아서 남은 문제인 BDHIJ를 하나씩 살펴봤습니다. B는 읽기 싫은 문제, D는 머리를 많이 써야 할 것 같은 문제, I는 어려워 보이는 문제, J는 쉬워 보이는 문제였습니다. H는 2일 전에 우연히 봤던 논문이 그대로 문제로 출제되었고, 논문 초록만 읽고 본문을 읽지 않은 2일 전의 저를 원망하면서 그대로 버렸습니다. 하위 호환인 문제(BOJ 17172)가 solvedac에서 루비 4이기 때문에 절대 풀 수 없는 문제라고 생각했습니다.

J가 그나마 쉬워 보여서 J를 잡았습니다. 제한이 70000인 것을 보고 구린 냄새가 났지만… 오히려 구린 냄새가 날 법한 방법을 중점적으로 생각해서 풀이를 빠르게 찾을 수 있었습니다. 구현은 간단했고, J에서 AC를 받아서 4등으로 올라갔습니다.

H는 못 푸는 문제라는 것을 깨닫자마자 버렸고 J를 풀었기 때문에, 이제 BDI만 남아있는 상황이었습니다. edenooo는 B, chansol은 D, 저는 I를 잡기로 했습니다.

I는 많이 어려운 문제인 것 같고 해결한 팀도 없어서 버리기로 했습니다. 이후 edenooo가 B 풀이를 발견해서 코딩을 시작했고, 저는 chansol과 함께 D 풀이를 고민했습니다. 하지만 대회가 종료될 때까지 B 코드가 완성되지 않았고 D 풀이도 나오지 않으면서 7솔브로 종료했습니다. 이번에는 해결한 문제 수가 같은 팀 중에서 패널티가 2번째로 작았습니다.

쉬운 문제를 빨리 풀고 J도 늦지 않게 해결한 점이 좋게 작용해서 프리즈 5등, 최종 8등이라는 높은 순위를 기록했습니다. D가 얼마 전 코드포스 기출이라서 몇몇 팀들이 날로 먹은 것을 감안하면 매우 좋은 결과라고 생각합니다. UCPC와 다르게 크게 반성할 점은 없는 것 같았습니다.

교내 IT 대학생 프로그래밍 경진대회

숭실대학교는 ICPC 예선으로 교내 프로그래밍 경진대회 등수를 매깁니다. 올해 재학생들 중에는 적수가 없다고 생각해서 별로 신경을 쓰지 않고 있었지만, 상금(장학금)을 목적으로 팀을 만든 휴학생 팀이 등장하면서 분위기가 바뀌었습니다.
코드포스 레드/SCPC 2등상 수상자인 kyo20111이 JangHakGeumNyam(장학금냠)이라는 팀명으로 참전한다는 소식을 듣고, 절대 지면 안 된다는 생각에 필사적으로 문제를 풀었습니다. 결국 이기긴 했지만 J를 풀기 전까지 패널티 1x 차이로 뒤처진 상태였기 때문에 많이 무서웠습니다. 덕분에 문제를 열심히 풀어서 좋은 경쟁이 되었다고 생각합니다.

뒷풀이

오랜만에 오프라인으로 인터넷 예선이 진행되었기 때문에 SCCC 부원들끼리 모여서 회식을 했습니다.

행복 회로

전체 14등 정도에 걸치면서 대학 순위 4~5등 정도가 될 거라고 예상했었는데, 전체 8등 대학 3등이라는 예상치 못한 결과가 나왔습니다. 고려대학교와 한양대학교 팀을 모두 이길 수 없을 것이라 예상했지만 어쩌다 보니 두 팀을 모두 이겼습니다. 또한 성균관대학교와 유니스트 팀도 생각보다는 강하다는 것을 깨달았습니다.

본선에서 받게 될 대학 순위의 하한이 내려가고 상한이 올라간 기분입니다. 예선 결과가 나오기 전까지는 4~5등을 예상했었는데, 이번 결과를 보니 3등도 가능하고 8등도 가능할 것 같아서 마음이 심란합니다. 월드 파이널을 노려볼 수 있다는 행복 회로가 돌아가면서도 동시에 수상조차 못할 수도 있다는 생각이 듭니다.

팀 연습 / 개인 연습

예선을 치르면서 리저널 대회 수상과 월드 파이널 진출 모두 충분히 할 수 있는 일이라는 생각이 들었습니다. 가능성을 조금이라도 높이기 위해서 지금껏 단 한 번도 진행하지 않았던 팀 연습을 대회 2주 전부터 열심히 했고, 팀 연습이 없는 날에는 혼자 대회 기출을 풀어보며 연습했습니다.

  • 11/07 18:00 ~ 21:00, 2021 BAPC
  • 11/11 15:00 ~ 18:00, 2020 GCPC
  • 11/13 10:00 ~ 15:00, 2021 SWERC
  • 11/14 18:00 ~ 21:00, 2022 BAPC
  • 11/15 23:30 ~ 26:30, 2022 경북대 교내 대회 (개인)
  • 11/16 10:30 ~ 13:30, 2022 BAPC 예선 (개인)
  • 11/17 17:00 ~ 21:00, 2022 NCPC
  • 11/18 15:30 ~ 17:00, ICPC Seoul Regional 예비 소집
  • 11/19 10:00 ~ 15:00, ICPC Seoul Regional Contest

다른 팀에 비해 연습을 많이 한 건 아니지만, 그래도 짧은 시간 동안 최선을 다했다고 생각합니다. 팀 연습 결과가 예상보다 좋아서 본선에 대한 기대치가 점점 올라가다 보니 어느새 우리 팀의 목표는 월드 파이널이 되었습니다.

팀 연습을 하면서 어느 정도 대회 진행에 대한 감을 잡았습니다. 2017 서울 리저널의 MolaMola 팀처럼 엄격한 대회 전략을 세운 건 아니지만, 어떤 상황에서 어떤 행동을 하는 것이 좋은지는 대충 깨달은 것 같았습니다.
또한 팀워크가 생각보다 아주 좋다는 것도 깨달았습니다. 저와 edenooo가 주로 활동하는 온라인 저지가 다르기 때문에 서로의 단점을 잘 커버할 수 있습니다. chansol은 다른 두 명에 비해 문제를 많이 안 풀었지만, 이런저런 코딩을 많이 해본 경험을 바탕으로 코딩 큐(queue)가 비었을 때 스트레스 테스트 등을 구현해서 문제를 푸는데 많은 도움을 주었습니다.

한 가지 불안한 점은, 팀 연습을 모두 쉬운 대회로 3시간만 했기 때문에 어려운 문제가 많은 5시간 셋에 익숙하지 않다는 점이었습니다. 일정 레벨 이하의 문제를 3시간 안에 전부 풀어내는 연습은 많이 했지만, 어려운 문제가 많이 있을 때 상대적으로 쉬운 문제를 찾아서 공략하는 연습을 하지 않았습니다. 서울 리저널은 보통 P4 이하 문제를 3~4개밖에 출제하지 않기 때문에 이 점이 많이 걱정되었습니다.

ICPC 본선

예비 소집

대회 당일에는 대회 본부에서 점심과 저녁 식사를 제공하지만 예비 소집은 식사가 제공되지 않습니다. 대신 학교 차원에서(!!) 식사비를 지원해 주셨습니다. 점심은 대회 장소인 킨텍스 주변에서 돈까스를 먹었고, 저녁은 VIPS에서 플렉스를 했습니다. 제 돈이 아니라 그런지 더욱 맛있게 느껴졌습니다.
팀원 3명 모두 식사를 자주 거르는 편인데 학교에서 식사비를 지원해 준 덕분에 든든하게 배를 채웠고, 3끼를 모두 먹은 스노우볼은 대회 본선 당일까지 굴러갔습니다. 정말 감사합니다.

대회 당일 아침

전날 10시 30분에 자기 시작했지만 새벽 2시에 깨서 다시 잠들지 못했습니다. 이대로 대회를 치면 대회 도중에 자는 대참사가 벌어질 수 있기 때문에 킨텍스까지 가는 동안(약 30분) 차에서 잤습니다. 7시 30분쯤 도착했고 대회 등록은 8시부터 진행되기 때문에, 주차장에서 30분 정도 더 잤습니다. 대회 도중에 각성 상태가 되는 것을 고려하면 이 정도로 충분하다고 생각했고, 실제로 시상식이 끝날 때까지 멀쩡했습니다.

ICPC 본선

대회장 앞에는 풍선들이 여러 개 배치되어 있고, 준비된 풍선의 개수를 통해 문제의 대략적인 난이도를 유추할 수 있습니다. G와 H번 문제를 나타내는 풍선의 개수가 매우 적었고 JKL번 문제의 풍선이 매우 많았기 때문에, 구현이 가장 빠른 제가 대회 시작과 동시에 IJKL번 문제를 보기로 했습니다.

제가 문제를 읽는 동안 chansol은 IDE(CLion) 세팅을 하고 컴퓨터를 제가 앉은 오른쪽으로 넘겨주었습니다. 컴퓨터가 중앙에 있는 것보다는 한쪽으로 치워두는 것이 좋을 것 같다고 판단했습니다.

K는 간단한 3차원 DP문제라서 빠르게 (무려 First Solve!) 풀었습니다. I는 아무리 봐도 쉬운 문제 같은데 풀이가 바로 떠오르지 않아서 edenooo에게 쉽다고 거짓말하고(…) 넘겼습니다. 다행히 edenooo가 빠르게 풀었고, 이어서 제가 J를 풀었습니다.

이어서 chansol이 E, edenooo가 F, 제가 L을 잡았고, 저를 제외한 다른 두 팀원이 각각 문제를 해결해서 5솔브로 올라왔습니다. 저도 L 풀이를 제출했지만 WA를 받아서 잠시 멈췄습니다.

edenooo는 E를 풀자마자 D로 넘어갔고, 저는 edenooo가 D 풀이를 떠올리고 코딩하는 동안 C의 풀이를 발견하고 구현 디테일을 고민하면서 손코딩을 했습니다. 그 시간 동안 chansol은 제 L 풀이를 보며 반례를 찾고 있었습니다. 잠시 후 edenooo가 D를 빠르게 해결하고 chansol에게 합류해서 같이 L 반례를 찾고 있었습니다.

C는 귀찮고 실수할 여지가 많은 기하 문제라서 천천히 코딩을 했습니다. 약간의 오타가 있었지만 빠르게 고쳐서 한 번에 AC를 받았습니다. 제가 C를 열심히 짜는 동안 다른 두 팀원이 L의 반례를 찾았고, 제가 C를 푼 직후에 바로 L을 새로 구현해서 맞았습니다.

여기까지 왔을 때 이미 월드 파이널을 확정 지은 상황이었지만, 대회 당시에는 아래에 있는 팀(특히 포스텍 000102팀)이 한 문제를 더 풀어서 올라갈 수 있다는 불안감 때문에 팀원 3명이 다 함께 A를 보았습니다. 얼마 지나지 않아서 edenooo가 A 풀이를 발견했고, 풀이를 그대로 받아서 제가 구현하기 시작했습니다.

열심히 구현해서 제출했지만 3번이나 틀렸고, 팀원 3명이 함께 1시간 동안 디버깅을 했지만 틀린 부분을 찾지 못했습니다. 결국 최후의 수단으로 edenooo가 처음부터 다시 짜기 시작했고, 잠시 후 짧은 환호와 함께 AC를 받았습니다. 대회 종료 46분 전이었습니다.

다른 팀들의 진행 상황을 보면서 패널티를 계산한 결과 이 시간 이후로 아무것도 안 해도 월드 파이널에 진출한다는 결론이 나왔고, 남은 시간 동안은 잡담을 하고 간식을 먹으며 놀았습니다.

그리고 블러핑을 하기 위해 대회 종료 15분 전과 13분 전에 각각 한 번씩 H에 제출했습니다. 이 블러핑의 효과가 좋았던 건지, 다른 팀들이 우리 팀의 성적을 정확하게 예측하지 못했습니다. 실제로는 9문제를 풀었지만 운영진 측의 실수가 있었는지 풍선은 8개만 왔고 스코어보드에서는 10문제를 푼 것처럼 보여서 여러 팀이 혼란에 빠졌던 것 같습니다. 그걸 보는 우리 팀원들은 조용히 웃고 있었고요.

결과 발표

최선의 상황과 최악의 상황을 모두 가정해도 리저널 5등, 대학 기준 3등이라는 결과는 바뀌지 않기 때문에 결과 발표는 긴장감 없이 보았습니다. 9문제를 푼 팀이 예상했던 것보다 많이 적었고, B와 G는 보자마자 버리길 잘했다는 생각이 들었습니다.

서울대 6팀과 카이스트 5팀 중 각각 1팀씩만 이기는 것을 목표로 잡았었는데, 서울대 3팀과 카이스트 1팀을 제외한 모든 팀을 이겼습니다. 예상했던 것보다 훨씬 높은 등수이고, 지금까지 했던 모든 팀 연습들보다 훨씬 더 잘 풀어서 정말 기쁩니다. 대회 끝나고 이렇게 후련한 적은 2년 전 브랜디 대회 이후로 처음입니다.

경쟁 상대라고 생각했던 팀들은 모두 많이 말린 것 같았고, 오히려 고려대학교와 한양대학교 안에서 2등할 것이라고 예상했던 팀들의 순위가 더욱 높았습니다. 포스텍 팀은 UCPC와 ICPC 예선에서 눈에 띄지 않았는데 이번 대회 성적이 매우 좋아서 놀랐습니다.

수상하신 분들 모두 축하합니다!

뒷풀이

대회에 함께 참가한 계절학교 친구들, 대회 스태프로 참가하신 분들, 그리고 그냥 놀러오신 분들까지 총 14명이 합정에서 만났습니다. 고기를 먹고 카페에 가서 실컷 떠들었습니다.

잡다한 이야기

쉬운 대회 기출로 3시간씩 연습했던 것이 오히려 큰 도움이 되었습니다. 이번에는 예년과 다르게 쉬운 문제의 비중이 높았고, 쉬운 문제를 빠르게 푸는 연습을 정말 많이 한 덕분에 패널티를 많이 줄일 수 있었습니다. 다른 팀들이 우리 팀을 이기기 위해서는 문제 수로 이겨야 하기 때문에, 성급하게 문제를 풀어서 많이 말렸다는 이야기를 들었습니다. 운이 좋았다고 생각합니다.

대회 끝나기 직전에 H에 제출한 코드는 다음과 같습니다. 대회가 끝나고 대회 채점 데이터를 공개할 때 비밀번호가 꺾2지않는마음. (RjR2wldksgsmsakdma.) 인 것을 보면서 많이 웃었습니다.

1
2
3
4
5
#include <iostream>

int main(){
    std::cout << "중요한 건 꺾이지 않는 마음\n";
}

저를 포함한 많은 사람들이 고려대학교가 월드 파이널에 진출할 것이라고 생각했지만 결국에는 숭실대학교가 월드 파이널에 진출했습니다. 대회는 이런 맛에 하는 것 같습니다.
중요한 건 꺾2지 않는 마음

마무리

지금까지 BOJ 랭커, solvedac 랭커, 네임드 블로그 등 인지도에 비해 수상 실적이 빈약해서 항상 부담감이 있었습니다. 물로켓 그 자체였던 브랜디 대회 1등과 아직은 대회 운영이 많이 미숙한 현대 모비스 대회를 제외하면 유의미한 실적은 KOI 1차 금상과 2차 동상밖에 없었습니다. 친구들이 무관 귀신이 붙었냐고 할 정도로 수상과는 인연이 없었습니다.

BOJ 랭킹만큼 쓸모없는 것도 없다는 것을 알기 때문에 대회 수상을 위해 정말 열심히 공부했습니다. 여름에 SCPC와 UCPC를 망치면서 많이 좌절했지만 ICPC 예선에서 8등을 하며 희망을 보았고, 이번에 리저널에서 은상을 받으면서 지난 5년간 열심히 공부한 것에 대한 보상을 받은 기분입니다.

대학 3등인 만큼 높은 확률로 월드 파이널에 진출하게 될 텐데, 열심히 준비해서 좋은 결과를 받을 수 있도록 노력하겠습니다.

응원해 주신 분들, 그리고 축하해 주신 분들 모두 정말 감사드립니다.