ICPC 준비의 첫걸음: 공부 방법과 대회 전략

작성일 | In

서론


지난 5월 4일에 성균관대학교에서 강연했던 것을 정리한 글입니다. 다음과 같은 내용을 다룹니다.

  1. 어떤 문제를 푸는 대회인가?
  2. 어떤 것에 초점을 맞춰서 공부해야 하는가?
  3. 최근 기출 문제에서 등장하는 알고리즘
  4. 전공과목과 연계되는 내용
  5. 대회 전략과 팀 워크

목차

  • ICPC 대회 소개
    • 프로그래밍 대회란?
    • ICPC 소개
  • 필요한 능력과 훈련 방법
    • 배경지식
    • 문제 해결 능력
    • 구현 능력
  • 고수가 되는 방법
    • 문제를 푸는 방법
    • 잘해지는 방법
  • 최근 대회 분석
    • 2020 ~ 2022 ICPC 예선
    • 2018 ~ 2022 ICPC 본선
    • 수상을 노린다면…
  • 학교 전공과목과의 연계
  • 대회 전략과 팀 워크
    • 대회 전략의 필요성
    • 스코어보드 활용
    • 디버깅
    • 다른 팀원이 키보드를 잡고 있을 때
    • 키보드를 잡은 사람이 없을 때
    • 팀 전략의 분류
    • 실제 사례
    • 오프라인 대회장

ICPC 대회 소개

프로그래밍 대회란?

프로그래밍 경시대회는 주어진 시간 동안 주어진 문제를 최대한 많이 푸는 형식의 대회입니다. 대회마다 차이가 있지만 보통 개인 대회는 4~5시간 동안 3~4문제, 팀 대회는 3~5시간 동안 10~12문제를 풀어야 합니다. 다른 대회와 조금 다른 점은 실시간으로 모든 참가자의 점수를 알 수 있다는 것입니다. 대회 도중에 아래 사진과 같은 스코어보드가 제공되어서, 각 팀이 어떤 문제를 몇 번 시도해서 해결했는지 확인할 수 있습니다.

대회에는 주어진 상황을 직접 시뮬레이션하는 문제, 주어진 수식을 효율적으로 계산하는 문제, 경우의 수를 세는 문제, 조건을 만족하는 최대/최솟값을 찾는 최적화 문제 등 다양한 문제가 출제됩니다. Problem Solving에 대한 전반적인 내용은 글의 주제를 벗어나므로 ho94949님께서 제작하신 Problem solving 슬라이드(링크)를 참고하시길 바랍니다.

ICPC 소개

ICPC는 국제 결승의 역할을 하는 World Finals와 지역 예선의 역할을 하는 Regional Contest로 구성되어 있고, 한국 대학교 팀들은 주로 Asia Seoul Regional Contest에 참가합니다. 서울 지역 대회는 한국 대학생 프로그래밍 경시대회 본선을 겸하기 때문에 대통령상, 국무총리상, 장관상 등 높은 상들이 걸려있습니다.

대회는 3인 1팀으로 진행되며, 각 팀은 1대의 컴퓨터만 사용할 수 있습니다. 출제 범위가 정해져 있는 올림피아드(링크)와 다르게 ICPC는 출제 범위가 정해져 있지 않습니다. 따라서 각 팀은 25페이지 이내의 문서(팀 노트)를 자유롭게 제작해서 지참할 수 있습니다. 3명이 1대의 컴퓨터만 사용할 수 있다는 점과 팀 노트의 존재 때문에 대회 전략이 대회 성적에 많은 영향을 미칩니다.

서울 지역 대회에 대해 조금 더 자세하게 알아보면, 서울 지역 대회는 예선과 본선으로 구성되어 있습니다. 예선은 보통 10월에 개최되며 3시간 동안 10~12문제를 해결해야 합니다. 모든 팀은 지도 교수의 감독하에 예선을 응시해야 하고, 대부분의 학교는 모든 팀이 한 장소에 모여서 응시하는 것으로 알고 있습니다.

각 학교마다 예선 등록 팀 수의 절반 이하만 본선에 진출 가능하기 때문에 학교마다 본선 진출 커트라인이 다릅니다. (링크의 1/2 규칙 참고) 1/2 규칙을 만족하는 팀 중 n문제 이상 푼 대학 내 m등 팀을 본선에 올리는 방식으로 본선 진출 팀을 선정합니다. ICPC에서 좋은 성적을 내는 학교일수록 본선 진출이 어려운 편이며, 주로 서울대학교 >>>>> 카이스트 = 고려대학교 >>> 서강대학교 = 성균관대학교 = 한양대학교 = 숭실대학교 순으로 어렵습니다. 특히 서울대학교는 본선에 진출하면 수상이 거의 확정될 정도로 본선 진출 난이도가 높습니다.

본선은 11월에 개최되며 5시간 동안 12문제를 해결해야 합니다. 예선과 다르게 본선은 모든 팀이 한 장소에 모여서 대회를 진행합니다. 대상 1팀, 금상 1팀, 은상 3팀, 동상 4팀, 장려상 5팀으로 총 14팀에게 시상하며, 매년 후원사 사정에 따라 특별상을 추가로 수여하는 것으로 보입니다. 상위 2~3개 대학의 1등 팀은 월드 파이널에 진출할 수 있습니다.

