(번역) 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)$의 값을 구하는 쿼리와 크게 다르지 않은데 어느 정도 정해로 접근하는 데 연막의 기능을 했다고 생각합니다.

700,000원짜리 글

2월 3일 금요일

낙성대 자취방

통근을 위해 계약했던 낙성대 원룸의 계약기간은 2월 28일까지. 짐을 빼야 된다고 생각하면 여기에 있을 수 있는 날은 3주 남짓 남았습니다. 근처에 사는 직장 동료들과 함께 근처의 맛있는 음식점과 펍에서 함께했던 즐거운 시간들, 자취방에 친구들과 동료들을 데려와서 보드게임도 하고 음식도 나눠먹던 생활들을 이제는 놔줘야 한다고 하니 정말 아쉽습니다.

3월에는 복학을 해야 합니다. 동료들의 이직/복학 시기와도 맞아서 다들 낙성대를 떠나 편한 위치로 옮겨갑니다. 제 학교 또한 마포에 있기 때문에 굳이 낙성대에 계속 남아서 40분 걸려 통학할 이유가 없겠습니다. 그럴 바에는 본가에서 50분 통학하는 게 낫겠습니다.

그런데 본가에는 제 공간이 있기는 하지만 제가 마음대로 쓰기에는 무리가 있습니다. 누군가를 데려오는 건 생각하기 힘듭니다. 음악을 틀어 두고 새벽까지 작업한다거나 하는 건 실례가 됩니다. 또한 지하철이 피해가는 위치에 있어서 서울 어딘가를 가려고 하면 기본 40분은 잡아야 하는 곳이라 그다지 매력적이지 않습니다. 이외에도 여러 이유가 있지만 통학에 편도 50분이 걸린다는 것과 제 공간을 마음대로 쓰지 못한다는 점 때문에, 자취를 2년 더 하기로 결심하고 새로 살 집을 찾기 시작합니다.


2월 6일 월요일

자취를 2년 더 하겠다는 제 결정에 어머니께서는 꽤 아쉬워하셨습니다. 보증금도 월세도 제 돈이기는 하지만, 그래도 달마다 비용이 나가는 걸 막을 수 있으면 막는 게 좋겠다는 의견을 주셨습니다. 하지만 그런 이유보다는 제가 없었던 기간 동안 본가에 꽤 활기가 사라져서 그랬을 것이라고 생각합니다. 그래도 좋은 매물을 함께 알아봐 주시고 부동산도 같이 다녀 주셨습니다. 참 죄송하고 감사합니다.

모아 둔 돈이 생각보다 꽤 있어서 전세를 알아봐도 괜찮겠다는 생각이 들었습니다. 막연하게 대출 금리를 알아봤습니다. 청년을 위한 전세대출 상품은 상대적으로 저금리로 제공되는 경우가 많았습니다. 버팀목 전세자금 대출의 경우 연소득이 5,000만원을 초과할 것이기 때문에 신청할 수 없다고 보고, 카카오뱅크 대출을 알아봤습니다.

장기미거래로 계좌가 잠겨 있어서 정확한 한도는 알아보지 못했지만, 신청 페이지 메인에는 최저 4.42%의 금리최대 2.22억원까지 가능하다고 적혀 있었습니다. 이 정보를 보고 금리를 4.42%로 하여 전세방을 구했을 때 달에 얼마를 내야 하는지를 계산했습니다. 보증금 2억짜리 집을 월 이자 48만-55만 정도에 살 수 있는 수준이었습니다.

별개로, 낙성대에 있던 짐 40% 가량을 본가로 가져왔습니다. 집이 꽤 허전해졌습니다.

오늘 한 일

  • 원래 살던 집에서 짐을 40% 뺌

2월 7일 화요일

수천만 원이 들어 있던 적금을 깼습니다. 만기를 채우지는 못했지만 어차피 이자율이 0.9%밖에 안 돼서 깨려고 생각하고 있던 참이었습니다. 전세계약금이 필요할 경우 이체하기 위해서이기도 합니다.

전셋집을 알아보려니 전세사기가 걱정됩니다. 인터넷을 뒤지다가 HUG 전세사기예방센터라는 사이트를 찾았습니다. 전세사기 유형별 사례 및 대처방안이 부동산 지식이 없는 저 같은 사람도 이해하기 쉽게 적혀 있었습니다. 여기 적힌 내용을 꼼꼼하게 읽어봤습니다.


2월 8일 수요일

직방 앱과 네이버 부동산 앱은 나름 괜찮지만, 여러 집을 비교분석하기는 힘듭니다. 제 대출 정보와 연동해 월 얼마를 내게 될지 환산해 주는 함수를 만들고 여러 집들을 비교해 보기로 합니다.

여러 지역의 집을 알아봤는데, 저 정도의 돈을 주고 2년 사는데 학교 바로 앞 정도가 아니면 많이 후회하지 않을까 하는 생각이 듭니다. 그래서 대흥역 근처로 계약하기로 마음을 굳힙니다.


2월 9일 목요일

본격적으로 집을 알아보기 시작했습니다. 학교에서 도보 3분 거리의 집 한 곳을 마음에 담아 두고, 부동산을 방문했습니다.

전체적으로 희고 화사한 분위기에 전보다 꽤 넓직한 집이었습니다. 모니터 두 개를 쓰기 때문에 책상은 마음에 들지 않았지만, 공간 자체가 넓어 부엌 맞은편에 책상을 따로 놓고 저 책상은 다른 용도로 쓰면 되겠다 싶었습니다.

이전 자취방은 원룸이라면 당연하겠지만 가로 1.2m 세로 1.2m 정도의 작은 화장실이 있었습니다. 어느 정도냐면 키 180cm의 주취자를 눕혀 놓고 세척하기에는 꽤 무리가 있는 정도입니다. 이곳은 이전 자취방 화장실의 두 배 정도 크기에 보일러실까지 있어서 마음에 들었습니다. 게다가 싱크대도 넓고 인덕션도 두 구, 엘리베이터도 있습니다.

등기부등본을구가 비어 있었습니다. 따라서 설정된 근저당권이 없다는 뜻입니다. 근저당권이 없다는 뜻은 집주인이 집을 담보로 대출을 받지 않았다는 것을 말해 줍니다. 집을 담보로 대출을 받았다면 집주인이 대출금을 제대로 갚지 못했을 때 집이 경매에 넘어갈 수도 있기 때문에 조심해야 합니다.

원래대로라면 학교 주변 다른 부동산도 돌아보려 했지만 이곳이 꽤 마음에 들었고, 서울 부동산들이 항상 하는 ‘빨리 계약해야 한다’는 말에 못 이겨 계약을 체결합니다. 임대인께서 직접 오셨고, 신분증을 보여주셨습니다. 여기까지는 적어도 제가 아는 전세사기 사례와 예방법들에 관한 지식 내에서는 별 문제가 없었습니다.

전세보증금은 2억원. 계약금은 여기의 10%인 2,000만원입니다. 작은 금액이라고 할 수 없는 돈이 통장을 빠져나가고 나니 왠지 모르게 불안합니다. 2년 살 집을 이렇게 막 결정해도 되나 하는 생각이 듭니다. 아까 보고 온 것보다 집이 좁은 것 같고, 역에서 좀 먼 것 같기도 하고, 내가 모르는 사기 수법이 있으면 어떻게 하나 같은 생각도 듭니다. 하지만 이미 계약은 해 버렸고, 이제는 전세대출을 알아봐야 할 때입니다.

