Codeforces IGM 달성 후기

Tue Jan 21 2025

얼마 전 Good Bye 2024를 치고 코드포스 IGM을 달성했다. 짝짝짝. 내가 ps를 고3 때 자소서 쓰기 싫어서 시작했던 것으로 기억하는데, 그게 맞다면 4.5년이 걸린 셈이다. 흥미롭게도 GM은 Good Bye 2023 라운드에서 달성했는데, GM은 3.5년이 걸린 셈이다. GM 달성은 딱히 후기를 작성하지 않았지만, 개인적으로 코포는 꽤나 재밌게 즐긴 컨텐츠였기 때문에 IGM은 후기를 작성해보기로 결심했다. 그래서 보통 다른 IGM 후기는 무슨 내용이 있는지를 찾아봤고, 다음의 글들을 참고해서 적당히 개요를 잡았다.

소감

일단 IGM을 달성해서 매우 기쁘다. 어느 정도로 좋냐면, 지인들에게 열심히 자랑하고 다녔다. 다만 나한테 IGM은 일종의 숙제 같은 느낌이었다. 주변에서 다들 IGM은 달성하니까 나도 그러고 싶다는 생각도 있었고, 대학 생활 내내 PS를 한 것치곤 막상 오프라인 메이저 대회에선 이렇다 할 성적을 낸 적이 없어서 뭐라도 성과를 내고 싶었다.

How to Study?

@qwerasdfzxcl님이 매우 정석적인 방법론을 소개하셨고, 타당한 방법이라고 생각한다. 실제로 나도 비슷한 방식으로 공부했지만, 여기서는 CP 연습의 원리적인 부분에 대해 내 생각을 정리해 보고자 한다.

한때 나는 수학 문제 풀이에 모종의 신비감을 느끼곤 했다 (요즘도 여전한 것 같긴 하다). PS도 비슷하게, 많은 경우 아이디어가 없으면 뭔가를 할 수가 없고, 문제에서 새로운 관찰을 만드는 과정이 창발적이고 통제 밖이기 때문이다. 어떻게 보자면 신내림이랑도 비슷하다고 생각했었다. 그래서 나는 PS를 잘하는 건 재능의 영향이 크다고 생각하고 있었다. 그러나 이 신비감을 떨쳐낸 것이 코포 실력 향상에 가장 중요한 요소였다.

실전에서 어떤 문제를 풀고 못 풀고의 차이가 어디에서 오는가? 이에 대한 내 나름의 답은, "예전에 비슷한 문제를 풀어본 경험이 있다면 풀고, 아니라면 못 푼다."이다. 보통 대회에서 마지막으로 AC를 받는 문제를 푸는 데 걸리는 시간은 전체 대회 시간의 $1 / 3$ 에서 $1 / 2$ 정도가 걸리고, 그보다 앞쪽의 모든 문제를 푸는 시간이 이와 비슷하거나 조금 더 걸릴 것이다. 따라서 이 난이도 부근의 문제에서 잘 훈련되어 있지 않은 유형이 나온다면 풀 확률이 꽤 낮다고 볼 수 있다. 또한 코포가 결국 상대평가의 성격을 지니고 있음을 고려하면, 비슷한 레벨의 다른 참가자들이 어딘가에서 본 적이 있어서 빨리 푸는 문제를 나는 몰라서 못 풀고 있다면 나만 손해다. 특히 레이팅이 높아질수록 이러한 효과가 극명해진다. '마지막 AC 문제'의 난이도가 점점 어려워지므로 문제 해결에 필요한 시간이 평균적으로 길어지며, 그러므로 운 좋게 비슷한 문제가 나왔을 때 얻는 이득이 상당하다. 또한 실력자일수록 푼 문제 수도 많기 때문에, 점점 더 연습한 범주의 문제를 마주할 확률이 높을 것이다. 그러므로 결론은 레이팅이 높은 구간일수록 오히려 재능보다 노력이 더 중요한 요소일 수 있다는 것이다.

이러한 관점에서 CP는 craft의 영역이 아닌가 싶다. 즉 반복적 연습으로 특정 기술에 숙달되어야 하는 분야라는 것이다. 그래서 언젠가부터 다음과 같이 연습법을 바꿨다.