필요한 능력과 훈련 방법

baactree님께서 작성하신 알고리즘 공부, 어떻게 해야하나요?(링크), Barkingdog님께서 작성하신 실전 알고리즘 0x00강 오리엔테이션(링크)를 함께 읽어보시는 것을 추천합니다. 저도 고등학생 때 이 글을 읽으며 공부했기 때문에 비슷한 내용을 이야기합니다.

문제를 풀 때 필요한 능력은 크게 배경지식, 문제 해결 능력, 구현 능력으로 구분해서 이야기합니다.

배경지식

첫 번째는 배경지식으로, 프로그래밍 문법, 자료구조/알고리즘, 수학적 지식 등 문제를 해결하는 데 필요한 모든 지식을 의미합니다. 중학생 때 배운 이차방정식의 근의 공식을 생각해 보면, 똑똑한 사람들은 혼자서 발견하기도 하지만 대부분의 학생은 공식의 유도 과정과 그 결과를 누군가에게 배웁니다. 마찬가지로 자료구조와 알고리즘도 똑똑한 사람들은 혼자서 발견하는 경우도 있지만, 대부분의 사람은 하나씩 공부해야 합니다.

배경지식이 부족하면 문제를 어떻게 풀지 몰라서 해설을 보는데 모르는 외계어가 적혀 있는 것을 많이 경험하게 됩니다. 반대로 이야기하면, 문제 해설에 나와 있는 모르는 키워드를 전부 공부하면 배경지식을 채울 수 있습니다.

문제를 필요할 때 필요한 세 가지 능력 중 배경지식이 가장 훈련하기 편합니다. 책이나 강의를 보는 방법도 있고, 요즘에는 인터넷에도 정말 좋은 자료들이 많이 있어서 의지만 있다면 누구나 쉽게 공부할 수 있습니다. 가르치는 것도 가장 쉽습니다. 따라서 여러분들이 돈을 지불하면서 다른 사람에게 문제 해결을 배울 때는 배경지식 말고 문제 해결 능력이나 구현 능력을 키워달라고 요구하는 것이 좋습니다.

문제 해결 능력

두 번째는 문제 해결 능력으로, 주어진 문제를 내가 알고 있는 배경지식을 사용할 수 있는 형태로 바꾸는 능력을 의미합니다. 수능 수학 30번 문제는 분명 고등학교 교육 과정에서 다루는 내용만으로 풀 수 있지만 대부분의 학생들이 해결하지 못한다는 것을 생각해 보면 문제 해결 능력이 무엇인지 쉽게 알 수 있습니다.

문제 해결 능력이 부족하면 문제 해설을 보면서 “이걸 왜 생각 못 했지?”, “아 이거 아는 건데…“와 같은 이야기를 자주 하게 됩니다. “아 이거 아는 건데…” 라는 말을 하게 되는 상황은 대부분 제대로 몰라서 못 푼 것이기 때문에, 겸손하게 자신의 부족함을 인정하고 공부하는 것이 중요합니다.

문제 해결 능력을 키우는 가장 좋은 방법은 좋은 머리를 갖고 태어나는 것입니다. 이건 불가능하니 다른 방법을 이야기하자면, 문제를 많이 풀고 다른 사람들이 작성한 문제 풀이를 많이 읽어보는 것이 좋습니다. 이때 풀이를 작성한 사람이 어떤 사고 과정을 거쳐서 풀이에 도달했는지 따라가는 것이 중요합니다. 풀이를 잘 작성하는 사람은 그 중간 과정을 잘 풀어서 쓰지만, 대부분의 글은 중간 과정이 생략되어 있기 때문에 그 빈 공간을 혼자 고민하면서 채워나가야 합니다.

구현 능력

마지막은 구현 능력으로, 내가 생각한 풀이 과정을 코드로 옮기는 능력을 의미합니다. 논술 대회가 아니라 프로그래밍 대회이기 때문에 결국에는 문제 해결 과정을 코드로 옮겨서 제출해야 하고, 코드로 옮기지 못하면 문제를 해결하지 못한 것과 다름없습니다.

구현 능력이 부족하면 대회가 끝난 다음에 “풀이는 알겠는데 이걸 어떻게 구현하지?”, “아 이거 다 풀었는데…“와 같은 이야기를 자주 하게 됩니다. 다 풀었다고 생각할 수 있지만 스코어보드에는 못 푼 것으로 기록되어 있기 때문에 그냥 못 푼 것입니다.

구현 능력을 키우는 가장 좋은 방법은 문제를 많이 풀고, 다른 사람의 코드를 많이 보면서 좋은 구현 방식을 학습하는 것입니다. 고인물을 한 명 정해서 코딩 스타일을 따라 하는 것도 좋은 방법입니다. 저는 고등학생 때 koosaga님의 코드를 많이 보면서 공부했습니다.

고수가 되는 방법

문제를 푸는 방법

사람마다 문제를 푸는 방법이 다릅니다. 크게 네 가지 정도의 유형으로 나뉘는데, 하나씩 시도해 보면서 자신에게 맞는 방법을 찾는 것이 중요합니다. 물론 모든 방법을 자유자재로 사용할 수 있으면 더 좋습니다.

