https://codingcompetitions.withgoogle.com/codejamio/round/00000000009d9870
Code Jam - Google’s Coding Competitions
Put your coding skills to the test as you work your way through multiple rounds of algorithmic coding puzzles for the title of Code Jam Champ and 15,000 USD.
codingcompetitions.withgoogle.com
한국 시각으로 3월 26일 오후 11시에 열린 Code Jam to I/O for Women 2022에 참가했다.
전체 327등, 한국 8등을 했다.
문제별 풀이를 쓰기에 앞서, 요즘 들어 가끔 무의식중에 코드를 작성하는, 정말 안 좋은 습관이 생긴 거 같다. 한때 완벽하게 깔끔한 코드를 짜려고 애쓰다가 실수하는 일이 많았는데, 한동안 거기에 집착하지 말아야겠다고 생각하면서 좀 괜찮아졌다가, 요즘은 그것이 약간 변형되어, 무의식중에 완벽한 코드를 짜려고 애쓰고, 그러다가 실수를 하지만, 애초에 내가 코드를 완벽하게 만들기 위해 설치해놓은 장치가 내 의식 속에서 구현된 게 아니기 때문에 그것을 발견하는 데 꽤 오래 걸리는... 그런 정말이지, 최악의 코딩 습관이 생겼다.
알고리즘 문제 풀이를 열정적으로 하지 않은 지 꽤 오래됐다. 가장 큰 이유는 컴퓨터공학 전공자로서 알아야 할 최소한의 알고리즘은 이제 마스터한 것 같다는 생각에서였던 거 같다. 그리고 그 이상의 고급 알고리즘을 더 공부하거나, 대회에 초점을 두고 연습하면서 내가 지금까지 했던 것 이상의 실적을 거두는 것에는 욕심이 없었던 것도 있다.
그래서 작년 초에 코드포스 블루를 달성한 이후에는 '취미 PS'를 했다. 말 그대로 정말 취미처럼, 가끔 하고 싶을 때 하는 딱 그 정도로만. 그래서 작년에는 각종 대회에 나가긴 했지만 특별한 욕심 없이 재미 위주였던 만큼 수상하거나 좋은 성적을 거둔 건 딱히 없다.
알고리즘 문제 풀이를 딱 이 정도로만 하는 것에 대해서 별로 문제를 못 느꼈는데, 요즘 내가 코드를 작성하는 모습을 보니 좋은 코딩 습관을 기르기 위해 앞으로는 2~3일에 한 문제씩이라도 꼭 풀어야겠다는 생각이다. 그리고 그때, 단순히 문제를 맞히기 위해 코드를 빠르게 작성하고, 제출하고, '맞았습니다!!'를 확인하고 넘어가는 게 아닌, 변수 이름 설정부터 시작해서 한 줄 한 줄에 온 정성을 다해 코드를 작성하면서 문제를 풀어야겠다.
무언가를 잘하고 싶다면 그것을 반복적으로 연습하면 된다. 좋은 코딩 습관을 기르고 싶으니 매일 꾸준히 예쁜 코드를 작성하는 연습을 해야겠다. 그리고 여기에 알고리즘 문제 풀이가 좋은 도구가 될 거 같다. 클래스로 분류된 문제들부터 풀어나가야겠다.
이제 대회 문제에 관해 이야기하려고 한다.
문제는 위 링크에서 확인해주세요!
# Inversions Organize
2N * 2N의 정사각형을 가로, 세로 방향으로 모두 절반씩 나누어 N * N 정사각형 네 개로 나눈다. 그리고 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래의 N * N 정사각형에서의 'I'의 개수를 각각 a, b, c, d라고 할 때
a + b = c + d
a + c = b + d
위 두 식을 만족해야 하고, 결국 a == d, b == c여야 한다.
따라서 답은 abs(a - d) + abs(b - c)이다.
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tc; cin >> tc;
for (int tc_i = 1; tc_i <= tc; ++tc_i) {
int n; cin >> n;
vector<string> arr(2 * n);
for (int i = 0; i < 2 * n; ++i) {
cin >> arr[i];
}
vector<vector<int>>count(2, vector<int>(2));
for (int i = 0; i < 2 * n; ++i) {
for (int j = 0; j < 2 * n; ++j) {
if (arr[i][j] == 'I') {
++count[i / n][j / n];
}
}
}
int answer = abs(count[0][1] - count[1][0]) + abs(count[0][0] - count[1][1]);
// print answer
cout << "Case #" << tc_i << ": " << answer << kEndl;
}
}
# Ingredient Optimization
각 order마다 주문이 들어오는 시간 이전에 deliver 되는 바질이 있는지 확인한다. 그리고 그 바질이 시드는 시간을 min heap에 저장하여 남은 수명이 짧은 바질부터 사용할 수 있게 한다. 그리고 min heap의 top과 주문이 들어오는 시간을 비교하여 만약 이 바질이 시든다면 pop하고, 사용할 수 있다면 count를 처리하고 pop 한다. count가 U가 되면 다음 주문으로 넘어가고, 그렇지 않으면 확인을 종료한다.
이 문제를 풀 때 시간을 허비한 두 가지 이유가 있는데
1. 각 주문을 처리할 수 있는지를 확인할 때, 주문이 들어오는 시간을 입력받는 것과 가능 여부를 확인하고 만약 불가능하다면 break 하는 것을 한 번에 처리했다. 그래서 테스트케이스의 입력을 다 받지 않고 다음으로 넘어가는 바람에 그다음 테스트케이스에서 값이 잘못 입력됐다. 그걸 발견하는 데 꽤 시간이 걸렸다.
2. WA를 두 번 받았는데... 그 이야기를 하기 전에 일단 코드를 첨부하겠다.
struct Delivery {
ll arrive, count, remain;
Delivery() {}
Delivery(ll a, ll b, ll c) {
arrive = a;
count = b;
remain = c;
}
};
struct Basil {
ll lasting, count;
Basil() {}
Basil(ll a, ll b) {
lasting = a;
count = b;
}
bool operator<(Basil a) const {
return this->lasting > a.lasting;
}
};
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll tc; cin >> tc;
for (int tc_i = 1; tc_i <= tc; ++tc_i) {
ll d, n, u; cin >> d >> n >> u;
queue<Delivery> del;
for (int i = 0; i < d; ++i) {
ll a, b, c; cin >> a >> b >> c;
del.push(Delivery(a, b, c));
}
ll answer = 0;
priority_queue<Basil> pq;
vector<ll> time_vec(n);
for (int i = 0; i < n; ++i) {
cin >> time_vec[i];
}
for (int i = 0; i < n /* && !del.empty() */; ++i) { // HERE
const ll& time = time_vec[i];
while (!del.empty()) {
const Delivery& cur = del.front();
if (time < cur.arrive) {
break;
}
if (cur.arrive + cur.remain < time) {
del.pop();
continue;
}
pq.push(Basil(cur.arrive + cur.remain, cur.count));
del.pop();
}
ll cur_count = 0;
while (cur_count < u && !pq.empty()) {
const Basil& cur_basil = pq.top();
if (cur_basil.lasting <= time) {
pq.pop();
}
else {
if (cur_count + cur_basil.count <= u) {
cur_count += cur_basil.count;
pq.pop();
}
else {
Basil leftover(cur_basil.lasting, cur_basil.count - (u - cur_count));
pq.pop();
pq.push(leftover);
cur_count = u;
}
}
}
if (cur_count == u) {
++answer;
}
else {
break;
}
}
// print answer
cout << "Case #" << tc_i << ": " << answer << kEndl;
}
}위에서 주석으로 HERE라고 표시한 부분에 !del.empty() 조건을 넣어서 틀렸다.
해당 for 문은 각 주문 처리될 수 있는지를 체크하는 부분이고, del은 앞으로 배달될 허브를 저장하는 변수다. 즉, 현재 주문이 처리될 수 있는지를 체크하는 것과 관계가 없다. 관계가 있는 건 del이 아니라 pq이다.
그런데 나는 무의식중에 del이 비어있지 않은지를 확인해야 한다는 조건을 추가했다. 대체 왜 그랬는지 모르겠다. 최근에 실수를 줄이기 위한 장치를 일부러 여기저기 설치하면서 코드를 작성하곤 했는데, 그러다 보니 그게 습관이 돼서 별로 크게 고민하지 않고 그냥 무의식중에 장치를 설치하게 된 거 같기도. 여튼, 변수의 용도와 코드의 흐름을 정확하게 따지지 않고 조건을 추가하는 바람에 아까운 WA를 두 번 받았다.
# Interesting Outing
사실 이 문제에서 저지른 만행이 더 최악이다.
위 문제는 결국 대회 중에 풀기라도 했지, 이건 결국 못 풀었다가 끝나자마자 문제점을 발견했기 때문.
며칠 전부터 2022 SUAPC Winter에 나온 Y라는 문제에 대해서 글을 써야겠다고 생각하고 있었는데, 그 덕분에 이 문제의 풀이도 금방 떠올랐다. 결국에 모든 지점을 방문해야 하므로 모든 간선의 가중치가 더해져야 하고, 그중에서 두 번 더해지는 것들의 합이 최소가 되어야 한다. 그러므로 트리의 지름을 구하고, 지름에 포함되지 않는 간선들이 두 번 더해지면 된다.
struct Node {
ll number, weight;
Node() {}
Node(ll a, ll b) {
number = a;
weight = b;
}
};
Node GetMax(int cur, vector<bool>& visited, const vector<vector<Node>>& adj, const ll& weight) {
Node ret(cur, weight);
for (const Node& next : adj[cur]) {
if (visited[next.number]) {
continue;
}
visited[next.number] = true;
Node next_max = GetMax(next.number, visited, adj, weight + next.weight);
if (next_max.weight > ret.weight) {
ret = next_max;
}
}
return ret;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tc; cin >> tc;
for (int tc_i = 1; tc_i <= tc; ++tc_i) {
int n; cin >> n;
vector<vector<Node>> adj(n + 1);
ll sum = 0;
for (int i = 0; i < n - 1; ++i) {
ll a, b, c; cin >> a >> b >> c;
adj[a].push_back(Node(b, c));
adj[b].push_back(Node(a, c));
sum += c;
}
vector<bool> visited(n + 1, false);
visited[1] = true;
Node last_node = GetMax(1, visited, adj, 0);
int start = last_node.number;
visited.clear(); visited.resize(n + 1, false);
visited[start] = true;
last_node = GetMax(start, visited, adj, 0);
ll answer = sum * 2 - last_node.weight;
// print answer
cout << "Case #" << tc_i << ": " << answer << kEndl;
}
}이 문제에서 한 바보짓은 다음과 같다.
1. 트리의 지름을 구할 때, DFS를 돌면서 한 노드에서 인접한 노드 각각으로 뻗어나가는 경우 중 return 되는 가중치 합의 최댓값을 구한다. 그런데 트리의 지름을 구하고 나서 나머지 간선에 대한 합을 구할 때 트리의 지름을 구할 때와 동일한 함수를 이용해서 인접한 각 노드에서 return 하는 값 중 최대를 구했다.
2. 이게 잘못됐다는 걸 대회가 끝난 후에야 깨달았다. 그래서 대체 무슨 정신인가, 라고 생각하면서 새로운 함수를 만들어서 각 노드로 뻗어나갈 때 합을 return 하는 함수를 만들었다. 그러면서 대회 중에 아무 생각 없이 return 값 중 최댓값을 저장한 스스로에 대해 대체 제정신인가, 바보인가, 하는 생각을 했는데...
3. 그러다가 블로그 글 적으면서 그제야 깨달았다. 그냥 합만 구하면 되기 때문에 함수를 따로 작성할 필요도 없이 답은 그냥 (전체 간선 가중치 합) * 2 - (트리의 지름)이라는 걸... 내가 스스로 바보라고 생각하는 동안에도 나는 바보였던 거다.
대체 정말 왜 이러는 걸까. 집중력이 부족한 걸까, 아니면 단순히 알고리즘 문제 풀이를 꾸준히 하지 않아서 그런 건가. 아니면 시간이 늦어서 정신이 없었던 건가. 뭐든 간에 지금 문제가 굉장히 심각하다는 것만큼은 확실하다. 정말 좋은 습관을 기르려고 훈련하고 노력해야겠다.
작년 대회에서는 전체 532등, 한국 8등을 했고, 그에 비해 등수가 올랐다는 것에는 의미가 있다.
그렇지만 목표는 150등 안에 들어서 Google I/O invitation과 swag와 stipend를 받는 거였고, 그걸 이루지 못해서 정말 아쉽다. 세 번째 문제를 시간 안에 풀었으면 등수 안에 들었을 걸 생각하니 더더욱.
그래도 내 코딩 습관의 문제점을 뼈저리게 깨달은 계기가 되었으니까 그걸로 충분하다고 생각하려고 한다. 장기적으로 보면 더 중요한 걸 얻은 걸지도.
습관의 힘은 세다. 정말. 정말 신경 써서 고쳐야겠다.