문제를 풀기 전에 항상 시간제한을 두었고, 그 안에 못 풀면 빠르게 solution을 읽었다.
문제를 풀고 나서는 문제로부터 takeaway를 최소한 하나라도 도출해 내려는 시간을 가졌다.
또한 다른 사람들의 깔끔한 구현을 배워서 내 구현 패턴을 개선해 보려고 노력했다.

결국, PS를 수능 공부하듯 접근했다. 문제를 유형별로 분류해서 머릿속에 정리해 두고, 문제 풀면서 얻은 takeaways를 리스트로 만들었다. 대회에서는 "풀 수 있는 문제는 기계적이고 신속하게 해결해서 penalty에서 이득을 보고, 다음 문제를 풀 시간을 확보하겠다"라는 전략을 세웠다. 아래는 NeoTLE로 그린 코포 performance 그래프인데, 실제로 처음 3년 동안 퍼포먼스가 별로 개선되지 않은 것을 고려하면 이러한 연습이 확실히 도움이 되었다는 것을 드러내고 있다고 생각한다.

Random Thoughts

추상적인 이야기만 하면 지루할 것 같아서, 몇 가지 구체적인 사항들을 적는다.

재밌는 문제 모음 (pjshwa): GM 가기 직전에 열심히 풀던 문제집이다. 이거 풀면서 위의 깨달음을 얻었기 때문에, GM에 직접적인 기여를 했다고 볼 수 있다.
재밌었던 DP 모음 (bnb2011): IGM 가기 직전에 열심히 풀던 문제집이다. IGM과의 관련성은 잘 모르겠지만, DP를 많이 푸는 건 구현력에 매우 좋다.
BOJ 랜디 기록을 보면, 내가 65분에 p1을 80% 정도 방어한다고 한다. '플래를 안정적으로 밀면 IGM에 간다'는 PS 계의 folklore는 사실인 듯하다. 80%가 어딜 봐서 안정적이냐고 물으면, 여기에 대해선 할 말이 없다. 65분은 사실 maximum이고, 평균은 그보다는 짧을 것으로 추정한다. 글 작성 시점 기준, p1의 성공에 걸린 평균 시간은 37분이 조금 넘는다. 분산은 계산 안 했는데 꽤 큰 거 같다.
코포는 레이팅 구간마다 레이팅 상승을 결정하는 요인이 다르다고 생각한다. 내가 느끼기에 CM-M 구간은 문제 풀이의 속도가 중요하고, IM-GM 구간은 풀 수 있는 문제의 범위가 중요하다. 특히 M/GM 구간, 즉 오렌지-레드 사이의 차이가 확연하다는 명제는 prevail belief라고 생각하는데 (나도 동의하고 있다), 그 이유가 정확히 이거라고 생각한다. 속도는 구현력을 늘리고 자기가 풀 수 있는 난이도의 문제들을 열심히 풀면 확실하게 빨라지는데, 풀 수 있는 문제의 상한을 높이는 건 그렇지 않기 때문이다.

Minor Tips

템플릿을 잘 만들어놓자. 이게 없이 CP를 하는 건 말이 안 된다.
대회 시작 전에 문제 점수 배점을 꼭 확인하자. 점수 배점 비율로 문제들 사이의 난이도 간극이나, subtask 문제들의 난이도 비율을 추정해 볼 수 있다.
아이디어 하나에 매몰되면 피 보는 경험이 많은 것 같다. 아무리 혹하는 관찰이 있어도 아닐 때가 있는 법이고, 아니면 후반부에 필요한 관찰을 먼저 해버린 것일 수도 있다. 항상 뇌를 open 해두자.
최상위권의 스코어보드나, PS적인 강점/약점을 알고 있는 지인들의 스코어보드를 보자. 얻을 수 있는 정보는 여러 가지가 있다. 대표적인 것은 출제진의 예상 난이도와 실제 참가자가 느끼는 난이도의 괴리이다. 뒤쪽 문제가 꽤 활발히 풀리고 있다면 문제 푸는 순서의 swap을 고려해 보라. 또한 최상위권의 참가자들이 특정 문제를 푸는 시간이 매우 짧다면, 구현이 간단한 애드혹이거나 일명 능지 문제일 확률이 높다. LGM도 결국 사람이라서, 구현량이 많은 문제는 시간이 걸릴 수밖에 없다. 마지막으로 나보다 조금 위쪽 레이팅 구간의 사람들이 현재 내가 잡고 있는 문제를 푸는 데 걸린 시간을 내가 이 문제를 푸는 시간의 기댓값 정도로 간주할 수 있다.