첫 번째 방법은 문제를 매우 많이 풀어서 DB에 넣어두고, 문제를 풀 때마다 DB에 쿼리를 날리는 것입니다. 똑똑하지 않은 사람들도 충분한 훈련을 통해 잘 사용할 수 있으며, 제가 주로 이 방식으로 문제를 해결합니다. 문제를 많이 풀고 복기하는 과정을 통해 다양한 유형과 풀이 방법을 기억한 다음, 비슷한 문제를 만났을 때 빠르게 꺼내서 쓸 수 있도록 연습해야 합니다.

두 번째 방법은 관찰 - 추측 - 증명 - 관찰 - 추측 - 증명 - … 을 반복하는 것입니다. 직관력이 좋을수록 풀이까지의 경로가 짧아지는 경향이 있습니다. 직관이 별로 뛰어나지 않더라도, 다른 사람이 작성한 풀이를 읽을 때 풀이에 도달하는 사고 과정에 집중해서 읽으면 천재들의 사고 과정을 모방하는 효과를 볼 수 있습니다.

세 번째 방법은 입력 제한과 시간제한을 보고 가능한 시간 복잡도와 알고리즘을 모두 나열하고 하나씩 대입해 보면서 생각하는 것입니다. 굉장히 이상해 보이지만 대회에서 꽤 유용합니다. 예를 들어 어떤 순서를 정하는 문제에서 $N \leq 500\,000$ 이면 그리디 문제일 확률이 높고, 시간제한이 3~5초 정도이고 $N \leq 50\,000$ 정도이면 시간 복잡도에 $\sqrt N$이 들어갈 확률이 높습니다. 물론 출제진들도 이런 것을 알고 있으므로 $O(N \log N)$에 풀 수 있는 그리디 문제에서 입력 제한을 $N \leq 400$ 정도로 주는 등의 심리전을 걸기도 합니다.

마지막은 풀이를 찾는 Decision Tree를 만드는 것입니다. 소문으로만 들어봤는데, 익숙해지면 풀이를 굉장히 빨리 찾을 수 있다는 이야기가 있습니다.

저는 보통 문제를 푸는 것을 미로찾기에 비유합니다. 아래 그림처럼 앞이 보이지 않는 어두운 미로에서 배경지식은 미로에 있는 촛불, 문제 해결 능력은 촛불의 밝기라고 생각해 봅시다. 배경지식을 공부하는 것은 미로에 촛불을 더 설치하는 것, 문제 해결 능력을 기르는 것은 촛불의 밝기를 키우는 것으로 생각할 수 있습니다.

Super Mario Wiki - NSMBW World 2-3 Screenshot.png

위에서 말한 문제를 푸는 네 가지 방법을 미로의 관점에서 다시 생각해 볼 수 있습니다. 문제를 매우 많이 풀어서 DB에 넣는 것은 문제의 유형도 하나의 사전지식으로 취급해서 수많은 곳에 촛불을 설치하는 것이고, 관찰 - 추측 - 증명을 반복하는 것은 합리적인 근거를 토대로 인근의 광원으로 이동하는 것입니다. 가능한 시간 복잡도와 알고리즘을 나열하거나 Decision Tree를 이용하는 것은 어떤 광원에서 탐색을 시작할지 결정하는 것으로 생각할 수 있습니다.

잘해지는 방법

많은 사람이 어떻게 하면 잘해질 수 있는지 물어봅니다. 문제를 많이 풀면 된다고 이야기하는 경우가 대부분이지만 사람들이 그걸 몰라서 물어보는 것은 아닐 테니까… 저는 문제를 매우 많이 풀어서 실력을 올렸기 때문에 문제를 많이 풀게 된 계기나 원동력이 무엇이었는지 고민을 했었습니다.

제가 생각했을 때 실력이 오르는 가장 효율적인 방법은 (내가 잘하는 것 같음 → 재미있어짐 → 재미있어서 더 열심히 공부함 → 잘해짐 → 잘해서 더 재미있음 → 더 열심히 공부함 → 더 잘해짐 → …)의 사이클을 타는 것입니다. 이 사이클 안에 들어가면 크게 신경을 쓰지 않아도 실력이 꾸준히 올라갑니다. 처음부터 재미있으면 운이 좋은 거니까 감사하게 생각하면서 열심히 공부하면 되고, 그게 아니라면 일단 잘해지는 것밖에 방법이 없으니 열심히 공부하면 됩니다. 뭐 결국 열심히 해야 합니다…

사이클 안에 들어간 다음도 중요합니다. 단기적인 성과를 뽑아내야 하는 상황이 아니라면, 스트레스를 받지 않고 PS가 재미있게 느껴지는 범위 안에서만 공부하는 것을 추천합니다. 저는 조금 극단적인 케이스인데, 재미없다고 느껴지는 순간 즉시 키보드에서 손 떼고 침대로 갑니다.

최근 대회 분석

2020 ~ 2022 ICPC 예선

