SCPC 2024 1차 예선에 참가했습니다 (1/3)

적당히 쉬엄쉬엄 풀어서 난이도에 비해 남은 시간이 다소 적습니다. 올해는 2번까지 풀지 않으면 Round 2를 가기 좀 힘들지 않을까 싶을 정도로 1, 2, 3번이 쉬웠습니다.

개인적인 난이도는 1 < 2 < 3 < 5 < 4번이었습니다.

1차 1번 – A보다 B가 좋아

길이 $N \le 300\,000$의 AB로만 이루어진 문자열이 있습니다. 이 문자열에서 길이 $2$ 이상의 어느 부분 문자열을 골라도 A의 개수보다 B의 개수가 크거나 같도록 하고 싶습니다. 원하는 위치에 B를 추가할 수 있다고 할 때 최소 몇 개를 추가해야 할까요?


작은 경우부터 생각해 봅시다.

길이 $2$인 부분 문자열은 AA인 경우만 피하면 됩니다.

길이 $3$인 부분 문자열은 AAA, AAB, ABA, BAA가 있는데, AA라는 부분 문자열을 어떻게 다 없앴다고 가정하면, ABA만 피하면 됩니다.

AAABA를 어떻게 다 없앴다고 가정하면, 길이 $4$인 부분 문자열은 무조건 A의 개수보다 B의 개수가 크거나 같음을 알 수 있습니다.

이 성질이 길이 $5$ 이상에서도 성립하는지 알아봅시다. 귀납법을 사용할 수 있습니다.

  • 길이 $K$의 문자열이 A로 끝나는 경우, AAABA 패턴이 존재하지 않으므로, BBA로 끝나야 합니다. 따라서 이 경우 뒤에서 AB 한 글자씩 총 두 글자를 뗀 길이 $K-2$의 문자열에서 성질을 만족했다면, 길이 $K$의 문자열에서도 성질이 유지됩니다.
  • 길이 $K$의 문자열이 B로 끝나는 경우, 길이 $K-1$의 문자열의 맨 뒤에 B를 하나 붙여 준다고 생각할 수 있습니다. 따라서 이 경우 길이 $K-1$의 문자열에서 성질을 만족했다면, 길이 $K$의 문자열에서도 성질이 유지됩니다.

따라서, AA 사이에 두 개 이상의 B가 있도록 추가해 주는 것으로 충분합니다.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);
    
    int t;
    cin >> t;
    for (int _ = 1; _ <= t; _++) {
        int n;
        cin >> n;
        string str;
        cin >> str;

        vector<int> idxs;
        for (int i = 0; i < n; i++) {
            if (str[i] == 'A') idxs.emplace_back(i);
        }

        int s = 0;
        for (int i = 0; i + 1 < idxs.size(); i++) {
            int d = idxs[i + 1] - idxs[i] - 1;
            s += max(0, 2 - d);
        }

        cout << "Case #" << _ << endl;
        cout << s << endl;
    }

    return 0;
}

1차 2번 – 배달

물건이 $N \le 300\,000$개 있습니다. $N$은 $4$의 배수입니다. 물건들에는 무게가 있습니다($1 \le \text{무게} \le 1\,500\,000$).

$4$개의 물건씩 골라 $N$개의 물건을 모두 배송할 예정입니다. 이 때, $4$개의 물건의 무게가 각각 $a \le b \le c \le d$라고 할 때, $$|d-c|+|c-b|+|b-a|+|a-d|$$원을 벌 수 있습니다. 모든 물건을 배달해서 벌 수 있는 최대 금액은 얼마일까요?


$a$, $b$, $c$, $d$의 대소가 이미 정해져 있으므로 절댓값 기호는 의미가 없습니다. 식을 정리합시다.

$$\begin{aligned}& |d-c|+|c-b|+|b-a|+|a-d| \\ =\, & (d-c)+(c-b)+(b-a)+(d-a) \\ =\, & 2d-2a\end{aligned}$$

따라서 가장 무거운 하나와 가장 가벼운 하나만이 배송비에 관여한다는 사실을 알 수 있습니다.

가장 무거운 물건들의 합을 최대화하고, 가장 가벼운 물건들의 합을 최소화하는 방법은 가장 무거운 $N/4$개의 물건들을 $d$로 배정하고, 가장 가벼운 $N/4$개의 물건을 $a$로 배정하도록 하는 것입니다.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);

    int t;
    cin >> t;
    for (int _ = 1; _ <= t; _++) {
        int n;
        cin >> n;

        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        sort(a.begin(), a.end());

        int m = n / 4;
        ll s = 0;
        for (int i = 0; i < m; i++) s -= a[i];
        for (int i = 3 * m; i < n; i++) s += a[i];

        cout << "Case #" << _ << endl;
        cout << s * 2 << endl;
    }

    return 0;
}

1차 3번 – 보안망 점검

보안 장비 $N \le 300\,000$개가 있습니다. 이들은 총 $N+1$개의 라인으로 연결되어 있으며, 이 중 $N$개의 라인은 보안 장비 $N$개를 원형으로 연결하고 있으며, 나머지 $1$개의 라인은 원형으로 연결되어 있는 보안 장비들 중 두 개를 잇습니다. 이 때, 정확히 $2$개의 라인이 파괴되었을 때 망이 분리되는 경우의 수를 구해야 합니다.


다시 말하면, 보안 장비 그래프는 $3$개의 사이클로 되어 있으며, 가장 큰 사이클은 크기가 $N$입니다.

큰 사이클을 나누는 한 개의 간선은 degree가 $3$인 정점 두 개를 찾는 것으로 찾을 수 있습니다. 그 한 개의 간선을 기준으로 왼쪽과 오른쪽에 간선이 몇 개 있나 확인합니다. 각각 $l$개와 $r$개가 있다면, 그래프를 분할하는 경우의 수는 $$\frac{l\left(l-1\right)}{2}+\frac{r\left(r-1\right)}{2}$$개임을 확인할 수 있습니다.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;

ll solve() {
    int n;
    cin >> n;

    vector<vector<int>> graph(n + 1);
    vector<int> deg(n + 1, 0);

    for (int i = 0; i <= n; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].emplace_back(v);
        graph[v].emplace_back(u);
        deg[u]++, deg[v]++;
    }

    vector<int> deg3;

    for (int u = 1; u <= n; u++) {
        if (deg[u] == 3) {
            deg3.emplace_back(u);
        }
    }

    assert(deg3.size() == 2);

    int a = deg3[0], b = deg3[1];
    ll l1 = 0, l2 = 0;

    function<int(int, int)> dfs = [&](int u, int p) {
        if (u == b) return 0;
        for (int v: graph[u]) {
            if (v == p) continue;
            return dfs(v, u) + 1;
        }
    };

    bool skip_flag = false;
    for (int c: graph[a]) {
        if (c == b && !skip_flag) {
            skip_flag = true;
            continue;
        }
        if (l1) {
            l2 = 1 + dfs(c, a);
        } else {
            l1 = 1 + dfs(c, a);
        }
    }

    ll s = 0;
    s += (l1) * (l1 - 1) / 2;
    s += (l2) * (l2 - 1) / 2;

    return s;
}

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);

    int t;
    cin >> t;
    for (int _ = 1; _ <= t; _++) {

        cout << "Case #" << _ << endl;
        cout << solve() << endl;
    }

    return 0;
}

1차 4번 – 딱 맞게

원소의 개수가 $5 \le N \le 100\,000$개인 두 중복 집합 $A$와 $B$가 있습니다.

여기에 일대일 대응 $F\left(A, B\right)$을 정의하여, 서로 대응하는 원소의 값의 차이의 절댓값들 중 가장 큰 값 $\max F\left(A, B\right)$를 계산할 수 있습니다. 이 값이 $1 \le L \le 10^9$보다 작으면서 가장 크게 되도록 해야 합니다. 이때 $\max F\left(A, B\right)$를 출력해야 합니다.


문제를 쉽게 써 봅시다. 배열 $A$와 $B$가 있어서, 이들의 순서를 잘 섞어서 $$\max \left\{ |a_1-b_1|,|a_2-b_2|,\cdots,|a_N-b_N| \right\}$$을 $L$ 이하가 되게 하면서 최대화하라는 문제입니다.

$A$와 $B$를 각각 정렬하면 $\max F\left(A, B\right)$가 최소가 됩니다. 이 사실을 통해, $A$에서 적당한 한 개의 값 $a$와 $B$에서 적당한 한 개의 값 $b$를 골라 놓고, 나머지 원소들을 정렬해 놓는 방법을 사용할 수 있습니다. 이미 정렬된 $A$와 $B$에 대해서 $|A_i-B_i|$, $|A_{i+1}-B_i|$, $|A_i-B_{i+1}|$의 값들을 미리 계산하여 관리하고 있다면 적당한 $(a,b)$ 쌍에 대해 충분히 빠르게 계산할 수 있습니다.

$|a-b| \le L$인 모든 쌍을 보는 것만으로 문제를 해결하는 데에는 충분합니다. 더 나아가서, $a$가 정해져 있을 때, $|a-b|$의 값이 $L$ 이하이면서 가장 크도록 하는 $b$를 적당히 잘 골라 주고, 이런 $(a,b)$ 쌍들만을 보는 것만으로 충분함을 보일 수 있습니다.

아래 코드의 복잡도는 $\mathcal{O}\left(N \log N\right)$입니다. 제 소스 코드는 세그먼트 트리와 이분 탐색을 쓰지만 단조성을 이용한 투 포인터 등의 방법으로 시간을 더 줄일 수 있습니다.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;

ll a[100010], b[100010];

ll p[400010], pa[400010], pb[400010];

void update(ll *tree, int x, int s, int e, int i, ll v) {
    if (s == e) {
        tree[x] = v;
        return;
    }
    int m = (s + e) / 2;
    if (i <= m) update(tree, x * 2, s, m, i, v);
    else update(tree, x * 2 + 1, m + 1, e, i, v);
    tree[x] = max(tree[x * 2], tree[x * 2 + 1]);
}

ll query(ll *tree, int x, int s, int e, int l, int r) {
    if (r < s || e < l) return 0;
    if (l <= s && e <= r) return tree[x];
    int m = (s + e) / 2;
    return max(query(tree, x * 2, s, m, l, r), query(tree, x * 2 + 1, m + 1, e, l, r));
}

void update_p(int i, ll v) {
    update(p, 1, 1, 100000, i, v);
}

void update_pa(int i, ll v) {
    update(pa, 1, 1, 100000, i, v);
}

void update_pb(int i, ll v) {
    update(pb, 1, 1, 100000, i, v);
}

ll query_p(int l, int r) {
    if (l > r) return 0;
    return query(p, 1, 1, 100000, l, r);
}

ll query_pa(int l, int r) {
    if (l > r) return 0;
    return query(pa, 1, 1, 100000, l, r);
}

ll query_pb(int l, int r) {
    if (l > r) return 0;
    return query(pb, 1, 1, 100000, l, r);
}

ll solve() {
    ll n, l;
    cin >> n >> l;

    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];

    sort(a + 1, a + 1 + n);
    sort(b + 1, b + 1 + n);

    for (int i = 1; i <= n; i++) update_p(i, abs(a[i] - b[i]));
    for (int i = 1; i + 1 <= n; i++) update_pa(i, abs(a[i + 1] - b[i]));
    for (int i = 1; i + 1 <= n; i++) update_pb(i, abs(a[i] - b[i + 1]));

    ll ans = -1;

    for (int ai = 1; ai <= n; ai++) {
        for (ll x: {a[ai] - l, a[ai] + l}) {
            int biv = lower_bound(b + 1, b + 1 + n, x) - b;
            for (int bi: {biv - 1, biv}) {
                if (bi < 1 || bi > n) continue;

                // move ai and bi to the end; calculate max abs diff of the rest
                ll mx = abs(a[ai] - b[bi]);
                mx = max(mx, query_p(0, min(ai, bi) - 1));
                if (ai > bi) {
                    mx = max(mx, query_pb(bi, ai - 1));
                } else {
                    mx = max(mx, query_pa(ai, bi - 1));
                }
                mx = max(mx, query_p(max(ai, bi) + 1, n));

                if (mx <= l) ans = max(ans, mx);
            }
        }
    }

    return ans;
}

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);

    int t;
    cin >> t;
    for (int _ = 1; _ <= t; _++) {
        cout << "Case #" << _ << endl;
        cout << solve() << endl;
    }

    return 0;
}

1차 5번 – 스퀘어

배열에서 $2$ 이상의 정수 $k$를 정해서, $k$개의 $k$를 $1$개의 $k^2$로 바꾸는 작업을 ‘스퀘어’라고 정의합시다. 예를 들어, $$\begin{aligned}& [\textcolor{#ff3b57}{2},4,\textcolor{#ff3b57}{2},4,2,2] \\ \rightarrow\, & [4,4,4,\textcolor{#ff3b57}{2},\textcolor{#ff3b57}{2}] \\ \rightarrow\, & [\textcolor{#ff3b57}{4},\textcolor{#ff3b57}{4},\textcolor{#ff3b57}{4},\textcolor{#ff3b57}{4}] \\ \rightarrow\, & [16] \end{aligned}$$과 같이 스퀘어 연산을 수행할 수 있습니다.

크기 $N \le 50\,000$의 배열이 있습니다. 각 원소는 $1$ 이상 $10^9$ 이하입니다. $Q \le 50\,000$개의 쿼리를 처리해야 합니다.

  • $l$ $r$: 배열 $a_l$, $a_{l+1}$, $\cdots$, $a_r$에서 가능한 ‘스퀘어’의 최대 횟수를 구하여 출력한다.

배열에서 $2$ 미만 및 $50\,000$ 초과인 원소들은 무시해도 된다는 사실과, ‘스퀘어’ 연산의 연쇄 반응은 최대 $4$번까지만 일어난다는 사실을 생각해 봅시다. 세그먼트 트리로는 어떻게 풀어야 될지 감이 잘 안 잡히지만, Mo’s는 사용하기 좋아 보입니다. 아래 코드의 시간 복잡도는 $\mathcal{O}\left(N + Q \log Q + Q \sqrt{N} \log \log N \right)$입니다.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;

const int m = 240;
int a[50001], cnt[50001];
ll ans[50000];

struct query {
    int l, r, i;

    query() : l(0), r(0), i(0) {}

    query(int l, int r, int i) : l(l), r(r), i(i) {}

    bool operator<(const query &rhs) const {
        return pii(l / m, r) < pii(rhs.l / m, rhs.r);
    }
};

void init(ll &val) {
    for (int x = 2; x <= 50000; x++) {
        int t = x * x;
        if (2 <= t && t <= 50000) {
            cnt[t] += cnt[x] / x;
        }
        val += cnt[x] / x;
    }
}

void add(ll &val, int x) {
    while (2 <= x && x <= 50000) {
        cnt[x]++;
        if (cnt[x] % x) return;
        val++;
        x *= x;
    }
}

void remove(ll &val, int x) {
    while (2 <= x && x <= 50000) {
        cnt[x]--;
        if ((cnt[x] + 1) % x) return;
        val--;
        x *= x;
    }
}

// sqrt 50 000 < 224
// sqrt sqrt 50 000 < 15
// sqrt sqrt sqrt 50 000 < 4
// sqrt sqrt sqrt sqrt 50 000 < 2

void solve() {
    int n;
    cin >> n;

    memset(cnt, 0, sizeof cnt);

    for (int i = 1; i <= n; i++) cin >> a[i];

    int q;
    cin >> q;

    vector<query> qry(q);
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        qry[i] = query(l, r, i);
    }
    sort(qry.begin(), qry.end());

    ll val = 0;
    int l = qry[0].l, r = qry[0].r;
    for (int i = l; i <= r; i++) {
        if (2 <= a[i] && a[i] <= 50000) cnt[a[i]]++;
    }
    init(val);
    ans[qry[0].i] = val;

    for (int i = 1; i < q; i++) {
        while (l < qry[i].l) remove(val, a[l++]);
        while (l > qry[i].l) add(val, a[--l]);
        while (r > qry[i].r) remove(val, a[r--]);
        while (r < qry[i].r) add(val, a[++r]);
        ans[qry[i].i] = val;
    }

    for (int i = 0; i < q; i++) cout << ans[i] << '\n';
}

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);

    int t;
    cin >> t;
    for (int _ = 1; _ <= t; _++) {
        cout << "Case #" << _ << '\n';
        solve();
    }

    return 0;
}

솔브드 굿즈는 어떻게 탄생했을까

솔브드는 문제해결을 좀 더 재밌게 할 수 있도록 항상 여러 고민들을 하고 있습니다. 항상 솔브드의 기획을 도와 주시는 havana723님의 아이디어로 이번에는 (문제해결 자체와는 약간 거리가 있지만) 시즌 2 종료를 기념으로 지금까지의 성과를 모아볼 수 있는 개인화 굿즈를 만들었습니다. 시즌 2 종료 시점의 프로필과 1년간의 변화량, 그리고 스트릭이 있는 아크릴 굿즈 등입니다. 지난 1년을 돌아보고 다음 1년의 의지를 다지는 계기가 되길 바라는 마음으로 준비했습니다.

이번 굿즈 샵의 총 주문 건은 정확한 값을 밝힐 수는 없지만 몇 백에서 천몇 백 건 쯤이었습니다. 이렇게 많은 개인화 작업을 어떻게 했는지 시행착오와 우여곡절을 이야기해 보려고 합니다.

시제품

아크릴 굿즈의 제작은 디자인으로부터 시작됩니다.

디자인은 굿즈 제작에서 제일 쉬운 부분입니다. 다만 고려해야 할 점들이 있습니다. 바로 인쇄가 되는 방식인데요, 인쇄 방식이 다소 특이해서 인쇄소에 세 개의 파일을 제출해야 합니다.

아크릴은 기본적으로 투명한 재료입니다. 투명한 매체에 한 번만 인쇄하면 글씨도 투명해지기 때문에, 보통 위 그림과 같이 색상을 1차로 인쇄하고, 거기에 흰색 잉크로만 2차로 인쇄해 발색이 선명하도록 합니다. 뒷면이 흰색이면 예쁘지 않기 때문에 색상을 3차로 한 번 더 인쇄해 앞뒷면이 같도록 할 수 있습니다. 앞면에 인쇄된 내용의 손상을 막기 위해 앞면이 아니라 뒷면에 차곡차곡 인쇄됩니다.

따라서 디자인은 하나를 하더라도 인쇄소에 보낼 파일은 총 세 개가 됩니다. 아크릴 모양을 결정하는 칼선 파일, 인쇄할 내용을 결정하는 색상 파일, 그리고 인쇄 영역 중 발색을 선명하게 할 부분을 결정하는 흰색 파일입니다. 또, 뒷면에 인쇄하기 때문에 파일은 전부 좌우반전되어 있어야 합니다.

일반적인 아크릴 굿즈 작업파일은 아래와 같이 됩니다.

인쇄물이기 때문에 색상 작업은 CMYK로 해야 하는데요, CMYK는 잉크의 비율로 색상을 나타내는 방법이기 때문에 따로 ‘투명도’라는 개념이 없고, 따라서 투명과 흰색이 구별되지 않습니다. 그런 이유로 흰색 파일에서 흰색으로 인쇄할 영역은 대신 검정 잉크 100%로 작업해야 합니다.

그리고 보통 제가 사용하는 글꼴이 인쇄업체에 설치되어 있지 않은 경우도 일반적이기 때문에 모든 글자를 도형으로 바꿔서 파일로 전달해야 합니다.

여기까지가 이제 제가 일상적으로 하는 일입니다. 디자인을 시작한 시점부터 여기까지 오는 데에는 하루면 충분합니다. 다만 이건 한 종류의 디자인을 할 때의 이야기입니다.

많은 종류의 디자인을 작업해야 한다면

하지만 몇십 몇백 종류의 디자인을 작업해야 한다면 이야기는 조금 달라집니다. 이번 굿즈 샵의 경우가 딱 그렇습니다. 주문자의 1년 통계를 불러와서 디자인에 적용해야 합니다.

디자인 프로그램은 그렇게 친절하지 않습니다. 값을 하나하나 바꾸고, 글자들을 도형으로 바꾸고, 좌우반전하는 과정을 거쳐야 합니다. 이 과정에서 실수를 하지 않기란 어렵습니다.

하지만 우리가 누군가요, 개발자잖아요! 아마도 이런 작업을 자동화할 수 있는 좋은 방법이 있을 겁니다.

첫 번째 방법 — ExtendScript (실패)