계약을 체결하고 집으로 돌아오는 중 어머니께서 ‘버팀목 전세자금 대출이 되지 않느냐, 퇴직했기 때문에 근로소득은 없는 것으로 볼 것 같다’고 하셨습니다. 마침 6시 직전이라 은행에 문의전화를 걸 수 있었습니다. 현재 퇴직자라면 근로소득을 0으로 보고 버팀목 대출을 받을 수 있다고 합니다. 그렇게 하면 연이율은 2.4% 이하로 줄어들고, 카카오뱅크의 4.44%보다는 두 배 적은 이자를 낼 수 있습니다. 이쪽으로 알아보기로 합니다.

늦은 시간이라 다음날 은행에 가 보기로 합니다.

오늘 한 일

  • 전세계약 체결 (전세보증금 2억원, 2023년 2월 25일부터 2년 계약)
  • 계약금 입금 (전세보증금의 10% = 2,000만원)

2월 10일 금요일

새로 살게 될 집과 가까운 은행에 가봐야 할 것 같습니다. 하지만 바쁘기도 하고, 우리은행 서강대지점은 사람이 항상 많기 때문에 높은 확률로 헛걸음질을 하게 될 것 같습니다.

우리은행 서강대지점에 전화를 해 봅니다. 대기 중인 고객이 51명이라고 합니다.

한 시간 후에 다시 전화했습니다. 대기 고객이 얼마 없었는데 그마저도 빠르게 빠졌습니다. 알고 보니 중앙 고객센터 같은 게 있고, 각 지점으로 로드 밸런싱 같은 걸 하는 것 같았습니다. 고객센터 직원 분께서는 제 실행예정일이 2월 25일이라는 말을 들으시고는 얼마 남지 않은 것 같다고 약간 당황하셨습니다.

서강대점으로 연결을 시도했습니다. 그러나 서강대점은 대출 쪽 직원이 한 분밖에 안 계신 곳이고, 그마저도 계속 통화중이셔서 실패했습니다. 서강대지점 근처 다른 지점에 문의드리고 싶다고 말씀드렸더니 신수동과 대흥동에는 지점이 없고, 공덕동에 금융센터가 있다고 하십니다. 그쪽으로 연결을 시도하셨으나 여기도 통화 중이셔서 실패했습니다.

아무래도 전화상담이나 방문상담 모두 어려울 것 같아서 서강대점에 예약을 잡았습니다. 오늘은 시간이 없었고, 가장 빠른 날짜는 다음 월요일이었습니다. 인터넷에서는 넉넉하게 대출 실행 2주 전에 은행을 방문하면 좋다고 되어 있었습니다만 다음주 월요일이면 잔금일로부터 2주 미만으로 남게 되기 때문에 불안해지기 시작합니다.

그 전에 제가 할 수 있는 게 있는지 알아보기 시작했습니다.

버팀목 전세자금대출은 주택도시기금이 보증공사와 은행을 통해 제공하는 대출상품입니다. 대출 프로세스는 대략 아래와 같습니다.

문서뷰어

위 프로세스의 ‘자격 확인’ 단계 중 ‘자격심사’와 ‘자산심사’는 미리 할 수 있는 방법이 있는데, 바로 주택도시기금의 인터넷대출신청(기금e든든) 웹사이트입니다. 빠르게 신청해 줬습니다.

대출 금융기관과 담보 종류를 선택해야 했는데, 별 생각 없이 우리은행 서강대지점과 주택도시보증공사(HUG) 보증을 선택했습니다. 그러다 전세대출을 이미 받아 본 친구의 ‘HUG는 2주만에 보증이 안 나올 것 같다’는 말에 대출신청을 취소하고 한국주택금융공사(HF)로 다시 넣습니다.

신청한 즉시 부적격 판정이 나왔습니다. 제가 국민임대주택에 살고 있고, 이미 기금 수혜를 받고 있기 때문에 부적격하다는 것이었습니다. 낙성대로 이사 오기 전에는 가족과 함께 국민임대주택에 살고 있었던 것이 사실이지만 지금은 그렇지 않아서 의아했습니다. 여하튼 주소 변경 내역이 포함된 주민등록초본을 제출하여 해결했습니다.

얼마 지나지 않아 또 소명자료를 제출하라는 고지가 왔습니다. 저는 최근에 창업하여 개인사업자가 되었습니다. 사업장을 임차했다면 보증금도 재산으로 보므로 사업장의 임대차계약서를 제출하라고 합니다. 재산이 3.6억 정도를 넘으면 안 되는데, 그랬다면 제가 대출을 알아보고 있지는 않았을 겁니다. 바로 제출합니다.

플랜 B 준비

아직 2주가 간당간당하게 남아 있기 때문에 혹시 모를 상황을 대비해 카카오뱅크 거래제한을 푸려고 시도해 봅니다. 공과금 고지서를 제출했는데, 이사올 때 이름을 바꾸지 않은 게 마음에 걸립니다. 그래서 카카오뱅크에 전화문의를 해 보니 이름이 다르면 어렵겠다고 하십니다. 다른 해제 수단으로는 6개월 내에 납부한 세금 영수증이 있는데, 2월으로부터 6개월 전이면 작년 8월입니다. 7월에 납부한 종합소득세 영수증밖에 없습니다. 다행히도 종합소득세는 연 1회만 내는 세금이기 때문에 괜찮다고 하십니다. 바로 제출하고 거래제한이 풀리기를 기다립니다.

오늘 한 일

  • 확정일자 발급
  • 기금e든든에 대출 신청
  • (플랜 B) 카카오뱅크 거래제한 해제를 위해 공과금 고지서 종합소득세 납부증명 제출

2월 11일 토요일

13일이 되기 전까지는 할 수 있는 게 없는데, 13일은 잔금일로부터 12일밖에 안 남은 날입니다. 아무래도 부족할 것 같습니다. 저의 이런 불안감을 알고 계셨는지 어머니께서 저도 모르는 사이에 부동산에 전화드려 잔금일 연기에 대해 여쭤보셨던 것 같습니다. 임대인 분과 합의해 입주일을 2월 28일로 연기했습니다.

부동산을 다시 방문해야 했습니다. 2,000만원이 걸려 있는데 한시라도 빨리 가야 할 것 같아서 택시를 타고 갔습니다. 3일이 늘어난 게 얼마나 큰 영향을 줄지는 모르겠으나, 최후의 보루 카카오뱅크도 적어도 15일 전에는 대출 신청을 넣어야 한다고 하여 아주 약간의 위안을 얻었습니다.

또한 HF 보증은 저는 받을 수 없다는 사실을 깨달았습니다. 간단히 말해서 HUG는 건물의 신용을 보고, HF는 세입자의 소득을 보는데, 버팀목 대출이 승인받는 조건은 제 근로소득을 소득심사에서 제하는 것이고, 그렇게 하면 저는 거의 무소득자가 됩니다. 이렇게 되면 HF 보증으로는 제가 필요한 만큼의 대출을 받을 수 없습니다. 무소득자의 보증한도는 4,500만원에 그치기 때문입니다. 보증을 바꿀 수 있는지 은행에 가서 물어보기로 합니다.