최근 3년 동안 예선에 출제된 문제의 solved.ac 난이도와 상위권 대학의 본선 진출 커트라인은 다음과 같습니다. 빠른 n문제로 표기되어 있는 대학은 문제 수가 아닌 페널티로 본선 진출이 갈린 대학교를 의미합니다.

  • 2020: S4 G4 G4 G2 G? P5 P4 P1 D5 D5 D? D3
    • 서울대학교: 8문제
    • 카이스트, 고려대학교: 6문제
    • 서강대학교, 성균관대학교, 한양대학교: 빠른 5문제
    • 숭실대학교: 5문제
  • 2021: S5 S1 G2 G1 P4 P4 P2 P2 D5 D4 D4 D4
    • 서울대학교: 빠른 6문제
    • 카이스트: 5문제
    • 고려대학교, 성균관대학교: 빠른 4문제
    • 한양대학교, 숭실대학교: 4문제
    • 서강대학교: 빠른 3문제
  • 2022: S4 S3 S2 G3 G2 P5 D5 D5 D4 D2 R?
    • 서울대학교, 카이스트: 7문제
    • 고려대학교, 서강대학교: 빠른 5문제
    • 성균관대학교, 숭실대학교: 5문제
    • 한양대학교: 4문제

서울대학교와 카이스트가 아니라면 solved.ac 기준 골드 이하의 문제만 모두 해결하면 대부분 본선에 진출할 수 있습니다. ICPC 예선은 가장 쉬운 3~4문제만 한글 지문을 제공해 주기 때문에, 한글 문제를 모두 해결한 다음 스코어보드에서 가장 많이 풀린 1~2문제를 더 풀면 본선을 노려볼 수 있습니다.

예선에서 가장 쉬운 5문제를 풀기 위해 필요한 개념은 다음과 같습니다. 기초적인 개념을 잘 활용하는 문제들이며, 본선 진출을 노린다면 어려운 배경지식을 공부하는 것보다는 알고 있는 내용을 잘 활용하는 것이 중요합니다.

2020 S4 G4 G4 G2 G?
그리디 최단 경로 스패닝 트리 DP DFS
2021 S5 S1 G2 G1 P4
정렬 완전 탐색 DP 기하 그리디
2022 S4 S3 S2 G3 G2
그리디 그리디 그리디 DP DP

서울 지역 예선과 비슷한 난이도의 대회로는 BAPC(BOJ 링크), GCPC(BOJ 링크), NCPC(BOJ 링크), Southeast USA Regional Division 1(BOJ 링크)가 있습니다. 조금 더 쉬운 대회로는 BAPC 예선, Southeast USA Regional Division 2도 있으니 팀 연습할 때 유용하게 사용하면 좋을 것 같습니다.

2018 ~ 2022 ICPC 본선

본선에서 수상을 노리는 팀들은 예선보다 훨씬 더 어려운 문제를 해결해야 합니다. 최근 5년 동안 본선에 출제된 문제의 solved.ac 난이도와 수상 커트라인, 대학 3등 안에 들기 위한 커트라인은 다음과 같습니다.

  • 2018: B1 G2 G1 P4 P4 P4 P2 P2 P1 D5 R4 R4
    • 수상: 7문제(P2), 대학 3등: 10문제(D5)
  • 2019: S4 G4 G3 G2 P4 D5 D5 D5 D4 D3 D2 D1
    • 수상: 7문제(D5), 대학 3등: 9문제(D4)
  • 2020: B1 G3 G2 G2 P3 P2 P1 D5 D4 D3 D2 D1
    • 수상: 7문제(P1), 대학 3등: 8문제(D5)
  • 2021: S4 G5 P3 P3 P3 P2 P2 D3 D3 D1 D1 R5
    • 수상: 7문제(P2), 대학 3등: 8문제(D3)
  • 2022: S2 G4 G3 G3 P5 P3 P2 D5 D4 D3 D2 R1
    • 수상: 8문제(D5), 대학 3등: 9문제(D4)

수상을 하기 위해서는 플래티넘 이하의 모든 문제를 해결해야 하고, 월드 파이널 진출을 노리는 팀들은 다이아몬드 하위권 문제도 모두 해결할 수 있어야 합니다. 이렇게 보면 굉장히 어려워 보이지만, 다양한 꼼수가 존재합니다.

수상을 노린다면…

서울 지역 대회는 플래티넘 ~ 다이아몬드 하위권 레벨에서 배경지식이 있으면 쉽게 풀 수 있는 문제가 꽤 자주 나옵니다.

  • 2019 예선: 컨벡스헐 트릭(D5)
  • 2019 본선: 센트로이드 분할(P2), 세그먼트 트리 변형(A.K.A. 금광세그, D5)
  • 2020 본선: 가우스 소거법(P3), FFT(P1), 분할 정복 최적화(D4), 도미네이터 트리(D2)
  • 2021 본선: KMP 알고리즘 변형(D3)
  • 2022 예선: 평방 분할(D5)

비슷한 문제가 여러 번 출제되는 경우도 자주 보입니다.

  • 2019 본선 H(D5) = 2014 KOI 중등부 4번 금광
  • 2021 예선 L(P2) ≒ 2022 본선 C(D4)
  • 2021 본선 K(D3) ≒ 2011 CEOI 기출 ≒ 2020 1차 선발 기출 = 2021 SCPC 2차 예선 기출
  • 2022 본선 A(D5) = BOJ 16883. 대각 게임
  • 2022 본선 B(D2) = 2016 1차 선발 기출 ≒ 2019 2차 선발 기출 (참고 링크)