제가 아크릴 파일을 제작하는 프로그램인 Adobe Illustrator에도 이런 자동화에 대한 수요가 많기 때문에 ‘액션’이라는 기능을 제공합니다. 일련의 작업 과정을 ‘녹화’하고, 나중에 액션을 한 번 클릭하면 녹화한 작업 과정을 그대로 실행해 줍니다. 말 그대로 매크로 같은 기능입니다.

그리고 더 나아가서 ExtendScript라는 자체 스크립팅 언어로 매크로를 짤 수도 있습니다. 예전에는 ExtendScript Toolkit이라는 자체 IDE를 제공했지만, 요즘은 VS Code 확장 플러그인을 설치해서 VS Code에서 ExtendScript 코드를 작성할 수 있습니다.

ExtendScript Toolkit

말이 ExtendScript지 사실 JavaScript와 거의 유사한 언어라서, TypeScript로 밥을 벌어먹고 있는 제가 쓰기에는 최고라고 생각했습니다. 이 기능이 있다는 걸 생각해내자마자 이 스크립트로 굿즈 파일을 자동 생성해 보기로 결심하고, 리서치에 들어갔습니다. ExtendScript가 JavaScript ES3 기반이라는 걸 알기 전까지는 순탄해 보였습니다.

저는 TypeScript 없는 환경에서 작업하지 않기 때문에 어떻게든 모던한 개발 방식으로 코드를 작성하고, 하나의 매크로 파일로 묶어 보려고 환경을 구성을 시도했습니다. Webpack과 TypeScript를 쓸 수 있으면 좋을 것 같습니다.

타입 정의와 API 문서

타입 정의는 따로 Adobe에서 제공하는 것은 없고, 대신 types-for-adobe라는 패키지가 있습니다. 문서도 docsforadobe.dev에 올라와 있는데, 공식인지 아닌지는 잘 모르겠습니다.

Typescript: "target": "es3"

놀랍게도 tsconfig.json의 target 필드의 값으로 es3이 허용됩니다1, 2. TypeScript 컴파일러 tsc는 아래와 같은 코드를…

`Hello ${person}, today is ${date.toDateString()}!`;

… 이렇게 바꿔 줍니다.

"Hello ".concat(person, ", today is ").concat(date.toDateString(), "!");

와, 즐겁네요! 이제 ES6 기능을 마구마구 쓰면서 개발할 수 있겠습니다.

아래 코드가 실행되지 않는 걸 경험하기 전까지는 말이죠.

elements.forEach((e) => e.move(groupItem, ElementPlacement.PLACEATBEGINNING));

로그를 열어 보니 forEach가 없다고 합니다. 아니, downleveling 잘 해 준다며요!

애석하게도 forEach라던가 Map, Set 같은 것들은 polyfill되지 않습니다. 이런 것들은 직접 polyfill해 줘야 합니다.

core-js

좋아요, polyfill이라는 단어가 나왔으니 core-js를 써 봅시다. webpack.config.js를 만들고, @babel/preset-env 같은 걸 구성해 봅시다.

그러면 이제 아래 코드가 실행이 안 됩니다.

x >= 10 ? x.toString() : x < 0 ? '00' : `0${x}`

이건 또 왜일까요?

ES3 스펙

ES3 스펙은 삼항 연산자 안에 삼항 연산자를 쓸 수 있도록 되어 있습니다3. 여기서 하나 상기해야 되는 사실이 있습니다. 이 코드가 돌아가는 환경은 어떤 Node 런타임과도, 어떤 브라우저와도 다르다는 사실입니다.

안타깝게도 ExtendScript는 ES3 같은 무언가지 ES3 그 자체가 아닙니다. Adobe가 ES3을 구현하려고 노력한 결과물입니다. 구현에 성공한 결과물이 아닙니다.

그런 이유로, ExtendScript에서 삼항 연산자 안에 삼항 연산자를 바로 적는 것은 허용되지 않습니다. 괄호를 씌워줘야 합니다(a ? (b ? c : d) : e)4.

ESLint 입장에서는 이런 환경은 듣도 보도 못했으므로 당연히 빨간 줄도 안 그어 줍니다. 빨간 줄을 그어 주기 위해 babel 플러그인을 만들어야 했습니다.

module.exports = function (babel) {
  const { types: t } = babel;

  return {
    name: "wrap-ternary-in-parentheses",
    visitor: {
      ConditionalExpression(path) {
        const { node } = path;

        // Only transform if not already in parentheses
        if (!t.isParenthesizedExpression(path.parent)) {
          const parenthesizedExpression = t.parenthesizedExpression(node);
          path.replaceWith(parenthesizedExpression);
        }
      },
    },
  };
};

유감스럽게도 이와 같은 코드를 몇 개 더 짜야 했습니다.

산 넘어 산

일단 어떻게든 샘플 데이터로 태그 레이팅 아크릴을 그리는 데에 성공했습니다. 이제 자동화를 해야겠죠? 일단 ExtendScript로 전부 해 보려고 했습니다.

여기서 ExtendScript와 일반적인 자바스크립트 환경이 갖는 또 다른 차이점이 발목을 잡습니다. ExtendScript에는 fetch가 없습니다. 이 정도는 예상했으니까 그럴 수 있다고 칩시다. 그런데 XMLHttpRequest도 없습니다. ExtendScript가 네트워크와 통신할 수 있는 유일한 방법은 소켓을 직접 여는 것뿐입니다.

system.callSystem()이라는 게 있긴 한데, 이건 Illustrator에는 없고 Bridge라는 다른 앱에만 있는 기능이라, BridgeTalk 같은 걸 써야 했습니다. 이걸로 curl 해서 가져올 수 있는가 싶었는데, 결과적으로 잘 안 됐습니다.

자동화를 솔브드의 관리자 API를 직접 호출하는 방법으로 하려고 했는데, 이래서는 TCP 소켓을 기반으로 HTTP와 HTTPS를 직접 구현해야 했습니다. 다행히도 JSXGetURL이라는 확장 프로그램이 어느 정도 해결해 줬으나, 플러그인을 유료로 판매하는 경우가 많은 그래픽 디자인 도구 시장 특성상, (작업하던 5월 당시에는) 플러그인 개발자께서 6월이 지나면 해당 확장 프로그램의 동작을 멈추게 하고 유료 판매 모델을 도입하려고 했던 것 같습니다. 지금은 해당 시한이 12월로 연기된 것으로 보이는데, 당시에는 사용 시간 제한이 너무 큰 단점으로 다가왔습니다. 7월에도 수정 작업을 해야 할 수 있었으니까요.

그래도 할 수 있는 데까지 한 번 해 보리라 생각했습니다. 다만 여기까지 만든 후 문서화되어 있지 않은 ExtendScript와 JS의 차이점, 그리고 부실한 Illustrator API 문서에 너무 스트레스를 받아서 도저히 더 이상 할 수 없다고 판단했고, 이 방법은 그만뒀습니다.

이 정도까지 구현했습니다.

두 번째 방법 — SVG 생성

ExtendScript로 작업을 했던 이유는 CMYK 색상 공간에서 작업하기 용이해서였습니다. 특히 흰색 잉크 인쇄 레이어는 K100 색상으로 작업되어야 했는데요, CMYK의 K100과 RGB의 #000000은 전혀 다른 색상이기 때문에 이런 부분을 해결해줄 수 있겠다고 생각했기 때문이었음이 가장 큰 이유였습니다.

#000000은 C93 M88 Y89 K80으로 변환됩니다.

ExtendScript를 쓸 수 없다면, 이미지를 SVG 형식으로 만들 수 있는지 고민해보기로 합니다. SVG는 벡터 그래픽으로, 이미지를 여러 도형들로 정의하는 표현 방식입니다. Illustrator는 SVG 포맷을 읽을 수 있습니다.

SVG의 색상 공간은 RGB이기는 해서, 흰색 잉크 레이어를 검정색 이미지로 만들면 K100이 나오지는 않는데요, 대신 도형은 색상 변경이 이미지보다 훨씬 편리하기 때문에 Illustrator로 가져온 뒤 K100으로 색상만 바꿔 주면 됩니다.

이제 SVG를 어떻게 자동으로 생성할 것인지만 고민하면 됩니다.

도와주세요, 사토리님!

갑자기 뭔 오타쿠 게임을 들고 오나 싶을 수 있겠는데요, 귀엽고 재밌는 스무고개 게임이니 관심이 있으시다면 꼭 해 보시기 바랍니다. 오타쿠 게임을 통해 힘든 개발 과정을 이겨내고 뭐 그런 건 아닙니다.

예전에 Vercel이 오픈 그래프(OG) 이미지를 생성하는 기능을 추가했다고 홍보한 적 있어서, 기반 기술에 대해 관심을 갖고 찾아본 적이 있습니다.

해당 기술은 HTML과 CSS과 비슷한 문법의 코드를 작성하면 SVG로 바꿔 주는 라이브러리 satori를 기반으로 하고 있습니다. 오픈 소스여서 누구나 쓸 수 있습니다.

OG 이미지에 대한 이야기를 잠깐 하고 넘어가 봅시다. HTML + CSS가 워낙 괜찮은 레이아웃 엔진이라 OG 이미지를 HTML과 CSS 기반으로 만드려는 시도는 많이 있었는데요, 다 좋은데 HTML과 CSS는 너무 기능이 많아서 HTML과 CSS로 OG 이미지를 렌더하려면 브라우저를 켜서 캡쳐해야 했습니다. 자동화는 되지만 꽤 느립니다.

satori는 반면에, 비슷한 문법으로 이미지 렌더에 꼭 필요한 기능들만을 별도의 렌더 방법으로 제공함으로서 브라우저를 켜지 않아도 되게 하여 이 문제를 해결합니다. 아니, HTML이면 HTML이고 CSS면 CSS지 무슨 비슷한 문법일까요?

satori는 React 렌더러입니다. React 렌더러가 무엇인가 하면, 쉽게 말하면 react-native 같은 겁니다. react-native도 JSX 코드를 짜지만 ‘렌더’되면 DOM 트리가 나오는 게 아니라 여러 플랫폼의 네이티브 코드가 나오죠. 이렇게 React는 간혹 DOM 이외의 곳들에서도 쓰이는데, 심지어는 React로 영수증을 생성할 수 있는 프로젝트 react-thermal-printer도 있습니다.

여하튼 satori가 ‘렌더’하는 것은 SVG 코드입니다. 이미지 내 요소들을 프론트엔드 개발자에게는 너무 익숙한 선언적 방법으로 작성할 수 있게 해 주고, flexbox와 최대한 비슷하게 동작하는 자체 레이아웃 엔진을 구현해 친숙한 개발 방법도 챙겼습니다. 이미 JavaScript + React로 많은 걸 짜 왔던 솔브드의 입장에서는 레이아웃 구현의 공수가 낮으리라 예상했습니다. 실제로 solved.ac 프로필 상단부 레이아웃을 satori를 이용해 구현하면 이렇게 됩니다.

<span
  style={{
    fontSize: 48,
    fontWeight: 700,
  }}
>
  {handle}
</span>
{badge !== null && (
  <img
    src={badge.badgeImageUrl}
    style={{
      width: 64,
      height: 64,
      filter: 'drop-shadow(0 8px 8px rgba(100, 100, 100, 0.3))',
      marginLeft: 12,
    }}
  />
)}
<img
  src={classImgUrl(classValue, classDecoration)}
  style={{
    width: 72,
    height: 72,
  }}
/>

정말 편하게 레이아웃을 구성할 수 있었습니다. 모든 과정이 순탄합니다.

자동 생성을 고려해 봅시다. 저번에 ExtendScript로 했던 방식과 다르게 이제 아예 서버에 적당한 파라미터로 GET 요청을 보내면 서버에서 SVG 코드를 계산해 주도록 합니다. 이제 주문 목록을 기반으로 서버에 이미지 생성 리퀘스트를 보내고, 서버가 보내온 SVG를 어딘가 저장하는 스크립트를 짜면 자동 생성 완료입니다. 그런 고로, 위에 적은 코드는 솔브드의 클라이언트에 있는 코드가 아니라 API 서버에 있는 코드입니다.

이제 특정 URL에 주문번호만 넣으면 해당 주문번호의 굿즈를 자동 생성해 줍니다.

앞서 말했듯이 걱정했던 것들 중에 폰트 문제도 있었는데요, 웹 폰트 환경과 디자인 프로그램에서의 폰트 환경은 약간 달라서 변환이 필요할까도 고민이었는데, 스크린샷을 보시면 아시겠지만 satori가 텍스트를 애초에 모양을 따서 도형으로 렌더해 줘서 이런 고민이 필요없었습니다. 폰트를 읽는 정도의 능력이라니 대단하군요. 이제 이걸 Adobe Illustrator에 가져오기만 하면 됩니다.

일반적인 Express.js 프로젝트에서 이런 디펜던시를 보게 될 일이 얼마나 있을까요?

난관

그러나 당연하게도 이런 일반적이지 않은 작업이 순탄할 리가 없습니다.

Adobe Illustrator는 SVG를 지원합니다. 적어도 저는 그렇게 알고 있었습니다. 하지만 막상 파일을 가져오려고 해 보니 뭔가 불길한 경고가 뜹니다.

무슨 일이 일어날까요? 정말 기대가 됩니다.

오…

Illustrator는 제가 열심히 만든 SVG는 전혀 읽지 못하는 기염을 보여줍니다.

알아보니까 Illustrator는 SVG의 <mask> 요소를 그렇게 좋아하지 않는 것 같습니다5,6. 게다가 <image> 요소의 이미지 URL을 나타내는 src 속성에 Base64로 표현된 이미지가 있는데, 브라우저는 완벽하게 읽어 주지만 Illustrator는 이게 무슨 말인지 모르는 것 같아 보입니다.

SVG의 구조를 변경할 수 있을까 싶어서 satori가 생성한 SVG를 열어봤는데 <mask> 요소 없이는 아무것도 그리지 못할 것 같은 구조였습니다. 막다른 길을 만난 걸까요?

세 번째 방법 — PNG 생성

애초에 이런 고민들을 했던 이유는 마스크가 K100이어야 하기 때문이었습니다. 굳이 SVG가 아니더라도 RGB 색상 공간의 이미지를 불러와 CMYK의 K100으로 바꿀 수 있는 기능이 Illustrator에 있으면 됩니다. 메뉴 이곳저곳을 뒤져보다가 뭔가 그럴싸한 메뉴를 발견했습니다. ‘편집 > 색상 편집 > 회색 음영으로 변환’이었습니다.

CMYK 모드의 문서에서 ‘회색 음영’이 뜻하는 건 단 하나밖에 없을 것 같습니다. 속는 셈 치고 눌러 봅시다.

성공했습니다. 완벽한 K100입니다. 진작 메뉴부터 뒤져볼 걸…

뭔가 처음 생각했던 개발 방법과는 많이 달라진 느낌이 없지 않지만 여하튼 이제 정말로 굿즈를 자동 생성하기 위한 모든 퍼즐 조각이 모였습니다. 이제 맞추기만 하면 됩니다.

resvg를 사용하면 SVG를 PNG로 렌더할 수 있습니다. Express 서버에 아래 네 줄만 추가해 주면 됩니다. 다만 역시 PNG 렌더 과정이 추가되니 SVG보다는 다소 느렸습니다.

  const resvg = new Resvg(svg, opts)
  const pngData = resvg.render()
  const pngBuffer = pngData.asPng()

  res.contentType('image/png').send(pngBuffer)

이제 정말로 자동화에 돌입합니다. Illustrator에는 ‘변수’라는 기능이 있습니다. CSV로 ‘데이터 세트’를 정의하면 여기에 저장된 값을 그대로 가져다 쓸 수 있고, 각 데이터 세트마다 어떤 매크로를 실행하게 할 수 있습니다. 약간 디자이너 버전 forEach 함수 같은 느낌입니다.

데이터 세트의 변수 유형으로는 이미지도 있습니다. 파일시스템 내의 경로를 CSV 파일 내에 정의해 주면 됩니다. 예를 들어 이렇게요.

ItemId,@Profile,@ProfileMask,@Streak,@StreakMask
41,/Users/shiftpsh/merch-generate/images/41_profile.png,/Users/shiftpsh/merch-generate/images/41_profile_mask.png,/Users/shiftpsh/merch-generate/images/41_streak.png,/Users/shiftpsh/merch-generate/images/41_streak_mask.png
60,/Users/shiftpsh/merch-generate/images/60_profile.png,/Users/shiftpsh/merch-generate/images/60_profile_mask.png,/Users/shiftpsh/merch-generate/images/60_streak.png,/Users/shiftpsh/merch-generate/images/60_streak_mask.png
103,/Users/shiftpsh/merch-generate/images/103_profile.png,/Users/shiftpsh/merch-generate/images/103_profile_mask.png,/Users/shiftpsh/merch-generate/images/103_streak.png,/Users/shiftpsh/merch-generate/images/103_streak_mask.png

일단 이런 CSV를 생성해 주는 Python 스트립트를 만들었습니다. 대충

  • 주문 목록을 가져오고
  • 하나의 주문 당 한 번, Express 서버에 아크릴 이미지 파일 생성 요청을 보내고, 그걸 PNG로 저장
  • 저장된 파일의 절대 경로를 CSV에 작성

하는 코드입니다.

def main():
    rows = read_file()
    print(f"Found {len(rows)} orders")
    count = 0

    with open('s2_2023_merge.csv', 'w') as csvfile:
        writer = csv.writer(csvfile)
        writer.writerow([
            "ItemId",
            "@Profile", "@ProfileMask",
            "@Streak", "@StreakMask"
        ])
        for row in rows:
            count += 1
            print(f"Downloading images for order {row[0]}... ({count}/{len(rows)})")
            item_id = row[0]
            order_id = row[1]
            writer_out = [item_id]
            for image_id in image_ids:
                filename = f"images/{item_id}_{image_id}.png"
                filename_mask = f"images/{item_id}_{image_id}_mask.png"
                download_and_save_image(image_url(order_id, image_id, item_id, False), filename)
                download_and_save_image(image_url(order_id, image_id, item_id, True), filename_mask)
                writer_out.append(filename_prefix + filename)
                writer_out.append(filename_prefix + filename_mask)
            writer.writerow(writer_out)

이렇게 생성된 CSV 파일을 Illustrator에 넣어 줍니다. ‘변수 > 변수 라이브러리 불러오기…’를 선택하면 데이터 세트를 불러올 수 있습니다.

이제 이미지를 로드한 직후 저장 직전까지 수행할 작업들을 ‘액션’으로 정의합니다.

