코드포스 블루, 퍼플 달성 후기 및 일지 & 공부법

 

(21.05.31 오렌지를 달성했습니다! https://rebro.kr/145) 

 

 

블루를 찍고 후기를 쓰려고 하였으나 정말 운이 좋게 빠르게 퍼플을 찍고 이제야 쓴다.

사실 아직 완전한 퍼플은 아니라고 생각한다.

오렌지, 레드도 아닌데 뭘 이렇게 난리를 치냐라고 생각할 수도 있지만... (약간 그렇긴 하다)

이 글을 쓰는 가장 큰 이유는, 내가 민트에서 블루를 가고 싶어서 몇개월동안 허덕일 때 정말 스트레스를 많이 받아서, 다른 사람들의 조언을 얻으려고 막 검색을 해봐도 다들 내 눈에 보이지도 않는 '오렌지, 레드 가는 방법'이나 아니면 정말 당연한 조언들뿐이었다. 

그래서 불과 한 달 전의 나처럼, 민트나 블루를 가고 싶어 하는 사람들이 매우 많다는 것을 알기 때문에, 혹시나 도움이 되지 않을까 싶어서 글을 써보려고 한다.  

 

물론 개인적인 기록, 되돌아보는 용도의 이유로도 글을 쓴다. 

 

그러므로 이미 블루 이상이신 분들은 개인적으로는 글을 안읽어주셨으면 좋겠다..... 민망하다..

 

 

  1. 일지

 

코포 시작 (2020. 05. 01.)

블루 달성 (2020. 10. 11.) : wogud6792.tistory.com/62

퍼플 달성 (2020. 11. 03.) : wogud6792.tistory.com/69

 

4월 중순부터 알고리즘 공부를 빡세게 시작하면서 코드포스도 같이 시작했다. 퍼플까지 6개월 걸렸다.

엄청 빨리 찍은 것 같지만 6개월간 코포 라운드에 virtual 포함해서 총 58번 참여했다. virtual 제외하면 45번 정도...?

정말 불가피한 날을 제외하고는 다 참여했고, 코포가 있는 날이면 약속잡기가 꺼려질 정도로 열심히 했다.

지금 생각해보면 오히려 레이팅이 잘 올랐다면 덜 열심히 했을 것 같다.

열심히 공부하고 문제를 아무리 풀어도 점수가 오히려 떨어지기만 하니 오기로라도 참가했었다.  

 

위의 계정 기록만 보면 되게 짧은 기간 안에 꽤나 쉽게 올라간 듯 보이지만 사실은 원래 계정이 있었다...

지금은 부계가 되어버린 계정이지만 새로운 마음가짐 겸, 'Rebro'라는 새 이름을 지으면서 계정을 새로 팠다. 

 

이게 그 계정의 기록이다..... 그래프만 봐도 수준이 어느 정도인지 보이지 않는가..?

딱 봐도 민트 하위 따리다. 불과 2달 전까지의 기록이다. 

 

 

1597점을 찍을 때까지만 해도 정말 좋았다. 이게 6월 중순이었으니 한 2달 가까이 된 시점이었는데, 공부를 하면 할수록 점점 레이팅이 올라가는 모습을 보이니까 내가 잘하고 있구나 하는 생각이 들었다. 블루는 당연히 시간문제라고 생각을 했다.

근데 기적처럼 그 뒤에 200점 가까이 꼬라박고 다시 원점으로 돌아왔다.

그 후에도 블루 직전까지 갔으나 역시나 자리를 찾아갔고 그 뒤에는 처음 할 때도 안 찍어봤던 점수로 끝없이 추락했다. 

지나고 보면 이 당시에 찍었던 높은 점수들은 단순히 한번 운이 좋아서 올라갔던 것이고, 실제 내 실력은 1400점대가 맞았다. 느꼈던 많은 문제점들이 있었는데 이는 뒤에서 언급하겠다. 

 

그렇게 최저 점수인 1333점을 찍고 계정을 갈아탔다. 

다들 뭔가 부르기 쉬운 핸들 이름을 가지고 있는게 부러워서 나도 하나 있으면 좋겠다는 생각에 계정을 새로 만들었고, 그린인 계정을 쓰기도 싫었다.

지금 생각하면 아주 잘한 선택인 것 같다. 

 

새 계정으로 시작한 코포는 꽤 성공적이었다.

이 시점부터 대회 performance가 1600 이상씩 찍히기 시작했고, virtual로 참가한 라운드는 더 높은 performance가 나왔다.

중간에 한 번씩 미끄러지긴 했지만, 예전엔 반대로 중간에 한번씩 잘했던걸 생각하면 많이 달라졌다.

어느 순간부터 확실히 실력이 늘어난 느낌을 받았고, 제일 하이라이트는 역시나 마지막 두 라운드다. 

 

그동안 div2에서 800등 안에도 들어보지 못했는데, 갑자기 8등을 해버렸다... 

 

 

C까지 풀었을 때 20등대 정도가 나와서 대박이다라고 생각하고 D는 어차피 못 풀 거 같으니 500~600등 정도는 나오겠다는 생각으로 마음을 비우고 D를 봤다.

근데 공책에 몇 분 슥슥해보니 바로 아이디어가 나와서 풀었고, standing에 5등이 찍힌걸 보니 내 눈이 의심스러웠다....

오픈 채팅방에서 같이 참여한 사람들의 축하를 받으니 이 맛에 코딩을 하는 건가 싶더라..

(칭찬을 즐기는 편)

 

사실 여기까지 하고 이 계정을 박제하려고 했다. 이 라운드 때는 운이 너무 따라줬고, 지금 수준에서는 절대로 더 올라갈 수 없다는 생각에 부계정도 이 정도 레이팅을 찍으면 도전해봐야겠다는 생각이었다.

그래서 부계로 다시 시작하려는 찰나에 raararaara님의 도전해보라는 한마디로 고민을 하다가, 더 도전해서 한 번이라도 떨어지면 그때 박제하자는 마인드로 참가했다. 그 결과는 성공적이었다. 

 

아직 진짜 퍼플이 아니라는 생각이 드는 이유도 이렇게 갑자기 올라가버린 탓이다.

서서히 올라왔다면 실력이 계속 늘어서 퍼플 수준까지 됐구나 하는 생각인데, 두 번 만에 올라와서 운이 많이 좋았다고 생각하고 아직은 블루 수준인 것 같다.

부계정도 퍼플을 단다면 그때서야 진짜 퍼플 실력이 나오지 않을까...

 

실제로 코포에 특화되어 있어서 백준에서 조금 어려운 문제를 풀 땐 블루 수준도 안 되는 기분이다... 요즘은 그래서 CP보단 어려운 (플래 이상) 문제들을 푸는 연습을 많이 하는 중이다. 

 

 

 

  2. 공부법

 

여기부터는 전적으로 내 개인적인 의견이다. 퍼플까진 아니고 블루를 노릴 수 있는 공부법 정도..?

필요한 부분만 참고했으면 좋겠다.

 

당연한 얘기겠지만, 공부법은 각자한테 맞는 걸 찾아가야 한다.

하지만 갈피도 못 잡는 상황이라면 타인의 공부법을 이용하는 것이 좋다고 생각하고, 또 이런 분들을 위해서 내가 줄 수 있는 팁..? 같은 것을 전달해보려고 한다. 

 

그러니 이미 블루 이상이신 분들은 자연스럽게 지나가시면 될 것 같다....

 

---

우선은, 내가 1500점을 못 벗어나서 스트레스도 많이 겪을 때 봤던 대표적인 조언들이 있었다. 

 

1. 코포는 코포로 공부해야 한다. 

 

이 말은 정말 맞는 말이다. 코포에 입문한 지 얼마 안 된 사람들은 대부분 코포의 문제 유형에 적응을 잘 못한다. 그래서 백준 문제나 다른 알고리즘 문제들만 풀다가 처음 코포 문제를 풀게 되면 A번부터 어려움을 겪는 사람들이 꽤 있었다. 

 

나도 이 말을 들었을 때, 매번 라운드마다 문제 유형이 다 다른데 코포 문제를 푼다고 새로운 라운드의 문제들을 풀 수 있는 게 맞나?라는 생각이 한동안 들었다.

특히나 코드포스에서는 ad-hoc 유형이 많이 나오기 때문이다. 그런데 어느 시점부터 새로운 문제를 보면 어떻게 푸는 유형인지 대충 눈에 보이기 시작했다.

결국 사람이 내는 문제이고, 언제까지나 항상 완전히 새로운 문제를 만들기는 쉽지 않다. 

 

지금 기억나는 예시로, 코드포스에서는 제한된 횟수 내에서 주어진 연산(operation)을 통해서 원하는 결과를 만드는 문제가 많이 나온다. 보통 이런 문제는 예시로 주어지는 연산 과정이 실제 정해와는 거리가 멀고 더 어렵다. 그래서 익숙하지 않은 사람들은 문제 예시대로 해결하려다가 못 푸는 경우가 많다.

나는 실제로 여기에 익숙해지니까 본문에 나온 과정을 크게 신경 쓰지는 않게 된다. 

 

예를 들어 만약 "N개의 원소가 나열된 배열이 주어질 때, 주어진 연산을 '최대 2N번' 수행해서 원하는 결과를 만드시오"와 같은 문제가 주어지면, 주로 정해가 딱 2N번 수행하거나 혹은 2N-1, 2N-2 등 제한에 딱 맞는 횟수이다.

그럼 원소가 N개이니 각 index당 2번씩 접근해서 가능한가? 혹은 한 index를 N번 연산하고, 다른 나머지 N-1개의 index를 1번씩 연산해서 가능한가? 같은 생각에 도달하기가 쉽다. 

이런 것들이 경험을 통해서 얻을 수 있는 것이다. (물론 당연히 100%는 아니다)

 

그래서 일단 기본적으로 열리는 라운드들은 참가를 하거나, virtual을 통해서 빠짐없이 참가하는 것을 권장한다. 실제로 나는 항상 평일에 6시 40분 기상을 해야 하는 상황이지만, 잠을 줄이고 매 라운드를 참가했다. (이젠 좀 쉴 예정....)

 

 

2. 자기 레이팅에 맞는 난이도의 문제들을 골라서 풀어라.

 

이 의견을 많이 봤는데, 나는 이용하지 않았다.

코포 사이트에서 Problem set을 들어가면 난이도별로 문제를 선별할 수 있다.

사람마다 다르겠지만 개인적으로는 난이도별로 문제를 미는 것보단 한 라운드별로 virtual 참가를 하는 게 더 좋은 것 같다. CP 특성상 문제를 빠르게 푸는 것이 많이 중요하고, 또 등수도 확인하면서 자기 수준을 특정할 수 있기 때문에 시간 여유가 된다면 2시간을 잡고 한 라운드를 푸는 것을 권장한다. 

 

codeforces-anytime.firebaseapp.com/

이 사이트에 아이디를 등록해두고 virtual로 참여하면 실제 라운드에서의 등수와 performance, 레이팅 변화를 알려준다. 

이를 통해서 내 수준이 어느 정도인지 계속 파악하면서 개인적인 문제점이 뭔지 찾아가면 많은 도움이 된다. 

 

 

3. 업솔빙(up-solving)이 중요하다. 

 

맞다. 정말 정말 중요하다. 내 레이팅 상승의 가장 크게 영향을 준 방법이 아닌가 싶다. 

업솔빙은 대회가 끝나고 못 푼 문제를 다시 풀어보는 걸 말한다. 

세 라운드에 단순히 참여하는 것보다 한 라운드를 제대로 업솔빙하는게 훨씬 공부가 많이 된다고 생각한다. 

 

정말 멍청하게도 처음 한 2달간은, 라운드가 끝나고 풀다가 실패한 문제는 해설 보고 이렇구나~ 하고 끝냈다. 2시간짜리 라운드에 참여하면 끝나고 복습은 30분 정도..? 이러니 당연하게 새로운 문제가 나오면 또 못 푸는 악순환이 계속됐다. 

그래서 업솔빙을 제대로 하고 나서 한 1~2달정도 지나니 실력이 늘어나는게 몸으로 느껴졌다. 

 

일단 기본적으로 업솔빙을 하는데 라운드 시간의 2~3배는 쓰는 걸 권장한다.

내가 업솔빙한 과정은 이렇다.

 

1) 못 푼 문제 다시 풀어보기

  - 2시간이 넘어가도 안 풀리면 그 문제는 2일 고민해도 안풀릴 확률이 높다. 바로 해설을 참고