따라서 수상을 노린다면 배경지식과 흔히 웰노운 테크닉이라고 불리는 유명한 기법들을 공부하는 것이 좋습니다. 배경지식을 대회 전에 급하게 공부하는 것은 소용없고, solved.ac 티어도 올릴 겸 평소에 조금씩 공부하는 것을 추천합니다. 웰노운 테크닉은 solved.ac 클래스 문제집을 풀어도 좋고, P3..D3 범위 안에서 푼 사람이 많은 문제부터 차례대로 풀어보는 것도 좋습니다. BOJ에 올라오는 대학교 교내대회 문제도 공부할 때 유용합니다.

팀 노트를 준비하는 것도 중요합니다. 코드는 팀 노트에 넣어 가더라도 각 알고리즘이 어떤 것을 입력받아서 무엇을 계산하는지는 알아야 합니다. 팀 노트에 넣는 코드는 빠르고 검증된 코드를 넣어야 하는데, 다른 팀들의 팀 노트를 참고하는 것도 좋고 Library Checker라는 사이트를 이용하는 것도 좋습니다.

학교 전공과목과의 연계

이산수학, 자료구조, 알고리즘을 제외한 다른 과목과는 별로 연관된 내용이 없을 것 같지만, 의외로 다른 전공과목에서 배우는 내용이 문제 해결에 도움이 되는 경우가 있습니다.

가장 먼저 언급할 것은 컴퓨터구조입니다. 문제를 풀다 보면 흔히 상수 커팅이라고 부르는, 실행 시간을 줄여야 하는 경우가 있습니다. 가장 좋은 방법은 연산 횟수를 줄이는 것이겠지만 그게 항상 가능하지는 않습니다. 구체적으로 다음과 같은 상황이 있습니다.

  • $N^2$은 시간 초과를 받지만 $N^2/8$은 AC를 받는 경우
  • 정해는 $O(N^2)$이지만 $O(N^3)$ 풀이만 알고 있을 때 어떻게든 문제를 풀고 싶은 경우

둘 다 일반적인 상황은 아니지만… 아무튼 컴퓨터구조에서 배우는 캐시 히트, 분기 예측, 메모리 정렬, SIMD와 같은 내용이 큰 도움이 됩니다. (링크1)과 (링크2)에서 실제 사례를 볼 수 있습니다.

선형대수학 관련 문제도 자주 보입니다. 가우스 소거법을 이용해 연립방정식을 풀어야 하는 문제(ex. 2020 서울 J)가 출제되기도 하고, 그래프 이론과 결합해서 그래프에서 특정 값을 구할 때도 사용합니다. 스패닝 트리의 개수를 구하는 Kirchhoff’s theorem, 최대 매칭의 크기를 구하는 Tutte matrix, DAG에서 정점이 중복되지 않는 경로를 만드는 경우의 수를 세는 LGV lemma 등이 대표적입니다.

오토마타는 오토마타 개념을 직접적으로 다루는 문제도 나오고, 그런 문제가 나오지 않더라도 DP의 상태 전이는 사실상 유항 상태 오토마타와 다름이 없고, KMP/Aho-corasick 같은 문자열 알고리즘은 오토마타 개념을 기본으로 깔고 시작합니다.

확률/랜덤 프로세스도 가끔씩 출제되고, 모르면 절대 못 푸는 유형으로 나오는 경우가 대부분입니다. 이전에 작성한 랜덤으로 문제 풀기라는 글을 읽어보는 것이 도움 될 것입니다. (링크)

대회 전략과 팀 워크

대회 전략의 필요성

장홍준(hongjun7)님께서 startlink live에서 발표하신 Teamwork in Programming Contests 강연을 함께 보는 것을 추천합니다. (링크) 저는 고등학생 때 이 영상을 보면서 팀 대회에 대한 꿈을 키워왔습니다.

위에서도 언급했지만 ICPC는 3명이 1대의 컴퓨터를 사용해 문제를 해결하는 대회입니다. 당연히 개개인의 실력도 중요하지만, 어떤 상황에서 누가 키보드를 잡을지 결정하는 것도 매우 중요합니다. startlink live 강연에서는 $\max(A,B,C)$를 만드는 것보다는 $A+B+C$를 만들기 위해 노력해야 한다고 표현합니다.

대회 전략의 목표는 다음과 같습니다.

  • 낭비되는 시간 감소
  • 서로의 강점을 파악
  • 서로의 약점을 보완
  • 위험 분산

특히 낭비되는 시간을 줄이는 것이 매우 중요합니다. 낭비되는 시간을 줄이는 최상의 시나리오는 다음과 같습니다.

  • A가 코딩하는 동안 B와 C는 풀이 고민
  • A가 문제를 풀어서 B가 코딩 시작, C는 A와 풀이 토론
  • B가 문제를 풀어서 C가 코딩 시작, A와 B는 각자 새로운 문제를 잡고 고민
  • …

낭비되는 시간 없이 잘 맞물려서 돌아간다는 것을 알 수 있습니다. 반면 최악의 시나리오는 정말 절망적입니다.

  • A가 코딩하다가 말려서 디버깅 시작, B와 C는 풀이를 완성했지만 아직 A가 키보드를 차지하고 있는 상태
  • A가 디버깅에 실패하고 B에게 키보드를 넘겨줌
  • B가 코딩하는 중간중간에 A가 키보드를 뺏어서 다시 디버깅함(…)
  • 구현하지 못한 풀이가 3개 남은 채로 대회 종료