이제 월요일이 되기 전까지 딱히 할 수 있는 게 없습니다. 2,000만원도 잃고 집에도 입주할 수 없는 상황이 생길까봐 너무 불안했지만, 아무것도 할 수 없다는 사실을 받아들이고 자러 가기로 합니다.

오늘 한 일

  • 입주일 연기 (2023년 2월 25일 → 2023년 2월 28일)
  • 새 계약서에 대한 확정일자 발급

2월 13일 월요일

일어나자마자 다음 순서로 은행들을 방문했습니다.

  • 신한은행 대흥역점
    • 개장시간에 맞춰 갔으나, 잔금일자 2월 28일은 어렵다고 합니다. 신한은행 거래내역이 없어서 곤란할 것 같다는 말도 어렴풋이 들은 것 같습니다.
  • 우리은행 서강대지점 (예약)
    • 여기도 2월 28일은 어렵다고 합니다. 근처 다른 지점이 있냐고 여쭤봤더니 신촌역 금융센터를 추천해 주셨습니다. 빠르게 출발합니다.

그 와중에 카카오뱅크 거래정지가 해제되었습니다. 카카오뱅크는 잔금일 15일 전까지만 신청이 가능하니, 오늘 하지 않으면 안 됩니다.

빠르게 대출한도를 알아봤으나 1억원까지만 나온다고 합니다. 나머지 1억원은 제 재산을 어떻게 영혼까지 다 끌어모으면 마련할 수도 있고 아닐 수도 있을 것 같은데, 그러면 등록금까지 낼 돈은 없어집니다. 게다가 금리가 비쌉니다. 버팀목으로의 대환 대출은 이사를 또 가지 않는 이상은 어렵습니다. 카카오 대출은 플랜 B로서 두기로 마음을 굳히지만, 오늘이 지나가면 사라지는 선택지라는 게 부담을 줍니다.

이후에 은행 몇 곳을 더 방문합니다.

  • 우리은행 신촌금융센터
    • 여기도 어렵다고 합니다. 서강대지점을 추천해 주십니다. 이미 다녀오는 길이라고 하니 연세대 서강대에서 안 돼서 이쪽으로 오시는 분들이 많은데 안타깝다고 하십니다.
  • 우리은행 공덕동효성금융센터
    • 번호표를 뽑고 조금 기다렸는데, 여기도 안 됩니다. 적어도 1달 전에는 오셔야 한다고 하십니다.
  • 신한은행 마포지점
    • 어렵다고 하십니다.

5연속 거절을 당하고 여의도, 망원, 시청을 돌면서 모든 은행을 방문해 보기로 합니다. 본가에 5개 은행에서 안 된다고 전화드렸더니 어머니께서도 알아봐주신다고 하십니다.

  • 우리은행 아현동지점 (전화문의)
    • 충정로 쪽으로 이동하면서 전화문의를 드렸는데, 어렵다고 하십니다.
  • 우리은행 망원역지점 (전화문의)
    • 안 된다고 합니다.
  • 강서구 쪽 은행 (본가에서 전화문의, 정확히 어디인지는 모르겠음)
    • 일정상 가능하지만, 매물이 너무 멀어서 관리하기 힘들기 때문에 거절당했습니다.
  • 우리은행 충정로금융센터 (전화문의)
    • 지점 직원분으로의 통화연결에 실패했습니다. 바쁘신 것 같아서 고객센터에 이후 전화해 달라고 메모를 남겨 달라고 했는데, 공덕에서 우리은행 서소문지점으로 택시를 타고 가던 도중 지점으로부터 힘들겠다는 전화를 받았습니다.
  • 우리은행 서소문지점 (전화문의)
    • 충정로와 마찬가지입니다.

아침 8시 40분부터 신한은행에 가서 대기를 했는데, 바쁘게 뛰어다니다 정신을 차리고 보니 벌써 오후 1시입니다. 전화를 몇 통을 돌렸는지 모르겠습니다. 우리은행 고객센터 통화연결음이 정말 듣기 싫어지고 매번 앞에 있는 50명의 고객들을 기다리게 만드는 로드 밸런싱이 너무나도 야속해집니다.

엔드게임

몇 시간 동안 외판원 순회를 하고 있자니 희망이 없는 것 같습니다. 슬슬 선택해야 할 시간이 다가옵니다. 당장 두 가지 정도의 방법이 떠오릅니다.

  • a) 잔금을 어떻게든 치루고 이후에 버팀목 전세자금 대출을 알아본다(3개월 내).
    버팀목 대출은 잔금일 이후 3개월까지도 신청이 가능합니다. 단, (보증금) – (제 전재산)을 대체 어떻게 구하느냐는 이제부터 생각해 봐야 합니다. 승인이 되면 최고 2.4%의 금리로 살 수 있습니다.
    지인들에게 손을 빌리기는 너무나도 미안하고, 제 나이가 그렇게 많지 않은 걸 감안하면 몇천만원을 흔쾌히 빌려줄 수 있는 사람도 없을 것 같습니다. 급기야 대부업체를 검색해보기까지 이릅니다(무서워서 문의조차 안 해보기는 했습니다). 사람이 궁지에 몰리면 이렇게까지 될 수 있다는 걸 느낍니다.
  • b) 카카오뱅크 대출을 1억원이라도 받고 나머지 잔금을 어떻게든 마련한다.
    이 옵션은 이전 옵션보다는 난이도가 약간 낮지만, 금리가 두 배 정도 뜁니다. 그리고 여전히 몇천만원을 어떻게 구할지를 생각해 봐야 합니다.
    이 경우의 몇천만원은 그래도 열심히 일하면 1년 안에 모을 수 있는 정도의 돈인 것 같아 보이기는 합니다. 하지만 빠르게 결정해야 합니다. 오늘이 지나면 사라지는 옵션이니까요.

갈등합니다. 어떤 선택지든 인생이 정말 정말 어려워질 것 같습니다.

그러다가 다른 해결 방법이 떠오릅니다.

  • c) 임대인 분과 현재 세입자 분께 위약금이라도 지불하고 입주일자를 한 번 더 미룬다.
    2억 원에서 제가 이미 입금한 계약금 2,000만 원을 제하면 1억 8,000만 원입니다. 1억 8,000만 원에 대한 법정 최고 이율의 월 이자는 300만원입니다. 작은 돈은 아니지만, 무려 2,000만 원을 잃을 수 있는 상황에서 이 정도의 위약금을 지불하고 모든 프로세스를 다시 시작할 수만 있다면 흔쾌히 지불할 의향이 있습니다.

이미 입주일자를 미뤘다는 점에서 임대인 분께 너무나도 실례되는 방법이고, 이 방법도 나름의 불확실성은 가지고 있지만, 양해해 주신다면 저에게는 최선의 해결 방법입니다.

서강대점으로 돌아오다

원래 저는 문제 상황에서 다른 사람들의 도움을 잘 빌리지 않는 성격이지만 지금은 그런 걸 가릴 때가 아닙니다. 일단 입주일자를 언제로 맞추면 대출이 실행될 수 있을지 알아보기 위해 우리은행 서강대지점으로 돌아왔습니다.