2) 해설 참고하고 정답 코드는 보지 않고 풀기

  2)-1. 그래도 안풀리면 해설 코드 살짝 보고 풀기  

  2)-2. 그래도 안풀리면 해설 코드 그대로 따라서 코드 작성해보기

3) AC를 받았다면 다른 사람들 코드 보기

 

나는 다른 사람들의 코드를 보는 것이 제일 공부가 많이 되었다. 해설만 보는 것과 차원이 다르다.

기본적으로 외국인들의 코드는 보기가 힘들어서 한국인 레드나 오렌지 코더의 코드를 많이 참고했다. 지인이 풀었다면 지인의 코드를 확인해도 좋다.

다른 사람들의 코드를 보다 보면 나는 생각지도 못한 풀이인데, 공통적인 풀이가 꽤나 있다. 이런 부분은 고수들은 다 아는 일명 웰논(Well-known)이라 불리는 알고리즘이나 구현 방식인 것이다. 다른 문제들에서도 많이 쓰이니 다들 비슷한 코드를 작성한 것이 아닐까? 

이런 코드들을 잘 익히고, 모르는 개념이면 구글링 해서 공부하고, 까먹을까 싶으면 메모도 해두면 실력 상승에 많은 도움이 된다. 

 

실제로 나는 스위핑 하는 방법이나, 큰 수 조합 구하기(8등찍은 라운드에 큰 영향을 주었다) 등을 코포의 다른 사람 코드를 보고 배웠고, 아직도 정말 유용하게 잘 쓰고 있다. 

 

 