키보드는 하나밖에 없는 희귀한 자원이기 때문에 효율적으로 사용해야 합니다. 문제를 푸는 과정을 생각해 보면 가장 먼저 풀이를 고민하고, 풀이를 찾으면 구현 방법을 고민하고, 그다음에 구현과 디버깅을 진행합니다.

풀이를 고민하는 시간에는 키보드가 필요하지 않습니다. 또한 키보드를 잡고 있지 않은 다른 팀원과 토론도 할 수 있습니다.

구현 방법을 고민할 때도 키보드가 필요하지 않습니다. 하지만 실제로 구현할 때는 키보드가 꼭 필요하기 때문에, 구현 방법을 잘 고민해서 구현 시간을 줄여야 합니다. 어떤 기능을 함수로 분리할지, 함수의 입력과 출력은 어떤 형식으로 할지 구상하고, 이를 바탕으로 코딩이 얼마나 걸릴지 예측하는 것이 좋습니다.

디버깅은 키보드가 필요할 수도 있고 필요하지 않을 수도 있습니다. 디버깅은 뒤에서 다시 이야기합니다.

스코어보드 활용

ICPC는 푼 문제 수가 같은 팀은 각 문제를 해결한 시간을 모두 더한 값을 기준으로 등수를 매기기 때문에 쉬운 문제부터 빨리 푸는 것이 좋습니다. 보통 많이 풀린 문제가 쉬운 문제이기 때문에 어떤 문제를 풀어야 할지 모르겠으면 스코어보드에서 많이 풀린 문제부터 풀면 됩니다. 이때 각 팀이 몇 번 시도해서 맞았는지도 알 수 있으므로, 문제를 한 번에 맞춘 팀이 없다면 실수하기 쉬운 문제이므로 구현하기 전에 풀이를 한 번 더 검증하고 구현할 때도 신중하게 코드를 짜는 것을 권장합니다.

수상을 노리는 팀들은 추가적인 정보를 미리 파악해 놓는 것도 좋습니다. 저는 작년 ICPC를 준비할 때 다른 잘하는 팀이 잘 푸는 문제의 유형을 미리 파악해 놓았습니다. 만약 그 팀만 빨리 푼 문제가 있다면 그 문제를 건들지 않는 것이 좋을 수도 있습니다. 실제로 UCPC 2018(링크)에 수학 올림피아드 문제가 그대로 나온 적이 있었는데, 1등 팀에는 IMO 국가대표 출신이 있어서 대회 시작 11분 만에 해결했지만, 두 번째로 푼 팀은 대회 시작 후 64분 뒤에 나왔었습니다.

디버깅

디버거를 사용하는 것은 컴퓨터를 사용해야 하기 때문에 다른 팀원이 코딩할 기회를 뺏는 것입니다. 따라서 구현할 문제가 많이 밀려있을 때 디버깅이 오래 걸릴 것 같으면 비키는 것이 좋습니다. 최대한 디버거를 사용하지 않고 디버깅해야 하는데, ICPC는 코드 인쇄 요청을 할 수 있으므로 제출과 동시에 코드 인쇄 요청을 하는 팀들이 꽤 있습니다.

인쇄된 코드를 보면서 디버깅할 일이 많으므로 눈으로 디버깅하는 연습을 꼭 해야 합니다. 논리가 잘못되지 않았는지, 코드로 잘못 옮기지 않았는지, 반복문 실행 도중에 invariant가 깨지지 않는지, 부등호 방향이나 i j k 같은 변수 이름을 잘못 쓰지 않았는지, 사용하지 않는 변수나 함수가 있는지 확인해야 합니다. 그리고 몇몇 사소한 실수는 의외로 다른 사람이 보면 잘 보일 수 있으므로 다른 팀원과 함께 디버깅하는 것도 좋은 방법입니다.

다른 팀원이 키보드를 잡고 있을 때

다른 팀원이 키보드를 잡고 있을 때 할 수 있는 행동은 다음과 같습니다.

  • 훈수 두기(페어 코딩)
  • 다른 문제 의사 코드 작성
  • 코드 인쇄해서 디버깅
  • 내 구현이 5~10분 이내로 끝날 것 같으면 키보드 뺏어서 구현하는 것도 고려

키보드를 잡은 사람이 없을 때

키보드를 잡고 있는 사람이 없을 때는 다양한 선택을 할 수 있습니다. 만약 검증하고 싶은 가설이 있는데 수학적으로 증명하기가 어렵다면 컴퓨터를 이용해 검증하는 것도 좋은 방법입니다. naive 코드를 작성해서 테스트해 볼 수 있습니다. 구현할 게 많아서 미뤄둔 문제를 조금씩 코딩할 수도 있고, 왜 틀리는지 모르겠는 코드가 있다면 스트레스 테스트를 작성해 볼 수도 있습니다.

하지만 키보드가 비어 있다는 것을 의식해서 성급하게 구현하는 것은 별로 좋은 선택이 아닙니다. 항상 어떻게 구현할지, 구현하는 데 시간이 얼마나 걸릴지 생각한 다음 팀원들에게 예상 시간을 이야기하고 구현하는 습관을 들여야 합니다.

팀 전략의 분류

대부분의 팀 전략은 크게 개인플레이 위주의 팀(Solver * 3)과 매니저 중심의 팀(Solver * 2 + Manager)으로 분류할 수 있습니다.