대출 상담 직원 분과 긴 이야기를 나눴습니다. 상황을 설명해 드렸더니 3월 10일 이후 입주할 경우에는 괜찮을 것이라고 하십니다. 넉넉잡아 3월 17일로 잠정적으로 정하고, 필요한 서류 목록 등의 안내를 받았습니다. 이 시점에서 제가 이미 신청했던 기금e든든은 취소되었습니다.

정말 일자를 미룰 수 있을지는 불확실했는데, 직원 분께서 제가 불안해하고 있는 걸 눈치채셨는지 혹시라도 미루는 데 실패하더라도 최대한 도와주시겠다고, 사람 일이 안 될 것 같아도 막상 해 보면 되는 것들도 있더라고 말씀해 주셨습니다. 28일에 실행되는 게 가능한지를 떠나서 정말 힘이 되는 한 마디였습니다. 이 글을 빌어 감사를 전하고 싶습니다.

부동산에 위약금이라도 내고 입주일자를 미루고 싶다고 말씀드렸습니다. 임대인께 여쭤보신다고 합니다.

2시가 되어서야 밥을 먹을 수 있었습니다. 무슨 일이 있을지 모르니 학교 편의점에서 간단히 끼니를 때웁니다. 학교에서 밥 먹는 건 오랜만입니다.

여행에 가도 이 정도는 안 걸을 것

돌파구

부동산에서 연락이 왔습니다. 임대인께서는 크게 개의치 않으나, 현재 임차인께서 보증금을 돌려받아야 새 집에 입주할 수 있어서 이 점이 걱정되신다고 합니다.

초조하게 기다립니다.

다행히도 현재 세입자께서 제 상황을 이해해 주시고 대출이자를 제가 대신 내는 것을 조건으로 승낙해 주셨습니다.

면목이 없었습니다. 안도의 한숨을 쉬었습니다.

당일 4시 20분에 계약서를 다시 한 번 수정하기로 합니다.

다시 주어진 한 달

부동산에 도착해서 임대인 분과 현재 임차인 분과의 삼자대면을 했습니다. 공인중개사께서 제가 너무 죄송해하는 걸 보시고 제 잘못이 아니라고 안심시켜 주셨습니다. 사실 건물 때문에 대출이 나오지 않은 이상 꼼꼼히 알아보지 않은 건 제 귀책이고 여전히 제 잘못이라고 생각합니다.

입주일자를 3월 17일로 미루기로 하고, 전례를 찾아보기 힘든 계약 변경 합의를 맺었습니다. 골자는 이러했습니다.

  • 계약금을 5,000만 원으로 올립니다.
  • 월세를 70만 원으로 하여 제가 2월 17일부터 3월 16일까지 임차합니다.
  • 3월 19일까지 전세보증급 완납에 실패할 경우, 이후 3개월 간은 월세를 120만 원으로 하여 일할 지급합니다.
  • 6월 19일까지 전세보증금 완납에 실패할 경우, 퇴거합니다.

여기서 ’70만 원’이 전 세입자 분께서 대출 이자로 합의하신 금액입니다. 임대인 분의 입장에서 봐도 거의 무상 임차를 제공해 주신 것이나 다름없습니다. 정말 감사하지 않을 수 없는 일입니다.

그래도 현 세입자 분께 보증금을 돌려드려야 입주를 하실 수 있기 때문에 계약금이 올라갔습니다. 이전에 입금한 2,000만 원에 더해 추가로 3,000만 원을 입금합니다. 계약금 5,000만 원의 엄청난 계약이 되었습니다.

계약서를 다시 작성하고, 확정일자를 다시 받았습니다. 오늘부터 잔금일까지의 카운터는 32일로 리셋됩니다. 은행에 전화해서 연기 사실을 말씀드렸더니 정말 다행이라며, 하지만 1개월 이전까지는 또 프로세스를 진행하기 어렵기 때문에 2월 20일에 재방문해 달라고 해 주셨습니다.

2월 20일에 은행 예약을 잡았습니다. 오늘은 편하게 잘 수 있을 것만 같습니다.

오늘 한 일

  • 은행 십수 곳 방문
  • 입주일 연기 (2023년 2월 25일 → 2023년 3월 17일)
  • 계약금 인상분 입금 (3,000만 원)
  • 새 계약서에 대한 확정일자 발급

2월 20일 월요일

각종 서류를 챙겨서 아침에 은행에 방문했습니다. 은행에 가서도 엄청나게 많은 서류를 작성하고 서명했습니다. 의외로 20분 가량으로 끝났습니다. 기금e든든 신청을 따로 할 필요 없이 은행에서도 처음부터 신청이 가능한 것 같습니다.

건물도 문제 없고, 제 신용도도 괜찮아서 별 일 없으면 3월 17일에 대출이 실행될 것이라고 합니다. 다행입니다. 이율은 제가 생각했던 것보다 훨씬 낮은 1.2%였습니다. 한 달에 15만 원의 이자만 내면 되는데, 전에 살던 곳의 월세가 45만 원이었던 걸 생각해 보면 버팀목 대출은 정말 감사한 제도라고 느낍니다.

새로 작성한 합의서 상 2월 19일부터 이곳의 세입자는 저입니다. 새 집을 처음 들어가볼 수 있었습니다. 계약 직후에 ‘집이 좁진 않을까’ 걱정했던 것과는 다르게, 다행히도 생각보다 많이 넓었습니다. 다만 입주 청소가 필요해 보였고, 책상도 새로 사야 할 것 같았습니다.

안타깝게도 줄자를 새로 가져오지는 못해서 도어락 비밀번호만 바꾸고 낙성대로 돌아옵니다.

오늘 한 일

  • 은행에서 대출 신청
  • 새 집 도어락 비밀번호 변경

2월 22일 수요일

대출 신청 적격 판정이 됐다는 알림이 왔습니다. 사전 자산심사를 통과했다는 뜻입니다.

이제 물리적인 고생길만 남았습니다. 새 집을 청소하고, 낙성대에서 새 집으로 짐을 옮기기만 하면 됩니다.

이제 걱정해야 하는 건 이곳을 비우는 것입니다. 하루종일 이삿짐을 쌌습니다. 짐을 빠르게 옮기기 위해 25일 아침에 입주청소업체를 예약합니다.

2월 26일에는 이사를 마쳤습니다. 1년 반 만에 그렇게 정들었던 낙성대와도 이제는 작별의 시간이었습니다.


3월 17일 금요일

대출이 실행되었다는 문자를 받았습니다. 힘들었던 여정의 끝입니다. 이제는 돈 걱정 없이 이곳에서 살면서 행복하게 학교를 다닐 수 있을 것 같습니다.


마치며

지난달에 했던 마음고생은 여기에 형언할 수 없을 정도인 것 같습니다. 뼈가 깎이는 일들을 겪으면서 정말 많은 걸 느끼게 되었습니다.

카카오뱅크는 ‘최저‘ 4.4%의 금리에 ‘최대’ 2.22억원을 대출해 줍니다. 하지만 그 금리와 한도가 나한테 적용되는 것은 아닙니다. 계좌정지가 풀리기까지는 그렇게 판단하지 말았어야 했습니다.