4. 기본 알고리즘(dp, greedy, dfs/bfs, binary search...)만 알아도 블루, 퍼플은 찍는다. 

 

한 70프로 정도는 맞는 말 같다. 정말로 기본적인 알고리즘만 아는 상태에서 블루 이상을 찍은 사람은 사실 소수라고 생각한다. 문제를 풀 때 대부분 이런 기본적인 알고리즘만 이용했기 때문에 이런 말들이 나오지 않았을까..?

그럼 다른 고급 알고리즘을 꼭 배워야 하나? 그건 또 아니다. 

 

"???????????????????????"

 

실제로 세그 트리나, suffix array, dp 최적화 같은 고난도 알고리즘은 div2에서는 거의 나오지 않는다. 대신에 이런 알고리즘들을 알고 있다면, 그 알고리즘 속에 담겨있는 여러 구현 과정을 문제 풀이에 이용할 수 있다. 

 

고수들에게 종종 이런 말들을 들을 수 있다.

"세그 트리처럼 풀었어요" , "LCA처럼 풀었어요", ~~

이 말들이 꼭 세그 트리나 LCA를 이용했다는 것이 아니라, 그 속에서 이용되는 작은 구현들이나 아이디어를 문제풀이에 이용했다는 것이다. 그럼 결국 문제 유형이 세그 트리와 LCA가 아니라 tree, dfs이고, 이것 역시 기본 알고리즘 유형 문제이지 않은가? 

 