할 일들을 액션으로 정의하면 ‘액션 > 일괄 처리’를 통해 데이터 세트에 대해 앞서 언급한 forEach 같은 걸 돌릴 수 있게 됩니다. 제 경우에는 두 번째 캔버스에 그려지는 마스크의 검정색(#000000)을 K100으로 바꿔야 했기 때문에 ‘회색 음영으로 변환’을 넣어 줬습니다.

이제 정말로 굿즈가 자동 생성됩니다! 작업을 돌려 놓고 쉬다 오면 생성이 완료될 겁니다. 생성 완료된 파일은 인쇄소에 바로 전달할 수 있는 형태입니다.

발주

엄청난 박스들이 왔습니다. 잠잘 공간만 겨우 남긴 채로 5일 동안 포장을 했습니다.

뒤늦게 깨달은 실수

이상한 점을 찾아봅시다.

2023년 6월 5일 오전 6시를 기준으로 생성해야 하는 프로필 그래픽이 무슨 이유에서인지 2023년 6월 4일 오후 9시를 기준으로 생성되었습니다. 대체 왜일까요?

한국 시각 오전 6시니까 UTC 기준 전날 오후 9시인 건 맞는데, 크게 간과한 부분이 있습니다. 위의 코드는 틀렸습니다. 대신 아래와 같이 적어야 합니다.

new Date('2023-06-04T21:00:00Z')
// or
new Date('2023-06-05T06:00:00+09:00')

로컬에서 서버를 돌렸기 때문에 당연히 시간대를 표시하지 않았으니 저 줄은 한국 시각으로 해석되고, 9시간 앞선 데이터로 굿즈를 만들어 발주하게 된 것입니다. NASA가 인치와 센티미터를 헷갈려서 위성을 추락시킨 사례를 처음 듣고 웃어넘겼는데 그런 기관이 할 수 있는 실수라면 저도 마땅히 할 수 있는 것이었습니다. 오만해지지 말아야 합니다. 네.

인쇄 사고가 발생한 굿즈를 전량 다시 제작했고 다시 보냈습니다. 결국에 굿즈 샵 캠페인을 열고 남은 건 없습니다. 여러분이 남습니다.

짧은 소감

이외에도 굿즈 샵 개최를 위해 결제모듈을 연동하고 쇼핑몰 시스템을 자체 제작하는 등 해 보지 않았던 시도들을 해 보면서 재밌게 개발했습니다. Express 프로젝트에 React 설치해서 굿즈 자동화 하는 건 여태까지 듣도 보도 못한 개발 과정이고 어디서도 해보지 못할 경험인 것 같습니다.

서버비에 도움이 될까 기대했는데 이 부분에서는 너무 큰 실수를 해서 안타깝고 아쉽습니다. 아무리 테스트와 점검이 귀찮고 힘들고 오래 걸리더라도 이렇게 중요한 일을 하기 전에는 제대로 점검해야겠다는 생각을 하게 된 계기를 마련하게 되었습니다. 위성 추락보다는 싸게 배웠으니 다행입니다.

끝으로 솔브드에 많은 관심 가져 주셔서 항상 감사드립니다!

각주

  1. https://www.typescriptlang.org/tsconfig#target
  2. https://www.typescriptlang.org/docs/handbook/2/basic-types.html#downleveling
  3. https://www-archive.mozilla.org/js/language/e262-3.pdf, 168쪽
  4. https://community.adobe.com/t5/after-effects-discussions/extendscript-throws-on-nested-ternary-operator/m-p/9573874
  5. https://community.adobe.com/t5/illustrator-discussions/illustrator-does-not-understand-svg-masks/m-p/12408862
  6. https://github.com/MakieOrg/Makie.jl/issues/882

(번역) 2023-2024 ICPC 아시아태평양지역 선발규정

이 포스트는 the Asia Pacific rules for 2023-2024의 번역본입니다.


아래 규정은 남태평양(호주, 뉴질랜드 등) 팀에는 적용되지 않습니다. 남태평양 지역의 월드 파이널 팀 선발은 아시아태평양 리저널과 상관없이 남태평양 리저널로만 결정됩니다.

기본 규정

A1. 한 팀은 최대 2개까지의 리저널에 참가할 수 있습니다.

A2. 예선대회가 존재하는 리저널이라면, 해당 리저널 개최국의 팀들은 해당 예선대회를 통한 선발 과정을 거쳐야만 합니다.

A3. 리저널은 아시아태평양지역 내의 해외 팀이 등록할 수 있도록 해야 합니다. 각 리저널은 해외 팀의 수에 상한을 둘 수 있습니다. 리저널의 디렉터는 해외 팀의 선발과 관련한 규칙을 둘 수 있습니다.

A4. 리저널은 남태평양지역 또는 동아시아지역 등의 다른 슈퍼리저널의 팀이 등록할 수 있도록 해도 됩니다. 이 팀들은 아시아태평양지역 리저널으로부터 월드 파이널 진출권을 얻지는 못합니다.

A5. 리저널을 개최하는 국가의 팀은 해외 리저널을 2개 참가해서는 안 됩니다.

월드 파이널 선발규정 (리저널 우승으로부터)

B1. 각 리저널의 우승자는 월드 파이널 진출권을 얻습니다. ‘우승자’란 리저널 참가팀 중 남태평양지역 및 다른 슈퍼리저널 출신 팀들을 제외하고 가장 높은 순위를 획득한 팀을 말합니다.

B2. 한 대학에서 두 개 이상의 팀이 리저널에서 우승하는 경우, 그 중 한 팀만 월드 파이널 진출권을 얻습니다. 어떤 팀이 진출권을 얻을지는 대학에서 결정하여야 합니다. 대학은 원한다면 해당 팀들을 플레이오프에 출전시켜 플레이오프에서의 순위를 기준으로 진출권을 배정하도록 할 수도 있습니다. 이 경우 해당 팀들은 플레이오프에 초청됩니다(D1 참조).

B3. 한 대학의 여러 리저널 우승팀 중 월드 파이널 진출권을 얻는 팀을 플레이오프를 통해 결정하는 경우(B2 참조), 다른 대학의 팀들의 플레이오프 성적과 관계없이 해당 대학 팀들 중에 순위가 가장 높은 팀이 월드 파이널 진출권을 얻습니다.

리저널 상수

C1. 각 리저널은 다음과 같이 정의된 리저널 상수 $S$를 가집니다.

\[\begin{aligned}S&=0.56\times\text{리저널 출전 대학 수} \\ &+ 0.24\times\text{리저널 출전 팀 수} \\ &+ 0.14\times\text{예선대회 출전 대학 수} \\ &+ 0.06\times\text{예선대회 출전 팀 수} \\ &+0.30\times\text{리저널 출전 해외 팀 수} \end{aligned}\]

리저널 상수의 계산에는 1문제 이상을 해결한 팀만을 고려합니다. 남태평양지역 또는 동아시아지역 등의 다른 슈퍼리저널의 팀도 상수 계산에 고려합니다.

  • (노트) 위 공식은 2020년 이후 아시아태평양지역 선발규정에서 가져온 것입니다.

플레이오프에서의 선발규정

D1. 리저널 우승팀들은 플레이오프에 오픈 참가팀으로 초청합니다. 이 팀들의 플레이오프에서의 성적은 월드 파이널 진출권에 영향을 미치지 않습니다. 단, 규정 B2 및 B3에 의한 예외가 존재합니다.

  • (노트) 우승 대학에서 우승팀만이 플레이오프에 초청됩니다. 우승 대학의 2등 및 3등 이하 팀은 초청되지 않습니다.
  • (노트) 해당 팀은 플레이오프 성적에 따른 순위를 부여받으나, 규정 E1(1)에서 고려하지 않으므로 다른 팀의 진출권에 영향을 미치지 않습니다.

D2. 각 리저널의 순위에 다음을 순차적으로 적용해 새 순위표를 만듭니다.

  1. 남태평양지역 또는 동아시아지역 등의 다른 슈퍼리저널의 팀을 제외합니다.
  2. 한 문제도 해결하지 않은 팀을 제외합니다. 1문제 이상 해결한 팀만을 남깁니다.
  3. 이전 단계에서 상위 50%만을 남깁니다. 이는 하위 50%는 플레이오프에 초청되지 않음을 의미합니다.
    • (노트) 3단계의 의도는 하위 50%가 플레이오프에 초청되는 일을 막기 위함입니다. 이는 규정 D3(3)에서 과소대표된 국가의 팀이라도 상위 50%의 성적을 거두지 못하면 플레이오프로 초청하지 않는 등의 드문 경우에만 발생합니다.
  4. 우승 대학의 팀을 제외합니다. 우승 대학은 우승 팀의 소속 학교입니다(B1 참조). 이 리저널 및 아시아태평양지역의 다른 리저널의 우승 대학에 대하여 이 과정을 적용합니다.
  5. 각 대학에서 4위 및 그 이하의 팀을 제외합니다.
    • (노트) 각 대학에서 플레이오프에 초청되는 팀 수는 최대 3팀입니다(D3(2) 참조).
  6. 남은 팀을 기준으로 순위를 다시 매깁니다. 다시 매긴 순위를 $R$이라고 할 때, 각 팀에 다음 값을 배정합니다.\[\frac{R-1}{S}.\]여기서 $S$는 리저널 상수입니다(C1 참조).
    • (노트) 이 정의와 다음 단계는 Shieh-Ishihata 공식을 기반으로 합니다. 이는 코로나19 이전 아시아태평양지역의 월드 파이널 팀 선발 규정의 주요 부분이었습니다.

D3. 아시아태평양지역의 모든 순위표를 합치고 다음을 순차적으로 적용합니다.

  1. 합친 리스트를 팀에 배정된 값을 기준으로 정렬합니다.
  2. 한 팀에 두 개의 항목이 존재한다면, 두 번째 항목을 제외합니다. 이후, 한 대학에 네 개 이상의 항목이 존재한다면, 네 번째 및 그 이후의 항목을 제외합니다. 이는 한 대학에서 최대 세 팀이 초청됨을 의미합니다.
  3. 아시아태평양지역의 각 국가에서 이 값이 가장 작은 팀을 한 팀씩 선발합니다. 이 팀들은 플레이오프에 초청됩니다.
    • (노트) 이는 과소대표된 국가들을 위한 와일드카드 규정입니다. 이 규정으로 인해 각 국가마다 한 팀 이상이 초청됩니다. 단, 초청되는 팀은 리저널에서 적어도 상위 50%의 성적을 거둬야 합니다(D2(3) 참조).
  4. 플레이오프 참가팀 수를 $P$로 둡니다. (3)에서 선발된 팀들을 제외하고, 팀에 배정된 값이 작은 순서대로 $P$팀이 될 때까지 선발합니다. 이 팀들은 플레이오프에 초청됩니다.

D4. 플레이오프로 초청된 팀이 출전을 포기하는 등 플레이오프로의 추가선발이 필요할 경우, 해당 팀을 모든 리저널의 순위표에서 제외한 후 D2와 D3의 규정을 다시 적용하여 선발합니다.

  • (노트) 이 경우 리저널 상수는 다시 계산하지 않습니다.
  • (노트) 플레이오프 출전 포기에 의한 불이익은 없습니다.

월드 파이널 선발규정 (플레이오프로부터)

E1. 월드 파이널 팀은 우선 B1 — B3으로 선발됩니다. 이후에, 플레이오프에서 상위 성적을 거둔 팀들이 아래와 같이 선발됩니다.

  1. 우승 대학의 오픈 참가팀을 제외합니다(D1 참조).
  2. 각 대학의 2위 또는 그 이하 팀을 제외합니다.
  3. 아시아태평양지역에 배정된 월드 파이널 슬롯의 수가 $N$개이고, B1 — B3으로 인해 선발된 팀의 수가 $M$팀이라면, 남인 팀 중 상위 $N-M$팀을 선발합니다.

UCPC 2023 예선 간략한 후기

전대프연 스탭을 하려다가 너무 바빠서 계획을 취소했기 때문에 올해는 참가자로 나왔습니다. 작혼우인전3of4너만오면고 팀으로 @havana723, @ydk1104 님과 함께 출전했고, 7문제를 풀었습니다(ABCDHIK).

저희 전략은 구현이 빠른 제가 구현을 다 하고, 제가 구현을 하는 동안 다같이 풀이를 생각하는 거였습니다. 간략한 풀이와 대회 중에 있었던 일 등을 소개합니다.

A. 체육은 코딩과목 입니다

+, 86초(페널티 1분). B4.5, #implementation, #arithmetic

@shiftpsh가 사이트가 열리자마자 보고 풀었습니다. UCPC 예선은 항상 첫 문제가 가장 쉬운 문제입니다.

북쪽을 기준으로 오른쪽으로 얼마나 많이 돌았는지를 저장합시다.

왼쪽으로 $90$도 돈다는 건 오른쪽으로 $270$도돈다는 것과 같으니까, $t_i$들을 다 더하고 $4$로 나눈 나머지를 보는 것만으로 충분합니다. 이 값이 $0$이면 그대로 북쪽입니다. 가장 시간이 오래 걸린 부분은 오른쪽이 동쪽이 맞는가가 생각이 바로 안 났던 부분인 것 같습니다.

저는 A를 풀고, H가 쉬워 보인다는 의견에 H를 잡으러 갔습니다.

D. 더 흔한 타일 색칠 문제

+, 26분(페널티 26분), S3, #implementation, #greedy

@havana723이 스코어보드를 보고 쉬운 문제라고 보고 잡았고, 바로 풀었습니다.

각 $K\times K$ 영역의 $i$행 $j$열에 나오는 문자를 봅시다. 모든 영역들에 걸쳐 어떤 문자가 몇 번씩 나왔는지 보고, 가장 많이 나온 문자로 바꿔 주면 됩니다.

처음에 D 지문의 형태를 보고 호락호락하지 않을 거라고 생각하고 넘어갔는데, 쉬운 문제였습니다.

I. 자석

+, 29분(페널티 29분), S1, #ad_hoc

@shiftpsh가 H를 보다가 좀 아닌 것 같아서 많이 풀린 I를 봤고, 바로 풀었습니다.

S극을 N극에 왼쪽에 놓는 경우는 그냥 배열을 뒤집어 놓고 N극을 왼쪽에 놓는 경우와 같으므로, 일반성을 잃지 않고 N극을 왼쪽에 놓는 경우만 생각하면 됩니다.

N극을 $i$번 위치에, S극을 $j$번 위치에 놓는다고 생각해 보면 변화량은 $a_i-a_j+K(j-i)$만큼입니다. $K(j-i)$ 부분이 없다면 $i$번째 위치 이전까지의 최댓값을 전처리하는 변수 $mx$를 만들어서 다음과 같은 알고리즘으로 쉽게 구할 수 있습니다.

for i = 0..n - 1
    answer = max(answer, mx - a[i])
    mx = max(mx, a[i])

$K(j-i)$ 부분이 문제인데, \[a_i-a_j+K(j-i)=(a_i-Ki)-(a_j-Kj)\] 로도 쓸 수 있습니다. 따라서 새로운 배열 $b_i=a_i-Ki$를 만들어 놓고 $b$에 대해서 위의 알고리즘을 돌리면 됩니다.

K. 세미나 배정

+, 52분(페널티 52분), G3, #parametric_search, #greedy

풀이를 @ydk1104가 냈고, 그걸 @havana723이 구현했습니다.

세미나 수의 최솟값에 대해 이분 탐색을 합시다. 최솟값을 고정하면 스케쥴이 만족 가능한지는 그리디하게 판정할 수 있습니다.

제가 문제를 안 봐서 잘 모르기는 합니다만, 팀원 분들의 의견에 의하면 이분 탐색에서 그리디하게 판정하는 과정에서 off-by-1 등 디테일하게 신경쓸 부분이 많았다고 합니다. 저는 그 동안 C를 짜고 있었습니다.

C. 차량 모듈 제작

+, 60분(페널티 60분), G3, #geometry, #mst, #greedy

@shiftpsh가 처음에 보고 구현이 복잡해 보여서 넘겼는데, 나중에 와 보니 그렇게 어렵지 않은 문제인 것 같아서 풀었습니다.

기어가 몇 개 안 됩니다. 기어를 노드로 생각하고, 기어와 기어를 연결하는 벨트의 길이를 비용으로 하는 $1\,000^2$짜리 완전 그래프가 있다고 생각할 수 있겠습니다. 벨트가 없어도 되면, 즉 기어와 기어가 접해 있거나 겹쳐 있다면 이 비용은 $0$입니다. 결국 최소 비용으로 모든 노드를 연결되게 해야 하는 문제가 됩니다. 이는 그래프에서 최소 신장 트리를 구하고, 모든 간선의 비용의 합을 구하는 것으로 해결할 수 있습니다.

벨트가 있을 때와 없을 때의 간선의 비용 차이는 많이 크기 때문에, 포함 관계 판정은 정확하게 해야 합니다. 포함 관계는 보통 두 원 사이의 거리 $d$가 두 원의 반지름의 합 $r_1+r_2$보다 큰지 작은지로 판정하는데, $d$는 정수로 표현하지 못하는 경우가 있을 수 있습니다. 다만 두 원 사이의 거리의 제곱 $d^2$는 정수로 표현 가능하므로, $d$와 $r_1+r_2$을 비교하는 대신 $d^2$와 $\left(r_1+r_2\right)^2$를 비교해 주면 됩니다.

벨트의 길이를 구하는 건 삼각함수에 대한 이해가 어느 정도 필요합니다. 위의 그림에서 벨트의 길이를 구하려면 $t$와 $\theta$의 값을 구해야 합니다.

일단 편의를 위해 $r_1<r_2$라고 합시다. 그리고 $\Delta r=r_2-r_1$로 둡니다. 그러면 피타고라스의 정리에 의해 \[t=\sqrt{d^2-\Delta r^2}\]가 됩니다.

$\theta$는 \[\cos^{-1} \frac{\Delta r}{d}\quad\text{또는}\quad\tan^{-1}\frac{\Delta r}{t}\]로 계산할 수 있습니다.

왼쪽 원의 호의 중심각은 $\pi-2\theta$고, 오른쪽은 $\pi+2\theta$입니다. 호의 길이는 중심각 곱하기 반지름의 길이이므로, 정리해 보면 벨트의 총 길이는 이렇게 됩니다. \[L = r_1\left(\pi-2\theta\right)+r_2\left(\pi+2\theta\right)+2t.\]

B. 물류창고

+1, 95분(페널티 115분), P3, #mst, #disjoint_set, #smaller_to_larger

모두가 머리를 맞대고 풀이를 생각했고, @shiftpsh가 구현했습니다. MST 아이디어는 @shiftpsh가, smaller to larger 아이디어는 @havana723이 생각했습니다.

첫 번째 관찰은 간선이 $M$개까지 필요하지 않을 수도 있다는 사실에 기반합니다. 상한이 작은 간선 몇 개는 절대 선택되지 않을 수도 있습니다. 조금 더 생각해 보면 주어진 그래프의 최대 신장 트리를 구하면 이 간선들만이 선택됨을 알 수 있습니다.

그러면 이제 문제 상황을 그래프가 아니라 트리로 줄여볼 수 있습니다. 이제 모든 노드의 쌍에 대해 경로의 상한의 합을 구해야 합니다.

두 번째 관찰은 문제를 작은 문제로 쪼개는 것에서 시작할 수 있습니다. 트리에서 가장 상한이 낮은 간선을 지나는 경로들을 생각해 봅시다. 이 간선을 지우면 트리는 두 개로 나눠질 것입니다(트리니까요). 각 색깔에 이 간선이 영향을 주는 경로는 대해 두 개로 나눠진 트리에서 해당 색깔을 가지는 노드의 수를 곱한 것만큼 있을 겁니다. 가장 작은 노드 순서대로 끊어 주면서 트리를 두 개로 쪼개고, 각각의 트리에서 문제를 해결할 수 있겠습니다.

그러나 일자 그래프에서 양 끝 노드들만 계속 삭제하는 상황을 생각한다면, 색상이 최대 $50\,000$개 존재할 수 있으니 여전히 굉장히 느리겠습니다.

여기서 트리를 작은 간선부터 끊어 주는 아이디어 대신 큰 간선부터 이어주는 아이디어를 생각해볼 수 있습니다. DSU를 하나 만들고, DSU 트리의 루트마다 (색상, 노드 개수)의 map을 sparse하게 관리해 줍시다. DSU에서 merge 연산을 할 때 무조건 작은 트리를 큰 트리에 붙여 주면서 작은 노드의 map에 있는 원소들을 큰 노드의 map에 누적해 줍니다. 이 테크닉은 smaller to larger라는 이름으로도 불리며, $50\,000$개의 색상의 노드가 $2$개씩 있는 최악의 경우에라도 $\mathcal{O}\left(n \log n\right)$ 정도밖에 안 걸리게 됩니다.

H. 팔찌

+4, 177분(페널티 257분), P1, #ad_hoc, #constructive, #stack

모두가 머리를 맞대고 풀이를 생각했고, @shiftpsh가 구현했습니다. Circular와 reflection이 상관이 없다는 중요한 관찰을 @ydk1104가 해 줬습니다.

첫 번째 관찰은 1번 쿼리와 2번 쿼리는 정확히 서로 반대의 역할을 한다는 점에서 착안합니다. 어떤 문자열 $A$를 어떤 과정 $r$을 거쳐 $A^\prime$으로 만들 수 있다면, 반대의 과정 $r^{-1}$로 다시 $A$로 만들 수 있습니다.

이 점을 이용해서, 주어진 두 개의 문자열 $A$와 $B$를 똑같은 문자열 $X$로 만들 수 있는지 봅시다. $A$에서 $X$로 가는 과정을 $r_A$, $B$에서 $X$로 가는 과정을 $r_B$라고 한다면, $A$에서 $B$로는 $r_Ar_B^{-1}$ 순서대로 실행하는 것으로 가능합니다.

일단 circular한 구조는 항상 linear하게 펼치고 생각하는 게 좋기 때문에, $1$번 구슬과 $N$번 구슬을 합치는 경우는 없다고 생각합시다.

두 번째 관찰은 어떤 문자열에 $1$번 연산을 가능한 한 많이 사용하면 똑같은 문자가 반복되는 형태로 만들 수 있다는 것입니다. 입력으로 받은 문자열을 순회하면서, 스택 구조를 활용해서 다음 알고리즘을 돌려 줍시다.

stack = []
for c in str
    emplace c to stack
    while length of stack >= 2
        if last two characters of the stack is same
            break
        else
            discard top two elements of the stack
            emplace the result of the 1st query to the stack

세 번째 관찰은 같은 문자가 반복되는 문자열은 홀짝성을 유지하면서 길이를 바꿀 수 있다는 것입니다. 아래는 길이를 $2$ 줄이는 연산에 대한 예입니다.

  • RRR / R → GB
  • RRGB / RG → B
  • RBB / RB → G
  • GB / GB → R

첫 번째 관찰에 의해 위의 연산들을 역으로 실행해 주면 길이를 $2$ 늘릴 수도 있습니다. 종합해 보면 모든 문자열은 R, G, B, RR, GG, BB 중 하나로 줄일 수 있습니다.

네 번째 관찰은 RR, GG, BB를 서로 바꿀 수 있다는 것입니다.

  • RR / R → GB
  • RGB / RG → B

하지만 R, G, B를 서로 바꿀 수는 없습니다, 또한, 예를 들어, R을 RR로 만들 수 없습니다. 어떤 연산을 하더라도 R, G, B에서 어떤 두 색깔을 고른 것의 개수의 합의 홀짝성을 바꾸지 않기 때문입니다.

이 관찰을 종합하면, 다음 중 한 가지 경우에만 문자열을 바꿀 수 있습니다.

  • 두 문자열 모두 R, G, B 중 하나로 줄일 수 있고, 줄어든 문자열 두 개가 같은 경우.
  • 두 문자열 모두 RR, GG, BB 중 하나로 바꿀 수 있는 경우. 줄어든 문자열 두 개는 달라도 됨.

이제 이걸 어떻게 circular하고 reflective하게 바꿀 수 있는지 생각해 봅시다. 그런데 모든 문자열들은 R, G, B, RR, GG, BB로 만들 수 있고, 이들은 이미 circular하고 reflective하기 때문에 크게 상관이 없을 것 같습니다. 이 방법으로 그냥 linear하게 해결하면 됩니다.

구현이 꽤 힘들었고, 구현 미스로 4번 틀렸습니다. 안타깝네요.

F. 응원단

시도하지 못함, P2, #ad_hoc

다른 사람들이 H번 구현에 고통받는 동안 @havana723이 풀이를 열심히 생각했습니다. 구현도 어느 정도 했지만 안타깝게도 시간 내에 제출하지는 못했습니다.

자리를 바꾸는 경우를 제외하고 생각해 봅시다. 셀을 4가지 경우로 나눌 수 있습니다.

  • 행이 홀수, 열이 홀수
  • 행이 홀수, 열이 짝수
  • 행이 짝수, 열이 홀수
  • 행이 짝수, 열이 홀수

어떤 셀이 모든 쿼리를 거치고 얼마나 이동해 있는가는 이 4가지 경우 안에서 전부 같다는 관찰이 가능합니다.

쿼리를 온라인으로 처리하면서, 각각의 경우에 대해 처음 시작 위치에서 얼만큼 이동했는지를 관리합시다. $\left(r, c\right)$에 어떤 값이 저장되어 있는지를 알고 싶다고 합시다. 4가지 경우 각각에 대해 $\left(r, c\right)$에서 이동 벡터를 빼 보고, 그게 실제로 처음에 각 경우의 맞는 셀의 위치에 있는지 확인합시다. 맞는 경우는 한 가지밖에 없을 것입니다. 그 경우에 대해, 초기 배열에 $\left(r, c\right)$에서 이동 벡터를 뺀 곳에 있던 값이 현재 $\left(r, c\right)$에 있는 값이 됩니다.

교체 쿼리의 처리를 위해 별도의 배열 swap을 관리합시다. Swap 쿼리가 나오면 그 때의 $\left(r_1, c_1\right)$, $\left(r_2, c_2\right)$ 값을 계산하고, 이 값을 swap 배열에서 바꿔 줍시다. 최종 출력에서 swap 배열에 있는 값을 출력해 주면 됩니다. 사실 swap 쿼리는 $\left(r_1, c_1\right)$과 $\left(r_2, c_2\right)$의 값을 구하는 쿼리와 크게 다르지 않은데 어느 정도 정해로 접근하는 데 연막의 기능을 했다고 생각합니다.

실수의 실수: 스페셜 저지만 붙인다고 끝나는 것이 아니다

$% TeX defines$ $\newcommand{\eps}{\varepsilon_{\mathrm{m}}}$ $\newcommand{\F}{\mathbb{F}}$

프로그래밍 문제를 출제하다 보면 가끔 실수를 다루는 문제를 출제하고 싶어질 때가 있습니다. 웬만하면 모든 걸 정수로 하면 좋겠지만 문제 상황이 그렇지 못할 경우도 존재하죠. 그러나 우리가 다루는 실수는 사실 정확히 말하면 실수가 아니기 때문에 조심해야 할 점들이 꽤나 있습니다.

이 글은 floating point 실수 연산의 오류 분석과, 이를 기반으로 프로그래밍 문제에서 좀 더 옳은 정답 데이터를 만드는 방법에 대해 소개합니다. 굳이 문제나 데이터를 만들지 않더라도 일반적으로 프로그래밍 문제에서 실수를 다루는 데에 참고하면 도움이 될 것입니다.

IEEE 754

By Vectorization: Stannered – Own work based on: Float example.PNG, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=3357169

아마 float이나 double 등을 처음 배울 때 한 번쯤은 봤을 법한 그림입니다. 지금은 잊어버렸을 수도 있겠습니다만, 아무튼 컴퓨터가 실수를 그렇게 정확하게 나타내지는 못한다는 것쯤은 알고 계시리라 생각합니다.

사실 floatdouble은 아무 실수나 나타낼 수 있는 것이 아니며, 분모가 $2^n$인 유리수만을 나타낼 수 있습니다. 심지어 $0.1$과 같은 우리가 보기에 간단해 보이는 유리수도 분모를 $2^n$으로 나타낼 수 없기에, double x = 0.1을 하면 $0.1$이 아니라 $0.1$을 최대한 근사한 값1이 들어가게 됩니다.

양수 float 값 $q$는 일반적으로 다음과 같이 저장됩니다2:

\[ q = 2^{\left(A-\mathit{bias}\right)} \times \left(1+B\right). \]

여기서 $A$는 음이 아닌 정수이고, $B$는 소숫점 아래에 쓸 수 있는 $0 \le B < 1$의 이진수 소수입니다. 수의 크기에 따라 $A$를 조절해서 $\left[1, 2\right)$보다 크거나 작은 수를 표현할 수 있습니다.

int, long long 등에 제한이 있듯이 float, double도 한정된 비트를 사용하는 만큼 제한이 있습니다. 아래 정보는 일반적인 온라인 저지 환경에서의 GCC를 가정합니다.

$A$$\mathit{bias}$$B$
float ($32$비트)$8$비트$127$$23$비트
double ($64$비트)$11$비트$1\,023$$52$비트
long double ($80$비트)$15$비트$16\,383$$64$비트
__float128 ($128$비트)$15$비트$16\,383$$112$비트

자릿수가 제한되어 있는 만큼 이산적입니다. 예를 들어 $3$자리만 사용할 수 있는 상황이고 $A = \mathit{bias}$, 즉 $q = 2^0 \times \left(1+B\right) = 1+B$라고 한다면 $1.\underline{000}_2=1$과 $1.\underline{001}_2=1.125$ 사이의 수는 표현할 수 없게 되는 것입니다.

사실 $A$나 $\mathit{bias}$보다 중요하게 봐야 할 건 $B$의 유효숫자 수입니다. 이게 전부 $2$진수라서 생각하기 어려울 수 있으니 $\log_2 10$로 나눠서 생각해 보면 이렇습니다.

$B$$10$진 자릿수
float ($32$비트)$23$비트$6.92$자리
double ($64$비트)$52$비트$15.65$자리
long double ($80$비트)$64$비트$19.26$자리
__float128 ($128$비트)$112$비트$33.71$자리

이 이후부터는 참값과 근삿값을 구분해야 할 일이 있으면 다음과 같은 표현법을 쓰도록 하겠습니다. $\F$는 ECMAScript 스펙에서 따왔습니다.

\[\begin{aligned} x_\R &= \textrm{참값 }x\\ x_\F &= \textrm{부동소수점 값으로 표현된 }x\textrm{의 근삿값} \end{aligned}\]

그리고 편의를 위해 $\mathit{bias}$는 $A$에 이미 더해져 있다고 생각하겠습니다.

정확도의 소실

유효숫자가 정해져 있다 보니 불가피하게 정확도의 소실이 일어납니다. 그래서 일반적으로 실수를 다루는 문제들은 절대/상대 오차 얼마 이하는 정답으로 간주합니다. 하지만 문제를 만드는 입장에서는 정해의 오차가 얼마 정도인지를 정확히 알고 있어야 참가자에게 ‘이 정도의 정확성을 갖는 풀이를 제출하십사’라고 요구할 수 있습니다. 반대로는 ‘이 정도의 정확도를 요구하려면 정해가 어느 정도로 정확해야겠구나’를 생각할 수 있겠죠.

여기서 ‘절대 오차’와 ‘상대 오차’에 대해 먼저 설명하도록 하겠습니다.

  • $x$의 근삿값 $y$가 $\delta_a$만큼의 ‘절대 오차’를 갖고 있다는 것은 $|x-y| \le \delta_a$임을 의미합니다.
  • 반면 $y$가 $\delta_r$만큼의 ‘상대 오차’를 갖고 있다는 것은 $\frac{|x-y|}{x} \le \delta_r$임을 의미합니다. 실생활에서 ‘$1$% 정도의 차이가 발생할 수 있다’같은 표현이 상대 오차 $0.01$이 발생할 수 있다는 것과 같은 표현이겠네요.

이제 자주 사용하는 연산들에서 오차가 얼마나 발생할 수 있는지 하나하나 뜯어보도록 합시다.

입력

조금 전에 참값을 어떻게 float이 다룰 수 있는 값으로 근사하는지 설명했습니다. 참값 $x_\R$를 유효숫자 $p$비트의 float 값 $x_\F$로 나타내려고 한다면 정확히 얼마만큼의 오차가 발생할까요?

일단 $x_\R = 2^A \times \left(1+B_\R\right)$라고 한다면, $B$의 자릿수 제한을 맞춰 주기 위해 $B_\R$을 최대한 가까운 $p$자리 이진 소수로 반올림합니다. 이렇게 하면 $B$에는 최대 $0.5 \times 2^{-p} = 2^{-p-1}$만큼의 절대 오차가 발생하게 됩니다.

$x_\R$과 $x_\F$의 입장에서는 어떨까요? 앞서 언급한 것은 $B$에서의 오차였으므로, $x$ 입장에서 생각하려면 $2^A$를 곱해 줘야 합니다. 그러면 $x$ 입장에서의 절대 오차는 $2^A \times 2^{-p-1}$입니다.

앞서 $A$는 수의 크기에 따라 조정된다고 설명했습니다. 음? 입력받는 값의 스케일에 따라 결정된다구요? 그러면 오차를 절대 오차보다는 상대 오차로 나타내는 것이 괜찮은 옵션인 것 같아 보입니다.

상대 오차는 최대

\[ |x_\R-x_\F| \le 2^A \times 2^{-p-1} \quad \textrm{이므로} \quad \frac{|x_\R-x_\F|}{x_\R} \le \frac{2^A \times 2^{-p-1}}{2^A \times \left(1+B\right)} = \frac{2^{-p-1}}{1+B} \]

이고, $0 \le B < 1$이므로

\[\frac{2^{-p-1}}{1+B} \le \frac{2^{-p-1}}{1+0} = 2^{-p-1} = \frac{2^{-p}}{2}\]

가 됩니다. 따라서 반올림 오차는 상대 오차로 최대 $\frac{2^{-p}}{2}$입니다. 이를 간단하게 나타내기 위해, 부동소수점 수에서 다음 수와의 간격을 나타내는 기계 입실론machine epsilon을 도입해 표기해 봅시다. 기계 입실론은 $\eps$과 같이 나타내고, $\eps = 2^{-p}$이므로 $\frac{2^{-p}}{2} = 0.5 \eps$로 표현할 수 있겠습니다.


결론: 실수를 입력받으면 최대 $0.5 \eps$만큼의 상대 오차가 발생합니다.


double에서 $p=52$임을 생각하면 유효숫자가 $15$자리쯤 된다고 볼 수 있습니다. 따라서 double을 입력받았다면 앞의 $15$자리까지는 믿을 수 있다고 할 수 있겠습니다.

부호가 같은 수의 덧셈

유효숫자 세 자리 float에서, $a_\F=1.\underline{101}_2$와 $b_\F=1\underline{10}.\underline{1}_2$를 더하는 상황을 가정해 봅시다.

그냥 더하면 $\left(a_\F + b_\F\right)_\R = 1\,\underline{000}.001_2$이 되지만, 우리의 float은 유효숫자 $3$개까지만을 허용하므로 $.001_2$ 부분을 날려야 합니다. 따라서 계산된 값을 다시 float에 저장하면 $\left(a_\F + b_\F\right)_\F = 1\,\underline{000}_2$ 부분만이 남습니다.

컴퓨터는 계산 과정에서는 저장하는 float의 두 배 정도의 공간을 사용해 정확하게 계산하고 이후 반올림하기 때문에, 덧셈의 경우에도 반올림 오차 한 번만이 발생합니다. 이는 상대 오차 $0.5 \eps$입니다.


부호가 같은 두 float의 덧셈에서는 $0.5 \eps$만큼의 상대 오차가 발생합니다.


그러나 여기에는 함정이 있는데, $a_\F \ne a_\R$이라는 점입니다. $a_\F$와 $a_\R$는 이미 $0.5 \eps$만큼의 상대 오차를 갖고 있습니다. 따라서 $\left(a_\F + b_\F\right)_\R$와 $a_\R + b_\R$의 상대 오차는 이미 $0.5 \eps$입니다. 여기서 반올림도 수행해야 하므로, 발생할 수 있는 오차는 최대

\[\left(1+0.5 \eps\right)\left(1+0.5 \eps\right)-1 = \eps + 0.25 \eps^2\]

입니다. $0.25 \eps^2$는 너무 작아서 무시할 수 있습니다(후술). 따라서 다시 결론을 내리면,


결론: 부호가 같은 두 실수를 입력받아 더하면 $\eps$만큼의 상대 오차가 발생합니다.


여담으로 큰 차이가 나는 두 수를 더하면 더하는 것에 의미가 없어질 수도 있습니다. 예를 들어 $a_\F=1\underline{001}_2$과 $b_\F=0.001\underline{101}_2$을 더하는 경우 계산 결과는 $\left(a_\F + b_\F\right)_\R=1\underline{001}.001101_2$이 되지만, 반올림하면 $1\underline{001}_2$이 되어 $a_\F$와 같아집니다. $\eps^2$ 자체는 float으로 정확히 표현할 수 있을지 몰라도, $\eps \times 2$ 이상의 값과 더하면 이와 같은 현상이 나타나기 때문에 생각하지 않아도 괜찮습니다.

곱셈과 나눗셈

이번에는 $a_\F=1.\underline{110}_2$와 $b_\F=1\underline{10}.\underline{1}_2$를 곱하거나 나누는 상황을 생각해 봅시다.

\[ \begin{aligned} \left(a_\F \times b_\F\right)_\R &= 1\underline{0}.\underline{11}0110_2 \\ \left(a_\F / b_\F\right)_\R &= 1.\underline{000}100111011000\cdots_2 \end{aligned} \]

반올림하면 이렇게 됩니다.

\[ \begin{aligned} \left(a_\F \times b_\F\right)_\F &= 1\underline{0}.\underline{11}_2 \\ \left(a_\F / b_\F\right)_\F &= 1.\underline{001}_2 \end{aligned} \]

계산 과정에서의 정확도 손실은 발생하지 않으며(나눗셈의 경우 무시할 수 있을 정도로 작습니다), 반올림 오차 $0.5 \eps$가 발생합니다.

이번에도 $a_\F \ne a_\R$임을 고려해 봅시다. $\left(a_\F\times b_\F\right)_\R$와 $a_\R\times b_\R$의 상대 오차는 $\eps$가 되고, 반올림을 수행해 $\left(a_\F\times b_\F\right)_\F$로 만들면 $1.5 \eps$가 됩니다. 나눗셈도 같은 방법으로 계산 가능합니다.


결론: 두 float의 곱셈/나눗셈에서는 $0.5 \eps$만큼의 상대 오차가 발생합니다.
두 실수를 입력받아 곱하거나 나누면 $1.5 \eps$만큼의 상대 오차가 발생합니다.


부호가 같은 수의 뺄셈

뺄셈, 혹은 부호가 다른 수의 덧셈은 위에서 언급한 덧셈과 비슷하지만 상황이 조금 다릅니다. 특히 $x_\F \ne x_\R$이면서 차이가 얼마 안 나는 값을 계산하려고 하는 경우입니다.

예를 들어 $a_\F=1.\underline{111}_2$에서 $b_\F=1.\underline{110}_2$을 빼는 경우를 생각해 봅시다. 결과는 $\left(a_\F-b_\F\right)_\R=0.001\underline{0\,00}_2$입니다. 이는 별 문제가 없어 보이지만, 계산 결과에서의 밑줄 친 $\underline{000}$은 $a_\F$에도 $b_\F$에도 없었던 값입니다. 이 새롭게 생긴 유효 비트 $3$개를 그냥 믿기에는 조금 꺼림칙합니다. 다행히도 두 값이 근삿값이 아니라 참값이라면, 즉 $a_\F=a_\R$고 $b_\F=b_\R$라면 계산 결과는 정확하고 믿을 수 있습니다.

하지만 $a_\F$가 정확한 값이 아니라면, 즉 $a_\F$과 $a_\R$의 차이가 크다면 문제가 됩니다. 예를 들어 $1.93$에서 $1.69$를 빼는 상황을 생각해 본다면 정확한 결과는 $0.24$여야 하지만, $1.93_\F=1.\underline{111}_2$, $1.69_\F=1.\underline{110}_2$이므로 $\left(1.93_\F-1.69_\F\right)_\F=0.001\underline{0\,00}_2 = 0.125$가 됩니다. 무려 두 배나 차이가 나네요!

조금 더 극단적인 예로 $|\varepsilon_\F| < \eps$에 대해 다음과 같은 계산을 한다고 가정해 봅시다.

\[ \left[ (1_\F+\varepsilon_\F)_\F-(1_\F-\varepsilon_\F)_\F \right]_\F \]

$2 \varepsilon_\F$이 나와야 할 것처럼 보입니다. 그러나 $\varepsilon_\F$이 반올림 오차보다 작으므로 실제로는 아래와 같이 계산됩니다.

\[ (1_\F+\varepsilon_\F)_\F-(1_\F-\varepsilon_\F)_\F= 1_\F-1_\F = 0_\F \]

이는 무려 $100$%의 상대 오차입니다. 이런 현상을 재앙적인 소거catastrophic cancellation라고도 합니다.3

따라서 뺄셈을 정확하게 하고자 할 경우 비슷한 두 값의 뺄셈을 최대한 피하도록 해야 합니다. 예를 들어 앞서 언급한 $(1+\varepsilon_\F)-(1-\varepsilon_\F)$의 경우, $(1-1)-(-\varepsilon_\F-\varepsilon_\F)$로 계산 순서를 약간 바꾸면 조금 더 정확한 값을 얻을 수 있을 것입니다.


결론: 부호가 같은 두 실수의 뺄셈을 하는 상황은 가급적 피하는 것이 좋습니다.


덧셈, 곱셈, 나눗셈은 상대적으로 훨씬 ‘안전한’ 연산이므로 가능한 경우 덧셈, 곱셈, 나눗셈만을 사용하도록 수정합니다. 일례로 실수 값의 누적 합을 구해야 한다면 대신 펜윅 혹은 세그먼트 트리를 사용할 수 있습니다.

여담으로, 같은 부호이더라도 두 배 이상 차이가 나는 값의 뺄셈은 $\eps$ 이하의 오차만이 발생함을 덧셈의 경우와 비슷한 방법으로 보일 수 있습니다.

뺄셈을 포기할 수 없다면

뺄셈의 오차를 다른 상황과 같이 생각할 수 없는 이유는 없는 유효숫자를 만들어야 하는 상황 때문입니다. 따라서 상대 오차를 계산하기는 어렵습니다. 하지만 절대 오차를 계산해 볼 수는 있습니다.

$a_\R$에서 $b_\R$을 빼는 연산을 생각해 봅시다.

  • 우선 이 값들을 입력받는 과정에서 반올림 오차 $0.5 \eps$가 생깁니다. 이 오차는 상대 오차이므로, 절대 오차로 바꾸면 각각 $0.5 \eps a_\R$과 $0.5 \eps b_\R$이 됩니다. 따라서 $a_\R-b_\R$과 $\left(a_\F-b_\F\right)_\R$은 최대 $0.5 \eps \left(|a|_\R+|b|_\R\right)$의 절대 오차를 가집니다.
  • 이제 $\left(a_\F-b_\F\right)_\R$을 $\left(a_\F-b_\F\right)_\F$로 근사합니다. 이 과정에서 반올림 오차 $0.5 \eps$가 한 번 더 생깁니다. $0.5 \eps \left(|a|_\R+|b|_\R\right)$의 절대 오차에 $0.5 \eps$의 상대 오차가 한 번 더 생기므로, 총 절대 오차는 $\left[0.5 \eps \left(|a|_\R+|b|_\R\right)\right]\left(1+0.5\eps\right)$입니다.
  • 앞서 언급했던 것처럼 $0.25 \eps^2$는 $0.5 \eps$에 비하면 무시할 수 있는 수준이므로, $0.5 \eps \left(|a|_\R+|b|_\R\right)$만큼의 절대 오차가 발생한다고 할 수 있습니다.

따라서 다루는 수들의 스케일을 알고 있다면, 다행히도 발생하는 오차를 절대 오차로나마 가늠할 수 있습니다.


결론: 부호가 같은 두 실수 $a$와 $b$가 있을 때,
$a$에서 $b$를 빼면 최대 $0.5 \eps \left(|a|+|b|\right)$만큼의 절대 오차가 발생합니다.


정리해 보면 이렇습니다.

연산부호가 같은 경우 오차부호가 다른 경우 오차
입력/반올림상대; $0.5 \eps$
$a_\R+b_\R$상대; $\eps$절대; $0.5 \eps \left(|a|+|b|\right)$
$a_\R-b_\R$절대; $0.5 \eps \left(|a|+|b|\right)$상대; $\eps$
$a_\R\times b_\R$상대; $1.5 \eps$상대; $1.5 \eps$
$a_\R / b_\R$상대; $1.5 \eps$상대; $1.5 \eps$

그러나 이 표에서 언급한 덧셈과 뺄셈에서의 상대 오차는 덧뺄셈 한 번에서 발생하는 오차이고, 덧셈을 계속 누적해나간다면 덧셈을 할 때마다 반올림 오차가 새로 발생하고, 이는 절대 오차로서 더해짐을 간과하면 안 됩니다. 프로그래밍 문제에서는 일반적으로 덧셈을 여러 번 하는 상황이 많기 때문에, 덧뺄셈은 아예 절대 오차로만 생각하는 편이 좋겠습니다. 이렇게 하면 부호가 같은 경우와 다른 경우에 차이가 없어지며, 다음과 같이 다시 한 번 정리할 수 있습니다.

연산오차
입력/반올림상대; $0.5 \eps$
$a_\R+b_\R$절대; $0.5 \eps \left(|a|+|b|\right)$
$a_\R-b_\R$절대; $0.5 \eps \left(|a|+|b|\right)$
$a_\R\times b_\R$상대; $1.5 \eps$
$a_\R / b_\R$상대; $1.5 \eps$

정해 코드의 오차 계산 및 문제 설계

문제에서 얼마만큼의 오차를 허용할지는 정해 코드의 최대 오차를 계산함으로서 정할 수 있습니다.

BOJ #1546 평균과 똑같은 문제를 조금 더 어렵게 세팅한다고 가정해 봅시다. 정해 코드를 이렇게 짰습니다.

double s = 0;

int n;
cin >> n;
while (n--) {
    double x;
    cin >> x;
    s += x;
}

cout << fixed << setprecision(12) << s / n << '\n';

일단 $s$의 오차는 덧셈 $N$번이 누적되므로 높게 잡아도 $N \times 0.5 \eps \left(s+s\right) = Ns\eps$ 이하의 절대 오차가 생깁니다. 마지막에 나눗셈 한 번을 하므로 상대 오차 $1.5\eps$가 한 번 더 생깁니다.

그러면 총 절대 오차는 $Ns\eps$, 총 상대 오차는

\[\begin{aligned} \left(1+\frac{Ns\eps}{s}\right)\left(1+1.5\eps\right)-1 &= \left(1+N\eps\right)\left(1+1.5\eps\right)-1 \\ &= N\eps+1.5\eps+1.5N\eps^2 \\ &= \left(N + 1.5\right)\eps \end{aligned}\]

가 됩니다.

허용 오차 설정하기

double로 풀리게 하고 싶다면 어떻게 해야 할까요? double에서는 $10^{-16} < \eps < 10^{-15}$이므로 넉넉하게 $\eps = 10^{-15}$로 두고 계산하면, 위 코드의 절대 오차는 $Ns \times 10^{-15}$, 상대 오차는 $\left(N + 1.5\right) \times 10^{-15}$가 나옵니다. 따라서 $N$의 값에 따라 오차 허용 범위가 달라지는데, $N = 10^5$로 설정한다면 상대 오차가 약 $10^{5-15}=10^{-10}$이 되므로 $10^{-9}$ 혹은 그보다 넉넉한 허용 범위를 잡으면 무리 없이 통과할 것입니다. (통상적으로 상대 오차 혹은 절대 오차 중 하나만 범위에 들어오면 맞도록 하기 때문에 그렇습니다.)

반대로 $N = 10^5$인 상황에서 float을 저격하고 싶다면 어떻게 해야 할까요? float에서는 $10^{-7} < \eps < 10^{-6}$이므로, $\eps = 10^{-7}$로 보수적이게 잡으면 상대 오차 $10^{5-7}=10^{-2}$라는 계산이 나옵니다. 따라서 허용 오차 범위를 $10^{-2}$로 잡으면 float을 사용한 코드가 통과하지 못할 가능성이 있고, $10^{-3}$ 혹은 그 이하로 잡으면 float이 통과하기 어려운 문제로 세팅할 수 있을 것입니다.

위의 예시에서도 그렇듯이 float의 경우 덧셈을 $100\,000$번만 하는데도 $10^{-2}$ 혹은 그 이상의 오차가 발생하기 때문에, float 코드는 부정확한 값을 도출하기 상당히 쉽습니다. 그래서 float을 굳이 통과시켜 주려고 의도하는 상황이 아니고서야 float으로 작성한 코드는 그냥 틀렸다고 생각하고, double으로 해결하는 경우만 신경써도 충분합니다.

In Practice

그러나 문제에서 요구하는 계산이 많아지고 복잡해지면 코드마다 사칙연산을 수행하는 횟수가 천차만별일 수 있습니다. 따라서 실수 오차를 신경쓰는 게 문제가 물어보는 주요 포인트가 아닌 이상 실제 세팅할 때는 위에서 언급한 표의 모든 상수를 $10$ 정도로 놓고 오차 허용 범위를 설계하게 됩니다. 앞의 상수는 계산 횟수에 비례하기 때문입니다.

연산일반적으로 허용하는 오차
$a_\R+b_\R$절대; $10 \eps \left(|a|+|b|\right)$
$a_\R-b_\R$절대; $10 \eps \left(|a|+|b|\right)$
$a_\R\times b_\R$상대; $10 \eps$
$a_\R / b_\R$상대; $10 \eps$

굳이 $10$으로 두는 이유는 앞서 말했듯이 상수와 계산 횟수는 비례하기 때문에, 상수가 너무 커질 정도로 계산 횟수가 많아지면 차라리 시간 초과가 나는 편이 낫기 때문입니다.

데이터 제작

특히 데이터를 제작할 때 주의해야 하는 점이 있습니다. 바로 데이터 자체에 오차가 있는 경우입니다. 데이터도 컴퓨터로 계산하는 것이기에 일반적인 방법으로 만든다면 데이터에도 그만큼의 오차가 생길 수밖에 없고, 이렇게 오차가 있는 데이터를 기준으로 채점하면 오히려 맞아야 하는 답을 틀리다고 채점하게 될 수도 있습니다. 실수를 많이 다뤄보지 않은 세터가 꽤 흔하게 하는 실수입니다.

이를 방지할 수 있는 방법은 여러 가지가 있는데, 몇 가지를 소개하자면:

  • long double, __float128, Python Decimal, Java BigDecimaldouble보다 훨씬 정확한 자료형을 통해 계산합니다.
  • 가능한 경우 모든 계산을 정수로 수행합니다. 분모와 분자를 관리하는 분수 구조체를 만들거나, Python Fraction을 사용하는 것도 고려해 볼 수 있습니다.

정해 소스의 오차가 최대 얼마인지를 계산하는 것의 중요성을 강조하고 싶습니다. 개인적으로 double로 풀리게 하고 싶다면 데이터는 적어도 최대 $10^{-15}$만큼의 오차만을 갖도록 만드는 것을 권장합니다.

여담

사칙연산 이외의 함수들의 오차는 어떻게 구하나요?

IEEE 754는 사실 아래의 연산들에 대해 가장 가까운 실수를 계산할 수 있도록 하고 있습니다4. 의외로 제곱근이 들어가 있습니다.

  • 사칙연산
  • 제곱근
  • 단일 곱셈 누산
  • 나머지 연산
  • 최대 및 최솟값

C는 이를 따라서, sqrtfmod는 반올림 오차, 즉 상대 오차 $0.5\eps$만을 가지도록 합니다. 단, 이는 인자들이 참값임을 가정한 오차임에 주의해야 합니다.

제곱근을 제외하고, GNU C에서 실수와 관련된 함수들의 구현과 오류의 대략적인 양은 문서에 명시되어 있습니다. 문서에서 명시된 ULPunit in the last place는 이 글에서 언급한 기계 입실론과 같은 단위인데, 상대 오차입니다.

보통 채점 환경으로 주로 사용되는 x86_64에서의 주요 함수의 오차는 다음과 같습니다. 모두 계산 결과에 대한 상대 오차이므로, 입력값의 오차를 따로 고려해 줘야 함에 유의합니다.

  • sin, cos, tan, asin, acos, atan: $\eps$
  • pow, exp, expm1, log, log1p: $\eps$
  • hypot: $\eps$
  • sinh, cosh, tanh, asinh, acosh, atanh: $2\eps$
  • cbrt: $4\eps$

일부 함수들은 정의역이 제한되어 있으므로(예를 들어 acos는 $-1$과 $+1$ 사이의 입력만 허용합니다) 계산 과정에서 실수로 정의역을 벗어나는 값을 넣지 않도록 주의해야 합니다. 또한 아래 함수들은 특정 범위의 입출력을 피하거나, 입력 범위에 각별히 주의하는 것을 요합니다.

  • log: 출력값이 $0$에 가까울 것으로 예상하는 경우.
    • $\log \left(x+1\right)$이 필요한 상황이라면 $x$의 값을 조금 더 정확히 입력할 수 있는 log1p 함수를 사용합니다: $\operatorname{log1p} x=\log \left(x+1\right)$.
    • $x$가 작다면, $x+1$을 계산하는 데에서 이미 정확도의 손실이 일어납니다.
  • exp, pow: 출력값이 $1$에 가까울 것으로 예상되는 경우.
    • $e^x-1$의 정확한 값이 필요한 상황이라면 마찬가지로 expm1 함수를 사용합니다: $\operatorname{expm1} x=e^x-1$.
  • fmod: 나눠지는 값이 나누는 값보다 너무 큰 경우.
    • 인자가 참값이 아니라 반올림된 값일 경우 뺄셈과 비슷하게 재앙적 소거가 쉽게 발생할 수 있습니다.

여담으로, tan 함수의 경우 $\left(\frac{1}{2}+n\right)\pi$ 왼쪽에서는 $+\infty$로 발산하고 오른쪽에서는 $-\infty$로 발산하지만, 어떤 부동소수점 값도 $\left(\frac{1}{2}+n\right)\pi$를 정확히 표현할 수 없어서 우려하는 오류가 발생하지 않습니다.

일부 연산은 CPU가 직접 지원하고, CPU의 구현에 따라 오차가 다르게 발생하는 경우가 존재합니다. 예를 들어 exp10 함수는 CPU가 10의 $N$제곱 연산을 지원한다면 코드로 계산하려고 하지 않고 하드웨어로 __builtin_exp10을 통해 더 빠르게 계산하려고 할 것입니다.

glibc 소스에서도 상세 구현을 확인하고 오차를 가늠할 수 있습니다.

다른 방식으로 오차를 구하는 글도 있던데 여기서는 왜 이렇게 구하나요?

아마 $a \pm b$의 오차 $\delta \left(a \pm b\right)$는 $\sqrt{\left(\delta a\right)^2+\left(\delta b\right)^2}$라고 설명하는 글을 보셨을지도 모르겠습니다. 이는 물리학 등에서 $a$와 $b$가 여러 번의 측정을 통해 얻어낸 평균값이고, 오차가 확률분포(특히 정규분포)에서 추출될 것이라고 가정할 수 있을 때 사용하는 방법입니다. 즉, 우리가 다루는 오차와는 다른 성격의 오차입니다. 여기에서는 수치해석적 관점에서의 오차 전파를 다루고 있습니다.

마무리하면서

부동소수점 오차는 참 다루기 힘든 주제입니다. 이 글이 부동소수점 오차에 대한 막연한 가늠과 추측을 해소하고 좀 더 좋은 문제들을 만드는 데 기여해, 제가 백준에서 맞왜틀을 덜 당할 수 있기를 희망합니다.

이 글 작성에 도움을 주신 김영현kipa00님과 김준원junie님께 감사의 말씀을 전합니다.

각주

  1. double의 경우 $0.1_\F$은 정확히 \[0.1000\,0000\,0000\,0000\,0555\,1115\,1231\,2578\,2702\,1181\,5834\,0454\,1015\,625\]입니다.
  2. $q=0$, $q=+\infty$, $q=\,$NaN, 그리고 $A = 0$인 경우는 예외입니다.
  3. 반면 두 값이 참값인 경우에서 일어나는 현상은 온화한 소거benign cancellation라고 합니다.
  4. https://en.wikipedia.org/wiki/IEEE_754#Required_operations

(23/7/19) 사칙연산 이외 함수들에 대한 설명을 추가했습니다. kiwiyou님께 감사의 말씀을 드립니다.

모스크바 ICPC 월드 파이널에 다녀왔습니다 (2)

ICPC 월드 파이널 참석 후기 — Привет!

인천공항 코로나 검사센터

버거킹을 먹은 후에는 인터넷으로 미리 코로나 검사를 예약하고 인천공항 코로나 검사센터에서 검사를 받았습니다. 당시에는 보건소에 가면 누구나 무료로 코로나 검사를 받을 수 있던 시절이었지만, 보건소 검사결과는 언제 나올지 모르는 반면 러시아 입국 시각을 기준으로 72시간 내에 받은 검사 결과가 필요했기에 한 명 당 10만 원 가량의 거금을 들여서 검사를 받았습니다.

비행기는 오후 11시 반에 출발합니다. 오후 1시에 PCR 검사를 받고 무려 10시간을 때워야 하는 슬픈 상황입니다.

사실 레드시프트가 해외 대회를 치러 간 건 처음이 아닙니다. 2019년에 태국 방콕 리저널에도 참가했었는데요, 당시 제가 팀노트 25장 × 3권을 무려 잉크젯 프린트로 인쇄하느라 늦어서 공항철도에서 내리자마자 게이트까지 뛰어갔는데도 비행기를 놓칠 뻔 한 적이 있었던지라 이번엔 일찍 공항에 왔습니다.

semteo04의 화려한 카드 마술

카드 셔플 문제의 출제자 semteo04는 서강대학교 마술 동아리 MASU-Z 부원입니다. 시간을 때우면서 신기한 마술들을 볼 수 있었어요.

한별이 아크릴

제가 모스크바 여행을 다녀온다고 하니 solved.ac 일러스트 작가님이 여행객 한별이 아크릴을 선물해주셨습니다. 제가 평소에 메고 다니는 가방이랑 같은 걸 메고 있네요. 저는 정말 성덕이 아닐까요? 이 글을 빌어 다시 한 번 감사의 말씀을 드립니다 🙏 

오래 걸어다니다 보니 피곤하고 덥고 온 몸이 땀 범벅이 돼서 샤워할 수 있는 곳을 알아보다가, 면세영역에 샤워실이 있다고 해서 일단 출국심사를 받았습니다.

사람 없는 공항

오른쪽이 출국심사대입니다. 심각한 코로나 상황을 보여주기라도 하듯 사람이 몇 명 안 보이는 공항 면세영역입니다. 터키나 러시아는 어떤 상황일지, 우리가 다녀오는 동안 우리나라는 어떻게 될지 걱정이 앞섭니다. 면세구역 중앙이라 아직 몇 명 보이기는 하지만 게이트와 가까워질수록 우리 말고는 아무도 없어서 비현실적인 기분이었습니다.

그리고 아쉽게도 코로나 상황 때문에 샤워실은 문을 닫았더라구요.

거대한 비행기와 작은 나

그렇게 이 시국에 해외에 나가보게 되었습니다.

여정표

앞선 포스트에서 언급했던 것과 같이 이 여정은 터키항공 TK091편으로 튀르키예(당시 터키)의 수도 이스탄불까지 날아가고, 여기서 환승해 터키항공 TK413편으로 러시아 브누코보 공항까지 가는 여정이었습니다. 여정표만 보면 5시간 반 정도만에 갈 수 있을 것 같지만 튀르키예와 한국의 시차는 6시간이라 TK091편만 무려 11시간 반이나 걸립니다. 가 본 곳이 전부 아시아뿐이라 6시간 초과의 비행기를 타본 적 없는 저로서는 걱정 반 설렘 반이었어요. 와 내가 드디어 시차 적응이라는 걸 해볼 수 있다니!

운좋게도 제가 창가 자리라서 인천 야경을 찍을 수 있었어요.

인천의 야경

11시간 반 앉아 있으면 굉장히 배고프죠. 밤에 출발한 비행기라서 저녁 기내식이 나왔습니다. 공항에서 저녁을 먹었지만 그냥 또 먹기로 합니다.

비빔밥

기내식은 비빔밥과 물고기 요리 중 하나를 고를 수 있었고 비빔밥은 외국 항공사 기내식 치고는 꽤 맛있었습니다. 터키항공은 튀르키예의 자존심인가?

심지어 이 비행기는 (꽤 비싼 값을 주면) 엄청 느린 위성 인터넷을 쓸 수 있게 해 줍니다. 기내에서 여자친구에게 깜짝 밤인사를 전할 수 있었어요. 트위터를 할 수 있는 속도는 아니었고….

그렇게 밥을 먹고 편하게 잤습니다. 자고 일어나니까 밥을 한 끼 더 줍니다.

아침 기내식

11시간 반 비행이라 기내식이 두 개 나오는 것 같네요. 약간 느끼하지만 맛있었습니다.

어떻게 보면 한나절동안 정말 아무것도 안 하고 앉아만 있는 거라 약간 사육당하는 느낌이 들더라구요. 하지만 피곤했기 때문에 먹고 또 바로 잤어요.

기념사진을 찍는 raararaara 선배를 찍는 shiftpsh의 기념사진

얼마 안 잤는데 튀르키예에 거의 도착해 있었습니다. 11시간 알차게 보냈네요! 답답한 비행을 가장 알차게 보낼 수 있는 방법은 바로 수면이 아닐까 싶네요.

굉장히 숙련된 파일럿이었는지 비행기 착륙을 무슨 고급 세단 승차감이 들도록 할 수 있다는 걸 처음 알았습니다. 터키항공은 신인가?

아무튼 러시아에 가자마자 호텔에서 씻겠다는 다짐으로 가득한 네 명은 지친 몸을 이끌고 환승을 합니다.

이스탄불 국제공항 면세점

이스탄불 국제공항은 웅장한 별천지였고 튀르키예는 다른 세계에 온 건가 싶을 정도로 사람이 많았습니다. 당시 우리나라 방역 상황에서는 상상하기 힘든 인파입니다.

샤워실 안내판이 눈에 띄고 면세점 내에 제가 정말 좋아하는 쉐이크쉑도 있었지만 환승 시간 간격이 그렇게 여유가 있는 편은 아니라서 바로 게이트로 이동하기로 합니다.

튀르키예에서의 아침

현지시각 새벽 5시에 도착했고 새벽 7시 45분 비행기를 타야 되기 때문에 날이 밝아오는 걸 볼 수 있었습니다. 우리나라와의 시차는 6시간이지만 비행기에서 너무 잘 잤는지 시차는 이미 적응해버렸습니다.

환승 티켓

최종 목적지인 모스크바로 출발합시다! 이번엔 두 시간만 가면 됩니다.

아침 기내식

보통 서울-제주 비행기는 기내식을 주지 않는데 터키항공 TK413편은 두 시간 비행임에도 불구하고 아침 기내식을 줍니다! 졸지에 아침 기내식을 두 개 먹어버린 돼지가 되었습니다. 꿀꿀. 근데 맛있었어요. 터키항공은 정말 최고의 항공사가 아닐까….

Привет, Россия!

러오환

긴 여정 끝에 드디어 러시아의 브누코보Внуково 국제공항에 도착했습니다. 셰레메티예보Шереметьево가 인천공항이라면 브누코보는 김포공항쯤의 포지션인 것 같습니다. 튀르키예는 가까운 나라니까요.

입국심사장으로 이동합니다. 러시아는 제1세계 국가들에게는 아직도 까다로운 입국 정책을 유지하고 있습니다. 하지만 적어도 러시아가 우크라이나와 전쟁하기 전까지는 한국의 이미지는 굉장히 좋기 때문에 입국심사는 큰 걱정 없이 통과할 거라고 믿었습니다.

그리고 실제로 두 명은 별 문제 없이 통과했습니다. 영어를 잘 모르는 눈치였는데, 영어로 몇 가지 물어보는 시도를 하더니 그냥 들여보내줬습니다.

하지만 두 명이 통과하고 나니까 입국심사대의 문이 전부 닫히고 다른 두 팀원이 입국심사대 저편에 갇혀 버렸습니다 …?

영문도 모른 채 30분동안 입국심사대를 경계로 두고 불안에 떨고 있었습니다.

나중에 물어보니 함께 입국한 다른 한국인의 일행으로 오해받아서 여권을 압수당하고 이것저것 물어봤다고 합니다. 우리나라도 아니고 남의 나라에서 이런 일을 겪다니 국제 이산가족 비슷한 게 될까 봐 정말 무서웠어요.

코카-콜라 바닐라

무서움은 코카-콜라 바닐라로 녹이기로 합니다.

처음 뵙겠습니다, 모스크바

모든 입국 과정을 무사히 마치고 공항 로비로 나왔더니 ICPC 자원봉사자 분들께서 우리를 기다리고 계셨습니다!

WELCOME!

브누코보는 모스크바와는 조금 거리가 있는 곳이라 모스크바 중심에 있는 숙소로 가려면 꽤 이동해야 합니다. 다행히도 ICPC에서 택시를 지원해 줘서 편하게 이동할 수 있었습니다.

얀덱스 택시

러시아판 카카오+네이버라고 할 수 있는 얀덱스Яндекс 택시를 두 대 불러 이동했습니다. 얀덱스는 검색엔진 회사인데 번역도 하고 택시도 하고 배달도 하고, 게임 플랫폼도 있고, 러시아 국내에서 구글보다 점유율이 높은 것까지 판박이입니다. 하나 다른 건 우리나라의 모든 곳에서 카카오 라이언 캐릭터를 볼 수 있는데 얀덱스는 캐릭터는 없는 거 같다 정도네요.

고속도로를 타고 크라운 플라자 호텔로 가는 길에서 차들을 많이 볼 수 있었는데 그 중에는 한국 중고차도 간간히 보였습니다. ‘최대적재량 4500kg’라는 한글이 적힌 현대 트럭이 인상깊었어요.

모스크바는 이렇게 세 개의 큰 순환도로로 이뤄져 있습니다. 중앙에 있는 순환도로 안에 크렘린과 붉은 광장이 있고, 이 근처에서 ICPC 월드 파이널이 개최됩니다. 우리나라로 치면 브누코보 공항은 김포공항쯤 되고, 대회 장소는 광화문 근처라고 할 수도 있을 것 같습니다. 물론 이제 모스크바 면적은 서울의 4배에 달하기 때문에 광화문 근처에서 이런 대회를 열 수 있는 공간이 있는가 하면 그건 또 모르겠다는 생각이 들지만 여하튼 그렇습니다.

호텔은 대회 장소에서 그렇게 멀지 않은 곳이었습니다. 역시 ICPC 8연속 우승을 차지하고 있는 러시아의 심장 모스크바에서 열리는 ICPC여서 그런지 만반의 준비를 한 것 같다고 느꼈습니다.

로비
객실
객실 뷰

모스크바 강변을 따라 지어진 러시아 건축 양식의 건물들이 보이는 멋진 뷰가 있는 객실이었습니다. 그림같이 아름다워서 눈을 뗄 수가 없었어요.

모스크바 산책

첫째 날에는 다들 시차적응도 해야 했고 십 몇 시간동안 비행기 타고 고생하느라 많이는 못 돌아다녔습니다. 다만 멀리까지 와서 호텔에만 있기는 아까우니까 산책을 나가기로 합니다.

개인적으로 공공디자인에 관심이 많아서 눈여겨봤는데 모스크바의 그것은 꽤 마음에 들었습니다. Moscow Sans를 사용하고 있는데 이런 디자인 언어가 대중교통과 거리 안내판 등 많은 곳에 적용되어 있었습니다.

그리고 사람들이 마스크를 안 쓰고 다닙니다. 실내에서도요! 당시는 2021년 9월이었고 우리나라는 음식점에서 식사를 오후 9시까지밖에 할 수 없었던 시국이었던지라 적잖은 문화충격을 받았죠.

숙소 근처 스몰렌스카야Смоленская 역까지 걸어가서 지하철을 타 보려고 역에 들어가서 노선도를 구경하고 있으니, 역무원 분께서 다가오셔서 미숙한 영어로 노선도에 그려진 붉은 별을 가리키면서 ‘여기 가면 멋진 거리도 있고 레닌 동상도 있다’ 같은 추천을 해주셨지만 여기까지 걸어온 것만 해도 힘에 부쳐서 내일 가 보기로 합니다.

스몰렌스카야 근처에는 아르바트Арбат 거리가 있습니다. 아르바트는 거리의 화가들이 많기로 유명합니다. 그래서 그런지 돌아오는 길에 캔버스에 유화 그림을 그리는 화가 분을 뵐 수 있었어요. 거리에서 그림을 그리는 광경은 우리나라에서는 잘 볼 수 없었던 광경이라서 유럽에 왔다는 실감이 나게 해 주는 무언가였네요.

모스크바 음식

저희와 비슷하게 온 경북대학교 Catdriip 팀과 연락이 닿아서 근처 식당에서 저녁을 먹기로 합니다. 찾아간 곳은 서강대학교 프로그래밍 대회 문제 Ресторан의 소재가 되기도 했던, 레스토랑 마트료시카Ресторан «Матрешка»입니다.

모스크바 강을 따라 걸어가면서 모스크바 야경을 볼 수 있었는데 밤의 모스크바도 엄청 예뻤습니다. 첫 번째 사진 왼쪽의 으리으리한 건물은 호텔이라고 하네요. 레스토랑 앞에는 마트료시카 조각상이 있었어요.

음식점에 들어오니 카운터에서 외투를 보관해 주시고 신발장처럼 번호표를 나눠주셨습니다. 이것도 신기한 부분이었는데, 며칠 살아보면서 느꼈던 부분이라면 러시아 사람들은 외투를 입고 대신 안에 따뜻한 옷을 입지는 않는 것 같았습니다. 실내 온도가 높은 대신 외투 보관소가 대부분의 시설에 있었던 느낌이었어요. 어쩐지 외투 입고 따뜻하게 입으니까 많이 덥더라구요.

왼쪽이 Redshift, 오른쪽이 Catdriip

dogdriip님과는 개인적으로 친분이 있어서 자주 뵈었지만 exqt 님과 skeep194 님은 초면이었습니다. 이쪽도 여러 사정으로 인해 2019년 서울 리저널 팀 구성과는 약간 다른 구성으로 출전했습니다.

메뉴판에 약간 의외의 음식이 보이는데, 러시아에는 의외로 전통 만두Пельмени가 있고 꽤 대중적이라고 합니다. 유럽과 아시아의 영향을 모두 받은 결과일까요?

저는 닭고기 포자르스키 코틀레타Пожарские котлета을 주문했습니다. 이름은 뭔가 치킨까스일 거 같고, 생긴 것도 실제로 도깨비방망이 같은 걸 끼얹은 치킨까스처럼 보이기는 하지만 되게 부드러운 다진 닭고기 튀김입니다.

맛은 예상할 수 있는 맛보다 맛있고, 약간 느끼했고.. 식감은 고로케 같은 느낌이었어요. 고로케도 좋아하고 닭고기도 좋아해서 개인적으로는 꽤 마음에 들었어요! 아마 서울에서 러시아 식당을 갈 일이 생긴다면 메뉴판에서 찾아보게 될 것 같네요.

물이 부족해서 더 달라고 요청했는데 이게 나중에 영수증에 떡하니 적혀 있었다는 점은 조금 당황스러웠네요. 심지어 에비앙… 무려 2,070루블, 당시 가격으로 33,120원이 7인 식사의 물 값으로만 나갔다는 건데… 이럴 때는 한국이 역시 최고인 것 같고 그렇죠.

알 수 없는 사진

러시아는 음식점 9시 영업제한 같은 게 따로 없었어서 늦게까지 맛있게 먹고 야경을 감상하며 천천히 숙소로 돌아왔습니다.

모스크바에서의 하루

아직 ICPC 공식 일정 시작까지는 하루 더 남은 관계로 다음 포스트도 아마 관광 이야기가 될 것 같네요. 1년만에 다시 쓰려니까 기억이 조금씩 사라져가는데 빨리 쓸 걸 하는 후회가 남습니다… 빨리 ICPC 얘기 하고 싶은데 어떻게 대회가 6일치 일정이나 되는지 모르겠네요. 여유가 되는 대로 더 써 보겠습니다!

시리즈: ICPC World Finals Moscow

  1. 모스크바 ICPC 월드 파이널에 다녀왔습니다 (1)
  2. 모스크바 ICPC 월드 파이널에 다녀왔습니다 (2)

UCPC 2022에서 번거로운 디스크립션 작업을 초고속으로 해결한 방법

사용해 보기: BOJ 디스크립션 툴 / 소스: GitHub


한국에서는 프로그래밍 대회가 많이 열립니다! 정말 고무적인 일입니다.

의외로 전국 대학생 프로그래밍 경시대회ICPC 리저널이 매년 열리는 나라는 많지 않습니다. 서강대학교에서는 2005년부터 매년 대회를 열어 작년에는 무려 17번째 교내 프로그래밍 대회가 열렸고, 전국 대학생 프로그래밍 대회 동아리 연합에서는 올해로 11번째 대회를 개최했습니다. 넥슨과 삼성전자 — 대한민국 최고의 게임 기업과 대한민국 최대의 정보기술 기업 — 도 꾸준히 관심을 갖고 대회를 열고 있습니다(각각 7회, 8회째). 최근에는 현대모비스 및 여러 스타트업들도 자체 대회를 개최하고 있습니다.

이렇게 프로그래밍 대회에 대한 국가적 관심이 커지고 있는 상황에서 학교/동아리 및 커뮤니티 대회 개최에 대한 수요가 커지는 것은 어떻게 보면 당연한 일인데요, 백준 온라인 저지가 학교/동아리 대회에 대해 무료로 채점 환경을 제공하고 있다는 건 참 다행인 점입니다.

디스크립션 작업에서 발생하는 문제들

하지만 이런 좋은 플랫폼이 있음에도 불구하고 온사이트 대회에서는 문제지를 만들어야 한다는 점 때문에 디스크립션을 작성하는 과정에서 마주하는 근본적 문제들이 존재합니다.

  • 출제자: (BOJ에서만 지문을 수정하고) 디스크립션 수정했어요!
  • 검수자 A: (출력할 문제지를 보면서) 🤔 어디가 수정됐다는 거지…
  • 검수자 B: (BOJ 지문과 출력할 문제지가 다른 상황을 보면서) 😵 어느 쪽이 의도된 지문일까?

이런 상황이 생길 수 있기 때문에 세팅 경험이 많은 사람이 있다면 BOJ와 문제지 중 한 쪽을 유일한 원천single source of truth으로 두고 작업하도록 하는 경우를 볼 수 있습니다. 가령 지문 작업은 BOJ에서만 하고 마지막 날에 모든 문제를 문제지에 옮긴다던가, 아니면 반대로 하는 식입니다.

그래도 여전히 몇 가지 문제가 있습니다. 가령 문제지를 Google Docs나 Word 등에서 작업하고 BOJ Stack에 붙여넣으면 포매팅이 영 이상해집니다.

어느새인가 들어가 있는 볼드, 전부 깨져 있는 수식
  • BOJ에 문제를 올리려면 HTML이 꽤 깨끗해야 합니다. 개인적으로 좋은 제약조건이라고 생각합니다. 근데 워드 프로세서는 일반적으로 그렇지 않죠. 이 제약 때문에 워드 프로세서에서 바로 붙여넣기할 수 없습니다.
  • 그렇다고 메모장에 붙여넣은 후 거기서 다시 가져오자니 열심히 만들어 둔 예쁜 리스트와 수식들이 전부 깨집니다. 공들여 만든 수식 $X=\frac{p_1l_1+p_2l_2+\cdots +p_Nl_N}{p_1+p_2+\cdots +p_N} =\frac{\sum_{i=1}^{N}p_il_i}{\sum_{i=1}^{N}p_i}$를 붙여넣었더니 X=p1l1+p2l2++pNlNp1+p2++pN=i=1Npilii=1Npi가 되어 있는 건 그다지 유쾌한 경험은 아니겠죠.

반대로 가자니… BOJ 수식 렌더 방식은 LaTeX인데, 이걸 그대로 지원하는 워드 프로세서는 잘 없는 것 같고, 그렇다고 Markdown 기반으로 작업하자니 글자에 색상을 못 넣는다거나 그림 포매팅을 자유롭게 하지 못하는 등의 제약이 많습니다.1

워드 프로세서를 사용하지 않는다면 어떨까요? 프로그래밍 문제의 디스크립션에는 수식이 정말 많이 등장하기 때문에 ICPC를 비롯한 여러 대회에서 여러 세터들이 LaTeX로 세팅하는 편입니다. 요즘에는 문제 제작에 있어서 필수불가결한 플랫폼인 Codeforces의 Polygon 플랫폼도 디스크립션을 LaTeX로 입력하도록 하고 있으며, UCPC도 LaTeX로 문제지를 세팅하고 있습니다.

BOJ의 수식 렌더 방식이 LaTeX라니 뭔가 순조롭게 옮길 수 있을 것 같습니다. 하지만 LaTeX에도 문제가 많습니다. 가령…

  • 수식뿐 아니라 본문에서도 여러 명령어를 사용할 수 있습니다. 예를 들어 \alpha 명령어는 그리스 문자 α를 입력합니다.
  • 리스트도 명령어를 쳐서 만듭니다. \begin{enumerate} ... \end{enumerate} 등입니다.
  • 기타 LaTeX만의 이상한 점들이 있습니다. 예를 들어 '는 무조건 오른쪽 닫는 작은따옴표입니다. ``는 왼쪽 여는 큰따옴표를 렌더합니다.

결국 지금까지는 어떻게 하든 문제마다 디스크립션을 한 땀 한 땀 옮겨 줘야 하는 경우가 대부분이었습니다. 제 경우에는 이런 작업을 2019/2020/2021년 서강대학교 프로그래밍 대회, 2020/2021 겨울/2021 여름 신촌 연합, UCPC 2020의 일곱 번의 대회에서 모든 문제에 대해 해 왔고 올해도 숨은 왼쪽 여는 따옴표 찾기를 하고 싶지는 않았습니다.

그래서 만들었습니다: 디스크립션 툴

BOJ 디스크립션 툴

그래서 LaTeX, 특히 Polygon 플랫폼과 많은 대회들이 사용하는 olymp.sty 형식 디스크립션들을 복사-붙여넣기할 수 있는 HTML로 바꿔 주는 툴을 만들었습니다. latex-utensils를 이용해 LaTeX를 파싱해 AST로 만들고, AST를 탐색하면서 다시 HTML로 빌드해 주는 툴입니다. 생성되는 HTML은 BOJ Stack 가이드라인을 최대한 따르려고 노력합니다.

HTML 수식 모드

원하는 경우 MathJax를 사용하지 않고 sup, sub, em 등을 이용해 수식을 렌더하도록 할 수 있습니다. 이 모드에서 렌더한 모든 수식도 BOJ 가이드라인을 최대한 따르려고 노력합니다. 예를 들어,

  • LaTeX에서는 연산자와 문자 사이에 띄어쓰기가 없더라도 변환된 HTML에는 자동으로 띄어쓰기가 들어갑니다.
  • 수식 안에 있는 모든 문자는 HTML로 변환할 때 이탤릭이 됩니다.
  • \times&times;가 됩니다. - (빼기 기호)는 &minus;가 됩니다.

라이트 버전 MathJax라고 생각하시면 됩니다. 아직 안 되는 것들도 있습니다. 명령어 재정의와 tabular 환경, 그리고 이미지 지원이 대표적인 예인데, 이미지 지원을 제외하고는 아마 다른 대회에서 출제/검수를 맡게 될 때 만들지 않을까 싶습니다.

바뀐 워크플로우

이제 Polygon 패키지 혹은 문제지를 만들고, 변환기의 도움을 받아 HTML로 변환한 뒤 BOJ Stack에 복사/붙여넣기만 하면 됩니다.

디스크립션 작업을 버전 관리가 되는 Polygon 혹은 실시간 편집이 되는 Overleaf의 둘 중의 하나로 일원화할 수 있어서 플랫폼 간의 컨플릭트가 사라지고, LaTeX에서 HTML 또는 HTML에서 LaTeX로 변환하는 과정을 더 이상 손으로 하지 않아도 되기 때문에 실수할 여지도 줄어들고 시간도 아낄 수 있습니다. 디스크립션 변환할 시간에 틀린 풀이 하나 더 짜고 데이터 하나 더 만들어 넣을 수 있게 되었습니다.

이미 UCPC 2022의 모든 문제를 이 툴을 사용해 변환했습니다. 모든 변환은 클라이언트에서 이루어지니 문제 유출 염려 없이 안심하시고 사용하셔도 괜찮습니다.

ckeditor 대응

Stack은 ckeditor를 쓰고 있는데, 포매팅이 있는 외부 HTML을 복사-붙여넣기하면 시맨틱한 요소를 빼고 모든 포매팅을 지워 버립니다. 아래 스크립트를 실행해 붙여넣기 필터를 전부 없애 줘야 합니다.

var o=CKEDITOR.filter.instances;Object.keys(o).forEach((k)=>o[k].disable())

여담

툴이 완벽하지 않은 부분들이 있으니 버그를 발견하신 경우 GitHub에 이슈 혹은 PR을 남겨 주시면 감사하겠습니다.

각주

  1. 디스크립션에서 글자에 색상을 넣지 못하는 건 의외로 중요한 이슈입니다! 특히 입력부에서 제시하는 어떤 문자열을 그대로 출력하라고 할 때 모노스페이스 폰트와 함께 글자 색상을 바꾸면 가독성이 굉장히 향상됩니다.

알고리즘 문제해결의 관점에서 프로그래밍 언어라는 것은

언어는 도구에 불과하다고들 합니다. 그리고 모든 도구는 용도와 장단점이 있습니다. 알고리즘 문제해결 필드에서 언어라는 도구를 어떻게 사용하면 좋을까요?

프로그래밍 대회에서의 문제해결에 대해 많은 이야기를 할 예정이지만 이제는 코딩 테스트도 알고리즘 문제해결에서 상당한 비중을 차지하고 있기 때문에 먼저 코딩 테스트에 대해 간단하게만 이야기해보겠습니다.

코딩 테스트

© 프로그래머스

코딩 테스트는 기업이 많은 지원자를 세심하게 리뷰하기 힘들기 때문에 두는 스크리닝screening 과정 중 하나로, 코딩 테스트 문제의 출제 목적은 수험자의 구현력과 논리적 사고력이 일정 수준 이상인지 평가하는 데에 있습니다.

일반적으로 같은 알고리즘을 짠다면 C++로 짜는 게 시간/공간 사용량 면에서 가장 효율적이라고 합니다. 하지만 현업에서 모두가 C++을 사용하지는 않죠? 가령 Typescript로 백엔드 개발을 하는 조직이 있는데 C++로 지원자를 평가한다고 생각해 봅시다. 지원자는 C++에 대한 이해가 부족해 Javascript에서 하던 것처럼 vector<int> 값을 &*도 안 붙이고 함수 인자로 넘겨버립니다.1 이 얼마나 끔찍한 일인가요? 지원자는 제 실력을 못 내고, 회사는 지원자를 제대로 평가할 수 없게 됩니다.

그래서 일반적으로 코딩 테스트 문제들의 시간 제한과 메모리 제한은 언어마다 다르도록 설정하거나 언어에 따라 배수를 두는 편입니다. 그래서 저는 코딩 테스트를 준비하시는 분들께는 자신이 가장 자신있는 언어 혹은 입문하기 쉬운 언어로 시작하시기를 추천드립니다.

프로그래밍 대회

반면에 프로그래밍 대회들은 C++을 사랑하기로 유명합니다.

왜 그럴까요?

세팅하는 입장에서

고통의 근원

문제를 만드는 입장에서 여러 언어의 존재는 참 머리아픈 일입니다. $\mathcal{O}\left(n^2\right)$ 솔루션은 돌게 하고 싶지만 $\mathcal{O}\left(n^2 \log n\right)$은 돌지 않게 하고 싶은 경우에서 C++만 놓고 생길 수 있는 일들에 대해 알아봅시다.

  • $\mathcal{O}\left(n^2\right)$ 솔루션 — 1.4초
  • $\mathcal{O}\left(n^2\right)$ 솔루션 + mmap fast I/O + Ofast — 1.0초
  • $\mathcal{O}\left(n^2 \log n\right)$ 솔루션 — 2.4초
  • $\mathcal{O}\left(n^2 \log n\right)$ 솔루션 + mmap fast I/O + Ofast — 2.0초

보통 시간 제한은 틀린 솔루션의 0.5배 시간 미만, 모델 솔루션의 2배 시간 초과 정도로 잡습니다. 그래서 이런 상황이 오면 약간 애매해지게 됩니다. 이제 세터는 어느 장단에 맞출지 생각해 봐야 합니다. 여러 가지 선택지가 있습니다.

  • 문제 상황과 $n$을 요리조리 바꿔 보면서 모델 솔루션과 틀린 솔루션 사이의 격차 늘리기
  • 상수 최적화를 문제 컨셉으로 잡고 시간 제한을 1.5초로 걸기
  • 그냥 fast I/O + Ofast까지 쓰면서 문제를 해결하려고 한 노력을 인정해 주기 위해 시간 제한을 2.0초로 걸기
  • 이미 기획된 난이도 커브를 벗어나더라도 아예 $\mathcal{O}\left(n^2 \log n\right)$를 정해로 두고 시간 제한을 4.0초로 걸기

여기에 이제 Python이 추가된다고 해 봅시다. 발생할 수 있는 일들은 이렇습니다.

  • C++ 기준으로 시간 제한을 1.5초로 줬는데 Python $\mathcal{O}\left(n^2\right)$ 코드가 2.0초에 도는 경우
  • C++ 기준으로 시간 제한을 1.5초로 주고 대회 플랫폼의 추가 시간 규정에 따라 추가 시간을 6.5초로 줬는데, Python의 $\mathcal{O}\left(n^2 \log n\right)$ 솔루션이 4.0초에 도는 경우
  • 온갖 짓을 다 해서 최적화한 Python $\mathcal{O}\left(n^2\right)$ 코드가 2.4초에 도는 경우
  • 온갖 짓을 다 해서 최적화한 Python 코드가 결국 메모리를 1GB 이상 사용해서 터지고, 메모리를 최적화하려고 봤더니 이번엔 시간이 터지는 경우
  • Python으로 풀면 현저히 쉬워짐
  • Python 코드가 set이나 dict를 사용2

결국 언어가 하나 추가될 때마다 모든 언어에 대해 문제 상황과 시간 제한, 그리고 데이터를 다시 고민해야 하는 상황에 빠집니다! 특히 언어별로 추가 시간을 주지 않는 일반적인 ICPC 스타일 대회의 경우 시간 제한 설정의 난이도는 말 그대로 기하급수적으로 증가합니다. 솔루션을 작성하는 데 있어서도 언어별로 조심해야 할 점들이 다른 건 말할 것도 없구요.

이렇게 여러 언어를 대응하는 것은 공수가 많이 드는 일이기 때문에 보통은 C++ 솔루션만 작성하고 다른 언어의 통과를 보장하지 않습니다. 알고리즘 대회에서 코드 간 형평성은 시간 복잡도를 기준으로 결정하는 것이 가장 좋다고 생각하는 입장에서는 언어별 추가 시간을 줬다가 Python에서 비효율적인 시간 복잡도로 작성한 코드가 통과할 수도 있고요.

참가자 입장에서

그래서 프로그래밍 대회 참가자 입장에서는 C++ 스탯만 쌓아도 충분합니다. 프로그래밍 대회들이 C++에서 풀기 까다로운 문제들을 잘 안 내는 것도 있습니다.

하지만 해결가능성이 C++만으로 보장되더라도, 보통은 다른 언어들의 사용을 어느 정도 허용하기 때문에 여러 언어들의 사용 방법을 알아 둬서 나쁠 건 전혀 없습니다. 문제를 읽고 머릿속에서 코드 길이 견적을 내 봤는데 C++ 코드보다 Python 코드 길이가 훨씬 짧다면, Python으로 코드를 짜고 해결 시각에서 상당한 우위를 점할 수 있습니다.

또한 언어별로 특징적인 기능들이 존재하는 경우 이 기능들을 최대한 활용해 문제해결 도움을 받을 수도 있습니다. C++이 아닌 언어에서 문제해결이 현저히 쉬워지는 몇 가지 예를 소개합니다.

문자열 다루기 — Python

문자열 파싱은 Python에서 쉬워지는 경우가 많습니다.

  • C++의 std::string은 일반적으로 다른 언어에는 있는 split이 없고, char를 하나하나 처리하기 싫다면 std::istringstream 등을 이용해야 합니다.
  • C++의 경우 비 ASCII 문자의 처리가 어렵습니다. 비 ASCII 문자들은 나오면 안 된다고 생각하는 것과 별개로….
  • C++의 정규식은 활용하기가 귀찮게 되어 있습니다.
  • Python의 f-string이 너무 강력합니다.

C++로 문자열에서 숫자들을 찾는 정규식을 구현하면 이렇게 됩니다.

regex re("\\d");
string str;

auto begin = sregex_iterator(str.begin(), str.end(), re);
auto end = sregex_iterator();
for (auto iter = begin; iter != end; iter++) {
    smatch match = *iter;
    cout << match.str() << " ";
}
cout << endl;

Python으로는 비슷한 작업을 아래와 같이 할 수 있습니다.

import re

p = re.compile('\\d')
result = p.findall(str)
print(result)

크고 정확한 수 다루기 — Python, Java, Kotlin

C++에서 가장 큰 부호 있는 정수 자료형은 $2^{63}-1 \approx 9.2 \times 10^{18}$까지를 표현할 수 있습니다.3 많은 문제들의 $N$ 제한이 $10^{18}$을 잘 초과하지 않는 이유이기도 합니다.

하지만 이 범위를 넘어가는 수의 사칙연산이 필요하다면 직접 구현체를 만들어야 합니다. 특히 큰 수의 곱셈과 나눗셈의 경우 단순히 $\mathcal{O}\left(1\right)$로 생각할 수 있는 문제가 아닙니다. $n$자리 곱셈을 초등학교에서 하듯이 구현하면 $\mathcal{O}\left(n^2\right)$의 시간이 걸리며, 더 효율적인 곱셈 방법이 필요하다면 $\mathcal{O}\left(n^{\log_2 3}\right)$의 Karatsuba 알고리즘 혹은 $\mathcal{O}\left(n \log n\right)$의 FFT를 짤 수 있어야 합니다.

Java와 Kotlin의 경우 $9.2 \times 10^{18}$을 초과할 수 있는 BigInteger를 지원합니다. Python은 아예 정수형 자체에 범위가 없고, 다룰 수 있는 수의 이론적 상/하한이 없습니다. 곱셈은 OpenJDK의 경우 자릿수에 따라 나이브, Karastuba 혹은 Toom–Cook 알고리즘을 사용하며, CPython의 경우에도 자릿수가 작으면 나이브, 크면 Karatsuba 알고리즘을 사용합니다.

정수 곱셈 문제들을 FFT로 풀 수 있듯이 이 사실에 기반해 FFT 문제를 Python 정수로 풀 수도 있기는 합니다. 아래는 이동 (BOJ #1607)를 실제로 Python으로 해결한 코드입니다. Karatsuba는 FFT보다 느린 경우가 많기 때문에 굳이 추천하지는 않고 대충 이런 방법도 있다는 걸 보여드리기 위해 남깁니다.

정확한 유리수 표현arbitrary precision이 필요한 경우 Python decimal과 Java BigDecimal을 사용할 수 있습니다. 추가로 Python은 어떤 유리수도 표현 및 계산할 수 있는 Fraction 모듈을 제공합니다.

특히 Google Code Jam에서는 제한이 $10^{18}$을 초과하는 큰 수를 다루는 문제들이 종종 등장하므로 알아 두면 좋습니다.

모듈로 곱셈 역원 — Python

C++에서 mod $p$의 나눗셈을 하려면 보통 Fermat의 소정리($n \times n^{p-2} \bmod p = 1$)를 바탕으로 분할 정복을 이용한 거듭제곱을 구현합니다.

놀랍게도 Python의 내장 pow 함수는 서로소인 $n$과 $m$에 대해 $n \bmod m$를 빠르게 구할 수 있습니다. 심지어 $m$이 소수가 아니어도 됩니다. C++에서는 $m$이 소수가 아닌 경우에는 Euler’s totient function 혹은 확장 Euclidean 알고리즘 구현에 대해 알고 있어야 합니다.

잉여역수 구하기 (#15995)는 Python으로 무려 두 줄만에 해결할 수 있습니다.

다각형의 bool 연산 다루기 – Java, Kotlin

다각형의 bool 연산(and, or, xor 등)은 C++로 직접 구현할 경우 상당히 다루기 힘든 주제입니다. Java의 java.awt.geom은 이런 작업들을 처리해 주는 구현체입니다. 단순다각형뿐만 아니라 원, 타원, 2-3차 베지어 곡선 등으로 이루어진 도형의 불 연산을 처리할 수 있고, 구한 도형의 꼭짓점 정보 등을 쉽게 구할 수 있습니다.

java.awt.geom 패키지를 활용해 문제를 해결하면 난이도가 꽤 낮아지는 문제들의 예시로는 이런 것들이 있습니다.

다만 충분히 효율적이지는 않기 때문에 모든 다각형의 불 연산 문제에서 사용할 수 있는 것은 아닙니다. 예를 들어 Lonely mdic (BOJ #10900)이나 직사각형의 합집합(BOJ #2185) 같은 문제는 geom만으로 해결하기는 어렵습니다. 메모리를 많이 사용한다는 Java 언어 자체의 한계도 존재합니다.

정리하면

누군가 알고리즘 문제해결을 코딩 테스트가 아닌 대회 준비로 시작한다면 저는 주저 없이 C++을 추천할 것입니다. 적어도 2020년대에는 C++만 배워도 대회에 등장하는 모든 문제를 해결할 수 있을 겁니다.

하지만 C++이 모든 경우에서 제일 좋은 툴은 아닙니다. 도구상자에 여러 도구들이 있다면 특정 상황에서 조금 더 편한 도구들을 꺼내 쓰는 것이 좋을 수 있습니다. 도구의 장단점을 정확히 알고 적재적소에 가져다 쓰는 것도 경쟁 프로그래머의 역량이라고 생각합니다.

각주

  1. C++에서는 모든 함수 인자가 기본적으로 값을 복사해 전달되며 vector<int>와 같은 동적 배열 타입도 그렇습니다. 반면 Javascript 등의 언어는 기본 자료형이 아닌 모든 함수 인자는 레퍼런스를 복사해 전달됩니다.
  2. Python의 setdict는 룩업에 $\mathcal{O}\left(n\right)$가 되도록 하는 데이터를 제작하기 쉽습니다. 이는 사실 C++의 std::unordered_map도 마찬가지입니다. 일반적으로 라이브러리 내부 자료 구조의 동작을 묻는 것은 문제의 포커스에서 벗어나 있기는 하지만, 대회 컨셉과 형식에 따라(예를 들어 참가자가 다른 참가자의 제출을 저격할 수 있는 TopCoder 혹은 Codeforces 등) 고려할 여지가 있습니다.
  3. G++이라면 __int128을 써서 $2^{127}-1 \approx 1.7 \times 10^{38}$까지는 어찌어찌 타협을 볼 수도 있겠습니다.

모스크바 ICPC 월드 파이널에 다녀왔습니다 (1)

ICPC 월드 파이널 참석 후기

여기 졸업을 앞두고 있는 사람 두 명과 펍지 엔지니어 한 명, 넥슨 엔지니어 한 명이 있습니다. 이 사람들은 어쩌다 이런 시국에 인천공항 버거킹에 모이게 되었을까요.

세렌디피티

휴가를 쓰고 호캉스를 온 날 조식을 먹으러 가려던 찰나 이상한 메일을 받게 됩니다. Fwd: ICPC World Finals Moscow – Sogang University라는 제목의 메일입니다. 월드 파이널? 대체 왜? 하는 심정으로 열어본 메일에는 믿기 힘든 내용이 적혀 있었습니다.

‘서강대학교 ICPC 관련인들께, […] 팀 Redshift가 모스크바에서 열리는 월드 파이널의 참가 자격을 얻게 되었습니다. 10월 1일에서 6일까지 모스크바에 올 수 있으면 됩니다. 한국에서 코로나19가 유행하면서 모스크바까지 오는 것이 힘들지도 모르겠습니다만, (아직까지 참석 가능성에 대한 회신이 없는 관계로) 팀이 정말 희망이 없는지 ICPC 매니저께서 확실히 알아야 합니다. 임 코치님께 회신을 요청해 주시면 감사하겠습니다.’

월드 파이널이라니? 내가? 왜?

2년 전에 ICPC 서울 리저널에서 8위에 오른 적이 있습니다. 8위까지 티켓이 내려갔다니, 싶지만 중요한 건 이게 아닌 것 같습니다. 침착하게 아래에 포워딩된 메일을 읽어봤습니다.

‘안녕하세요 코치님, […] 8월 9일 오후 11:59 CST까지 회신 부탁드리겠습니다. 이 때까지 회신이 없으면 참가하지 못하는 걸로 간주하도록 하겠습니다. 질문이 있으면 자유롭게 회신 부탁드려요. 월드 파이널에서 뵙길 바라겠습니다!’

맙소사, 오늘은 8월 12일인데…

빠르게 머리를 굴려 봅니다. 스팸메일은 아닌 거 같다. 진짜 월드 파이널에 진출한 거 같긴 하다. ICPC 본부에서 8월 9일까지 답장을 주라고 했는데, 8월 12일에 이런 메일이 왔다. 그것도 학회 홈페이지 맨 밑에 적힌 메일 주소로 왔다.

그러면 제가 할 일은 명확했습니다. 최대한 빨리 회신을 보내야 합니다. 바로 코치 교수님과 팀원들에게 전화를 걸어서 협조를 구했습니다.

첫 번째 산: 참가 신청

2019년 레드시프트는 17학번 박건(lvalue), 17학번 이준석(semteo04)과 저(shiftpsh)로 이루어진 팀이었습니다. 같은 나이라서 서로 편하게 반말하고 있어요. 글을 읽고 계신 분들이라면 이름보다는 핸들이 더 익숙할 테니, 앞으로는 핸들로 적도록 하겠습니다.

semteo04는 펍지에서 산업기능요원으로 복무 중입니다. 그렇다는 건 보통 평일 아침에 일어나 있고, 따라서 전화를 받을 수 있다는 뜻입니다. 누구보다 경쟁 프로그래밍에 진심인 친구여서 아마 월파라면 무슨 일이 있어도 휴가를 쓰고 비행기에 함께 오를 것입니다. 그리고 몇 분 안 지나 제가 옳게 봤다는 걸 확인할 수 있었습니다.

lvalue는 졸업하고 KAIST AI대학원에서 연구를 하고 있습니다. 아마 아침에 안 일어나 있을 것입니다. 평소에도 전화를 안 받기로 유명합니다. 나중에 연락하기로 합니다. 다행히도 트위터 맞팔이라, 멘션이나 DM을 보내면 곧잘 확인할 것입니다.

코치 교수님께서는 제 어셈블리프로그래밍 교수님이셨는데, 당시 러시아발 해외입국자는 14일 자가격리가 필요했기 때문에 안타깝게도 본인께서는 참석하지 않길 원하셨습니다. 그리고 이후 받은 lvalue의 연락에서 연구하느라 바빠서 참석하기 어려울 것 같다는 답변을 들었습니다.

이렇게 시작부터 두 가지 문제가 생겼습니다.

  • 코치가 참석할 수 없다면 팀의 참가자격은 유지되는가.
  • 팀원이 참석할 수 없는 경우에도 그러한가.

다행히도 예외적인 경우였기 때문에 팀원을 2019년 혹은 2020년 리저널 참가 이력이 있는 학생으로 대체 가능했으며, 코치가 참석하지 않아도 괜찮다는 답변을 받았습니다.

2021년 레드시프트는 lvalue 대신 전해성(seastar105) 선배와 함께 UCPC에 출전해서 5등상을 받은 바 있습니다. 이 구성으로 다시 출전하고 싶었지만 안타깝게도 seastar105 선배께서는 당해년도 리저널 본선 출전 이력이 없으셨습니다.

그래서 학회 슬랙에서 최대한 빠르게 모집했습니다. 이윤제(yjyj1027) 선배와 이상원(gumgood) 선배께서 빠르게 연락을 주셨습니다. gumgood 선배께서 더 빠르게 연락을 주신 관계로, 이렇게 모스크바행 레드시프트가 결성되었습니다. 메일을 받고 7시간만입니다.

ICPC 시스템에 등록된 화면

이후 임지환(raararaara) 선배께서 co-coach로 오시길 희망하셔서, 이렇게 4명이서 여행 계획을 세우게 되었습니다.

티켓은 10위(UNIST Underdog 팀)와 11위(경북대학교 Catdriip 팀)까지 내려가서 한국에서만 7개 팀이 출전하는 유례없는 해가 되었습니다. 대회 참가를 위해서는 예방접종을 완료해야 했는데, 아시아태평양 지역 내에서 한국과 일부 나라를 제외하고는 백신 수급 상황이 좋지 않거나, 러시아발 입국자에 대한 자가격리 조치가 강력했거나, 아예 입출국을 허용하지 않았습니다. 한국의 비교적 나은 방역 상황으로 인해 운좋게 티켓을 얻었다고 생각합니다.

두 번째 산: 백신

사람들은 종종 제 장점을 강력한 추진력을 가졌다는 것이라고 말합니다. 반대로 말하면 앞만 보고 가느라 사소한 것들을 놓치는 건 약점이라고 할 수 있을 것 같습니다. 일단 참가할 수 있다고 질러놨지만…

참가자들은 예방접종을 완료해야 합니다

…출국 전에 예방접종을 완료해야 했습니다. 출국 예정일은 9월 말, 지금은 8월 12일이었습니다. 50일가량 남은 상황이었습니다. 그러나 fully vaccinated의 의미는 ‘접종 완료 후 14일 경과’이고, ‘접종 완료’는 2차접종이 필요한 백신의 경우 2차접종까지를 의미하기 때문에 2차접종을 36일 안에 받아야 한다는 뜻이 되었습니다.

네 명 모두 1차조차 미접종이었습니다. 당시 Pfizer 백신은 1차와 2차접종 사이 간격이 6주(=42일)였고, 그조차도 접종받기 너무나 어려웠습니다.

먼저 정부의 도움을 얻는 방법을 알아봤습니다. 질병관리청까지 올라갔다 내려온다고 합니다. 왠지 오래 걸릴 것 같은 느낌이 듭니다. ICPC는 소관부처가 어디일까요? ICPC는 경제활동일까요?

초청장이 있긴 하지만 여권번호가 적혀 있지 않아 아마도 승인해주지 않을 것 같았습니다. 그래도 일단 서류를 작성해 보냈습니다.

하지만 만에 하나 불승인되면 출국할 수 없게 됩니다. 불확실한 도박에 걸 수 없었습니다. 모두가 머리를 싸매면서 각자의 방법으로 갖가지 채널로 문의했습니다.

그러던 중 다행히도 저희 어머니께서 동네 병원에 직접 전화를 걸어 예약을 성공하셨습니다. 같은 방법으로 저뿐만 아니라 팀원 모두 동네 브루트포싱으로 1차접종 예약에 성공합니다. 접종일은 바로 이틀 후인 8월 14일이었습니다.

8월 14일은 UCPC 본선이기도 했습니다. 타이레놀 한 알을 먹고 바로 서강대 앞 스터디 카페로 달려가 UCPC 본선을 치뤘습니다.


1차접종은 가능한 한 최대한 빠르게 했지만 2차접종을 앞당기는 것이 필요했습니다. 당시 Pfizer 백신은 6주 후에 접종이 가능했습니다.

다행히도 접종 간격을 앞당기는 것은 보건소에 문의를 넣으면 비교적으로 쉽게 처리할 수 있었습니다. 양천구보건소에 수십 번 전화를 시도한 끝에 접종 간격을 4주로 단축할 수 있었습니다. 팀원 모두가 9월 11일에 2차접종을 완료했고 9월 말 출국 일정에 차질이 없게 되었습니다.

세 번째 산: 여행 일정과 경비

semteo04와 저는 산업기능요원으로 복무 중입니다. 그게 무슨 뜻이냐면 대학생이지만 직장에 다니고 있다는 뜻이고, 그게 무슨 뜻이냐면 여행을 다녀오려면 휴가를 써야 된다는 뜻입니다. 남은 휴가일 수를 고려해서 여행 일정을 잘 짜야 합니다.

또 하나 문제는 여행 경비였습니다. ICPC에서 지원해 주는 것은 대회 기간 중의 숙식 비용뿐이었습니다. 대회 기간을 벗어난 비용과 비행기값은 우리가 부담해야 했고, 이는 결코 만만한 비용은 아닙니다.

학교의 힘을 빌리기로 합니다. 방콕 리저널에 참가했을 때

㉠학교 대표가 아니라서 지원해줄 수 없다, ㉡학교 대표로 중국(2010년 월드 파이널) 갈 때는 지원해줬으니 나중에 ㉢학교 대표가 되어 와라’

는 말을 듣고 살짝 분했던 기억이 있습니다. 이제는 학교가 뭐야 국가대표가 되었으니 당당히 지원해 달라는 연락을 드렸습니다.

하지만 아무리 ㉢학교 대표가 되더라도 시국에 학교가 지원을 해주는 것도 학교 입장에서는 부담스러울 수 있을 거라고 생각했고, 백신 접종 간격을 4주로 단축시키기 위해 + 휴가를 쓰기 위해 당장 항공권이 필요한 상황이었습니다. 그렇게 고민하던 찰나 정말 감사하게도 ㉡학교 대표의 최백준(baekjoon) 선배께서 도와주실 수 있다는 말씀을 해 주셨습니다.

그렇게 외교부 홈페이지를 바쁘게 뒤져보면서 경유 노선을 찾아봤습니다. 유력 후보를 조사한 결과 다음과 같았습니다.

  • (모든 나라) → 러시아: ICPC에서 특별 비자를 발급해 줄 예정
  • 한국 → 폴란드: 도착 후 24시간 이내 출국(경유) 시 자가격리 면제
  • 한국 → 터키: 접종확인서가 있는 경우 자가격리 면제
  • 한국 → 프랑스: Pfizer, Moderna, AstraZeneca 백신 2회 접종 후 2주 경과
  • 한국 → 네덜란드: 접종확인서가 있는 경우 자가격리 면제

따라서 한국 → 러시아, 한국 → 폴란드 → 러시아, 한국 → 터키 → 러시아 중 하나를 타는 게 이상적이어 보였습니다. 가는편으로는 출발 시간이 제일 괜찮아 보였고 최단 소요시간이 붙어 있었던 폴란드항공을 타고 가기로 합니다. 백신 접종 연장을 위해 항공권이 당장 필요했고, 제가 당장 보유 현금은 제일 많았기에 일단 결제했습니다.

이번 달 끼니는 삼각김밥으로 때워야 합니다.

그리고 오는편은 가격이 싼 터키항공으로 예약했습니다. 항공권 예약을 마치고 백신접종 기간도 단축시키고 휴가도 썼습니다. 미필인 semteo04와 저는 국외여행허가서 신청을 완료합니다. 남은 휴가 8일 모두를 러시아에 쏟아부었습니다. 다만…

네 번째 산: 지원 불가, 그리고…

법인카드 결제분만 지원이 가능하며, 그 중에서도 재학생에게만 지원이 가능하다는 답변이 돌아왔습니다. 이미 결제했기 때문에 지원이 힘들다는 것이었습니다. 백준님께는 죄송하게 된 일이지만 사실 그렇게 큰 충격은 아니었습니다.

그러나 진짜 문제는 따로 있었습니다.

당시 러시아는 경유항공편의 경우 경유지를 제한하고 있었습니다. 그 중에 폴란드가 없었습니다.

ICPC 운영 측에 비자 발급을 도와줄 수 있느냐고 여쭤봤더니 ‘러시아 정부 차원에서 입국승인 행정명령을 내렸기 때문에 안심해도 좋다’는 답변이 돌아왔습니다. 불안하지만 일단은 안심합니다.

그러나 진짜 문제는 따로 있었습니다.

오는편이 연착되었습니다. 연착 자체는 큰 문제가 아니지만, 휴가를 전부 소모해버려 이대로면 산업기능요원 복무가 연장되고 맙니다.

결국 불안했던 가는편을 포함해 모든 항공권을 취소하고, 새로 여정을 짜기로 했습니다. 가는편은 9월 28일 터키 경유 밤비행기로, 오는편은 10월 8일 대한항공 직항으로 결정합니다.

새로 항공권을 결제하면서 2명분의 경우 학과 지원을 받을 수 있었고, 나머지 2명분의 경우 네 명이 똑같이 분담하기로 결정했습니다(~32만 원). 싼 값에 러시아 다녀오는 셈 치고요.

ICPC 대시보드의 호텔 예약 UI

ICPC 대시보드에는 호텔 예약 정보 조회 기능도 있습니다. 신기하죠.

호텔은 대회 기간 중에만 지원되었습니다. 여정 중에 대회 기간이 아닌 기간의 경우 따로 결제했습니다. 다행히도 따로 결제한 날들과 지원받은 날들의 예약을 합쳐 주셔서 방을 옮기지 않고 지낼 수 있었습니다.

이제 공항에서 PCR 테스트만 받고 결과지를 챙겨 가면 모든 준비는 끝납니다. PCR 검사 결과가 나올 때까지는 6시간가량이 걸린다고 합니다. 가는편을 밤비행기로 변경한 덕분에 당일에 검사를 받아도 문제없게 되었습니다.

이스탄불으로

한국을 떠나기 위한 모든 준비를 마쳤습니다. 출국심사를 마치고 경유지인 이스탄불로 이동합니다.

공항 도착 이후의 이야기는 언제가 될 지 모르는 다음 포스트에서 정리해 보겠습니다.

시리즈: ICPC World Finals Moscow

  1. 모스크바 ICPC 월드 파이널에 다녀왔습니다 (1)
  2. 모스크바 ICPC 월드 파이널에 다녀왔습니다 (2)

2022년에 React 컴포넌트 라이브러리 만들기

@solved-ac/ui-react를 만들기 위한 여정

TL;DR:

  • create-react-library는 쓰지 마세요.
  • peerDependencies에 추가하는 라이브러리는 devDependencies에도 추가하세요.
  • styled-components 기반 라이브러리에서 SSR 이슈가 발생한다면 이 글을 참고하세요.

저는 다음 달이면 3년차가 되는 프론트엔드 개발자입니다. 하나 고백하자면, 안타깝게도 저에게는 프론트엔드 사수가 있었던 적이 없습니다. 여태까지 독학한 React 지식으로 얼렁뚱땅 일해왔다고 할 수 있습니다. 여태까지는 잘 먹혔습니다.

근데 이제 파트장입니다. 야 이거 큰일 났다. 면접도 내가 봐야 되고 신규입사자 교육도 내가 해야 되는데 나는 아는 게 하나도 없네…

그래서 인터넷의 힘을 빌리기로 합니다.

작성했던 코드를 잘 짰던 못 짰던 일단 올리고 보는 겁니다. 이렇게 하면 사수 분들이 마구마구 생기겠지? 회사 코드를 올릴 수는 없고, 마침 개인적으로 컴포넌트 재사용에 대한 니즈가 있던 solved.ac 코드를 정리해서 올려보기로 합니다.

첫 삽 뜨기

모르는 게 있을 때 취해야 하는 참된 개발자의 자세, 바로 구글 켜기입니다.

구글에 creating a react component library를 검색한 결과

1시간 정도 구글링해본 결과 아래 옵션들로 정리할 수 있었습니다.

Bit은 좋아 보이지만 나중에 뭔가 하려면 돈을 내야 될 것 같은 분위기를 느껴서 제외했습니다. 그냥 rollup을 직접 쓰는 것과 create-react-library의 도움을 받는 것 중에서 고민하다가 create-react-library를 골랐습니다. 간단해 보여서였습니다.

프로젝트를 만들고 기존에 쓰던 테마 정의와 함께 Button 컴포넌트를 옮겨왔습니다.

어 그런데 뭔가 이상합니다.

이 왜 any?

분명히 테마도 타입 정의가 잘 되어 있고 styled-components도 잘 임포트되어 있는데 테마 속성들이 전부 any로 뜹니다. 심지어는 styled component prop도 any가 뜹니다. 타입 추론이 없는데 어떻게 개발을 합니까? 이건 천재지변입니다.

styled-componentspeerDependencies에만 있고 devDependencies에는 없었음을 확인하고 고치는 데는 의외로 많은 시간이 걸렸습니다.

dependencies, devDependencies, peerDependencies

TL;DR: 라이브러리를 개발할 때 peerDependencies에 뭔가를 추가하려면 devDependencies에도 똑같은 패키지를 추가해야 합니다.

너무 기니까 dependencies를 줄여서 deps라고 부르도록 합시다.

depsdevDeps는 패키지를 빌드했을 때 프로덕션 번들에 포함되는지 아닌지의 차이가 있습니다. devDeps에는 주로 @types/*라던가 Prettier, Babel 플러그인과 같이 개발 과정이나 빌드 등을 도와주는 패키지들이 들어갑니다. 이미 완성된 코드에다 ESLint를 돌릴 이유는 없으니까요.

하지만 depsdevDeps는 사실 일반적인 프론트엔드 프로젝트에서는 별 상관이 없습니다. 이는 webpack의 번들 방식 때문인데, webpack은 entryPoint부터 시작해서 import들을 따라가면서 패키지들을 필요에 따라 넣기 때문입니다. create-react-app@types/* 같은 의존 패키지들을 전부 devDeps가 아니라 deps에 때려박아도 별 일 없는 이유이기도 합니다. 개인적으로는 싫지만…

peerDependencies

라이브러리를 만들면 아무도 의존하지 않는 패키지 – 예를 들면 프론트엔드 앱 – 를 만들 때는 볼 수 없었던 peerDeps와 마주하게 됩니다. peerDeps에 의존성을 추가하면 내 패키지에서 의존성을 관리하는 대신 내 패키지를 의존하는 패키지에서 의존성을 대신 관리하게 됩니다.

말이 조금 헷갈리는데, 예를 들어 내 프로젝트가 라이브러리 A, B, C를 쓰는데, 세 라이브러리 모두가 D라는 패키지에 의존한다고 합시다.

  • 세 라이브러리에서 D를 deps로 두는 경우에는 node_modules에 A > D, B > D, C > D 모두가 들어가게 됩니다.
  • D를 peerDeps로 두는 경우에는 node_modules에 A, B, C, D가 따로따로 들어가고, 내 프로젝트 단에서 A, B, C 각각이 내 프로젝트에서 직접 가져온 D에 의존할 수 있도록 해 줍니다.

요약하면, peerDeps는 의존성 트리 최적화를 위해 내 패키지를 쓸 패키지들에게 ‘이거 대신 설치해 주세요’라고 설명하는 것과 같습니다. 이건 ‘내 패키지 자체에서는 이 의존성을 굳이 쓰지 않겠어요’라는 말과 같은 말입니다. 다 좋은데 그러면 내가 내 패키지는 어떻게 개발하죠?

빌드된 모습

결과적으로는 peerDepsdeps 모두에 의존성이 들어가야 합니다. 이렇게 하면 빌드된 index.js에서 peerDepsrequire를 사용하도록 바뀌고 나머지는 잘 번들됩니다. 이 require는 로컬 환경에서는 deps에 의해 설치된 패키지를, 피의존 환경에서는 이 패키지의 peerDeps에 의해 설치된 패키지를 활용할 것입니다.

알고 나면 어렵지 않은 이유지만, 라이브러리를 만드는 입장에서 peerDeps를 설명해 둔 리소스가 현저히 적어서 알기까지 너무 오래 걸렸습니다. 이건 험난한 여정의 시작일 뿐이라는 걸 당시의 저는 몰랐습니다.

인터넷에 올리기 부끄럽지 않은 코드 짜기

const ButtonContainer = styled.button<ButtonContainerProps>`
  display: inline-block;
  vertical-align: middle;
  text-align: center;
  background: ${({ backgroundColor }) => backgroundColor}; // XXX
  /* ... */
`

이건 안 좋은 코드의 예입니다. solved.ac에서는 버튼에 색상을 그렇게 많이 집어넣거나 색상에 애니메이션을 줄 일이 없었기 때문에 기존에는 이렇게 구현했지만, styled-components는 모든 경우의 수마다 CSS 클래스를 하나씩 만들 거고 자칫 다이나믹할 수 있는 값을 이런 식으로 구현하면 퍼포먼스 이슈가 생길 것은 안 봐도 비디오, 웰 노운 팩트입니다.

따라서 CSS 변수를 사용하기로 합니다. 스타일드 컴포넌트 안에서는 색상 등을 var(--solvedac-button-background-color) 등으로 정의하고, 컴포넌트에 인라인 스타일로 --solvedac-button-background-color: #17ce3a와 같은 식으로 넣어주면 됩니다. 이걸 잘 쓰기 위해 타입스크립트의 도움을 받고 싶습니다. 예를 들어 아래와 같은 코드를 작성하면…

const [vars, v] = cssVariables(
  [
    'backgroundColor',
    'hoverBackgroundColor',
    'textColor',
    'hoverTextColor',
    'hoverShadow',
    'activeShadow',
  ],
  'button'
)

…스타일드 컴포넌트에서는 이렇게 가져다 쓰고…

const ButtonContainer = styled.button<ButtonContainerProps>`
  display: inline-block;
  vertical-align: middle;
  text-align: center;
  background: ${v.backgroundColor}; // Does not trigger class name generation which is good
  /* ... */
`

…인라인 스타일은 이렇게 넣을 수 있게 말이죠.

<ButtonContainer
  disabled={disabled}
  circle={circle}
  fullWidth={fullWidth}
  style={{
    [vars.backgroundColor]: computedBackgroundColor,
    [vars.hoverBackgroundColor]: computedHoverColor,
    [vars.textColor]:
      computedBackgroundColor &&
      readableColor(computedBackgroundColor, solvedTheme),
    /* ... */
    ...style,
  }}
  {...rest}
>
  {children}
</ButtonContainer>

이게 전부 타입 추론이 되게 하기 위해서 열심히 타입스크립트 매드무비를 찍습니다. readonly를 사용하면 string 배열을 tuple 취급하게 할 수 있습니다. 여기서 [...T]는 TS 4.0 기능입니다.

export const cssVariables = <T extends Array<string>>(
  names: readonly [...T],
  prefix: string
): [
  { [key in T[number]]: `--solvedac-${string}` },
  { [key in T[number]]: `var(--solvedac-${string})` }
] => {
  const vars = Object.fromEntries(
    names.map((name) => [
      name,
      `--solvedac-${prefix}-${name
        .replace(/[A-Z]/g, (m) => `-${m.toLowerCase()}`)
        .replace(/^-/, '')}`,
    ])
  ) as { [key in T[number]]: `--solvedac-${string}` }

  const v = Object.fromEntries(
    Object.entries(vars).map(([k, v]) => [k, `var(${v})`])
  ) as { [key in T[number]]: `var(--solvedac-${string})` }

  return [vars, v]
}

이렇게 하면 에디터가 타입 추론을 잘 해 줍니다. 그런데 갑자기 빌드가 되지 않습니다. 이번엔 왜일까요?

CSSProperties와 다시 만나는 declaration merging

리액트는 기본적으로 인라인 스타일에 --solvedac-button-background-color 같은 걸 허용하지 않습니다. CSSProperties의 키가 아니기 때문입니다. 리액트의 index.d.ts에는 이런 주석이 달려 있습니다.

export interface CSSProperties extends CSS.Properties<string | number> {
    /**
     * The index signature was removed to enable closed typing for style
     * using CSSType. You're able to use type assertion or module augmentation
     * to add properties or an index signature of your own.
     *
     * For examples and more information, visit:
     * https://github.com/frenic/csstype#what-should-i-do-when-i-get-type-errors
     */
}

직접 인덱스 시그니쳐를 만들고 싶으면 type assert를 하거나 module augmentation을 하라고 합니다.

Type assert는 웬만해서는 쓰기 싫기 때문에 declaration merging을 했습니다. 예전에 테마 타입 정의하는 데 고생한 적이 있어서 비교적 쉽게 해결했습니다. 이렇게 하면 됩니다.

type CustomProp = { [key in `--${string}`]: string }
declare module 'react' {
  // eslint-disable-next-line @typescript-eslint/no-empty-interface
  export interface CSSProperties extends CustomProp {}
}

오래된 react-scripts, 관리가 중단된 microbundle-crl

리액트 프로젝트에서 타입스크립트 관련해서 뭔가 안 된다 싶으면 이 친구입니다. react-scripts는 자기만의 webpack 설정 등을 쓰기로 유명합니다.

create-react-libraryreact-scripts@3.4.1을 설치해 줍니다. TS 4.0을 지원하지 않는 버전입니다. yarn add react-scripts@latest -D로 해결해 줍니다.

이외에도 microbundle-crl은 예전 버전의 Babel을 사용하고 있으며, 2년 전 microbundle 소스의 포크입니다. Unfork 해 줍니다.

Zero configuration을 표방하는 패키지를 종종 보게 되는데, 일반적인 경우에는 좋지만 일반적이지 않은 경우에는 꽤 골치아파지게 됩니다. 여담으로 react-scripts를 쓰면서 webpack 구성을 바꿔야 하는 경우가 있다면, eject하는 대신 react-app-rewired를 사용해 보시기 바랍니다.

이제 모든 게 다 잘 됩니다. 슬슬 solved.ac에 적용해 볼까요?

이상해요

뭔가 이상한 솔브드

사이트에 새 컴포넌트들을 적용하고 띄워 보니 패딩이 사라져 있습니다. 그럴 리가 없는데… 링크를 타고 다른 페이지들을 로드해 보면 정상적으로 보입니다. Prop `className` did not match와 같은 증상이 또 나타났습니다! 이번엔 테마 정의도 declaration merging으로 해 줬고 babel-plugin-styled-components도 잘 설정해 줬는데 대체 왜?

SSR의 악몽

생성되어 있는 componentId

dist/index.js를 확인해 봤을 때 컴포넌트 ID는 빌드 시점에 생성되는 것을 알 수 있습니다. Babel 플러그인이 잘 동작했다는 뜻입니다.

그러면 의심이 가는 부분은 solved.ac 프론트엔드 프로젝트에서 ServerStyleSheetcollectStyles 해 주는 부분입니다. 이 방향으로 검색해 봤더니 FAQ가 하나 나옵니다. yarn link에 대한 내용이지만 이 라이브러리에도 적용할 수 있을 것 같습니다.

styled-components는 싱글톤이고, 각자의 스코프에서 렌더할 컴포넌트들을 전부 관리합니다. 따라서 solved.ac 프론트엔드 프로젝트와 방금 만든 UI 라이브러리에 있는 styled-components는 다른 styled-components라는 뜻입니다. 이걸 강제로 같게 만들어서 한 쪽의 styled-components가 프론트엔드 프로젝트와 UI 라이브러리 모두의 컴포넌트를 관리하게 해 줘야 합니다.

모든 require('styled-components')가 특정 경로의 모듈로 resolve 되도록 모듈 alias를 해 주면 되는데 Next.js + Typescript 환경에서는 비교적 간단하게 해결할 수 있었습니다.

{
  "compilerOptions": {
    "paths": {
      "styled-components": ["./node_modules/styled-components"]
    }
  }
}

이렇게 해 주면 SSR도 잘 적용되는 것을 확인할 수 있습니다.

Update: @solved-ac/ui-react는 이제 emotion을 사용하고 있습니다. emotion은 일부 셀렉터를 제외하고는 SSR 환경에서 별도의 설정 없이 사용할 수 있습니다. (2022/06/20)

사수 무제한 제공 거짓말 사건

컴포넌트를 라이브러리화하고 정상적으로 렌더하기 위한 과정들이었습니다. 모르면 맞아야 하는 도메인 지식들이 너무 많은데, 컴포넌트 라이브러리를 만드는 사람이 많지 않은지 리소스도 상당히 적었고 그로 인해 너무 고생을 많이 했습니다. 나는 있는 코드를 그대로 올리면 누군가 코드 리뷰를 해 주지 않을까 싶었던 것뿐인데!

그래도 이제 잘 동작하니까 계속 여러 컴포넌트들을 정리해서 올려봐야겠어요. 가뜩이나 리소스 없는 분야인 것 같은데 이 글이라도 여러분의 쓸데없는 삽질 예방에 도움이 되었으면 좋겠습니다.