버팀목 전세자금은 퇴직자의 경우 근로소득을 제합니다. 문의해야 알 수 있는 사항이었습니다. 문의해보지 않고 버팀목이 안 될 것이라고 판단하지 말았어야 했습니다.

인터넷 블로그들은 전세자금 대출은 2주 전에 신청하라고 합니다. 하지만 그건 학기가 시작되는 시기, 학교 근처 매물, 그것도 서울에서의 상황과는 거리가 멉니다. 최소한 한 달 전에는 은행에 문의했어야 했습니다.

이번 일을 겪으면서 만사를 안일하게 생각하지 말아야 된다는 교훈을 얻었습니다. 앞으로 제가 비슷한 일을 겪는 것을 예방하기 위해, 그리고 혹시 모를 다른 분들의 고생을 막기 위해 글으로 남겨 두려 합니다.

아직은 조금 더 정리가 필요하지만 지금은 새 집에서 나름 행복하게 살고 있습니다

전세계약 체크리스트 (23/3/20 추가)

  • 전세사기 예방
    • HUG 전세사기예방센터 꼼꼼히 읽기
      • 등기부등본 확인 – ‘을구’에 설정된 근저당권이 과하지 않은가?
      • 시세 확인 – 집값이 보증금보다 작거나 비슷하지는 않은가?
      • 임대인 확인 – 계약서에 적힌 임대인과 같은 사람이 와서 계약하려고 하는가? 다른 사람이 왔다면, 위임장이 있고 위임장에 찍힌 도장을 증명할 인감증명서가 있는가?
      • 이중계약 확인 – 이전 세입자가 아직 살고 있는가?
  • 버팀목 전세자금대출
    • 넉넉하게 1달~3주 전에 은행에 방문하여 상담하는 것을 추천
      • 1달보다 더 전이라면 아직 신청이 불가능할 수 있음
    • 대출 조건을 만족해야 함, 아래는 2023년 3월 기준 그 중 일부
      • 무주택자 세대주, 또는 실행일로부터 1개월 이내 세대주 예정자
      • 주택도시기금대출, 은행재원 전세자금대출 및 주택담보대출 미이용자
      • 소득 ≤ 5,000만 원, 자산 ≤ 3억 6,100만 원
        • 소득금액증명을 발급해 소득 확인 가능
        • 현재 무직자라면 근로소득을 0으로 봄
        • 기타소득의 경우 증빙을 제출해야 할 수 있음
      • 전용면적 ≤ 85㎡, 보증금 ≤ 3억 원
    • 대출 한도는 2억 원이나, 만 25세 미만일 경우 1.5억 원 이하임
      • 만 25세 미만인 경우 우대금리 0.3%p
    • 자세한 내용은 은행과 상담할 것
      • 우리 1599-0800, 국민 1599-1771, 기업 1566-2566, 농협 1588-2100, 신한 1599-8000
  • 카카오뱅크 전세자금대출
    • 1달~15일 전 안에 신청해야 함
    • 한도와 금리는 카카오뱅크 앱에서 실제로 신청서를 작성하여 확인할 것
      • 메인 화면에 나오는 것은 ‘최저’ 금리와 ‘최고’ 한도로 본인에게 적용되는 것이 아닐 수도 있음
    • 대출 조건을 만족해야 함
    • 자세한 내용은 은행과 상담할 것
      • 1599-3333

새로운 시작의 앞에서

2022년 회고

3년의 휴학 기간 동안 산업기능요원으로 복무했습니다. 이제 학교에 있었던 시간보다 회사에 있었던 시간이 더 길어졌습니다.

코로나는 확실히 무서웠고 그 광풍을 저도 피해갈 수 없었습니다. 그러나 이 글을 쓰고 있는 지금은 그 무서움이 꽤 농담이 된 것 같습니다. 18학번으로 입학했지만 비대면 수업을 받는 시대는 거치지 못하고 넘어가버렸습니다.

회사를 차렸습니다

4년간 만들어 오고 있는 solved.ac는 제가 가장 즐겁게 엔지니어링하고 있는 프로젝트입니다. 그래서 다시 학생이 되는 지금이 아니면 언제 해 보겠느냐는 생각으로 회사를 차렸습니다.

복학과 졸업 이후에도 다니던 회사를 계속 다닐 수 있는 옵션은 있었습니다. 급여도 적당히 만족스러웠고, 업무 프레셔도 높지 않았고 사람들도 좋아서 고민이 정말 많이 되었습니다. 하지만 제 프로그래밍-디자인-기획의 복합 역량을 제일 잘 발휘할 수 있는 프로젝트이며, 그렇게 많지는 않지만 이미 10만 명 가까운 유저가 사용 중이라는 것도 결정하는 데에 도움을 줬습니다.

여태까지 저는 제가 하고 싶은 일을 하면서 살았을 때 제일 즐겁게 살았습니다. 그래서 졸업까지 남은 2년을 지금 저에게 있어서 제일 즐거운 일을 오래오래 할 수 있을지 아닐지에 대한 테스트베드로 삼아보려고 합니다. 솔브드는 어디로 가게 될까요?

복무만료

2월에 훈련소를 다녀왔고, 5월에 복무만료가 되었습니다. 이제 예비군입니다.

코로나 시대의 훈련소는 정말 재밌는 곳입니다. 훈련을 3주간 하는데, 그마저도 반 정도 기간은 단체 격리라 야외 훈련은 마지막 1주에 몰아서 합니다. 그런데 조교들까지 단체 확진돼서 우리는 사격훈련과 수류탄 훈련 외의 훈련을 받아보지 못했습니다.

그리고 저도 훈련소 안에서 코로나에 걸려서 논산에서 어디 경기도로 끌려가서 개별 격리 당하고, 그곳에서 수료까지 했습니다.

이외에는 인터넷 편지 받은 거를 제외하고는 모든 군대 이야기는 재미없으니 하지 않겠습니다. 편지 보내주셔서 감사합니다!

성과 자랑

제가 2019년에 정한 PS 인생 목표는 이랬습니다.

올해는 이 중 하나를 더 이뤘습니다. 바로 구글 코드잼입니다!

구글 코드잼 성적은 2019년 2라운드(2,443rd), 2020년 2라운드(1,427th), 2021년 2라운드(1,328th)였습니다. 특히 2021년에는 배열 인덱스를 잘못 잡아서 히든 테스트케이스를 놓치고 진출을 실패했던지라 너무너무 아까웠는데 다행히도 작년의 실수를 올해 만회할 수 있었습니다.

SCPC 2022 Final을 통과했다는 건 무슨 말일까요?

SCPC는 올해도 무수상입니다. 4년 연속인데 언제 상을 타볼 수 있을지 모르겠습니다. 사실 2019년이 가장 가능성 있었을 것 같은데요…

코드포스는 열심히 안 치다가 다시 쳤더니 퍼플로 내려갔습니다. 레드는 너무 요원해 보입니다. 적의환향 어디 갔냐고….

갑자기 분위기 해커톤