즉, 고급 알고리즘을 요구하는 문제는 나오지 않지만, 알고 있다면 다른 문제들을 풀 때 영향을 줄 수 있다는 의미이다. 물론 확률은 낮다. 하지만 한문제마다 레이팅 변화가 큰 코포에서는 그거 하나때문에 아이디 색이 달라질 수 있다. 

대신, 어설프게 알고 있다면 오히려 악영향을 줄 수 있다.

 

실제로 겪은 경험인데, '이분 매칭'에 대해서 미리 작성해둔 코드만 있고 어떤 개념이다 정도만 아는 상태였다. 그리고 코포 문제로 이분 매칭스러운 문제가 나와서 "내가 배운거다!" 하고 수십 분 동안 코드를 작성했는데, 알고 보니 V와 E가 10만이 넘는 문제였다. 이분 매칭의 시간 복잡도를 제대로 알지 못한 상황에서 써먹으려다가 손해본 것이다.  

 

물론 lazy seg, Suffix Array, splay tree, CHT, HLD, FFT 등등 아주 어려운 알고리즘을 공부하라는 의미는 아니다. 오렌지, 레드 이상이 된다면 모를까. 실제로 나 또한 이 알고리즘을 모른다.

하지만 굳이 배척할 필요는 없고, 적어도 플래티넘 급의 알고리즘들의 구현 과정을 잘 알고 있다면, 다른 쉬운 문제들을 풀 때 도움이 될 수 있을 것이다. 꼭 이용되지 않더라도 개인의 구현 능력 자체는 증진되지 않을까...

 

