티스토리 뷰

 

2022 ICPC Seoul Regional에 참가했습니다. 대략 올해 4월부터 11월까지 약 7~8개월 가량 준비한, 2022년에 제가 가장 오랜 기간 준비한 프로젝트입니다.

 

ICPC는 팀 대회입니다. 같은 대학교에 재학 중인 학생 3명이 함께 참가하는 대회입니다. 그런데 일부 대학들을 제외하면, ICPC를 제대로 준비하기란 쉽지 않습니다. 일단 팀원을 모으는 것부터가 어렵습니다. ICPC가 무엇인지를 아는 사람조차 많지 않다면 과장일까요? ICPC가 컴퓨터 과학 분야에서 가지는 가치나 권위를 생각해본다면 안타까운 일입니다.

 

사정은 제가 속한 전북대학교에서도 마찬가지였습니다. ICPC를 제대로 준비하던 사람이 없었고, 그래서 저는 아예 새로운 팀을 꾸려 0에서부터 시작하기로 했습니다. 동시에 다소 황당하게도 저는 ICPC 본선에서 수상하고 싶었습니다. 그래서 ICPC 본선 수상을 목표로 준비하기로 했습니다.

 

정리하자면 저는 대회 경험이 없는, 흔히 말하는 뉴비 팀을 꾸려 ICPC 본선에서 수상하고자 했습니다. 이 글은 그 과정과 결과를 담은 글입니다.

 

팀원 정하기

4월입니다. 팀원을 정해야 했습니다. 팀원 후보들을 정리하고, 우선순위가 높은 분들부터 컨택했습니다. 당시 전북대학교에는 저를 포함해서 ICPC 본선 수상권의 실력자가 없었습니다. 그에 근접하는 분들도 없었습니다. 따라서 어떤 분들과 팀을 하든, 오랜 기간 연습하고 실력을 높여야 했습니다. 이런 이유에서 현재의 실력이 아닌 잠재력에 따라 팀원 분들을 컨택했습니다. 감사하게도 가장 먼저 컨택한 두 분이 흔쾌히 팀원 제의를 수락해주셨습니다. 최인혁님, 이정현님과 함께하게 됐습니다.

 

배경지식 쌓기

당시 저희 팀은 ICPC 본선 수상을 위한 최소한의 배경 지식도 없었습니다. 가장 시급한 문제는 배경 지식을 쌓는 일이었습니다. 문제를 풀 최소한의 지식조차 없다면, 당연히 본선 수상을 할 수 없을 테니까요. 따라서 5~7월에는 배경 지식을 쌓는데 집중했습니다(7월 이후에도 꾸준히 배경 지식을 쌓았습니다).

 

유명한 kks227님의 블로그 커리큘럼을 중심으로 다양한 자료를 참고해가며 공부했습니다. 다익스트라 알고리즘부터 heavy-light decomposition에 이르기까지, 총 50여개의 알고리즘/자료구조를 공부했습니다. 참고로 50여개의 주제를 모두 처음 공부한 것은 아닙니다. 저 같은 경우는 절반 이상의 주제를 이전에 공부한 적이 있었지만, 1년 이상 알고리즘 공부를 쉬어 복습이 필요했습니다. 다른 팀원 분들은 처음 공부하는 주제가 많았습니다. 아무튼 상당히 어려운 과정이었는데, 모든 팀원 분들이 다 잘 따라와 주셨습니다. 후반에 가서는 오히려 제가 진도가 늦어졌습니다. 아래는 이 기간 동안 저희 팀이 공부한 알고리즘/자료구조 목록입니다.

 

공부한 알고리즘/자료구조 목록

 

한 가지 아쉬움이 남는 부분이 있습니다. 다양한 알고리즘/자료구조를 공부했지만, 아직도 공부하지 못한 주제가 많습니다. 그런 탓에 후술할 팀 연습에서 배경 지식 부족으로 풀지 못한 문제들이 많았습니다. 아래는 알고리즘 대회에 출제되지만 아직 저희 팀이 공부하지 못한 알고리즘/자료구조 모음입니다. 사실 처음 계획한 분량은 거의 다 공부했지만, 아래의 주제들이 알고리즘 대회에 출제된다는 사실을 잘 몰랐습니다. 알았더라면 무리해서라도 아래의 주제들까지 공부했을 것 같습니다.

 

아직 공부하지 못한 알고리즘/자료구조 목록

 

팀 연습