개인플레이 위주의 팀은 기본적으로 3명이 각자 문제를 풀다가 막히면 토론하는 방식입니다. 3명의 실력이 비슷하거나 분야가 겹치지 않을 때 사용하면 좋습니다. 매니저 중심의 팀은 두 명이 문제를 푸는 동안 다른 한 명이 문제 분배, 디버깅, 전략 수정 등 여러 가지 일을 맡아서 처리하는 방식입니다. 매니저 중심의 전략은 팀마다 세부 전략이 정말 많이 다르기 때문에 여러 팀의 실제 사례를 보면서 전략을 세우는 것이 좋습니다.

2022년 서울 리저널 숭실대학교 NLP팀의 팀 전략은 아래에서 소개할 것이고, 그 밖에도 몇몇 팀들의 전략을 소개한 글을 링크합니다.

  • 서울대학교 MolaMola - 2017 서울 리저널 1등, 2017 쓰쿠바 리저널 3등, 2018 월드 파이널 5등 (링크)
  • 고려대학교 1_Hoeaeng_2_Hawawang - 2020 서울 리저널 7등, 2021 월드 파이널 진출 (링크)
  • 포스텍 000102 - 2022 서울 리저널 8등 (링크)
  • 도쿄대학교 Cxiv-Dxiv - 2017 쓰쿠바 리저널 1등, 2018 월드 파이널 4등 (링크, 일본어 주의)

아래는 2022 서울 리저널 5등을 기록한 숭실대학교 NLP팀의 전략입니다.

실제 사례 - 팀원 구성

팀원 구성은 다음과 같습니다. 팀원마다 장단점이 매우 뚜렷한 팀이라고 생각합니다.

  • jhnah917 - BOJ 9000문제, solvedac 마스터, Codeforces 오렌지
    • 장점: 골드 1 이하의 쉬운 문제를 빠르게 해결, 구현 속도가 매우 빠름, 자료구조/그래프/기하 알고리즘을 많이 알고 있음
    • 단점: 수학을 잘 못함, 오래 고민해야 하는 문제를 잘 풀지 못함, 30분 안에 풀이를 못 찾으면 5시간 동안 못 찾는 경우가 많음, 한 번 말리면 크게 말림
  • edenooo - BOJ 3000문제, solvedac 루비3, Codeforces 레드
    • 장점: 문제 풀이 능력과 코딩 속도/정확도 모두 좋음, 팀원 중 수학을 가장 잘함, 대회 참가 경험이 매우 많음
    • 단점: 실수를 자주 함, 익숙하지 않은 분야가 꽤 있음
  • chansol - BOJ 1500문제, solvedac 다이아4, Codeforces 퍼플
    • 장점: 풍부한 개발 경험을 바탕으로 키보드가 비어있을 때 구현이 복잡한 문제나 스트레스 테스트 등을 잘 구현함
    • 단점: 다른 2명에 비해 문제를 많이 안 풀었음

팀원의 단점이 명확한 것은 안 좋은 요소이지만, 다행히 팀원의 장점이 서로 다르므로 다른 팀원의 단점을 잘 커버할 수 있었습니다. 특히 저는 BOJ, edenooo는 코드포스에서 주로 활동했는데, 주로 활동하는 사이트가 다르고 각자 사이트에서 최상위권이었기 때문에 두 명이 커버할 수 있는 문제의 범위가 매우 넓었습니다.

커버할 수 있는 문제의 합집합이 큰 것은 장점이지만 교집합이 작은 것은 팀 구성 자체의 단점입니다. 한 명이라도 상태가 안 좋으면 타격이 큰데, 특히 저는 대회 시작 후 3시간이 지나면 퍼포먼스가 급격하게 떨어진다는 단점이 있습니다. 처음에는 이걸 고치려고 했지만 잘되지 않아서, 그냥 3시간 동안 최대한 많이 푸는 방향으로 팀 연습을 돌렸습니다. 실제로 2번을 제외한 모든 팀 연습은 3시간만 진행했습니다.

실제 사례 - 대회 초반 (-10 ~ 60분)

대회 전략은 대회 시작 10분 전부터 시작합니다. 대회장에 들어가면 앞에 풍선이 배치되어 있는데, 풍선의 개수를 보면서 문제의 난이도를 유추했습니다. 대회 끝나고 스태프한테 물어보니 대회장에 꺼내놓은 풍선의 개수는 전부 똑같았다고 하던데… 뭐 아무튼 잘 맞았으니 다행입니다.

일반적으로 제일 쉬운 문제는 앞쪽에 배치되어 있기 때문에 팀 연습을 할 때는 제가 ABCD, edenooo가 EFGH, chansol이 HIJK를 잡았습니다. 하지만 풍선을 보니 C부터 H까지가 전부 지뢰처럼 보여서(…) 제가 뒤쪽 4문제를 잡는 것으로 급하게 전략을 수정했습니다.

처음에는 위 사진처럼 컴퓨터가 가운데에 있고, 왼쪽 봉투 안에 계정 정보와 문제지가 들어있습니다. 하지만 예비소집 때 컴퓨터를 만져보면서 컴퓨터를 오른쪽에 배치하는 것이 최적이라는 결론을 내렸습니다. 따라서 대회가 시작하자마자 컴퓨터를 옮기는 과정도 미리 준비해갔습니다.