참고로 개인적으로 꼭 필요하다고 생각되는 알고리즘들은 Math, DP, Greedy, DFS/BFS, Prefix sum, 기본적인 tree 개념, Disjoint-set union, Binary-search 정도이다. 적어도 퍼플에 도달하기 까지는.

 

---

추가적으로 라운드에 참여할 때 생각하면 좋을 것 같은, 내가 전달하고 싶은 팁이다. 

 

1. Div.2의 A, B번은 생각보다 쉽다.

 

Div.2의 A와 B, 더 나아가 쉬운 C번까지는 코드가 길어봤자 10~15줄이다.

그런데 주변의 그린 이하이신 분들의 틀린 코드를 보면 쉬운 문제임에도 불구하고, 지나치게 긴 경우가 자주 있다.

이런 경우에는 맞추면 정말 다행인 것이고, 틀리면 수정하기가 되게 힘들고 뇌절하기 쉽다.

초반 문제는 직관적인 아이디어를 요구하는 문제가 많고, 그 아이디어를 안다면 코드의 길이가 매우 짧기 때문에 나 같은 경우는, 만약 라운드 도중 코드가 20~30줄이 넘어간다면 코드를 짜는 것을 멈추고 다시 풀이 방법을 생각해본다. 

 

 

2. 연필로 풀어보는 습관을 가지자.

 

딱 보고 바로 풀이가 떠오를만한 문제를 제외하고는 무조건 손으로 풀어보는 걸 권장한다.

손 코딩을 하라는 의미는 아니고, 예시를 만들어서 어떤 과정으로 답이 나오는지를 그려보라는 의미이다. 

나도 손으로 써보는 습관을 가지려고 계속해서 노력하는 중이지만, 최근 두 라운드에서 레이팅이 급격하게 오른 이유 중 하나는 이전 라운드와는 다르게 코드를 짜기 전에 손으로 대충 풀어보고 작성을 했다. 

그전까지는 코드를 짜면서 머릿속으로 구현하다가 WA를 받으면 그때부터 손으로 다른 예시들을 만들어 봤었는데, 공책으로 푸는 5분의 시간이 1번의 WA보다 덜 손해인걸 알게 되면 그 시간이 크게 아깝지 않게 느껴진다. 

 

 