어느 정도 배경 지식과 감각이 쌓이고, 6월부터 본격적인 팀 연습을 시작했습니다. ICPC 예선 전까지는 주로 골플랜디(백준에서 골드, 플래티넘 문제들을 랜덤으로 골라 푸는 연습 방법)를 했습니다. 평균적으로 10문제 중 7~8문제를 푸는데 성공했습니다. 당시에는 무덤덤했는데, 저희 팀이 팀 결성 전까지 얼마나 부족했는가를 고려할 때 상당히 좋은 결과였던 것 같습니다.

 

ICPC 예선 이전 팀 연습 기록 일부

 

ICPC 예선 이후에는 주로 플랜디(백준에서 플래티넘 문제들을 랜덤으로 골라 푸는 연습 방법)를 했습니다. ICPC 2021 본선 기록으로 미루어 볼 때, 수상권에 들기 위해서는 정확히 플래티넘 문제들까지 모두 풀어야 한다고 예상했기 때문입니다. 당시 저희 팀은 골드 문제까지는 무난히 풀어냈기 때문에(간혹 골드 1 난이도의 문제를 놓치기는 했습니다), 승부처는 플래티넘 문제가 될 것이라고 판단했습니다.

 

구체적으로 5시간 동안 10개의 플래티넘 문제를 푸는 방식으로 연습했습니다. 평균적으로 10문제 중 6문제 정도 푸는데 성공했습니다. 딱 한 번 ICPC 본선 일주일 전에 진행한 팀 연습에서, 10문제를 모두 푸는데 성공해 크게 기뻐했던 기억이 납니다.

 

보통은 주로 ICPC 기출 문제로 팀 연습을 진행하는 것으로 알고 있습니다. 그러나 저희 팀은 ICPC 기출 문제보다는 플랜디를 위주로 연습했습니다. 그 이유는 효율성에 있습니다. ICPC 기출 문제로 연습하게 되면 5시간 동안 평균 3~5개의 플래티넘 문제를 접할 수 있습니다. 그러나 플랜디를 하게 되면 5시간 동안 10개의 플래티넘 문제를 접할 수 있습니다. 다른 실력 있는 팀들에 비해 알고리즘 문제를 푼 경험이 현저히 부족한 저희 팀에게는, ICPC 기출 문제보다 플랜디가 효율적이라고 판단했습니다.

 

ICPC 예선 이후 팀 연습 기록 일부

 

2학기 중간고사가 끝난 후부터는 일주일에 3번, 각 5시간 동안 팀 연습을 진행했습니다. 이 기간 동안 다들 연습을 따라가기 벅차했습니다. 특히 대학원 과제와 일정이 겹쳐버린 최인혁님 같은 경우 업솔빙(대회나 연습 등을 마친 후 문제를 복기하고 다시 푸는 과정)을 거의 못했습니다.

 

여러 번의 팀 연습을 거치며 팀 전략도 어느 정도 정했습니다. 대략적인 팀 전략은 아래와 같습니다.

 

대략적인 팀 전략

 

여름 방학 집중 공부

학기 중에는 신경 쓸 일들이 많습니다. 과제, 시험 공부.. 특히 최인혁님은 대학원 준비와 동아리 회장 업무까지 겹쳐 상당히 바빴습니다. 그래서 상대적으로 한가한 여름 방학 때 최대한 많이 공부하기로 했습니다. 구체적으로 평일에는 하루에 최소 8시간 30분 이상 공부하고, 이를 달성하지 못할 시 하루에 5000원의 벌금을 내기로 했습니다.

 

여름 방학 스터디 규칙

 

저는 사실 하루에 8시간 30분은 그리 많다고 생각하지 않습니다. 8시간 30분은 최소한의 기준이었습니다. 그러나 지치는 것은 어쩔 수 없었습니다. 8월 즈음부터는 다들 규칙을 잘 지키지 못했습니다.

 

벌금 기록 일부

 

또한 여름 방학 때는 대회 감각을 키우기 위해 코드포스, 앳코더 같은 온라인 대회에 참가했습니다. 당시 코드포스 기록을 살펴보니 제가 블루~퍼플 구간의 퍼포먼스를 냈었는데, 현재는 퍼플~오렌지 구간의 퍼포먼스를 내는 것을 보니 실력이 늘긴 했나 봅니다.

 

교수님과의 미팅

컴퓨터공학부의 정진홍 교수님께서 전체 과정 동안 코치 역할을 해주셨습니다. 대략 한 달에 한 번 정도 미팅을 가지면서, 저희 팀의 진행 과정과 앞으로의 방향에 대해 피드백을 주셨습니다. 'ICPC 예선 이후에는 플랜디에 집중하기'나, '7월까지 대부분의 배경 지식을 익히기' 등의 전략을 정하는데, 정진홍 교수님의 도움이 있었습니다.

 