Future Work?

공교롭게도 IGM 달성과 대학교 졸업이 시기적으로 겹쳐버려서, PS에 대한 의욕이 소강상태로 접어들었다. 게다가, 예전엔 IGM쯤 찍으면 어디 가서 PS 못한다는 소리는 안 듣지 않을까 싶었는데, 막상 보니 코포 실력이 PS 실력을 잘 대변해 주지도 못하며, 오히려 내가 약점을 더 잘 파악하게 되어서 김이 팍 샜다. 다음 단계인 LGM까지의 간격이 너무 크다는 점도 한몫한다. 그래서 당분간은 현생이 약간 바쁜 것도 있고 해서, 쉬면서 다음 목표를 생각해 보지 않을까 싶다.

물론 PS/CP 실력을 늘리는 것 말고도 설정할 만한 목표가 없진 않다. 일단 내가 아직도 UCPC 수상을 해본 적이 없는데, 이건 대학원이라도 가는 게 아닌 이상 참여도 못 한다는 제약이 있다. 그 외에는 대회 개최가 있는데, 이건 기회가 되는대로 시도해 볼 것 같다. 그리고 뜬금없게도 최근에 멘토링 비스름한 걸 시작했는데, 생각보다 공수가 많이 든다는 걸 깨달았다. 일단 교육적인 문제 목록을 선정하는 것도 꽤 어렵고, 내가 그 문제의 풀이를 알고 있어야 설명이 가능하며, 구현을 해 봤어야 코드를 보고 코멘트를 할 수가 있고, 그 내용이 전부 꽤 best practice에 가까워야 한다는 점 때문에 꽤 골머리를 썩이고 있다. 다만 이걸 성심성의껏 진행해 보는 게 개인적으로도 좋은 challenge라는 느낌은 든다. 그 외에도 PS와 관련해서 시도해 보고 싶은 프로젝트들이 있긴 한데, 아직은 잘 모르겠다.

Conclusion

위에서 비슷한 얘기를 했는데, 내가 생각하기에 GM-IGM 구간은 다시금 문제 풀이 속도가 병목이 되는 구간이다. 그렇기 때문에 GM을 달성한 직후엔 IGM도 금방 가지 않을까 생각했으나… Hello 2024에서 3솔을 하는 끔찍한 사태를 마주했고, 마음이 꺾여 6개월쯤 코포를 거들떠보지도 않은 기간 때문에 예상보다는 오래 걸렸다. 다만 가능하다면 대회를 많이 치도록 하자. 보통 실전에서 푼 문제는 그 당시의 긴장감, 무게감 때문에라도 유독 기억에 잘 남는 편이니, 사실 효율로 따지면 제일 좋은 공부법이 아닐까 싶다.

이와 관련해서 motivating한 일화를 하나 말하겠다. 내가 망쳤던 Hello 2024에는 clamp function의 composition을 segment tree로 처리하는 것에 관련된 문제가 나왔었다. 당시에는 처음 보는 내용이었고, 조금의 진전도 없던 채로 대회가 끝났었다. 이후에 풀이를 읽었는데 꽤 신기해서 인상 깊은 문제였는데, 놀랍게도 이번 Good Bye 2024에 똑같은 내용이 나왔다! 그래서 시간을 아끼는 데 매우 큰 도움을 줬고, 그 뒤의 문제 하나를 추가로 AC를 받았을 때 대회 종료가 2분밖에 안 남았었으니, 이 문제를 몰랐다면 IGM 달성은 못 했을 것 같다.

목표를 향해 노력하는 모든 분을 응원한다! 이 후기가 그 과정에 어떤 형태로든 도움이 된다면 그것도 기쁠 것 같다. 글에 대한 피드백, 코멘트들은 언제든 환영이다.