3. 현재 푼 사람의 수를 확인하자. 

 

거의 대부분의 라운드는 난이도 순서대로 문제가 배치가 되어있지만, 가끔씩 그렇지 않은 경우가 있다. 

이런 경우는 지금 이 문제를 푼 사람 수를 확인하는 것이다. 

예를 들어서 C번이 안 풀려서 현재 스코어보드를 확인하니 C번은 2000명이 풀었고, D번은 500명이 풀었다. 

이러면 당연히 D가 더 어려워서 D도 못 풀 확률이 높으니 C에 좀 더 투자를 해본다. 

만약 C를 2000명이 풀었고 D를 1300명이 풀었다면, D도 꽤 풀만하다는 의미이기 때문에 개인적으로 마지노선 시간을 정해놓고, 그 시간까지 못 풀면 D로 넘어간다. 

만약 C를 2000명이 풀었고 D를 2500명이 풀었다면, D가 C보다 쉽다는 의미이다. 그러므로 빠르게 D로 넘어간다. 

 

다른 경우로 B는 원래 쉬운데 이 문제는 도저히 안 풀려서 봤더니 현재 푼 사람이 여전히 1000명 이하이다. 그러면 이번 라운드의 B는 어려운 문제인 것이다. 

만약 푼사람이 5000명이 넘어갔다면, 풀이가 정말 간단한데 떠올리지 못하고 있을 확률이 매우 높다. 

 

이처럼 현재 푼 사람 수를 이용해서 문제풀이 전략을 세울 수 있다.

CP는 항상 상대평가이기 때문에, 단순히 3솔이 목표다! 4솔이 목표다!라고 하기보단, 자신만의 기준을 잡아서 라운드마다 전략적으로 참가하는 게 레이팅 상승에 도움이 될 수 있다. 

만약 지금 div2에서 표본이 작다면 동시에 열리는 div1의 동일한 문제의 푼 사람 수를 확인할 수도 있다.

 

 

4. 잔머리를 굴리자.

 

다른 사람도 이용하는 방법인지는 모르겠으나... "그 정도까지 한다고?"라고 생각할만한 나만의 방법이 있다. 

 

코드포스에선, 대회 도중에는 당연히 다른 사람들의 코드를 볼 수 없지만 status에서 제공하는 정보가 있다. 

바로 메모리와 시간이다. 

 

풀이가 전혀 떠오르지 않는 어려운 문제인 경우에 status를 들어가서 맞은 사람들의 메모리 크기나 시간을 확인한다. 

각자 다르겠지만 그래도 비슷한 값들이 나올 때에는 이 값을 가지고 어느 정도의 크기만큼 배열이나 벡터를 잡았구나, 이 정도 시간이면 시간 복잡도가 이거구나 등의 힌트를 간접적으로 얻을 수 있다.

 

예를 들면 N = 1000인 배열을 이용해서 문제를 푸는데 맞은 사람들의 메모리 크기를 보니 int 변수 100만 개가 차지하는 크기만큼 이용이 됐다. 그러면 1000*1000 만큼의 배열을 선언해서 문제를 풀었지 않을까? O(N^2) dp인가? 대략 이런 식이다. 

 

사실 이 방식 때문에 결정적으로 문제를 푼 경우는 거의 없다. status를 확인하는 순간 이미 이 문제는 못 풀 확률이 매우 높은 상황이기 때문이다. 그래도 뭐...안풀리면 뭐라도 해봐야지..

 

---

6개월 동안 고군분투하면서 얻어낸 경험들이지만 사실 나조차도 제대로 따르고 있는지는 모르겠다. 지극히 개인적인 의견이지만 만약 레이팅 올리는 방법을 찾다가 이 글을 봤다면 꼭 도움이 됐길 바란다.... 다들 블루, 퍼플, 그 이상까지 올라가기를...!