즉흥적으로 팀을 꾸려 나간 Junction Asia 2022에서 2등을 했습니다. 중고등학생 때는 해커톤을 많이 나갔는데, 대학교에 와서는 알고리즘 문제해결 관련 필드에 있느라 해커톤은 잘 안 나갔습니다. 해커톤을 마지막으로 나갔던 게 거의 2017년?쯤이었던 것 같으니 5년만입니다.

부산에서 열리는 온사이트 해커톤이었습니다. 제가 나갔던 어떤 해커톤보다 큰 규모의 해커톤이었습니다. 호텔도 지원해 주고, 피자도 줍니다.

금요일부터 일요일까지의 대회여서 저는 개인사유로 휴가 쓰고 회사 몰래 나왔습니다.

4명 팀인데 프론트엔드 엔지니어가 4명, 백엔드 엔지니어 3명이었던지라 개발은 다른 분들께 맡길 수 있겠다고 생각해서 저는 개발은 많이 안 하고(위에 보이는 노트북에 스티커 붙이는 프론트엔드만 개발했습니다), 대신 프레젠테이션을 만들고 디자인에 공을 들였습니다. 여기서 Figma를 처음 써 봤는데 정말 세상에 이렇게 편한 디자인 툴이 있을 수가 없다는 생각이 들었습니다. 이후 모든 프레젠테이션을 Figma로 만들고 있습니다.

다년간의 해커톤 경험으로 빠르게 작업하지 않으면 잠을 설치면서 개발하고 디자인할 걸 알고 있었기 때문에 디자인은 첫 날에 거의 끝내버렸고, 둘째/셋째 날은 프로젝트가 어떻게 시장에서 먹힐지를 어필할지 열심히 생각하면서 프레젠테이션을 깎았던 것 같습니다. 해보니까 빠르게 작업하지 않으면 잠을 설치는 게 아니고 그냥 예전의 저는 작업을 빠르게 하지 못했던 거고 빠르게 해도 잠은 어찌됐든 설치는 거였습니다.

블록체인이라는 분야에 대한 막연한 두려움과 이것저것 때문에 블록체인 트랙으로 가게 될 거라고는 상상도 못했는데, 블록체인을 무서워하지 말고 그냥 한번 데이터베이스처럼 써 보라는 Chainapsis 발표를 듣고 설득당했던 것 같습니다. 무엇보다 Ignite CLI가 너무 사용하기 쉽게 되어 있었습니다.

즐겜하러 나왔는데 트랙 2등을 하는 영광을 누렸습니다. 상금은 아웃백에 썼어요. 감사합니다!

오랜만에 해커톤을 나가 보니 제일 힘든 건 집에 돌아와서 바로 다음날 출근하는 거였던 것 같습니다.

소프트웨어 개발

솔브드

올해는 크고 작은 다른 일들이 많아서 솔브드에 쏟을 수 있는 시간이 많지 않았습니다. 길라잡이는 시간을 많이 쏟아야 하는 컨텐츠이기 때문에 본업이 있는 상황에서는 만들기 어려웠던 것 같습니다. 대신 내실을 다지는 개발을 위주로 했습니다.

  • SEO에 조금 더 신경을 썼습니다. 오픈 그래프 스펙을 도입하고, 자동 트윗을 게시할 때 그래픽을 만들어 주도록 했습니다.
    • 다만 자동 트윗 이미지 생성은 최적화할 부분이 많아 보입니다. Puppeteer를 써 봤다 정도에 의미를 부여할 수 있을 것 같습니다…
  • 솔브드의 UI 코드를 정리해 @solved-ac/ui-react를 만들었습니다. (후기)
    • 이 과정에서 styled-components를 걷어내고 emotion으로 스택을 바꿨습니다.
  • 아직 완벽하지는 않지만, 영어로 i18n을 했습니다.
  • 문제 검색 쿼리를 최적화했습니다. DBA가 된 기분이었습니다.
    • 작년까지는 8천 문제 푼 사람들 5명의 교집합을 구하려고 하면 서버가 터졌습니다…
  • 길라잡이 에디터의 기반을 아주 약간 다졌습니다.

내년 목표는 이렇습니다.

  • 길라잡이 에디터를 사용할 수 있는 상태까지 발전시키기
  • 가능하다면 백엔드에서 Sequelize 걷어내기. Sequelize를 오랫동안 사용해 본 결과 이건 ORM이 아닌 것 같습니다. 앞으로는 Prisma를 쓰든 EdgeDB를 쓰든 할 것입니다.
  • 백엔드 내실 다지기. 사용자가 많아지면서 웹 서버가 가끔 죽는데, 지금은 Redis도 SQS도 없습니다. 더 늦기 전에 추가해야 합니다.

적어놓고 보니 한 게 많이 없는 것 같습니다. 훈련소도 다녀왔고, 특히 재택에서 출근 근무로 바뀐 탓에 출퇴근 시간 2시간이 사라져 버려서 그런 것 같네요… 퇴근하고 나면 정말 피곤합니다.

이외에도

올해도 정보올림피아드 대회 시스템 프론트엔드 유지보수 작업을 했습니다.

한국정보과학교육연합회의 단계별 프로그래밍 교육 프로그램 BIKO를 만드는 데에 참여했습니다.

평소 팬이었던 ARForest님의 컴필레이션 앨범 The Unattended와 3집 Deep Inside 앨범 사이트를 작업했습니다. Framer Motion으로 애니메이션 작업을 했습니다. WebGL이 배우고 싶어졌습니다.

대회 운영과 출제

NYPC

올해도 시스템 개발과 출제를 맡았습니다. 참가자인 척 끼어 있는 출제진을 찾아보세요!

저는 본선 1519부문 5번 〈지름길〉 문제를 냈습니다. 최단 거리 트리를 생각하다가 두 노드의 최단 거리 트리를 합친 걸 최소화하는 문제는 어떨까 하는 생각에 발제했는데, 어쩌다 보니 가장 어려운 문제로 출제되었습니다. 여러 비하인드가 있는데 이야기 가능한 범위가 어디까지인지는 모르겠습니다.

위의 링크를 들어가 보고 아셨을 수도 있겠지만 해설 사이트도 새로 작업했습니다. 원래도 GitHub에 올라와 있는 오픈 소스 프로젝트여서 GitHub의 좋은 점들을 활용하고 싶었고, GitHub Actions와 Next.js SSG를 사용해 MDX로 작성된 문제 파일을 수정하면 자동 배포가 되도록 구성했습니다. 기존에는 Jekyll과 Kramdown 엔진을 사용해 수식을 작성했는데, 인라인 수식을 $$ ... $$로 작성해야 하는 아주 끔찍한 문법을 쓰고 있었기 때문에 프로젝트를 그냥 처음부터 다시 만들었습니다.

NYPC 출제진으로 일하는 것도 정말 즐거운 경험이었습니다. 저는 이제 퇴사했지만 혹시 출제에 관심이 있으시다면 넥슨 입사 어떠신가요? 의외로 게임 클라이언트뿐만 아니라 웹 프론트엔드/백엔드, 블록체인, MLOps 등 정말 여러 분야에서 채용을 진행하고 있습니다. 보충역 산업기능요원을 알아보고 계신다면 제가 다녔던 엔진스튜디오도 좋은 옵션이라고 생각합니다. 엔진 혹은 넥슨에 레퍼럴이 필요하시면 제 메일로 문의 부탁드립니다.

