코포 블루 달성

배치고사 완료

 

현대모비스 알고리즘 경진대회를 본 이후,

1) CP에 관심이 생겨서

2) 언젠가 한 번은 해보고 싶어서

3) 백준 아이디를 파랗게 칠하고 싶어서

코드포스를 좀 했습니다. 

총 6번의 round를 치루면 소위 '배치고사'가 완료되어 본인의 rating이 결정됩니다. 배치고사 이내 블루를 찍어서 다행입니다.

 

코드포스 문제 스타일 (DIv.2 기준)

A~D 공통

구현이 그렇게 중요하진 않습니다. 삼성 SW 테스트는 툭하면 한 문제당 코드 100줄이 넘어가는데, 그런 문제는 별로 없어요.

디버깅도 그렇게 중요하진 않습니다. 어차피 채점(실시간으로 작은 샘플인 pretest로 채점을 해 주는데, pretest 통과하면 왠만하면 system testing도 통과합니다.)도 해주고, A, B는 많이 틀릴 일이 없고, C, D는 몇 번 틀리냐보다도 푸냐 못푸냐가 중요해서... 

수학 문제가 좀 나옵니다: 많이 출제되는 날에는 Mathforces 소리를 듣기도 하더라고요.

'구성적' 스타일의 문제가 많습니다: 코테 위주로 알고리즘 공부한 분들은 많이 생소할 거예요.

일반적으로 A, B, C, D, E, F 총 6개의 문제가 나옵니다.

등수는 푼 문제 개수, 푼 문제에 대해 틀린 횟수 및 푼 시간 등의 요소로 결정됩니다.

 

A, B

 - round마다 다른데, 일반적으로 A랑 B는 난이도가 크게 차이나지 않아, 둘이 같이 묶었습니다.

 - 살짝의 수학적 감각을 기반으로한 애드혹, 그리디 문제가 주로 출제됩니다.

   - 대충 머리속으로 1~2줄이면 정당화를 할 수 있는 아이디어를 구현하면 됩니다.

 - 구현량이 얼마 안 되어(다만, 구현량 자체는 A와 B가 차이가 납니다), 맞는 아이디어를 도출해내기만 했다면 잘 안 틀립니다.

 - 블루를 가려면 (쉬운 B 기준) A, B를 합쳐서 20분 내로 풀어야 좋습니다: 만약 C 이후 문제를 푼다면 A, B 해결 속도가 크게 의미가 있진 않으나, 블루를 노리는 수준이라면 C 이후 문제를 못 푸는 날이 꽤 있습니다. 이럴 때, A, B를 빠르게 풀었다면 순위 방어가 됩니다.

 - 팁이라면, 괜히 꼬아서 생각할 필요가 없습니다. 애드혹 및 그리디한 접근('왠지 이렇게 하면 될 거 같은데...?'와 같은 생각)을 한 후, 맞는지 검증하여 구현하면 됩니다.

 

C

 - 일단 B보다 확 어려워집니다.

 - 대략적으로 N > 10만으로 주어져, naive한 O(N^2) 풀이 대신 O(NlogN) 풀이를 요구하는 문제들이 나옵니다.

 - 그래서 O(NlogN) 이하의 알고리즘이 많이 쓰입니다: 그리디(O(N)), 이분 탐색 N번하기, 세그먼트 트리 등...

 - 합쳐서 3솔하면 대략 민트라고 하는데, 저는 좀 빨리 푸는 편(+제가 본 round들이 좀 어려웠던 듯...)이라 블루 퍼포가 뜨네요.

 - 코테에 나오는 알고리즘 내의 범위에서 출제되긴 합니다. 그래서, 코테 준비한 분들은 C까지는 풀어볼 만 해요.

 

D

 - E보다는 C랑 난이도가 비슷하나, C보다 어렵긴 해서 생각이 잘 안 납니다.

 - 확정적으로 4솔하는 수준이면 퍼플을 가지 않을까 싶어요.

 

E 이후

 - 여기서부턴 '씹덕' 알고리즘을 좀 알아야할 겁니다.

 - 몰?루

 

하면 할 수록 재미있고 그렇긴 한데, 그만해야 할 거 같습니다. 그 이유로는,

- 솔직히 제가 이미 코테 수준보다는 알고리즘을 잘해서 PS에 많은 시간을 계속 투자할 이유가 없습니다. 

- 구현 + 디버깅 연습이 안 됩니다.

- 문제 풀이 방법이 프로그래머스 스타일 코딩테스트랑 상극입니다. 프로그래머스 문제는 N이 널널해서 N으로 알고리즘 유추도 잘 안 되고, 구현 많고, 디버깅 중요하고, 채점 안해주고... 코테 대비로도 좀 애매해요.

- 11시 35분에 한 round가 시작하여, 끝나면 1시 35분가 됩니다. 다른 사람 풀이도 보면서 채점이 다 끝나길 기다리면 대략 2시 반이 되고, 자려고 침대에 누우면 머리속에 editorial에서 본 풀이를 생각하면서 3시 넘어서 잠에 듭니다. 이러면 꿈에서 문제 풀면서 숙면을 취하지 못합니다. 잠도 잘 못자고, 너무 늦게 자고... 별로 안 좋습니다.

 

퍼플까지는 n(10<=n<=50)번의 라운드만 하면 도달할 거 같은데, 나중에 시간 나면 해볼까 합니다.

 

P.S.

마지막 round 개 잘 봤음ㄷㄷ 거의 퍼플급 실력