예선 대회

ICPC 예선입니다. 결과부터 말하자면 전체 35등(교내 1등)을 차지했습니다. 저희 팀이 4월 전까지 얼마나 실력이 없었는가를 고려하면 좋은 성과지만, 목표가 ICPC 본선 수상이라는 점을 고려하면 부족한 성과입니다.

 

팀 2 3 5 8 14, 35등

 

저희 팀은 총 6문제를 풀었습니다. 하위 6문제까지는 무난한 골드 이하 문제라고 추측되는데, 7문제부터는 난이도가 급상승해서 좀 당황했습니다. 구체적인 대회 중 진행 상황은 다음과 같습니다.

 

  • 9분: A번이 간단한 구현 + 냅색 문제라는 것을 깨닫고 빠르게 코딩해 AC를 받았습니다.
  • 20분: E번이 간단한 그리디 + 이분 탐색 문제라는 것을 깨닫고 빠르게 코딩해서 제출했으나, 이분 탐색 구현 상에 문제가 있어 1번 틀린 후 AC를 받았습니다. 대회 중에 흥분해서 평소라면 하지 않았을 실수를 했던 것 같습니다.
  • 24분: 무난히 C번 문제를 풀었습니다.
  • 72분: 쉬운 문제로 보이는 F, G, K번 문제를 한동안 풀지 못해 조금 초조해하고 있었습니다. 그러던 중 K번이 dag에서 최단 경로를 찾는 문제라는 것을 깨닫고, 1번 틀린 후 AC를 받았습니다.
  • 101분: 2번을 틀린 끝에 F번을 풀었습니다. 언젠가 백준에서 F번과 유사한 그래프 문제를 본 적이 있어 쉽게 풀이를 떠올릴 수 있었습니다.
  • 115분: G번이 dp 문제라는 것을 진작에 깨달았으나, 구현에서 헤매다가 1번 틀렸습니다. 재귀로 짜면 TLE가 날 것 같아 비재귀로 짜느라 더욱 헤맸었는데, 결국 재귀 풀이로 AC를 받았습니다.
  • ~180분: 그 이후에는 D, J번 문제를 고민해 보았으나 마땅한 풀이를 찾을 수 없었습니다. 결국 J번의 $O(n^2)$ 나이브 풀이를 시도해보기로 했습니다. 다양한 커팅을 시도하면서 4번을 제출해 보았는데, 모두 TLE를 받았습니다. 대회가 끝난 후 다른 팀들의 후기를 들어보니, 실제로 잘 커팅하면 $O(n^2)$ 풀이도 통과된다고 합니다.

 

올해 전북대학교는 최초로 ICPC 본선에 3팀이 진출했습니다. 전북대학교의 알고리즘 실력이 어느 정도 올라왔다는 뜻일까요? 예선 대회 전까지 2팀은 진출할 수도 있겠다고 예상했었는데, 3팀이나 진출해서 좀 놀랐습니다.

 

여담으로 대회가 끝난 후 저는 업솔빙을 해야 한다고 주장했지만, 대회에 참가한 다른 팀들과 뒷풀이를 하러 갔습니다. 고기를 먹었는데 무려 40만원이 나왔습니다.

 

본선 대회

드디어 고대하던 본선 대회입니다. 결과부터 말하자면 총 5문제를 풀어 최종 36등으로 마무리했습니다. 사실 수상하기에는 저희 팀의 전력이 객관적으로 부족하다는 것을 알지만, 2n위는 노려볼 만하다고 생각했는데 아쉽습니다.

 

팀 2 3 5 8 14, 36등

 

구체적인 대회 중 진행 상황은 다음과 같습니다.

 

  • 16분: 스코어보드를 보고 J번 문제가 가장 쉽다는 사실을 확인했습니다. 풀이는 바로 알았지만, 코드를 짜는데 약간 버벅여 16분 만에 AC를 받았습니다.
  • 29분: I번 문제를 풀었습니다.
  • 49분: F번 문제를 풀었습니다. Jump할 필요가 없는 구간들을 하나로 합치는 연산을 구현하는 데 시간이 걸렸습니다.
  • 116분: 1번을 틀린 끝에 E번 문제를 풀었습니다. Source 노드와 destination 노드가 같은 노드인 코너 케이스에서 틀렸습니다.
  • 170분: 1번을 틀린 끝에 K번 문제를 풀었습니다. 단순한 3차원 dp 문제였는데 그 사실을 너무 늦게 알아차렸습니다. 근거 없는 가정에 기반한 풀이를 시도하다 1번 틀렸습니다.
  • ~300분: 남은 시간 동안 D, L번 문제를 수 차례 시도했었으나 풀지 못했습니다.

 

