CP, CodeForces 가이드
본 글에서는 CP와 CodeForces에 대한 가이드를 제시한다.
CP (Competitive Programming) 이란
CP보다는 PS(Programming Solving) 이라는 단어가 훨씬 익숙할 것이다. 사실 두 개의 단어는 꽤 많이 혼동되고 있고 사람마다 사용하는 의미가 다르다. 흔히 우리가 알고리즘 문제를 푸는 것을 PS라고 하며, CP는 말 그대로 빠르게 코드를 짜야 하는 “경쟁적 코딩” 이다. 개인적으로는 다음과 같이 생각하고 있고, 앞으로 이 블로그에서도 이렇게 사용할 예정이다.
- PS는 알고리즘 문제 풀기, CP는 그 중에서 빨리 짜야 하는 경우
- CP의 예시: 코테 (코딩테스트), CodeForces Contest 등등
- CP는 PS에 포함되는 용어
그러나 CP랑 PS를 구분하지 않는 경우도 다반수이며, 포럼에도 이런 토론이 많이 올라와 있다. 이 블로그의 게시글에 의하면, 일본과 중국의 경우에는 어느 정도 통일된 용어가 이용되는 것 같다. 필자는 그래도 느긋하게 고민하면서 백준 푸는 거랑, 최대한 빠르게 코드를 짜는 CodeForce Contest에는 확연한 차이가 있는 것 같아서 나누어 부르려고 한다.
CodeForces 이란
CodeForces는 정확히는 알고리즘 대회가 열리는 사이트이고, 이 대회를 그냥 CodeForces 대회라고 보통 부른다. 본인 블로그의 이 글에서도 등장한다!
레이팅과 Division
우선 레이팅이라는 것이 존재한다. 게임에서의 MMR(Matchmaking Rating)과 유사한 개념이라고 생각하면 편하다. 참여한 대회의 상대적인 성적에 따라 이 레이팅이 변동한다. 레이팅 등급에 따라 색깔이 부여되며, 아래의 표와 같다. 백준에서 이름에 색깔이 입혀진 경우를 본 적 있을텐데, 백준에서 CodeForces와 연동을 하여 이 등급 색깔이 백준에 표기되는 것이다.
첫 Contest를 보면 1400점에서 시작하며, 점수가 떨어지지 않는다면 저 민트색이 된다. 몇 번 더 점수를 올리면 파랑이가 될 수 있다. 개인적인 목표는 바이올렛이다! 바이올렛은 상위 7%에 해당하니, 롤로 따지면 플레4 정도에 해당한다. 플레 정도면 어디가서 롤 좀 한다고 말할 수 있지 않나?ㅎㅎ
위의 표를 보면 Division 이라는 것이 있는데, 이는 대회 난이도라고 생각하면 된다. 바이올렛이 되어야 Division 1에 참가할 수 있으며, Division 1 부터는 복잡한 개념들과 어려운 알고리즘들이 등장한다. 다른 말로 말하면, Division 2와 3에서는 어려운 알고리즘들이 등장하지 않는다. 이 블로그의 게시글에 의하면 퍼플까지 Math, DP, Greedy, DFS/BFS, Prefix Sum, 기본적인 Tree 개념, Disjoint-set Union, Binary Search 정도만 알아도 충분히 도달할 수 있다고 말한다. 또한, 고급 알고리즘을 요구하는 문제는 나오지 않지만 알고 있다면 다른 문제들을 풀 때 영향을 줄 수 있다고 언급한다. 즉, 고급 알고리즘들의 작은 구현들이나 아이디어들은 이용할 수 있는 것이다. 역시 아는 만큼 보인다!
대회 참가
굉장히 대회가 자주 열린다. 일주일에 최소 두 번 정도? CodeForces 사이트의 Contest 탭에서 다음 대회 일정을 확인 및 Register 할 수 있다. Register는 시험 시간 24시간 전부터 가능하며, 대부분의 시험은 우리나라 기준 23:35 ~ 01:35 의 2시간동안 이루어진다.
필자는 2021.02.16 일자의 Codeforces Round #702 (Div.3)을 처음으로 도전할 예정이다. 본의 아니게 Division 3부터 시작하게 되었는데, 맛보기 느낌으로 시작하면 될 것 같다 ㅎㅎ (Division 3이 Division 2보다 쉽다)
[2021.02.18] Codeforces Round #703 (Div.2)을 처음으로 시작하였다!
대회 규칙
대회는 보통 A ~ E 나 A ~ F 의 5~6 문제로 이루어진다. 보통 쉬운 난이도가 앞쪽에 배치되어 있는데, 그렇지 않을 때도 있다. 보통은 푼 사람 수가 실시간으로 뜨기 때문에, 이를 이용해서 쉬운 문제를 먼저 접근해 보는 것이 유리하다.
문제의 점수는 A부터 점점 올라가며, 시간이 지날수록 점차 감소한다 (1분이 지날때마다 2점씩 감소). WA(Wrong Answer, 틀렸습니다)를 받을 때마다 50점이 감소한다(원래 문제 점수의 30% 아래로는 떨어지지 않는다). 이 점수 체계가 빠르고 정확한 문제풀이를 요구한다. 참고로, 기존의 코드 복붙 제출이 가능하다.
또한, 꽤나 복잡한 Hack이라는 시스템이 있다. 우선, 대회 시간 내에 채점을 할 때는 대략 15개 정도의 테스트 케이스(Pretest)만 이용한다. 따라서 실제로 코드가 완벽하지 않더라도 Accepted가 될 수 있다. 다른 참가자의 Accepted 된 코드에서 에러를 일으키는 반례 테스트 케이스를 찾는 것을 Hack 이라고 한다. Hack에 성공하면 100점을 얻고, 실패하면 50점을 잃는다. (단, 컴파일 에러나 아예 첫 번째 테스트 케이스부터 오답이 발생하면 점수가 차감되지 않는다). Hack을 하기 위한 조건은 다음과 같다.
- Hack을 할 대상이 나와 같은 Room (대회에서 임의로 배정해 주는 그룹)에 있어야 한다.
- 내가 Pretest에 통과한 문제이고 Lock을 해야 한다. Lock은 Pretest에 통과한 문제의 제출을 더 이상 하지 않겠다는 선언이다. Lock을 해야만 다른 사람의 코드를 보고 Hack을 시도할 수 있다.
Hack을 당하면 CodeForces 사이트에서 알람이 온다.
만약 Lock을 하지 않았다면 오류를 고쳐 재제출을 해야 할 것이고, Lock을 이미 했다면 어쩔 수 없이 틀린 문제가 된다. 조금 덧붙이자면, Hack을 당하지 않도록 코드를 의도적으로 지저분하게 적는 것은 결국 자신에게 손해이다. 빨리 Hack을 당해야 고쳐서 제출할 수 있기 때문이다. Hack이 될 코드는 어차피 System Test에서 걸러진다는 뜻
대회가 모두 끝난 이후, Pretest를 통과한 코드들에 대해 60개 이상의 테스트 코드로 재채점이 이루어진다(System Test). 이 System test가 통과해야 비로소 해당하는 점수를 받는다.
Virtual Contest
기존에 시행되었던 대회를 “실제로 시험장에 있었던 것처럼” 참여할 수 있다. 지나간 대회에서 Virtual Participation 을 누르면 된다. 2시간을 똑같이 재고 풀게 되며, 시험장 기준으로 현재 등수도 확인할 수 있다! 개인적으로 CodeForces 사이트에서 가장 마음에 드는 기능이다.
CP 용어 정리
업솔빙 (Upsolving)
대회가 끝난 후에 문제를 푸는 것. 실제로 업솔빙을 해야 실력이 효율적으로 는다는 의견이 굉장히 많다.
AC
Accepted, 맞았습니다! 를 의미. 보통 초록색
WA
Wrong Answer, 틀렸습니다 를 의미. 보통 빨간색
TLE
Time Limit Exceeded, 시간 제한 초과
MLE
Memory Limit Exceeded, 메모리 제한 초과
RE
Runtime Error, 런타임 에러 (접근 불가능한 영역에 접근하는 경우가 대부분)
CE
Compile Error, 컴파일 에러
올솔
All Solve로, 모든 문제를 풀었다는 뜻이다.
맞왜틀 / 틀왜맞
맞았는데 왜 틀려, 틀렸는데 왜 맞아 를 의미.
좌셋
모든 문제가 풀렸으면서, 모든 문제를 푼 사람은 없는 문제 셋을 의미.
모든 문제가 풀렸기 때문에 대회 시간 내에 풀 수 있는 문제들이라는 뜻이며, 모든 문제를 푼 사람은 없기 때문에 변별력이 있었다는 뜻이다. 좌셋은 성공적인 대회, 좋은 대회의 기준이 되기도 한다.
CP, CodeForces 가이드
http://yxxshin.github.io/2021/02/16/2021-02-16-CodeForces-Manual/