ICPC 서울 리저널

휴학 중이라 ICPC에 나갈 수 없었는데, 올해는 온사이트로 열리게 되어서 스태프로 일했습니다. 본선에 오신 분이라면 저를 만났을지도 모르겠습니다. 제가 풍선을 달아 드렸을 수도 있구요.

사실 작년에도 참관하기는 했습니다. 스코어보드 공개할 때 제가 잠깐잠깐 나옵니다… 내년부터는 다시 참가자로 대회를 나가 보려고 합니다.

저는 시간에 여백이 부족해서 따로 글을 쓰지는 못했지만 같이 운영해 주신 스탭 분들의 블로그 후기들을 읽어 보시면 스탭으로서의 현장 경험을 조금이나마 느낄 수 있으실 것 같습니다.

UCPC

작년에는 학교에서 팀을 꾸려서 대회에 나왔지만 올해는 다시 전대프연으로 돌아와서 대회 운영을 도왔습니다.

UCPC는 출제로는 연이 별로 없구요, 대신 디자인과 운영에 도움을 드렸습니다. 이번 로고 모양 폼보드 명찰과 폼보드, 티셔츠 등이 제 작품입니다. 개인적으로는 꽤 마음에 들었던 디자인들입니다.

대회 당일에 정말 많이 뛰어다니면서 땀도 많이 흘리고 힘들었던 기억이 있습니다. 200명을 수용할 수 있는 합리적인 가격의 대관처는 정말로 찾기 어렵습니다. 그리고 협소한 대관처는 꽤나 덥습니다.. 이후에 킨텍스에서 진행된 ICPC에서 일하면서 정말 부러웠습니다.

SPC / 서강 프로그래밍 대회

제가 항상 제일 쉬운 문제와 제일 어려운 문제를 내는 대회입니다. 올해에도 어김없이 적당히 쉬운 문제 하나제일 어려운 문제 하나를 냈습니다. 어려운 문제 쪽은 개인적으로 잘 냈다고 생각하지만 쉬운 문제 쪽은 머리가 꼬일 수 있는 지문 + 약간의 케이스 워크 때문에 1~2학년 디비전의 두 번째 문제로 내기에는 약간 부적절했던 것 같다는 소회입니다. 이 자리를 빌어 사과드립니다… 하지만 졸업하실 때는 이 정도는 푸셔야 해요.

언젠가부터 소프트웨어중심대학이 잘려서 학교의 지원을 받기 힘들게 되었고, 학교 지원만으로 충분히 대회를 열 수 있었던 예전과는 다르게 후원도 알아봐야 하고 고생이 많으셨을 텐데 열정 넘치는 멋진 분들께서 운영해 주셔서 대회가 성료될 수 있었던 것 같습니다. 참 다행입니다. 항상 감사드립니다.

빅파이 아직은 안 물립니다. 감사합니다.

이외에도

2023년 1월에 열리는 보드게임컵을 준비 중입니다. 온라인 대회지만 다른 오프라인 대회만큼 고생하고 있는 것 같습니다. 참가해 주시면 기쁠 거예요!

컨퍼런스

고려대학교 중앙 컴퓨터 동아리 KUCC에서 《코딩 테스트 및 알고리즘 문제해결 공부 방법》을 발표했습니다. 코딩 테스트가 개발자 취업 과정에서 어떤 단계에 있는지부터 설명하고, 무슨 언어를 고르면 좋을지, 공부 시작은 어떻게 하면 좋을지, 문제 하나를 해결할 때 시간 분배는 어떻게 하면 좋을지, 그리고 합격하기 전까지 어떻게 공부하면 좋을지 설명했습니다. 저 개인적으로는 코딩 테스트를 피험자로 본 적은 없지만 넥슨 엔진스튜디오 면접 TF에서 일한 경험과 프로그래밍 대회를 준비하던 경험을 녹여 예비 개발자 분들께 도움이 될 만한 내용을 꽉꽉 눌러 담았습니다. 이 발표 자료는 코딩 테스트를 준비하는 분들께 제가 강력히 추천하는 자료이기도 합니다.

프로그래머스의 초청으로 프로그래머스 컨퍼런스 1st에서 《모두의 성장을 위한 서비스 만들기: solved.ac 개발 경험을 토대로》를 소개했습니다. solved.ac를 만들어가면서 했던 — 기여 시스템 설계, 가이드라인 설정, AC 레이팅 설계 — 등에 관련된 길었던, 어찌 보면 계속되고 있는 고민들에 대한 답을 냈던 경험을 정리해 보고 이를 통해 커뮤니티 운영자로서 배운 점들을 공유했습니다. 발표를 준비하면서 커뮤니티의 공감을 얻으려면 확고한 방향을 갖고 기획해나가야 한다는 점을 다시 한 번 되새길 수 있었습니다.

한국항공대학교 학술제에서 《새내기 코딩 마법사를 위한 2차 전직 준비하기》를 주제로 이제 막 학교에 들어온 학생들에게 앞으로의 ‘전직 루트’를 소개했습니다. 학교에서 알려주는 것과 회사에서 하게 될 것들은 다르기 때문에, 회사에서 필요로 하는 역량들에 대해 설명하고, 이를 ‘전직 퀘스트’에 빗대어 어떤 퀘스트들이 있고 어떻게 준비하면 좋은지 발표했습니다. 앞서 고려대학교 KUCC에 했던 코딩 테스트 관련 내용도 간단히 소개했습니다.

지식을 공유하는 건 즐거운 일이라고 생각하지만 사실 저는 제 말의 무게에 힘이 실리는 걸 별로 좋아하지는 않습니다. 제가 알고 있는 내용이 틀릴 수도 있고, 모두에게 적용할 수 있는 것도 아닐 수 있기 때문입니다. 그래서 발표를 부탁받으면 준비하는 데 시간을 많이 쏟게 되는 것 같습니다. 제가 공유한 지식이 누군가에게는 긍정적인 도움이 되었으면 좋겠습니다. 지금 다니고 있는 학교에서도 뭔가 발표해 볼 기회가 있으면 좋겠다 싶은데 서강대는 컨퍼런스가 예전엔 Release에서 주최하는 것이 있었다가 요즘은 안 열리는 것 같아 아쉽네요….

초청해 주신 KUCC, 프로그래머스, 그리고 한국항공대학교 소프트웨어학과에 다시 한 번 감사드립니다.

디자인

solved.ac의 복잡한 페이지 구조를 어느 정도 정리하는 작업을 했습니다.

아이덴티티를 정립하는 것을 목표로 전대프연 UCPC 디자인을 했습니다. 웬만하면 앞으로도 이 로고를 유지하려고 합니다.

서강대학교 프로그래밍 대회 디자인도 작업했습니다.

여기 플래티넘 5 주변 이펙트를 만들었습니다.

쓸데없이 멋진 시즌 종료 보상도 만들었습니다.

이외에도 이것저것 자잘한 디자인을 했는데, 모아보고 나니 상당히 적은 양입니다. 올해는 정말 바빴나 봅니다.

일상 이야기

자취 생활 끝

