이게 무슨 해괴망측한 소리일까요?
이 글은 알고리즘 문제해결 트레이닝에 대한 사견私見입니다.
지금부터 전제를 하나 합시다.
- 밥 먹고 알고리즘 공부만 하면 얼마나 걸릴지는 몰라도 언젠가는 코드포스 레이팅 3,000이 될 겁니다.
뭐, 세상에는 레이팅이 3,000을 넘는 괴물들도 다수 있지만 일단은 이론적으로 밥만 먹고 문제만 풀면 언젠가는 3,000에 갈 수 있다고 합시다. 사람마다 걸리는 시간은 다르겠지만요. 이를 근거로 공부한 시간 $t$에 대한 실력 $f$를 아래와 같이 모델링해 봅시다.
\[f\left(t\right) = 3\ 000 \left(1-a^t\right)\]
하지만 실력은 올라가기만 하는 건 아닙니다. 어떤 날은 컨디션이 좋아서 머리가 잘 돌아가고 문제가 잘 풀릴 수도 있는 반면 어떤 날은 피곤하거나 우울하거나 뭐 물리적으로는 손가락이 아프다거나 할 수 있죠. 그렇기 때문에 조금 더 정확하게 실력을 모델링하려면 노이즈를 끼워야 할 겁니다. 대충 아래와 같은 모델은 어떤가요?
\[f\left(t\right) = 3\ 000 \left(1-a^t\right) + b \sin \left(ct\right)\]
좋습니다. $t$의 스케일이 얼마일지는 모르겠지만 이게 우리의 현재와 미래 실력을 대략적으로 모델링해준다고 합시다. 믿어 주세요.
하지만 제 레이팅은 계속 제자리인걸요
위 그래프에서 어떤 사람이 레이팅 1,400에서 1,600까지 가는 여정만을 한 번 살펴봅시다.
아마 가장 먼저 드는 생각은 이거일 거예요. ‘실력은커녕 내 그래프는 이거랑 비슷하지도 않은데…’ 맞아요. 쉽게 와닿지 않죠? 하지만 제가 여기에다 점을 몇 개 찍어볼게요.
… 어떤가요, 있을 법한 그래프이지 않나요? 운이 정말 나쁘다면 이런 경우도 가능할 거구요.
이 그래프의 주인공은 과연 영영 파란색 닉네임을 달지 못하게 되는 걸까요? 우리는 결국에는 1,600이 될 거라는 사실을 알고 있지만, 점선을 지우고 나서 이게 자신의 그래프라고 생각한다면 정말 슬플지도 모르겠네요…
대회는 실력의 샘플링에 불과하다
여기서 중요한 관찰이 하나 있습니다.
우리가 모델링한 실력 그래프와 코드포스 레이팅 그래프 사이에는 큰 차이점이 있습니다. 우리 그래프는 연속적이지만 코드포스 그래프는 그렇지 않다는 점입니다. 이는 ‘대회’라는 시스템의 본질에서 기인합니다.
대회는 우리 실력이 지금 이 순간 어땠는지만을 알려주지, 실력을 실시간으로 알려주지는 않습니다.
이게 왜 큰 차이냐면, 코드포스 레이팅 그래프가 우리의 실력을 정확하게 말해주지 않는다는 뜻이기 때문입니다.
한 마디로, 대회는 실력의 샘플링에 불과합니다. 심지어 샘플링 주기가 짧지도 않습니다. 그래서 사실 그래프에 찍힌 점들만 보고 거시적으로 어디로 갈지 예측하는 건 불가능에 가깝습니다. 위에서는 실력 기복을 $b \sin ct$라고 퉁쳤지만 사실 그렇지도 않을 거구요.
게다가 보통 한 대회에는 문제가 6개밖에 없기 때문에, 모든 분야가 고르게 출제될 수도 없으며, 운 나쁘게 내가 자신없는 분야가 출제되어서 평소보다 못 풀 수도 있습니다. 다시 말하면 샘플링 자체도 그렇게 완벽하지는 않습니다.
문제 수 이야기가 나와서 말인데 레이팅 말고 대회에서 해결한 문제 수로 바꿔서 생각해 볼까요? 코드포스에서는 몇 문제를 풀었는지가 레이팅을 결정하는 중요 요소로 작용하죠. 하지만 푼 문제 수는 보통 한 자리 정수입니다. 굉장히 이산적인데요, 대회마다 나오는 문제의 난이도가 일정하다고 하면, 위에서 만든 실력 모델링 그래프는 대략 아래처럼 됩니다.
똑같은 3솔브여도, C를 간신히 해결한 3솔브와 D를 다 생각했는데 시간이 약간 부족해서 못 푼 3솔브는 다를 겁니다. 여유롭게 3솔브를 하고 아깝게 4번째 문제를 못 풀었다면 적어도 간신히 3솔브를 했을 때보다는 확실히 성장했을 테지만, 결과적으로 스코어보드에 보이는 건 똑같이 세 개의 초록색이겠죠.
마지막으로, 코드포스의 레이팅 공식조차 실력을 완벽하게 표현해 주지는 못합니다. 코드포스의 공식은 마지막으로 친 대회 결과에 상당히 큰 영향을 받도록 설계되어 있습니다. 최근 5개 정도 대회만 실력을 유의미하게 반영해 주는데요, 연속적으로 운이 좋거나 나쁘면 아예 색깔이 바뀔 수도 있는 시스템이라 평소 실력을 제대로 반영해 주지 못합니다. 관련해서는 djm03178님의 Codeforces 레이팅에 관련된 글을 읽어 보면 좋습니다.
그러니까 문제를 평소보다 못 풀어도 괜찮고, 레이팅이 떨어지더라도 괜찮아요. 애초에 그게 진짜 본인의 실력은 아닐 거예요.
그래서 목적지는 레이팅이 아니다
라고 말하고 싶습니다. 바꿔 말하자면, 레이팅은 진짜 실력이 아니고, PS 실력을 키우는 것과 레이팅을 올리는 것은 비슷해 보이면서도 다르다고 생각합니다.
물론 색깔을 바꾸기 위해 알고리즘 문제해결 공부를 하는 것도 정말 멋진 일입니다. 하지만 그 과정이 정말 지치고 힘이 든다면, 레이팅은 좋은 목표가 아닐지도 모릅니다.
하지만 실력을 키우면 레이팅은 자연스럽게 올라갈 거예요. 이런 마음가짐을 가지고, 대회를 충분히 많이 치면 언젠가는 목표하는 레이팅이 될 수 있다는 희망을 갖고, 나 자신의 가능성을 믿도록 합시다.
조금 현실적인 조언
- 업솔빙 / 문제 수를 목표로 하기 — 그래도 해결하는 문제 수는 레이팅보다 직관적이면서도 그렇게 많이 변하는 값은 아니기 때문에 목표로서 유의미하다고 생각합니다.
문제 레이팅을 목표로 하는 것과 맥락을 같이하는데요, 대회에서 풀었던 제일 어려운 문제의 다음 번 문제를 해결하려고 시도해 봅시다. 모르겠다면 에디토리얼을 보고 인사이트를 얻어갑시다. 아까운 실수로 틀렸다면 너무 자책하지 말고 오히려 자신을 격려해 줍시다. 뼈아픈 실수일수록 반복하는 일이 적을 거예요. 궁극적으로는 대회에서 해결할 수 있는 문제 수를 늘리는 것을 목표로 합시다. - 문제 레이팅을 목표로 하기 — 문제 수를 목표로 하는 것과 맥락을 같이합니다.
코드포스 대회가 끝나면 Problemset에 문제 레이팅이 공개됩니다. 목표 문제 레이팅 $r$을 정해 두고, 대회가 끝난 후 $r$ 이하의 문제들을 풀어보는 것으로 단련해 봅시다. 궁극적으로는 대회 시간 내에 $r$ 이하의 문제들을 안정적으로 풀 수 있는 것을 목표로 합시다. - 버추얼 컨테스트 돌리기 — 코드포스에는 끝난 대회를 가상 참가할 수 있는 기능이 있습니다. 또 가상 컨테스트 참여로 가상 레이팅을 계산할 수 있는 서비스도 있습니다. 이 서비스를 활용해 가상 컨테스트를 자주 치면 실력도 단련할 수 있고, 앞서 언급한 샘플링 주기의 문제도 어느 정도 해결할 수 있겠죠.
- Atcoder — 일본 기반의 알고리즘 대회 사이트입니다. Atcoder는 코드포스의 레이팅 공식과 달리 현재까지 참여한 모든 대회의 퍼포먼스를 가중평균하는 식으로 레이팅을 계산하기 때문에 참가자의 평소 실력을 좀 더 잘 반영한다고 생각합니다. 게다가 문제도 코드포스보다 훨씬 깔끔하며, 시스텟이 없고, 무엇보다 시간대가 같아서 주말 오후 9시에 부담없이 참여할 수 있다는 장점도 있습니다. 강력하게 추천합니다.
- 팀 연습 하다 오기 — 조금 더 긴 시간 동안 더 어려운 문제들에 대해서 생각해볼 수 있는 좋은 방법입니다. 새로운 인사이트를 얻을 수 있습니다.
- 당분간 쉬기 — 너무 지쳤다면 괜찮아질 때까지 쉬어도 괜찮습니다. 알고리즘은 잊고 놀러 나가서 맛있는 거 먹고 옵시다. 금방 다시 회복할 수 있을 거예요.
알고리즘 문제해결이 여러분을 마음고생시키지 않았으면 좋겠어요. 여러분의 문제해결을 항상 응원합니다.