생각해 볼 만한 점이 두 가지 있습니다. 첫 번째로 연습 때는 플래티넘 난이도의 문제를 어느 정도 확률로 풀어낼 수 있었는데, 정작 대회 때는 플래티넘 난이도의 문제를 풀어낸 경우가 드물었습니다. ICPC 본선 뿐만 아니라 많은 대회에서 그랬습니다. 연습과 실전의 차이인지, 혹은 문제 유형의 차이인지 모르겠지만, 아무튼 앞으로 참가할 대회에서는 이 부분을 개선해야겠습니다. 두 번째로 문제의 세부적인 조건을 놓치는 경우가 많았습니다. 예를 들어 F번에서 interval들이 정렬된 상태로 주어진다는 것도 몰랐고, E번에서 outdegree가 최대 10이라는 것도 몰랐습니다. 그동안 지문 해석은 한 사람에게 맡겨왔는데, 교차 검증할 필요가 있는 것 같습니다.

 

여담으로 참가자 분들과 staff 분들 중 이 분야에서 유명하신 분들이 많았는데, 인사라도 건네고 싶었지만 그런 분위기가 아닌 것 같아 거의 하지 못했습니다.

 

마무리하며

7~8개월이라는 긴 시간 동안 함께 해준 최인혁님, 이정현님께 감사드립니다. 제 고집에 따라 다소 무리한 일정을 세운 것 같기도 한데, 두 분 모두 바쁜 와중에도 잘 소화해 주셨습니다.

 

아쉽게도 최인혁님은 올해를 마지막으로 졸업하겠지만, 이정현님이나 저는 그렇지 않습니다. 한 가지 희망적인 사실은, 저나 이정현님은 모두 실력이 가파르게 상승하는 중입니다. 충분히 오래 공부하여 실력이 어느 정도 수렴한 상태가 아닌, 아직까지 성장할 여지가 많이 남은 상태입니다. 이 추세라면 앞으로 있을 대회에서는 더 높은 성적을 기대해봐도 좋지 않을까요?

 

마지막으로 솔직한 얘기를 해보겠습니다. 저는 이 분야의 고수들을 동경합니다. 저 역시 그들과 같은 실력을 가지고 싶다는 강렬한 욕망이 있습니다. 이번 ICPC를 통해서 아직까지는 제가 그들과 같은 레벨에 오르지 못했다는 것을 여실히 깨달은 것 같습니다. 부족한 점들을 철저히 분석하여 개선해서, 하루 빨리 실력을 키우고 싶습니다.

 

여담으로

  • 저희 팀은 대회나 팀 연습 전에 루틴이 있습니다. 바로 UFC 정찬성 선수의 입장곡 'The Cranberries - Zombie'를 듣는 것인데요. 경기에 나서는 정찬성 선수처럼 비장하게 대회에 임하자는 다소 오글거리는 의미입니다.
  • 저희 팀은 팀 이름을 정하는데 많은 고민이 있었습니다. 다른 팀들의 원한을 살 수 있는 'Problem J is well-known DP', 요즘 가장 핫한 래퍼 NBA YoungBoy에서 영감을 받은 'JBNU YoungBoys'나 'JBNU Never Broke Again', 전 UFC 더블 챔피언 코너 맥그리거를 따라 지은 'Jeonju McGregor: The Notorious'나 'The Notorious Jeonju McGregor', 기타 'Code Gangsta', 'Farmer Takahashi and N Wagyu', 'Bibimbap Boys' 같은 팀 이름 후보들이 있었습니다. 최종적으로 피보나치 수에서 영감을 받은 '2 3 5 8 14'로 정했습니다.
  • 이정현님은 내년에 밴드를 한다고 합니다. 장발 록커, 내사랑 내곁에, 포스트 박완규, 한국의 리치 블랙모어, 21세기의 비틀즈 이정현 화이팅!
  • 저도 내년부터 (흑인음악의 열정적인 장르팬으로서) 프로듀싱을 배워보고 싶었는데, ICPC 결과를 보고 나니 그냥 전공에 집중해야 할 것 같습니다. 두 마리 토끼를 잡으려다 하나도 제대로 못 잡을 것 같아요.
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG
more
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함