2022년 8월 28일부터의 낙성대 자취 생활은 2023년 2월 28일을 끝으로 끝나게 됩니다. 회사 출근을 위해서 계약했던 집인데, 학교가 마포~신촌 근처라 낙성대에서 통학하기에는 참 애매해졌습니다.

자취 생활은 생각보다 어렵지는 않았습니다. 설거지나 청소는 할 만 했구요, 제일 어려웠던 건 세면대에 걸린 머리카락 빼내는 거였던 것 같습니다. 그리고 새롭게 알게 된 지식은 치킨스톡은 상온에서 곰팡이가 필 수 있다는 사실입니다.

1년 반 동안 살면서 추억을 많이 쌓았습니다. 가령, 이탈리아 방식의 카르보나라를 할 수 있게 됐습니다.

요리도 해 보고, 회사 동료들을 데려와서 보드게임도 하고, 링고 가서 치맥 하고 했던 즐거운 기억들이 생각납니다. 낙성대역 5번 출구에서 언덕을 꽤 올라가야 나오는 집이지만 복학하면 그리워질 것 같습니다.

낙성대 주민을 위해 자취 생활 하면서 자주 갔던/시켜먹었던 가게 목록을 정리해 보겠습니다. 리뷰는 믿지 마세요. 제가 맛을 보장합니다 👍

  • 백채김치찌개 낙성대점(봉천로 590, 낙성대 4출): 깔끔하고 맛있는 김치찌개입니다. 배달보다는 식당에 가서 먹는 게 이득입니다. 다만 식당에 가서 먹으려면 두 명 이상이서 가야 된다는 점이 흠이라면 흠이네요… 보달라에 치즈계란말이로 변경해서 드세요.
  • 쟝 블랑제리(낙성대역길 8, 낙성대 4출): 이 동네에는 왜 체인 빵집이 없나 고민했는데, 이곳 때문인 것 같습니다.
  • 오월의 김밥(봉천로 605, 낙성대 1출): 아침-점심에만 하는 유명한 김밥집입니다. 가게에 가서 주문하면 줄을 오래 서야 될 수도 있어서, 꼭 전화로 예약하고 가지러 가야 합니다.
  • 피자네버슬립스 샤로수길점(봉천로 534 2층, 설입과 낙성대 중간쯤): 페퍼로니 피자는 꼭 드셔보세요. 라지는 엄청나게 크니까 주의하세요… 하프앤하프도 됩니다.
  • 옷살(관악로 164 B1층, 설입 2출): 근본 인도 음식점입니다. 매운맛 단계와 고기 종류를 커스텀할 수 있고, 양도 꽤 됩니다. 카레 여기만큼 하는 곳은 아직 못 봤습니다. 배달도 해 주는데 가끔 맥도날드보다 빨리 옵니다.
  • 삼백돈(남부순환로230길 48, 설입 1출): 삼백돈 체인의 본점입니다. 개인적으로는 돈카츠 진짜 잘 합니다. 정돈에 약간 못 미치는 수준? 배달도 해 줍니다. 이수점이랑 여기서 둘 다 배달이 되는데 여기가 좀 더 낫습니다.
  • 링고(봉천로 518-4 2층, 설입과 낙성대 중간쯤): 알고리즘 하는 사람들한테는 이미 well-known인 호프집입니다. 세계의 수많은 맥주들을 만나볼 수 있습니다. 이런 종류의 맥주가 있었나 싶은 맥주들은 다 여기서 처음 만나봤던 것 같습니다. 제가 스타우트를 제일 좋아한다는 사실도 처음 알았구요.
    근데 여기는 치킨도 진짜 잘합니다. 동네에서 제일 잘하는 것 같아요. 가격대가 좀 있지만, 치킨과 플랑베, 그리고 기네스 칵테일은 꼭 한 번 가서 드셔보시는 걸 추천합니다!

배달 맛집도 정리해 봅니다.

본가에서 통학할지 신촌에 집을 새로 얻을지는 고민 중입니다. 제가 움직이는 데 쓰는 시간을 상당히 아까워해서 통학은 별로 하고 싶지 않을 것 같기도 합니다.

한별이 광고

신분당선 판교역 강남 방면에 걸린 한별이 광고를 보신 적이 있나요? 올해는 생일선물로 무려 지하철 광고를 선물받았습니다! 정말 예쁜 한별이 감사합니다 매일 보면서 퇴근했어요

여러가지 일들

제주도로 휴가를 다녀왔습니다. 9.81파크에서 카트도 타고, 카페 그루브에서 멋진 일몰을 보고, 정말 멋진 경험이었어요.

마작을 배웠습니다. 마장에서 스안커도 해 봤습니다. 쯔모!

아직은 다른 사람 패 안 보고 내 패만 보고 칩니다. 그러니까 레이팅이 안 오르죠..

마치며

다사다난했던 해는 아니었지만, 큰 결정들을 했고 큰 변화를 앞두고 있는 해였습니다. 안정적이던 회사를 나오고 회사를 차렸습니다. 자취 생활도 끝나갑니다. 내년에는 어디로 흘러가게 될까요? 어떻게 되든 할 수 있는 한의 최선을 다하고 싶습니다.

월파 후기는 아직도 쓰지 못했습니다. 빠르게 정리해서 올려 보고 싶은데, 시간이 많이 없었던 것 같습니다. 기억이 사라지기 전에 정리해야겠습니다.

올해도 수고하셨습니다. 내년에도 힘내 봅시다. 새해 복 많이 받으세요! 🎍

회사가 되었습니다

알고리즘 문제해결 분야는 정말 매력적입니다. 어려운 문제를 해결했을 때의 뿌듯함과 차근차근 실력을 쌓아가면서 느낄 수 있는 성취감을 더 많은 분들께서 느껴 봤으면 좋겠다는 생각을 가지고 있습니다. 그래서 solved.ac를 만들어나가는 것은 제가 가장 즐거워하는 일이면서 제가 정말 잘 할 수 있는 일입니다. 이 일에 집중하면서 제 역량을 온전히 발휘하기 위해 넥슨 엔진스튜디오에서 퇴사하고 창업에 나서기로 결심했습니다.

토이 프로젝트로 만들어 오던 solved.ac를 사업으로서 영위하기 위해 2022년 12월 5일 ‘솔브드’로 개인사업자 등록을 완료했습니다. 2019년 6월 5일에 개발을 시작했으니 딱 3년 반 만입니다. 솔브드는 그 동안 9만 명의 프로그래머 분들께 알고리즘 문제해결을 공부하는 여정에 도움을 드렸습니다.

앞으로도 ‘알고리즘 문제해결 학습의 이정표’에 걸맞는 서비스가 되도록 노력하겠습니다. 특히 컴퓨팅 사고력과 코딩 테스트의 중요성이 대두되고 알고리즘 문제해결 애호가들이 어느 때보다 많아진 지금, 학습자들과 애호가 모두를 아우를 수 있는 이정표를 마련하기 위해 끊임없이 개척해 나가겠습니다. 기여자 분들의 노고를 폄하하거나, 문제해결과 실력 상승의 재미를 해치고 박탈감을 발생시키는 사업 모델 등은 지금도 앞으로도 도입하지 않을 것입니다.

잘 부탁드리겠습니다. 감사합니다!

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

$% 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)