Codeforces 시작 그리고 첫 문제풀이 후기

휴학을 결심했을 때 최우선 목표가 알고리즘 공부였고 종만북이라 불리는 '알고리즘 문제 해결 전략' 책으로 이론을 공부하다 최근에는 문제들을 적극적으로 풀고 있다.

BOJ에서 문제를 풀다가 난이도를 실버, 골드 이런 식으로 나누고 있는 것을 보고 호기심이 생겨서 검색해봤다.

그리고 https://solved.ac를 발견했다. 문제들마다 난이도가 있고 푼 문제들로 내 점수가 오르는 게 너무 재미있을 것 같아 몇 문제를 풀어봤었다.

이건 같은 학교 사람들의 랭킹인데 익숙한 닉네임들이 보여서 자극이 많이 됐다.

그런데 더 찾아보니 해외사이트인 https://codeforces.com를 발견했고 문제가 영어라는 점이나 매일마다 대회 형식의 라운드가 열리는 점 등 장점이 더 많은 것 같아 코드 포스를 주로 하기로 결정했다.

출처 : https://namu.wiki/w/Codeforces

그리고 점수가 내려갈 수도 있는 레이팅 제도가 더 재밌어 보이는 것도 코드 포스를 선택하는데 영향을 줬다.

이번 연도 내에 퍼플이라 불리는 Candidate Master에 가는 게 목표인데 꽤나 힘든 여정이 될 것 같다...

어제 자기 전에 한번 체험해보고 싶어 이미 끝난 Codeforces Round #736 (Div. 1)에 Virtual participation 해봤다.

문제는 Div. 1이 제일 쉬운 건 줄 알고 참여했는데 숫자가 낮을수록 어려운 거였다. 

 

Codeforces Round #736 (Div. 1)의 문제들

A, B, C, D1, D2, E 6문제가 있고 뒤로 갈수록 어려워진다.

A 문제를 풀 때까지는 가장 쉬운 난이도 라운드의 가장 쉬운 문제를 풀고 있다고 생각하고 있었기 때문에 

생각보다 간단하게 풀리지 않아서 당황했었다. A 문제가 단순한 시뮬레이션 문제라 생각하고 제출했지만 처음에는 메모리 초과, 메모리 초과를 해결하자 시간 초과가 나왔다.

A 문제에 더 매달려봤자 딱히 성과가 없을 것 같다는 생각이 들어 B문제로 넘어갔고 B문제를 읽고 나서야 뭔가 잘못됐다는 것을 느꼈다.

가장 쉬운 라운드의 문제는 아닌 것 같다는 의심이 들어서 검색해봤고 가장 어려운 라운드였다는 것을 알게 됐다.

그래서 라운드를 더 진행하는 것은 포기하고 라운드 1등의 A번 문제 코드를 분석했는데 1등의 코드는 Syntactic Sugar가 많아 익숙해지기 전까지 가독성은 떨어지는 것 같다.

https://codeforces.com/contest/1548/problem/A - A 문제

https://codeforces.com/contest/1548/submission/124521888 - 1등의 코드

//别丢包了！
#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define pi pair<int, int>
#define mod 998244353
template<typename T> bool chkmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chkmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}
ll ksm(ll a, ll b) {if (b == 0) return 1; ll ns = ksm(a, b >> 1); ns = ns * ns % mod; if (b & 1) ns = ns * a % mod; return ns;}
using namespace std;
const int maxn = 200005;
set<int> r[maxn];
int ans = 0;
bool chk(int a) {
    if (r[a].empty()) return 1;
    if (*r[a].rbegin() <= a) return 1;
    return 0;
}
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        r[u].insert(v), r[v].insert(u);
    }
    int q;
    cin >> q;
    int ans = 0;
    for (int i = 1; i <= n; i++) ans += chk(i);
    for (int i = 1; i <= q; i++) {
        int t, u, v;
        scanf("%d", &t);
        if (t == 3) printf("%d\n", ans);
        else {
            scanf("%d%d", &u, &v);
            ans -= chk(u), ans -= chk(v);
            if (t == 1) r[u].insert(v), r[v].insert(u);
            else r[u].erase(v), r[v].erase(u);
            ans += chk(u), ans += chk(v);
        }
    }
    return (0-0); //<3
}

복기를 해보자면 시간 초과가 뜬 시점에서 시뮬레이션이 아니라는 것을 눈치챘어야 했는데 당황해서 생각도 못했던 거 같다. 1등의 코드를 보고 나서야 O(n+q) 문제라는 것을 알게 됐다.

마음이 급해져서 코드만 들여다보면서 의미 없이 고쳤는데 틀렸을 때는 노트에 써가면서 생각하는 시간을 아까워하지 말아야겠다.

그리고 자료구조 사용도 잘못됐다. 인접 행렬을 사용하려고 vector를 사용했었지만 메모리 초과가 난 이후에 인접 리스트로 바꿨을 때 set을 몰라서 그대로 vector를 사용했던 것도 아쉽다.

최근에 JS랑 Python으로 문제를 풀다가 이번에 C++을 다시 사용하게 됐는데 옛날에 배워서 알고 있다고 자만했던 거 같다. STL을 한번 정리할 필요가 있다고 느꼈다.

구체적인 목표가 없어 공부가 늘어지는 느낌이 들었는데 코드 포스 덕분에 목표가 눈에 보이기 시작했다.