[요약] ICPC 전략 가이드

https://people.cs.uchicago.edu/~borja/pubs/sigcse2016-programming-contests.pdf

sigcse2016-programming-contests.pdf

0.74MB

 

 

이 글은 Aaron Bloomfield와 Borja Sotomayor의 "A Programming Contest Strategy Guide"를 읽고 한국어로 요약한 내용입니다. 핵심을 간단하게 전달하기 위해 필자의 해석이 담겨 원문과 다른 내용이 있을 수 있습니다. 

세줄 요약

저자는 북미 대학 ICPC 코치들이다. 1999년 이후로 한 번도 북미 출신 대학이 우승 못하고 항상 러시아 / 중국 / 폴란드만 우승한다는 사실에 안타까움을 금치 못한다. 따라서 "어떤 팀들이 ICPC에서 활약하는가"를 자신들의 월드파이널(줄여서 월파) 코치 경험을 통해 사례 기반 연구하여 발표한다.

 

본문

잘하는 팀들의 공통점
1. 실제환경과 유사한 5시간 & 1PC 기반 연습을 최대한 많이 돌렸다
2. 다른 팀들을 모집해서 함께 연습을 돌렸다.  
3. 연습이 끝난 직후 팀(들)이서 반드시  Problem Discussion 세션을 가졌다. 이때 Offical Solution을 보는 것도 좋았다. 없다면 코치/고수의 도움을 받는 것은 항상 실력 향상에 도움이 된다.

팀노트
팀노트는 모르는 알고리즘을 배우고 쓰기 위한 용도가 아닌, 이미 사용해본 적 있는 알고리즘의 구현을 헷갈리지 않고, 더 빠르고 정확하게 구현하기 위한 것이다. 이러한 알고리즘의 존재는 연습을 통해서만 알 수 있다.

 

코치 문화
ICPC 문화가 유지되기 위해서는 졸업한 이후에라도 후배들에게 코치 역할을 자처하는 것이 좋고, 반대로 학부생들도 (꼭 icpc 출신이 아니더라도) 졸업생들에게 적극적으로 도움을 요청하는 것이 중요하다. 직접적으로 문제 풀이에 도움을 주는 것이 아니더라도, 팀의 연습 일정을 정하고, Discuss Session, 팀노트 구성에 도움을 줄 수 있는 사람이 있는 것은 중요하다. (이와 같은 연습-이외의 업무도 일주일에 1시간 정도 투자할 필요가 있는 것으로 파악됨. -> 알맞은 난이도의 문제 셋을 고르고, 여러 팀들을 모으고 등)

대회 전략
5시간 대회는 보통 4단계로 구성된다.
오프닝: 몇 분 안에 가장 쉬운 한 문제를 찾고, 가장 코딩이 빠른 사람이 이를 푸는 것.
초반: 나머지 두 명 또는 한 명은 문제의 난이도와 카테고리를 구별하기 위해 남은 '모든 문제'를 읽는다. 그 사이 발견된 쉬운 문제들을 누군가 코딩한다.
중반: 쉬운 문제들은 얼추 풀렸고, 구현이 어려운 문제들을 푼다.
엔드게임: 이 때는 체력적으로도 지친 상태이기 때문에 어려운 문제를 붙잡는 것이 아니라, 지금까지 푼 문제 중 풀릴듯말듯 한 문제들을 끝까지 붙잡고 풀어내는 것이 이길 확률을 높여준다.

이 전략은 일반론적인 전략이며, 문제 셋의 난이도에 따라 달라질 수 있다.

팀 전략
초기 icpc 대회까지는 3명이 개인 플레이를 해도 어느 정도 좋은 성과를 낼 수 있었지만, 대회 문제의 난이도가 상향 평준화됨에 따라 팀 전략의 중요성이 매우 커졌다. 

다양한 팀 전략이 존재할 수 있으나, 실제 대회 전에 반드시 명확하게 구축되어야 한다.
예시)
한 사람은 계속 문제를 읽고 생각하며, 필요시 pseudo-code를 짠다. 다른 두 사람은 pair-programming하는 것. 그리고 이를 rotate하여, 한 사람만 계속 생각하는 일은 없도록 한다.
장점: 코드의 에러가 현격히 적어진다.
단점: 한 순간에 최대 2개의 문제만을 볼 수 있다.

ex)각자 서로 다른 문제를 보는 전략
장점: 문제가 쉬울 때 1.5배 효율적이다.
단점: 문제가 어려울 경우 각기 흩어져서 결국 아무 문제도 못 푸는 경우가 많다.

친밀도
팀이 모두 best-friend가 될 필요는 없는데, 적어도, 쉽게 말해 서로를 기분 상하지 않게 깔 수 (비판할 수) 있는 정도로는 친해져야 한다.

팀 내에서의 역할
ex) 코더(구현 담당), 알고리스트(이론 담당), 디버거(코드의 오류를 찾는 사람)
ex) Specialist: 기하 담당, 플로우 담당, dp 담당.
ex) 대회 초반까지는, 각자 쉬운 문제를 맡아 풀고 대회 중반부터는 문제의 성격에 따라 Specialist 전략으로 각자 잘하는 문제를 받아 풀기.

Tunnel Vision을 피하기
정말 많은 팀들에서 만약 어떤 문제에 굉장히 많은 '맞왜틀'이 나온다면 이 코드가 정답에 근접했다는 생각에 그 코드를 놓치 못하고 팀을 망가트린다. 이는 굉장히 common 사례이며, 대부분 정답에 근접하지 못한 경우가 많고 팀의 페널티와 더불어 다른 팀원을 방해한다. 따라서 이 경우, 역시 상황마다 다르겠지만, 일반적으로 '5번'의 틀린 제출이 있을 경우 그 코드를 프린트하여 offline-debugging하는 것을 제안한다. 물론 이는 팀의 수준에 따라서 그 횟수는 달라질 것이다.

 

여기까지가 요약이며, 더 자세한 내용을 원하는 분들은 위의 원문을 참조해주세요.

---

더 읽으면 좋은 글

모범사례
포스텍 팀의 2024 월드파이널 진출 https://leo630.tistory.com/213
실제로 위에 나온 내용들을 거의 다 지키는 모습을 볼 수 있음.
ex) 무한 팀연습, 단체 팀연습, 서로 친함.

 

https://cheet0se.tistory.com/15

"스테이플러를 이용하여 문제지 관리하고 서브라임 텍스트에서 코드를 바로 프린트할 수 있는 extension을 다운"

이외에도 구글에 "ICPC 후기"라고 검색해서 다양한 팀들의 이야기와 꿀팁을 들을 수 있다.

 

팀 전략 구성

https://justicehui.github.io/etc/2023/05/30/icpc-preparation/

https://zigui.tistory.com/19

https://degwer.hatenablog.com/entry/20180422