저는 대회가 시작하자마자 쉬운 문제를 최대한 빨리 풀어야 하기 때문에 오른쪽에 앉아서 시작합니다. edenooo는 왼쪽 자리에서 시작했고, 대회가 시작되면 봉투를 뜯은 뒤 뒤쪽 4문제를 저에게 전달했습니다. chansol은 가운데에서 시작했고, 대회가 시작하면 로그인하고 CLion 환경설정까지 마친 다음에 컴퓨터를 오른쪽으로 이동시켰습니다. 그동안 저는 뒤에 있는 문제 4개를 모두 읽은 뒤, 쉬운 문제 3개를 찾아서 두 문제는 직접 해결하고 한 문제는 edenooo에게 전달했습니다.

저와 edenooo가 초반 3문제를 해결하는 동안 chansol은 남은 문제 중 쉬운 문제를 찾아서 번역하고, 예제 설명까지 추가해서 코딩을 마치고 나오는 팀원들에게 전달했습니다. 첫 1시간은 이렇게 한 명이 문제를 분배하고, 나머지 두 명이 번갈아가면서 문제를 푸는 방식으로 진행합니다.

30분 안에 해결할 수 있는 쉬운 문제를 모두 해결하면 대회 초반이 끝납니다. 지난 ICPC에서는 첫 1시간 동안 P5 이하인 5문제를 모두 해결했고, 이 시점에 4등을 기록했습니다.

실제 사례 - 대회 중반 (60 ~ 180분)

중반부터는 긴 호흡을 갖고 고민해야 하는 문제를 해결해야 하는 단계입니다. 팀원의 장단점이 명확하기 때문에 문제를 잘 나눠 갖는 것이 중요합니다. 전형적이거나 어려운 배경지식을 사용해야 하는 문제는 주로 제가 가져가고, 오래 고민해야 하는 문제는 주로 edenooo가 가져갑니다. 그동안 chansol은 풀이 토론, 페어 코딩, 디버깅 등을 수행합니다.

풀이가 나오면 키보드 스케줄링을 잘하면서 코딩을 시작하면 되고, 못 풀겠으면 문제를 교환하거나 토론해서 풀이를 찾아야 합니다. 대회 수상을 노리는 팀이라면 대회 중반에 잡는 문제는 어려운 문제가 아니기 때문에, 문제가 풀리지 않는다면 팀원 3명이 모두 붙어서 고민하는 한이 있더라도 꼭 풀어내야 합니다.

여기까지 왔을 때 높은 등수에 올라왔다면 거의 다 완성되었다고 볼 수 있습니다. 지난 ICPC에서는 3시간 동안 플래티넘 이하의 모든 문제를 해결하고, D4인 C번도 해결해서 4등을 유지하고 있었습니다.

실제 사례 - 대회 후반 (180 ~ 300분)

대회 중반을 특별히 말리는 것 없이 잘 넘겼다면, 마지막 2시간 동안에는 수상을 가르는 문제 하나를 풀면 됩니다. 이제 와서야 말할 수 있지만 저는 3시간이 지나면 퍼포먼스가 급격하게 떨어지기 때문에 사실상 edenooo를 믿고 기도하는 것이 가장 큰 전략이었습니다. chansol은 edenooo가 고민하는 문제를 함께 고민하거나 테스트 케이스를 제작하는 역할을 주로 수행했고, 저는 함께 토론하거나 다른 어려운 문제를 “이전에 풀어본 문제”로 바꿀 수 있을지 고민했습니다.

지난 ICPC에서는 다행히 A를 풀어내서 5등으로 마무리했습니다.

오프라인 대회장

위에서도 조금씩 언급했지만, 오프라인 대회장은 팀 연습과 환경이 다르기 때문에 여러 돌발상황이 발생할 수도 있고 불편한 점이 있을 수도 있습니다. 대회 전날 예비 소집이 본 대회와 동일한 환경에서 진행되기 때문에, 예비 소집을 하면서 최대한 변수를 통제할 수 있는 전략을 세워야 합니다.

또한, 문제지와 팀 노트를 합하면 50페이지 정도 되는데, 대회 시작하고 2시간 정도 지나면 종이 50장이 섞여서 내가 풀고 있는 문제지를 찾지 못하는 참사가 발생할 수도 있습니다. 종이 정리하는 것도 신경 써야 합니다. 저는 푼 문제는 모두 바닥에 버리는 방식을 선택했습니다.

질의응답

  • 쉬운 문제를 잘 알아보는 방법
    • ICPC 예선은 영어 지문만 제공되는 문제가 있고, 한글 지문이 함께 제공되는 문제도 있음
    • 한글로 된 3~4문제가 가장 쉬운 문제이므로 한글 문제부터 빠르게 해결하고, 그 이후로는 스코어보드를 따라가면 됨
  • 권장 공부 시간
    • 고등학생 때는 평균적으로 하루에 8시간 정도 했고, 지금은 4시간 정도 하는 중
  • 쉬운 문제를 빨리 푸는 방법
    • 브론즈 실버 골드 각각 2000개씩 풀면 됨
    • 서울 지역 대회에 나오는 골드 이하 문제는 대부분 전형적인 유형만 나오기 때문에 익숙해지면 빨리 풀 수 있음