1300 정도 되면 해당 색깔에 안착했다 판단하고 글을 쓰려고 했는데 대박이 터져서 지금 쓰게 되었다.
왜 써요?
인터넷에 검색하면 코드포스 블루 가는 법은 인기가 많은데 앳코더 민트 가는 법은 글 자체가 없어서 쓴다.
앳코더 민트도 충분히 가기 어렵다... 여기 통계에 따르면 앳코더 민트는 코드포스 블루와 동동하다고 여긴다.
그래서 앳코더를 널리 추천하고 싶기도 하고 나처럼 코드포스가 아니라 앳코더를 목표로 공부하는 사람들에게 도움이 되라는 뜻으로 부족하지만 글을 쓴다.
물론 코포 퍼플이나 앳코더 블루 이상이신 분들은 코웃음 치면서 넘기면 된다.
민트를 어떻게 달았는가?
사실 본인은 민트를 허무하게 찍었다.
AtCoder Beginner Contest 258을 보면 등수가 418로 확 튄 것을 볼 수 있다.
스코어보드로 보면 더 가관이다. E, F를 재끼고 G를 풀었다.
일이 왜 이렇게 되었냐 하면 D에서 조금 실수를 하고 B를 59분에서야 풀어 망한 냄새가 스멀스멀 올라왔는데 우연히 등수를 확인하다 이상하리만큼 G가 많이 풀린 것을 발견하고 읽어보았다.
그런데 어라? 빅데이터 수업 때 나왔던 프로젝트였다. 바로 삼각형 찾기.
당시 하둡에서 삼각형을 찾기 위해 갖은 고생을 했던 나는 그때의 검색 기억을 살려 비트셋 최적화로 $O(\frac{N^3}{64})$에 푸는 방법을 다시 찾아냈고 그렇게 AC를 받아버리게 된 것이다. 그렇게 1600점을 얻고 민트가 될 수 있었다.
여기까지만 보면 "이새끼 순 뽀록 아니냐?"라고 할 수 있겠지만 그래도 지금은 저거보다 더 올랐으니 이 정도는 귀여운 해프닝으로 봐주면 감사하겠다.
앳코더의 특징과 코드포스와의 차이
앳코더의 레이팅을 집중적으로 올리고자 하면 앳코더에 대해 이해하고 코드포스와 어떤 차이가 있는지 살펴보는 게 좋을 것이다.
앳코더를 잘 모를 때 읽으면 좋다. 이미 알고 있으면 이 문단은 넘어가도 무방하다.
영어 지문이 읽기 쉽다
당장 코포랑 앳코더의 아무 문제 가져와서 비교해도 앳코더가 더 읽기 쉽다. 따라서 문제 이해도 편하고 풀기도 편하다. 다만 문제 번역도 일본 사람이 하는 거 같은데 조금 이상하게 되었을 경우 더 헷갈리게 된다.
이에 대해선 교수님이 전에 했던 말을 인용한다.
한국인이 쓴 영어가 한국인에게 잘 읽히는 이유는 같은 교육권에서 교육을 받았기 때문에 읽는 한국인에게도 익숙한 방법으로 작성되고 수준 역시 눈높이에 맞기 때문이다.
아마 일본도 우리나라랑 가까이 있기 때문에 우리 역시 읽기 쉽지 않나 하는 사견이다.
Hack 시스템이 없다
앳코더에는 hack 시스템이 없어 콘테스트 결과가 당일 내로 반영되고 "내가 맞았다."는 결과를 보장받게 된다.
그러면 만약 테스트 케이스가 약하면 어떻게 될까? 그냥 인정해준다. 무자비하게 핵을 당할 수 있는 코포와는 달리 너그럽게 들여보내 준다.
데이터가 명백히 약한 경우에는 콘테스트가 끝난 뒤 after_contest라는 이름의 보강 테스트 케이스가 새로 추가돼서 추가된 이후에 제출을 할 경우에는 after_contest까지 채점을 하게 된다.
레이팅 변화가 코포에 비해 아주 느리다
이게 사람들이 코포를 많이 하는 이유라고 볼 수 있다.
코포는 블루를 가고 싶다 하면 꾸준히 블루 퍼포먼스를 유지하는 것으로도 단기간에 블루를 달성할 수 있다.
그런데 앳코더는 아니다. 위 상황과 동일한 시간으로 색깔을 한 단계 올리고 싶으면 그보다 두 단계 높은 색깔의 퍼포먼스는 찍어줘야 할 것이다...
원래 다른 사이트에서 그 정도 실력인 상태가 아니면 점수 50점 올리는 것도 보기 드물다.
당장 본인이 가장 좋은 성적을 낸 결과만 봐도 165점 준다. 아마 코포였으면 400점은 줬을 것이다.
어쨌든 코드포스에 비해 레이팅 상승이 느리기에 앳코더로 처음 CP(Competitive Programming)를 하려는 사람들은 긴 인내심을 가져야 할 것이다. 아니면 말도 안 되게 빨리 성장하거나...
물론 망했을 경우에도 점수가 조금 깎인다는 장점은 있다.
앳코더의 콘테스트들(ABC, ARC, AGC)
앳코더는 코드포스의 디비전처럼 콘테스트를 3개의 수준으로 나눠 관리하고 있다.
ABC: 내가 보기엔 앳코더를 해야 할 이유 중 가장 큰 부분을 차지하는 콘테스트이다. ABC는 2022년 8월 기준 100분에 8문제를 풀도록 하고 있으며 문제 기조는 "최대한 많은 알고리즘과 테크닉을 알려주자."이다. 문제 자체는 뻔하게 보일 수 있지만 입문자들도 어느 정도 풀 수 있는 문제가 나와 자신감을 올려주고 나오는 알고리즘의 범위가 방대하다 보니 모르는 알고리즘을 공부하기 좋다.
ARC: ABC와는 결이 다르다. 문제를 풀기 위해 필요한 관찰력이 급격히 올라간다. 아마도 xOI 같은 올림피아드 류와 비슷한 것 같다. 그리고 필요한 사전 지식도 ABC보다 깊다. 올림피아드 문제에 익숙할 때 하면 좋을 것 같다.
AGC: 한 번도 콘테스트를 쳐보진 않아서 잘은 모르겠다. 다만 확실한 건 네임드도 제대로 풀기 힘든 것들이 나온다.
세 수준에 대해 공식적인 설명에 관해선 앳코더 전 어드민이 쓴 코포 블로그가 있으니 관심이 있다면 참고해보자.
https://codeforces.com/blog/entry/78109
Rated range of AGC - Codeforces
codeforces.com
앳코더는 어떻게 공부해야 하나요?
ABC에 집중하기
ARC부터는 꽤 어려워서 입문자에겐 ARC 이상의 문제를 공부하는 것이 비효율적일 수 있다. 가능하면 ABC의 문제들을 위주로 공부하고 콘테스트에 참여하는 게 좋을 거 같다.
백준 꾸준히 풀기
코드포스와 관련된 글에는 "코드포스는 코드포스로 연습해라"라는 의견이 주를 이룬다. 하지만 앳코더는 조금 다르다. 앳코더는 코드포스와는 달리 나오는 알고리즘의 범위가 넓다.
코드포스 블루를 위해서는 이진 탐색, 그리디, BFS와 같은 기본 알고리즘을 알고 있는 상태에서 아이디어를 잘 관찰하고 풀이를 이끌어낼 것이 요구되는 반면, 앳코더 민트는 관찰력이 덜 필요한 대신 많은 알고리즘, 문제 풀이에 자주 나오는 테크닉과 어느 정도의 수학 지식을 숙지한 상태에서 문제에 올바르게 활용할 것이 요구된다.
여기까지 읽었다면 딱 맞는 플랫폼을 생각할 수 있다. 바로 백준 저지이다. 백준 저지에서는 수만 개의 문제가 제공되고 solved.ac로 난이도를 평가할 수 있기 때문에 양질의 문제를 많이 풀 수 있게 해준다.
따라서 앳코더 점수를 올리기 위해서라면 백준 문제도 많이 푸는 것 역시 권장된다. 물론 쉬운 것만 풀 생각은 말고 주기적으로 새로운 알고리즘을 공부하거나 티어 랜덤 디펜스를 통해 도전적인 문제를 많이 풀어봐야 한다.
좀 포장해서 그렇지 쉽게 말하면 "적당히 어려운 거 닥치는 대로 많이 푸세요."다. 앳코더 비기너는 정직하게 푼 만큼 성과가 보인다.
Atcoder Problems 이용
구글에 atcoder problems를 검색하면 좋은 사이트가 하나 나온다.
여기서는 깃허브 인증을 통해 내 앳코더 핸들을 연동할 수 있는데 여기서 버추얼 연습 기능과 문제 추천 등 앳코더로 공부할 때 많은 도움을 준다.
앳코더 문제에 많이 익숙지 않은 상태면 우상단 Training 메뉴를 들어가자.
그러면 Easy, Medium, Hard 각각 100문제씩 제공하는 문제집이 나온다.
본인은 이 중에서 Medium, Hard 문제들을 어느 정도 풀 것을 강력히 권하는데, 여기 문제들이 "앳코더는 이런 스타일이다!"를 파악하기 좋기 때문이다.
적응 목적 외에도 문제 자체가 많이 유익하므로 많이 풀어보도록 하자.
그리고 자기가 이미 콘테스트에 참여해서 레이팅이 있다면 User 탭을 누른 뒤 Recommendation을 들어가 보도록 하자.
그러면 위와 같이 Easy, Moderate, Difficult로 나눠 자신의 레이팅 수준에서 풀어야 하는 문제들을 추천해준다.
본인은 세 수준을 모두 해볼 것을 권하는데, Easy에 있는 문제여도 내가 모르는 지식이나 알고리즘이 필요한 문제가 왕왕 있기 때문에 고루고루 연습하는 것이 좋다.
참고로 저기 위에 시험관은 일본어를 할 줄 모른다면 활성화하지 말자. 해외에 오픈되기 전에 존재했던 일본어 only 문제가 나온다.
콘테스트 난이도 체크와 업솔빙
앳코더는 콘테스트가 끝난 즉시 에디토리얼(해설)을 제공한다. 참여한 콘테스트 페이지에서 메뉴에 Editorial 메뉴가 활성화 되는데 거기서 내가 콘테스트에서 풀지 못한 문제의 해설을 반드시 확인하도록 하자!
ABC는 기출에 관대하기 때문에 오늘 나왔던 유형이 미래에 또 나올 수 있다. 그런 점에서 해설을 공부할 이유는 충분하니 잘 보도록 하자.
다만 앳코더 해설은 종종 불친절한 경우가 있는데 경험상 앳코더에 많이 냈던 유형일수록 해설을 불친절하게 쓰는 경향이 있다. 해당 유형이 처음으로 나왔던 때의 에디토리얼을 보면 아주 잘 설명하고 있다. 근데 그 처음 나온 문제를 알고리즘 분류도 제공 안하는데 어떻게 찾겠는가? 이거는 좀 그렇다.
아무튼 읽어도 뭔가 읽히지 않는다면 즉시 코드포스 discussion에 가서 물어보거나(앳코더 공지가 코포에서도 이루어지기 때문에 거기서 이야기할 수 있다.) 커뮤니티에 질문을 올리도록 하자.
둘 다 여의치 않으면 업솔빙을 포기하는 것도 괜찮다고 본다. 그거 외에도 배울 가치가 있는 문제들이 백준에 널려있다.
그리고 atcoder problems에 늦어도 하루 안에 콘테스트 문제의 난이도가 게시된다.
저기 문제 옆 원에 마우스 커서를 호버 하면 문제의 측정 레이팅이 표기되는데 이는 그 레이팅의 사람이 해당 문제를 콘테스트 안에 풀 확률이 50%라는 뜻이다.
게시된 난이도를 보면서 "아 나는 이 정도까지는 푸는구나. 여기부터 막히는데 이 색깔을 잘 푸는 연습을 해야겠구나" 등 자신의 실력에 대해 분석 및 훈련 강도를 정할 수 있다.
본인의 테이블로 예시를 들면 "아 이 사람은 보통 민트 레이팅의 문제부터 풀거나 못 풀 수도 있구나. 민트 이상의 문제를 집중적으로 훈련하면 되겠는데?"와 같이 어떤 수준의 문제를 연습해야 하는지 척도를 세울 수 있다.
자신의 문제 풀이 동향을 보면서 적절한 연습 계획을 짜도록 하자.
Virtual Contest
대회를 준비하는 사람들에게는 실제 콘테스트처럼 연습할 수 있는 virtual 참여를 권장한다. 시간 재서 푸는 연습을 하기 가장 좋은 방법이기 때문이다.
앳코더에서 virtual contest를 할 수 있는 방법은 두 가지인데
첫 번째는 앳코더 콘테스트 홈피에서 Vritual Participation 하기
두 번째는 Atcoder Problems의 우상단 메뉴 중 Virtual Contests 메뉴를 이용하는 방법이 있다.
여기서 진행 중인 버추얼에 참여하거나 Create New Contest를 통해 내 입맛에 맞는 콘테스트를 만들어 참가할 수 있다.
콘테스트를 만들 땐 문제 뽑기 기능을 지원해서 내 수준에 맞는 콘테스트를 만들기 정말 좋다.
본인은 보통 '아 그냥 대회 연습하는 겸 앳코더 공부하고 싶다!' 할 때 무지성으로 버추얼을 만들어서 친다.
예상 참여자를 입력해 그들이 이미 풀었던 문제를 제외하는 기능도 제공하니 적극 애용하도록 하자.
CP 할 때 정신 건강 챙기기
꽤 중요한 거 같아서 적고자 한다.
사람은 누구나 자기가 얼마나 연습했든 간에 성적이 좋지 않은 시기가 찾아온다.
당장 내 프로필만 봐도 빛나는 성과를 보기 전에 한 달 동안 내려가기만 한 적이 있다.
어지간한 강철 멘탈을 가진 사람이 아니면 당연히 심적으로 큰 고통을 겪으며 공부할 의욕이 떨어질 것이다.
특히나 본인은 PS를 취미가 아니라 경쟁의 목적으로 하는 거기 때문에...
아무튼 여기에 대해서는 좋은 글들이 있다.
https://blog.shift.moe/2021/06/11/do-not-get-obsessed-with-ratings/
목적지는 레이팅이 아니다 – shifted
이게 무슨 해괴망측한 소리일까요? 이 글은 알고리즘 문제해결 트레이닝에 대한 사견私見입니다. 지금부터 전제를 하나 합시다. 밥 먹고 알고리즘 공부만 하면 얼마나 걸릴지는 몰라도 언젠가
blog.shift.moe
PS공부 하면서 좌절감을 느낀 분들이 읽어봤으면 하는 나의 2016년
최초 작성일: 2016.12.23 (금) 최종 수정일: 2020.09.15 (화) 2016년 PS를 시작했던 나를 돌아보며 최근에 제가 어떻게 PS(Problem Solving)를 시작하게 되었고, PS 공부하면서 얼마나 큰 좌절감 속에서 살았는지
plzrun.tistory.com
나는 여기에 더해 본인이 부진에 빠졌을 때 하는 공부 방법들을 덧붙이고자 한다.
ARC 이상 rated로 치지 않기
앳코더는 아예 콘테스트 레지부터 rated, unrated 옵션을 제시하는데 대폭락을 경험한 것도 2주 연속 ARC를 rated로 참여하고 참교육을 당해서이다. 진짜 ARC 문제들 미리 풀어보고 아닐 거 같으면 rated로 하지 말자.
Unrated로 참여하기
위랑 비슷하게 맘 아주 편하게 먹고 당분간 unrated로 보는 것도 괜찮다. 올라갈 일도 없지만 내려갈 일도 없으니 얼마나 편안한가?
문제 티어랑 태그 감상하기
무슨 개소리냐 싶겠지만 내가 옛날부터 가지고 있었던 악취미다. 정확히 어떤 거냐면 공부하지도 않은 학문을 그냥 보기만 하는 거다.
예시로 고등학생 때는 도서관에서 이산수학 책을 빌려 단순히 "구경"하는 기행을 벌이기도 했다.
지금은 백준 저지에서 현재의 내가 혼자 절대 풀지 못할 어려운 문제의 태그를 까면서 "아 어떻게 하면 세그 트리랑 다익스트라가 붙어있냐고 ㄹㅇㅋㅋ" 이런 식으로 혼자 감탄하고 혼자 웃는다.
그렇다 보다 보면 특정 태그 조합에 흥미가 생겨 다시 공부할 의욕이 생기는 그런 흐름으로 간다.
구현, 완전 탐색 문제집 풀기
머리를 비우고 오로지 시키는 대로 하는 문제들을 푼다. 단순 노동하면 잡생각이 나지 않는 거랑 비슷하다.
그렇게 하다 다시 재미를 붙이면 본 공부를 이어갈 수 있다.
코포 공부하기
의외로 나쁘지 않다. 본인은 원래 코포 안 좋아하는데 이럴 때 A~B 위주로 풀면 조금 재미있다.
궁극적으로 부진에 빠지면 다시 올라갈 수 있다는 긍정적인 마음가짐을 가지고 공부를 하자.
앳코더 팁
그러면 앳코더를 공부하는 법은 알았으니 여기에 더해 알면 좋은 내용을 설명하겠다.
ABC에는 빈출 유형이 있다.
앳코더를 80번 넘게 참여하면서 발견한 건데 E 이하에서 주기적으로 나오는 알고리즘 유형이 있다. 이를 파악하고 있으면 아무래도 해당 유형을 능숙하게 처리할 수 있을 것이다.
imos 법
특정 범위에 더하고 빼는 연산을 엄청 많이 하는데 그 결과에 대한 질의를 마지막에 딱 한 번만 하는 경우 d차원 공간에 대해 $O(N^{d})$으로 해결할 수 있는 기법이다.
ABC에서는 1차원 상태 공간에서 imos 법을 수행하는 문제가 많이 나온다.
이 포스트에서 공부할 수 있다.
분할 정복, 재귀
가끔 이렇게 생긴 문제가 나온다.
https://www.acmicpc.net/problem/5904
5904번: Moo 게임
Moo는 술자리에서 즐겁게 할 수 있는 게임이다. 이 게임은 Moo수열을 각 사람이 하나씩 순서대로 외치면 되는 게임이다. Moo 수열은 길이가 무한대이며, 다음과 같이 생겼다. m o o m o o o m o o m o o o
www.acmicpc.net
단순히 직접 나열하거나 반복하는 걸로는 시간 초과가 나므로 관찰로 발견할 수 있는 수식과 재귀를 통해 필요 없는 범위를 빠르게 지나가면서 문제에서 요구한 지점을 찾는 문제가 나온다.
나는 이런 분할 정복 문제들을 공부하기 좋은 문제집을 백준 저지에서 찾지 못했는데 누가 제보해주면 좋을 거 같다.
누적합으로 시간 복잡도를 줄이는 DP
N이 1000 이상이고 그냥 단순 동적 계획법을 하면 $O(N^{3})$이 되어 시간 초과를 받는 문제가 있다.
이는 동적 계획법을 수행할 때 누적합으로 적절히 처리를 해주면 $O(N^{2})$로 바뀌어 무난하게 해결이 된다.
https://www.acmicpc.net/problem/2616
2616번: 소형기관차
첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있
www.acmicpc.net
KOI 소형기관차가 그나마 비슷할 거 같은데 ABC E 이하에서 나오면서 적당히 괜찮은 문제는 백준에 잘 안 보인다.
유니온 파인드 + 오프라인 쿼리
ABC에서 유니온 파인드를 쓸 수 있는 문제는 D 이하에서 툭하면 나온다. 적당한 유니온 파인드 문제를 먼저 많이 풀도록 하자.
그리고 거기에 더해 E에서는 유니온 파인드와 오프라인 쿼리를 섞는 문제가 나온다.
https://www.acmicpc.net/problem/13306
13306번: 트리
표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 트리의 정점의 개수와 질의의 개수를 나타내는 두 정수 N과 Q (1 ≤ N, Q ≤ 200,000)가 주어진다. 다음 N-1개의 줄의 i번째 줄에는 정점 i+1의 부
www.acmicpc.net
이거 공부하면 ABC E수준으로 나오는 유니온 파인드 문제는 다 풀 수 있을 거라 본다.
주기 찾는 문제 / 순열 사이클 분할
대충 뭘 무한 번 할 건데~~ 로 시작하거나 어떤 동작을 K번 했을 때($K \leq 10^{18}$) 결과는? 을 묻는 문제가 있다. 혹은 좀 더 헷갈리게 하려고 $10^{100}$번 한다는 표현도 있다.
재귀 유형과 묘하게 비슷할 수 있지만 십중팔구 그 무한한 동작에서 생기는 일정한 패턴을 포착하여 연산 횟수를 최적화 한 뒤, 모든 연산을 한 결과를 구하는 문제다.
대충 적당한 수만큼 제시한 동작을 시뮬레이션하면서 발생하는 패턴을 찾아 풀면 된다.
백준 저지에서 관련된 태그는 "순열 사이클 분할"이다. 간략히 설명하면 수열의 원소들의 위치를 이리저리 바꾸는 연산을 하다보면 적절히 짧은 주기로 원래 상태로 돌아오게 되는데, 이 주기를 몫으로 빼고 나머지 횟수를 짧게 시뮬레이션 할 수 있다.
말은 쉬운데 꼬아서 내면 "아 주기 찾는 문제 같은데 뭐 어쩌라는 거야?" 같은 상황이 발생하니 역시 많이 풀어보는 게 좋다.
백준 저지에서는 올림피아드 기출을 풀어보는 것을 추천한다.
https://www.acmicpc.net/problem/2487
https://www.acmicpc.net/problem/18783
앳코더 기출도 풀어보자. 성격이 조금 다르다는 것을 눈치챌 것이다.
https://atcoder.jp/contests/abc241/tasks/abc241_e
https://atcoder.jp/contests/abc258/tasks/abc258_e
그밖에도 자료구조 응용, 정수론, 조합론이 나오는데 기출 풀고 백준 열심히 하자.
검색해보기
민트를 어떻게 달았는가? 문단에서 알 수 있듯이 ABC는 구글에 검색하면 나오는 문제를 출제하는 경우가 있다. 스코어보드를 보면서 뭔가 심상치 않으면 검색해보자. 뭔가 얻을 수 있을지도 모른다.
이렇게 쓰고 보니 앳코더 시작한 지 3년이 조금 안 돼서 민트를 달았다는 사실에 징글징글하다는 생각이 든다. 앳코더는 정말 인내심을 가지고 해야 한다.
마치며
물론 이것은 개인 경험에 의해 쓰는 것이기 때문에 다른 사람과는 방법에 차이가 있을 수 있다. 그렇지만 이 글을 보고 도움이 되어 민트를 달성했으면 좋겠다.
'CP diary' 카테고리의 다른 글
| CLion PS용으로 설정하기(파일 입출력, 다중 main) (0) | 2022.10.06 |
|---|
