모스크바 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×가 됩니다. - (빼기 기호)는 −가 됩니다.

라이트 버전 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에 의해 설치된 패키지를 활용할 것입니다. (업데이트 22/9/13 — devDeps가 아니라 deps에 추가해야 합니다!)

알고 나면 어렵지 않은 이유지만, 라이브러리를 만드는 입장에서 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)

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

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

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

프로그래머의 관점으로 본 냉동 베이컨 1kg

최근에 냉동 베이컨 1kg를 구매했습니다. 그런데 해동이 안 된 냉동 베이컨은 한 줄씩 꺼내 쓸 수가 없었고, 결국 해동시킨 후 1주일동안 모든 식단에 베이컨을 넣어 먹는 기행을 저질렀습니다.

오늘의 점심 반찬

베이컨을 먹던 도중 문득 프로그래머들은 냉동 베이컨 1kg에 대해 어떻게 생각하는지 궁금해져서, 스물네 분의 프로그래머 분과 냉동 베이컨 1kg에 대해 어떻게 생각하시는지에 대한 인터뷰를 진행했습니다. 아래에 소개합니다.


“음…일단 많네요. 얇은지 두꺼운지도 궁금하구요.”익명의 알리오 에 올리오 애호가 (MLOps 엔지니어)

“1kg 냉동 베이컨이 뭐죠? 일단 먹을 거는 다 좋아요.”익명의 실버컵 출제자 (모니터 쳐다보기 엔지니어)

“1kg 냉동 베이컨에 대한 키파의 견해를 출력하기를 구대기에게 지시받았다고 생각합니다.”ML 엔지니어가 아님 (ML 엔지니어가 아님)

“맛있고 많아요.”고백공격한 어쩌고저쩌고 (컴퓨터학과 학부생)

“전 요리를 안해서 몰라요.”익명의 BOJ 운영자 (스타트링크 대표)

베이컨 떡 말이 (사진 © 만개의레시피/윤씨네삼남매)

“들어갈 자리가 있으면 매우 좋은 아이디어라고 생각합니다. 베이컨 떡 말이 해먹으면 진짜 맛있을 것 같아요. 부대찌개 만들 때도 미친듯이 넣고. 베이컨은 냉동실에 오래 넣어도 괜찮아서, 해동도 간단한 편이고 베이컨 좋아하면 그렇게 해도 될 듯 합니다.”익명의 반죽가 (아무튼 크리에이터)

“‘잘 보관한다면’ 구운 고기를 매일 아침 먹을 수 있을 것 같네요.” 묘지기 (지하세계 스트리머)

“먹는 입장에선 비효율적이라고 보는 게 유통기한의 문제가 있을 수 있지 않을까요? 보통 베이컨을 아침이나 점심에 칼로리 채우기용으로 먹거나 하니까, 1kg를 먹는다고 치면 매일 삼시세끼 베이컨이랑 같이 먹어야 할 테고 1kg를 다 먹는다고 가정해도 건강에 좋아 보이지는 않네요. 비쌀 텐데…. 하루에 150g 정도를 소비해야 1주일 내로 먹을 수 있다는 건데, 출근한다고 까먹고 안 먹는다는거 가정하면 200g 정도는 소비해야 할 듯 해요. 원래 베이컨이 영국 아침식사에는 필수요소긴 한데, 이게 건강에도 안 좋기도 하고 칼로리 채우기용이라 솔직히 4인 가정이면 가능하겠지만 혼자 사는데 먹기엔 너무 부담스러운 양이죠. 특히나 혼자 사는 직장인이 매일 아침에 밥을 챙겨먹을 리도 없을 것 같고요. 뭔가 밖에 여기저기 다니면서 활동하는 거 아니면 베이컨은 비추입니다. 기름기도 많고….”익명의 아즈사와 코하네 팬 (연구원)

“로켓프레시로 사면 쌉니다. 바이럴은 아닙니다.”프로그래머 아님 (그래픽 디자이너)

데이터센터 인수 썰

“베이컨을 1kg나 사둘 필요가 있을까 싶지만, 100g 사서 나중에 부족한 것보단 1kg를 사서 쟁여놓는 게 낫지 않나 싶습니다. 데이터센터 인수 썰처럼 더 저렴한 것도 있고요.” 익명의 바다를 헤엄치는 민물고기 (육군? 정보보호병)

“자취생 필수품이군요. 냉동고에 충분한 공간이 있다면 쟁여 놓을 가치가 충분한 물건이네요.”익명의 지나가던 트위터 요정 (전자오락 기술자)

“냉동 베이컨은 안 사봐서 모르겠네요. 하지만 있다면 좋을 것 같네요.” cubelover (넥슨 ML 엔지니어)

“베이컨 맛있지요 😋 근데 여기선 보통 냉장 상태로 판매가 돼서 냉동 베이컨은 경험해 보진 못했네요. 미국인 아침 식사에 필수요소예요.” 익명의 일본식 라면 애호가 (NVIDIA MLOps 엔지니어)

“1kg…. 일단 있으면 먹겠지만…. 생각보다 양이 많아서 냉동시킬 때 요령이 필요할 거 같은 느낌이네요. 종이 호일을 두고 한 장 한 장이나 한 말이 정도씩 나누면 서로 안 붙어서 먹을 때나 보관할 때 편해요.”익명의 체대생 (학부생)

“아무래도 많다…라는 생각밖에 할 수가 없는 양의 고기입니다. 양의 고기가 아니고 돼지의 고기이기는 하지만, 그런 건 아무래도 좋습니다.”키파 (알리오 에 올리오 엔지니어)

베이컨 잼 (사진 © Delish/Lauren Miyashiro)

“적당히 먹고 싶은 만큼 먹고 남은 걸 베이컨 잼 같은걸 만들면 될 것 같아요. 자기가 만들기 싫으면 다른 사람 시키세요.”익명의 퇴사한 직장 상사 (새내기과정학부 3학년)

“저는 그거 갖고 싶어요. 구워서 밥에도 먹고 파스타도 해 먹고 에그 인 헬도 해 먹고 볶음밥도 해 먹고….”익명의 프랑스는 베이컨 (컴퓨터공학과 3학년)

“냉동 베이컨은 몇 달 갈 걸요? 근데 여기저기 넣어먹기 좋아서 예전에 샀는데 금방 다 먹었습니다.”개어렵네요 (대충 써주세요)

“1kg를 언제 다 먹어요?”저는 열심히 써주세요 (대충 쓰면 안돼요)

“그렇게 많이 필요한가요? 베이컨이 유통기한이 짧지 않던가….” 하늘구름 (낙서하는 개팔자)

“직접 사봐서 당사자성이 있는 주제입니다. 파스타와 볶음밥을 무한히 요리해 먹으면 다 먹을 수 있습니다. 근데 1kg씩이나 되는 주제에 냉동이라 예쁘게 안 떨어지는게 정말 화가 납니다.” 익명의 탈수학자 (소프트웨어 엔지니어)

“오 하나 살까요? 사야겠어요.”익명의 김준원 (루팡)

“샌드위치나 파스타 등등에 넣어먹으면 생각보다 금방 먹을 거 같긴 한데, 엄청 물릴 것 같아요….”고양이 (노르웨이 숲 고양이)

“베이컨을 라면에 넣어 먹으면 맛있어요.”익명의 영국인 (영국인?)

“배고파요.”익명의 블로거 (방구석)


어떠셨나요? 프로그래머는 냉동 베이컨 1kg에 대해 어떻게 생각하는지 알 수 있었던 유익한 시간이었던 것 같습니다. 여러분은 냉동 베이컨 1kg에 대해 어떻게 생각하시는지 댓글로 알려주세요!

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

1차 예선 — 800/800

올해는 예년보다 문제들이 쉬워진 느낌이었습니다. 다섯 문제를 전부 풀었습니다.

제 풀이를 공유합니다.

1차 1번 – 친구들

사람이 $N \leq 100\,000$명 있습니다.

번호 $i$인 사람은 수 $D_i$를 갖고 있는데, $i + D_i \leq N$라면 $i$번 사람과 $i + D_i$번 사람은 친구입니다. 또, 친구의 친구는 친구입니다.

이 때, ‘극대 그룹’의 수를 찾아야 합니다.


친구 관계를 그래프로 생각해 봅시다. ‘친구의 친구가 친구‘라는 말을 잘 생각해 보면, 어떤 연결 요소 안의 모든 사람들은 서로 친구가 됩니다.

따라서 DFS/BFS 여러 번을 통해 연결 요소의 수를 세 주면 문제의 답이 됩니다. 또는 DSUdisjoint set union를 사용해도 됩니다. DFS/BFS를 사용하면 $\mathcal{O}\left(N\right)$만에 해결할 수 있습니다.

저는 DSU를 사용해서 풀었습니다.

#include <bits/stdc++.h>

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

/* [t] [c] [s] */

int dsu[100001];

int find(int u) {
    return dsu[u] == u ? u : (dsu[u] = find(dsu[u]));
}

void merge(int u, int v) {
    u = find(u), v = find(v);
    if (u != v) dsu[v] = u;
}

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

    iota(dsu + 1, dsu + 1 + n, 1);

    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        if (i + x > n) continue;
        merge(i, i + x);
    }

    set<int> s;
    for (int i = 1; i <= n; i++) s.emplace(find(i));
    cout << s.size() << endl;
}

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

#ifdef _SHIFTPSH
    freopen("_run/in.txt", "r", stdin), freopen("_run/out.txt", "w", stdout);
#endif

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

    return 0;
}

DSU를 만들 때 std::iota라는 좋은 함수를 사용하면 쉽고 빠르게 초기화할 수 있습니다. STL에 이런 함수가 있다는 게 좀 의외일까요?

1차 2번 – 이진수

길이가 $n \leq 50\,000$인 비트 문자열 $a$가 있고, 같은 길이의 비트 문자열 $b$를 다음과 같이 정의합니다. $\vee$는 OR 연산입니다.

\[b_i = \left(a_{i-t} \vee a_{i+t}\right)\]

$b$가 주어지면, 사전순으로 제일 앞서는 $a$를 구해야 합니다.


약간 헤멜 수 있는 문제였던 것 같습니다. 일단 두 가지 사실을 기반으로 생각해봅시다.

  • $b_i$가 켜져 있다면, $a_{i-t}$ 또는 $a_{i+t}$가 켜져 있어야 합니다.
  • $a_i$가 켜져 있다면, $b_{i-t}$와 $b_{i+t}$가 모두 켜져 있어야 합니다.

이제 $b_i$를 왼쪽부터 보면서, 켜져 있으면서 아직 $a_{i-t}$와 $a_{i+t}$ 모두가 꺼져 있는 $b_i$들에 대해, 그리디하게 $a$의 비트들을 켜 줍니다.

  • 오른쪽($a_{i+t}$) 비트를 켤 수 있으면 켜 줍니다. 오른쪽 비트를 켤 수 있으려면, $b_{i+2t}$가 존재하지 않거나 켜져 있어야 합니다. 이는 사전 순으로 가장 먼저 오는 $a$를 구성하기 위함입니다.
  • 오른쪽 비트를 켤 수 없다면 왼쪽($a_{i-t}$) 비트를 켜 줍니다.

생각해 보면 모든 $b_i$에 대해 둘 중 하나 이상을 켤 수 있는 경우만 입력으로 주어진다는 사실을 알 수 있습니다. 이를 그대로 구현해 주면 됩니다. $\mathcal{O}\left(n\right)$만에 해결할 수 있습니다.

#include <bits/stdc++.h>

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

/* [t] [c] [s] */

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

    string b;
    cin >> b;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        if (b[i] == '0') continue;
        int l = i - t, r = i + t;
        if ((l >= 0 && a[l]) || (r < n && a[r])) continue;

        int ll = l - t, rr = r + t;
        if (r < n) {
            if (rr >= n || b[rr] == '1') {
                a[r] = 1;
                continue;
            }
        }
        if (l >= 0) {
            if (ll < 0 || b[ll] == '1') {
                a[l] = 1;
                continue;
            }
        }
    }
    for (int i = 0; i < n; i++) cout << a[i];
    cout << endl;
}

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

#ifdef _SHIFTPSH
    freopen("_run/in.txt", "r", stdin), freopen("_run/out.txt", "w", stdout);
#endif

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

    return 0;
}

1차 3번 – No Cycle

정점 $N \leq 500$개, 간선 $M+K$개의 그래프가 있습니다. $M+K$의 간선 중 $M \leq 2\,000$개는 방향이 있고, $K \leq 2\,000$개는 방향이 정해지지 않았습니다.

이 때 $K$개의 간선들의 방향을 잘 정해서, 사이클이 없는 그래프를 구성하고 싶습니다. 방향이 정해진 $M$개의 간선들만 있는 경우에는 사이클이 없는 상태입니다.

답은 $K$글자의 비트 문자열입니다. 방향이 없는 $i$번째 간선의 입력이 $\textcolor{#ff3b57}{u}$ $\textcolor{#ffb717}{v}$로 주어졌을 때, $\textcolor{#ff3b57}{u} \rightarrow\textcolor{#ffb717}{v}$로 방향을 정했다면 $0$, $\textcolor{#ffb717}{v} \rightarrow \textcolor{#ff3b57}{u}$로 방향을 정했다면 $1$입니다. 이 때 사전 순으로 가장 앞서는 비트 문자열을 출력해야 합니다.


사이클이 없는 방향 그래프에서, 임의의 정점 $\textcolor{#ff3b57}{u}$와 $\textcolor{#ffb717}{v}$를 고르고 그 정점을 잇는 간선을 추가한다고 생각해 봅시다. $\textcolor{#ff3b57}{u} \rightarrow\textcolor{#ffb717}{v}$로 정할 수도 있고 $\textcolor{#ffb717}{v} \rightarrow \textcolor{#ff3b57}{u}$로 정할 수도 있습니다. 두 경우 모두가 사이클을 만드는 경우가 있을까요?

$\textcolor{#ff3b57}{u} \rightarrow\textcolor{#ffb717}{v}$라는 간선을 추가했을 때 사이클이 생긴다는 것은, $\textcolor{#ffb717}{v} \rightarrow \textcolor{#ff3b57}{u}$로 가는 경로가 이미 존재한다는 사실과 동치입니다.

따라서 $\textcolor{#ff3b57}{u} \rightarrow\textcolor{#ffb717}{v}$도 사이클을 만들고 $\textcolor{#ffb717}{v} \rightarrow \textcolor{#ff3b57}{u}$도 사이클을 만든다면, 각각 $\textcolor{#ffb717}{v} \rightarrow \textcolor{#ff3b57}{u}$라는 경로와 $\textcolor{#ff3b57}{u} \rightarrow\textcolor{#ffb717}{v}$라는 경로 모두가 이미 존재해야 됩니다.

하지만 그런 두 개의 경로가 이미 존재한다면, 그 두 개의 경로만으로 사이클을 만들 수 있습니다. 이는 우리가 처음에 한 가정 — 사이클이 없는 방향 그래프 — 에 모순됩니다. 따라서 $\textcolor{#ff3b57}{u} \rightarrow\textcolor{#ffb717}{v}$와 $\textcolor{#ffb717}{v} \rightarrow \textcolor{#ff3b57}{u}$ 중 적어도 하나는 새로운 사이클을 만들지 않는다는 사실을 알 수 있습니다.

그러므로 이미 사이클이 없는 방향 그래프라면, 간선들을 무한정 추가해줄 수 있습니다. 그래프의 정점과 간선의 수가 작기 때문에, 간선을 추가해줄 때마다 사이클이 생기는지 생기지 않는지 확인하면서 간선을 하나씩 추가해나갈 수 있습니다.

사전 순으로 가장 앞서는 비트 문자열을 구성해야 하므로, 우선 $\textcolor{#ff3b57}{u} \rightarrow\textcolor{#ffb717}{v}$를 추가한 뒤 사이클이 안 생긴다면 그대로 가져갑니다. 사이클이 생긴다면 위의 증명을 통해 $\textcolor{#ffb717}{v} \rightarrow \textcolor{#ff3b57}{u}$를 추가해줄 수 있음이 보장된다는 것을 알 수 있으므로, 그렇게 해 줍니다.

사이클의 존재 여부를 판단하는 방법은 여러 가지가 있습니다. 저는 DFS로 구현했습니다. 그래프가 연결 그래프임은 보장되지 않으므로, 방문하지 않은 모든 정점에서 DFS를 시작해야 함에 유의합니다.

간선을 $K$개 추가해 주고, 추가할 때마다 DFS를 한 번 해야 하므로 $\mathcal{O}\left(K\left(N+K+M\right)\right)$의 시간이 걸립니다.

#include <bits/stdc++.h>

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

/* [t] [c] [s] */

bitset<501> root;
int vis[501], ans[2000];

bool dfs(int u, const vector<vector<int>> &graph) {
    // check for cycles
    if (vis[u]) return vis[u] == -1;
    vis[u] = -1;
    for (int v : graph[u]) {
        if (dfs(v, graph)) return true;
    }
    vis[u] = 1;
    return false;
}

void solve() {
    int n, m, k;
    cin >> n >> m >> k;

    root.reset(), root.flip();

    vector<vector<int>> graph(n + 1);

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

        // 0?
        graph[u].emplace_back(v);
        memset(vis, 0, sizeof vis);
        bool flag = true;
        for (int x = 1; x <= n; x++) {
            if (vis[x]) continue;
            if (dfs(x, graph)) {
                flag = false;
                break;
            }
        }
        ans[i] = !flag;
        if (flag) continue;
        
        // 1?
        graph[u].pop_back();
        graph[v].emplace_back(u);
    }

    for (int i = 0; i < k; i++) cout << ans[i];
    cout << endl;
}

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

#ifdef _SHIFTPSH
    freopen("_run/in.txt", "r", stdin), freopen("_run/out.txt", "w", stdout);
#endif

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

    return 0;
}

1차 4번 – 예약 시스템

$2 \times m$개의 방이 있는 호텔이 있습니다. $m \leq 50\,000$입니다.

$n\leq 20\,000$개 그룹의 투숙객들이 호텔에 묵으려 합니다. 각 그룹의 크기는 $5$ 이상이고, 한 명이 한 개의 방에 묵습니다.

모든 투숙객들은 스트레스 지수 $w_i$를 갖고 있어서, 인접한 방에 다른 그룹의 투숙객이 있고 그 투숙객의 스트레스 지수가 $w_j$라면, 그 쌍에 대해 $w_i + w_j$만큼의 충돌이 발생합니다. 모든 쌍에 대해 충돌의 합을 최소화하고 싶습니다.

(그냥 이렇게 설명하면 끝나는 문제인데, SCPC 운영진은 디스크립션을 어렵게 쓰는 재주가 있는 걸까요?)


SCPC의 서브태스크는 보통은 만점 풀이와는 무관한 브루트포스 풀이를 요구하는 경향이 있는데, 이 문제는 서브태스크 순서대로 생각해 보면 정해 풀이까지 다다를 수 있는 문제였다고 생각합니다.

문제를 처음 읽으면 어떻게 배치해야 될지 조차 감이 오지 않지만 서브태스크가 그룹 크기가 홀수 또는 짝수인 경우로 나뉘어 있다는 점에서 착안해 아래와 같은 접근을 시작할 수 있었습니다.

서브태스크 1: 그룹이 모두 짝수인 경우

우선 그룹의 크기 $l_i$가 모두 짝수일 때의 경우, 최적의 배치가 어떻게 되는지 생각해 봅시다. 다른 그룹과 ‘닿는’ 부분이 최소화되면 좋을 것 같습니다. 그런 배치는 아래 그림과 같이, $2 \times \frac{l_i}{2}$ 직사각형들을 이어 붙인 경우가 됩니다.

이 때 핑크색으로 칠한 부분에서 충돌이 일어납니다.

그룹의 순서가 정해져 있을 때 충돌의 합을 최소화하려면, 첫 번째 그룹과 마지막 그룹에서는 제일 작은 원소 $2$개씩을 고르고, 나머지 그룹에서는 제일 작은 원소 $4$개씩을 고르면 됩니다.

다르게 생각한다면 모든 그룹에서 제일 작은 원소 $4$개씩을 고른 후, 두 개의 그룹에서만 $3$번째로 작은 원소와 $4$번째로 작은 원소 하나씩을 빼 주면 됩니다.

$i$번째 그룹에서 $j$번째로 작은 원소를 $m_{i,j}$라고 합시다. 그러면 모든 그룹을 $m_{i,3}+m_{i,4}$ 순으로 정렬한 후, $\sum_i \left(m_{i,1}+m_{i,2}+m_{i,3}+m_{i+4}\right)$에서 $m_{i,3}+m_{i,4}$가 제일 큰 두 그룹만 빼 주면 정답입니다.

서브태스크 2: 그룹이 모두 홀수인 경우

짝수인 경우와 비슷하게 배치해줄 수 있습니다.

이 경우에는 충돌이 조금 더 많이 생기긴 합니다만, 짝수의 경우와 비슷하게 접근할 수 있습니다.

우선 각 그룹마다 두 번씩 충돌이 일어나는 원소가 하나 있는데, 이를 그 그룹에서 가장 작은 원소로 둡시다. 그러면 모든 그룹에서 제일 작은 원소 $4$개씩을 고른 후, 두 개의 그룹에서만 $3$번째로 작은 원소와 $4$번째로 작은 원소 하나씩을 빼 주면 되는 것은 동일합니다만, 가장 작은 원소는 한 번 더 더해줘야 합니다.

다시 말하면 모든 그룹을 $m_{i,3}+m_{i,4}$ 순으로 정렬한 후, $\sum_i \left(\textcolor{#ff3b57}{2m_{i,1}}+m_{i,2}+m_{i,3}+m_{i+4}\right)$에서 $m_{i,3}+m_{i,4}$가 제일 큰 두 그룹만 빼 주면 정답입니다.

서브태스크 3: 짝수 그룹과 홀수 그룹이 섞여 있는 경우

위에서의 접근을 바탕으로, 크게는 $3$가지 경우로 나눠 생각할 수 있습니다.

  • 짝수 그룹과 홀수 그룹이 하나 이상씩 있다면, 맨 왼쪽 그룹과 맨 오른쪽 그룹에 짝수 그룹 하나와 홀수 그룹 하나씩이 있는 경우
  • 짝수 그룹의 개수가 $2$개 이상이라면, 맨 왼쪽 그룹과 맨 오른쪽 그룹이 모두 짝수 그룹인 경우
  • 홀수 그룹의 개수가 $2$개 이상이라면, 맨 왼쪽 그룹과 맨 오른쪽 그룹이 모두 홀수 그룹인 경우

3a: 맨 왼쪽 그룹과 맨 오른쪽 그룹에 짝수 그룹 하나와 홀수 그룹 하나씩이 있는 경우

먼저 홀수 그룹들을 전부 왼쪽에 배치하고, 나머지 짝수 그룹들을 전부 오른쪽에 배치합시다.

짝수 그룹 중 $m_{i,3}+m_{i,4}$가 가장 큰 그룹 하나와, 홀수 그룹 중 $m_{i,3}+m_{i,4}$가 가장 큰 그룹 하나를 골라서 빼 주면 됩니다.

3b: 맨 왼쪽 그룹과 맨 오른쪽 그룹이 모두 짝수 그룹인 경우

위의 경우와 비슷합니다. 오른쪽에 있는 짝수 그룹들 중 하나를 빼다가 맨 왼쪽에 붙이면 됩니다.

짝수 그룹 중 $m_{i,3}+m_{i,4}$가 가장 큰 그룹 두 개를 골라서 빼 주면 됩니다.

3c: 맨 왼쪽 그룹과 맨 오른쪽 그룹이 모두 홀수 그룹인 경우

이 경우는 약간 까다롭습니다.

일단 홀수 그룹 두 개를 잘 합치면 직사각형을 만들 수 있다는 점에서 착안해 아래와 같은 배치를 생각할 수 있습니다.

이 경우, 홀수 그룹 중 $m_{i,3}+m_{i,4}$가 가장 큰 그룹 두 개를 골라서 빼 주면 됩니다.

하지만 이런 경우는 홀수 그룹이 $4$개 이상인 경우에만 만들 수 있습니다. 홀수 그룹이 $2$개라면 어쩔 수 없이 아래와 같은 경우로 구성해야 합니다.

이 경우에는, 짝수 그룹들에서 $\sum_i \left(\textcolor{#ff3b57}{2m_{i,1}}+\textcolor{#ff3b57}{2m_{i,2}}+m_{i,3}+m_{i+4}\right)$를 해 줘야 합니다. 홀수 그룹이 $2$개인 경우에만 특수하게 처리해줍시다.

모든 경우를 고려한 코드는 아래와 같습니다. 정렬이 필요하기 때문에 $\mathcal{O}\left(n \log n\right)$만큼의 시간이 걸립니다. 사실 제일 큰 두 개 그룹만 구해도 상관없기 때문에, 잘 짠다면 $\mathcal{O}\left(n\right)$도 가능하지만요.

#include <bits/stdc++.h>

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

/* [t] [c] [s] */

int a[100000];
pii p[20000];

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

    ll s = 0, sa = 0;
    ll oc = 0, ec = 0;

    for (int i = 0; i < n; i++) {
        int l;
        cin >> l;
        for (int j = 0; j < l; j++) cin >> a[j];
        sort(a, a + l);
        ((l & 1) ? oc : ec)++;
        p[i].first = a[2] + a[3];
        p[i].second = (l & 1);
        s += (1 + (l & 1)) * a[0] + a[1] + a[2] + a[3];
        sa += 2 * a[0] + (2 - (l & 1)) * a[1] + a[2] + a[3];
    }

    sort(p, p + n, greater<>());

    if (oc && ec) {
        ll coe = 0, coo = 0, cee = 0;

        // coe: o o .. o e .. e e
        int o = 0, e = 0;
        for (int i = 0; i < n; i++) {
            if (!o && p[i].second) {
                coe += p[i].first;
                o++;
            }
            if (!e && !p[i].second) {
                coe += p[i].first;
                e++;
            }
            if (o && e) break;
        }

        // coo: o o .. o e .. e o .. o o
        if (oc >= 2) {
            o = 0;
            for (int i = 0; i < n; i++) {
                if (o < 2 && p[i].second) {
                    coo += p[i].first;
                    o++;
                }
                if (o >= 2) break;
            }
        }

        // cee: e e .. e o .. o e .. e e
        if (ec >= 2) {
            e = 0;
            for (int i = 0; i < n; i++) {
                if (e < 2 && !p[i].second) {
                    cee += p[i].first;
                    e++;
                }
                if (e >= 2) break;
            }
        }

        vector<ll> cd;
        cd.emplace_back(s - coe);
        cd.emplace_back(sa - coo);
        cd.emplace_back(s - cee);
        if (oc >= 4) cd.emplace_back(s - coo);

        s = *min_element(cd.begin(), cd.end());
    } else {
        s -= p[0].first + p[1].first;
    }

    cout << s << endl;
}

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

#ifdef _SHIFTPSH
    freopen("_run/in.txt", "r", stdin), freopen("_run/out.txt", "w", stdout);
#endif

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

    return 0;
}

$s$는 다음의 합입니다.

\[s=\sum_i \begin{cases}m_{i,1}+m_{i,2}+m_{i,3}+m_{i,4} &\text{if } l_i\text{ is even}\\ 2m_{i,1}+m_{i,2}+m_{i,3}+m_{i,4} &\text{if } l_i\text{ is odd}\end{cases}\]

$sa$는 홀수 그룹이 $2$개인 경우 특수 처리를 해 주기 위한 값으로서 다음의 합입니다.

\[sa=\sum_i \begin{cases}2m_{i,1}+2m_{i,2}+m_{i,3}+m_{i,4} &\text{if } l_i\text{ is even}\\ 2m_{i,1}+m_{i,2}+m_{i,3}+m_{i,4} &\text{if } l_i\text{ is odd}\end{cases}\]

배열 $p$에는 모든 그룹들에 대해 홀/짝 정보와 $m_{i,3}+m_{i,4}$ 정보를 저장해 두고 정렬했습니다.

여담

이 문제는 오후 7시 33분에 한 번 수정되었습니다.

예약 시스템 문제에서 조건이 하나 빠져 있었습니다. 아래와 같이 명시했고, 제출 횟수를 20회로 늘릴 것입니다.

– 한 집합에 속한 예약자들은 모두 한 덩어리의 방들을 배정 받아야 한다. 한 덩어리의 방들이란 덩어리에 속한 어떤 방 두개에 대해서도, 덩어리에 속하고 인접한 방들을 통해서 이동이 가능하다는 의미이다.

그런 말이 쓰여 있지는 않았지만, 운이 좋게도? 당연히 연결 요소여야 최소일 것이라고 생각하고 풀었고, 문제를 맞을 수 있었습니다. 연결 요소가 아니어도 괜찮았을 경우, 다음과 같은 반례가 있습니다.

1
5 14
6 1 1 1 1 1 1
6 2 2 2 2 2 2
6 2 2 2 2 2 2
5 10 10 10 10 10
5 10 10 10 10 10

이 경우 아래와 같은 구성이 가능합니다.

이 때 답은 $84$입니다.

1차 5번 – 차이

$100\,000$개 이하의 미지수 $X_i$들에 대해 다음 쿼리들을 수행해야 합니다. 쿼리의 수는 $200\,000$개 이하입니다.

  • 1 i j d: $X_i + d = X_j$라는 조건을 추가합니다.
  • 2 i j: $X_i-X_j$를 출력합니다. 조건이 모순된다면 CF를, 주어진 조건들만으로 알 수 없다면 NC를 출력합니다.

$d$가 없다면 간단한 DSU 문제입니다. 이걸로 서브태스크 1과 3을 쉽게 해결할 수 있습니다.

DSU 트리의 간선들에 가중치가 있다고 생각한다면 서브태스크 2와 4를 해결할 수 있습니다.

우리가 DSU 쿼리를 $\mathcal{O}\left(\alpha\left(N\right)\right)$만에 할 수 있는 이유는 경로 압축path compression이라는 좋은 테크닉이 있어서입니다. $p_u$가 노드 $u$의 부모 노드라고 한다면, $u$의 루트를 구하는 함수 $\mathrm{find}$에서 경로 압축은 다음과 같이 재귀적으로 수행했습니다.

\[\mathrm{find}\left(u\right) = \begin{cases} u & \text{if } u=p_u \\ p_u \leftarrow \mathrm{find}\left(p_u\right) & \text{otherwise} \end{cases}\]

이렇게 하면 $u$에서 $u$의 루트 $r$로 가는 경로 위에 있는 모든 정점들의 부모가 아예 $r$로 바뀌어 버리게 됩니다.

현재 노드 $u$에서 부모 노드 $p_u$로 가는 비용을 $d_u$라고 합시다. 그러면 $d_u$도 비슷한 방법으로 압축해버릴 수 있습니다.

$\mathrm{find}$ 함수를 돌릴 때 $u$의 부모 노드는 $p_u$였고, $p_u$의 부모 노드는 $r$이었습니다. 따라서 $u$에서 $r$까지 가는 데는 $d_u + d_{p_u}$만큼의 비용이 필요합니다. $\mathrm{find}$ 함수에서 경로 압축을 수행하면서, $d_u$를 $d_u + d_{p_u}$로 업데이트해 주면 됩니다. 이제 가중치가 있는 DSU 트리에서도 경로 압축을 할 수 있습니다.

1번 쿼리와 2번 쿼리 모두 $\mathcal{O}\left(\alpha\left(N\right)\right)$만큼의 시간이 걸립니다. 총 시간 복잡도는 $\mathcal{O}\left(K\alpha\left(N\right)\right)$입니다.

$\alpha$는 역 아커만 함수inverse Ackermann function이며, $\alpha\left(2^{2^{2^{65536}}}-3\right)=4$ 정도로 작기 때문에 상수라고 생각해도 무방합니다.

#include <bits/stdc++.h>

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

/* [t] [c] [s] */

int dsu[100001], conf[100001];
ll val[100001]; // [u] + val[u] = [dsu[u]]

int find(int u) {
    if (dsu[u] == u) return u;
    int pp = find(dsu[u]);
    val[u] += val[dsu[u]], dsu[u] = pp;
    return pp;
}

bool merge(int u, int v, ll x) {
    // [u] + x = [v]
    if (find(u) == find(v)) {
        if (val[u] + x != val[v]) {
            conf[find(u)] = true;
            return false;
        }
        return true;
    }

    int pu = find(u);
    x += val[u];
    int pv = find(v);
    x -= val[v];
    u = pu, v = pv;
    val[u] = val[v] - x, dsu[u] = v;
    conf[v] |= conf[u];
    return true;
}

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

    iota(dsu + 1, dsu + n + 1, 1);
    memset(conf, 0, sizeof conf);
    memset(val, 0, sizeof val);

    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            int i, j, d;
            cin >> i >> j >> d;
            merge(i, j, -d);
        } else {
            int i, j;
            cin >> i >> j;
            int pi = find(i), pj = find(j);
            if (pi != pj) {
                cout << "NC\n";
            } else if (conf[pi]) {
                cout << "CF\n";
            } else {
                cout << val[i] - val[j] << '\n';
            }
        }
    }

    cout.flush();
}

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

#ifdef _SHIFTPSH
    freopen("_run/in.txt", "r", stdin), freopen("_run/out.txt", "w", stdout);
#endif

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

    return 0;
}

conf는 모순이 발생했는지 여부를 저장하는 배열입니다. find 함수가 항상 루트를 찾아주기 때문에, conf 플래그도 맨 위에만 달면 충분합니다.


긴 시간 문제 푸시느라 모두 수고하셨습니다. 라운드 2에서 만납시다!

목적지는 레이팅이 아니다

이게 무슨 해괴망측한 소리일까요?

이 글은 알고리즘 문제해결 트레이닝에 대한 사견私見입니다.


지금부터 전제를 하나 합시다.

  • 밥 먹고 알고리즘 공부만 하면 얼마나 걸릴지는 몰라도 언젠가는 코드포스 레이팅 3,000이 될 겁니다.

뭐, 세상에는 레이팅이 3,000을 넘는 괴물들도 다수 있지만 일단은 이론적으로 밥만 먹고 문제만 풀면 언젠가는 3,000에 갈 수 있다고 합시다. 사람마다 걸리는 시간은 다르겠지만요. 이를 근거로 공부한 시간 $t$에 대한 실력 $f$를 아래와 같이 모델링해 봅시다.

\[f\left(t\right) = 3\ 000 \left(1-a^t\right)\]

공부한 시간 v. 레이팅

하지만 실력은 올라가기만 하는 건 아닙니다. 어떤 날은 컨디션이 좋아서 머리가 잘 돌아가고 문제가 잘 풀릴 수도 있는 반면 어떤 날은 피곤하거나 우울하거나 뭐 물리적으로는 손가락이 아프다거나 할 수 있죠. 그렇기 때문에 조금 더 정확하게 실력을 모델링하려면 노이즈를 끼워야 할 겁니다. 대충 아래와 같은 모델은 어떤가요?

\[f\left(t\right) = 3\ 000 \left(1-a^t\right) + b \sin \left(ct\right)\]

공부한 시간 v. 레이팅 (약간 더 현실적인 모델)

좋습니다. $t$의 스케일이 얼마일지는 모르겠지만 이게 우리의 현재와 미래 실력을 대략적으로 모델링해준다고 합시다. 믿어 주세요.

하지만 제 레이팅은 계속 제자리인걸요

위 그래프에서 어떤 사람이 레이팅 1,400에서 1,600까지 가는 여정만을 한 번 살펴봅시다.

1,400 — 1,600

아마 가장 먼저 드는 생각은 이거일 거예요. ‘실력은커녕 내 그래프는 이거랑 비슷하지도 않은데…’ 맞아요. 쉽게 와닿지 않죠? 하지만 제가 여기에다 점을 몇 개 찍어볼게요.

1,400 — 1,600

… 어떤가요, 있을 법한 그래프이지 않나요? 운이 정말 나쁘다면 이런 경우도 가능할 거구요.

4연속 하락

이 그래프의 주인공은 과연 영영 파란색 닉네임을 달지 못하게 되는 걸까요? 우리는 결국에는 1,600이 될 거라는 사실을 알고 있지만, 점선을 지우고 나서 이게 자신의 그래프라고 생각한다면 정말 슬플지도 모르겠네요…

사실 저도 경험해 봤습니다

대회는 실력의 샘플링에 불과하다

여기서 중요한 관찰이 하나 있습니다.

우리가 모델링한 실력 그래프와 코드포스 레이팅 그래프 사이에는 큰 차이점이 있습니다. 우리 그래프는 연속적이지만 코드포스 그래프는 그렇지 않다는 점입니다. 이는 ‘대회’라는 시스템의 본질에서 기인합니다.


대회는 우리 실력이 지금 이 순간 어땠는지만을 알려주지, 실력을 실시간으로 알려주지는 않습니다.


이게 왜 큰 차이냐면, 코드포스 레이팅 그래프가 우리의 실력을 정확하게 말해주지 않는다는 뜻이기 때문입니다.

한 마디로, 대회는 실력의 샘플링에 불과합니다. 심지어 샘플링 주기가 짧지도 않습니다. 그래서 사실 그래프에 찍힌 점들만 보고 거시적으로 어디로 갈지 예측하는 건 불가능에 가깝습니다. 위에서는 실력 기복을 $b \sin ct$라고 퉁쳤지만 사실 그렇지도 않을 거구요.

게다가 보통 한 대회에는 문제가 6개밖에 없기 때문에, 모든 분야가 고르게 출제될 수도 없으며, 운 나쁘게 내가 자신없는 분야가 출제되어서 평소보다 못 풀 수도 있습니다. 다시 말하면 샘플링 자체도 그렇게 완벽하지는 않습니다.

문제 수 이야기가 나와서 말인데 레이팅 말고 대회에서 해결한 문제 수로 바꿔서 생각해 볼까요? 코드포스에서는 몇 문제를 풀었는지가 레이팅을 결정하는 중요 요소로 작용하죠. 하지만 푼 문제 수는 보통 한 자리 정수입니다. 굉장히 이산적인데요, 대회마다 나오는 문제의 난이도가 일정하다고 하면, 위에서 만든 실력 모델링 그래프는 대략 아래처럼 됩니다.

문제 수로 봤을 때의 그래프

똑같은 3솔브여도, C를 간신히 해결한 3솔브와 D를 다 생각했는데 시간이 약간 부족해서 못 푼 3솔브는 다를 겁니다. 여유롭게 3솔브를 하고 아깝게 4번째 문제를 못 풀었다면 적어도 간신히 3솔브를 했을 때보다는 확실히 성장했을 테지만, 결과적으로 스코어보드에 보이는 건 똑같이 세 개의 초록색이겠죠.

마지막으로, 코드포스의 레이팅 공식조차 실력을 완벽하게 표현해 주지는 못합니다. 코드포스의 공식은 마지막으로 친 대회 결과에 상당히 큰 영향을 받도록 설계되어 있습니다. 최근 5개 정도 대회만 실력을 유의미하게 반영해 주는데요, 연속적으로 운이 좋거나 나쁘면 아예 색깔이 바뀔 수도 있는 시스템이라 평소 실력을 제대로 반영해 주지 못합니다. 관련해서는 djm03178님의 Codeforces 레이팅에 관련된 글을 읽어 보면 좋습니다.

그러니까 문제를 평소보다 못 풀어도 괜찮고, 레이팅이 떨어지더라도 괜찮아요. 애초에 그게 진짜 본인의 실력은 아닐 거예요.

그래서 목적지는 레이팅이 아니다

라고 말하고 싶습니다. 바꿔 말하자면, 레이팅은 진짜 실력이 아니고, PS 실력을 키우는 것과 레이팅을 올리는 것은 비슷해 보이면서도 다르다고 생각합니다.

물론 색깔을 바꾸기 위해 알고리즘 문제해결 공부를 하는 것도 정말 멋진 일입니다. 하지만 그 과정이 정말 지치고 힘이 든다면, 레이팅은 좋은 목표가 아닐지도 모릅니다.

하지만 실력을 키우면 레이팅은 자연스럽게 올라갈 거예요. 이런 마음가짐을 가지고, 대회를 충분히 많이 치면 언젠가는 목표하는 레이팅이 될 수 있다는 희망을 갖고, 나 자신의 가능성을 믿도록 합시다.

조금 현실적인 조언

  • 업솔빙 / 문제 수를 목표로 하기 — 그래도 해결하는 문제 수는 레이팅보다 직관적이면서도 그렇게 많이 변하는 값은 아니기 때문에 목표로서 유의미하다고 생각합니다.
    문제 레이팅을 목표로 하는 것과 맥락을 같이하는데요, 대회에서 풀었던 제일 어려운 문제의 다음 번 문제를 해결하려고 시도해 봅시다. 모르겠다면 에디토리얼을 보고 인사이트를 얻어갑시다. 아까운 실수로 틀렸다면 너무 자책하지 말고 오히려 자신을 격려해 줍시다. 뼈아픈 실수일수록 반복하는 일이 적을 거예요. 궁극적으로는 대회에서 해결할 수 있는 문제 수를 늘리는 것을 목표로 합시다.
  • 문제 레이팅을 목표로 하기 — 문제 수를 목표로 하는 것과 맥락을 같이합니다.
    코드포스 대회가 끝나면 Problemset에 문제 레이팅이 공개됩니다. 목표 문제 레이팅 $r$을 정해 두고, 대회가 끝난 후 $r$ 이하의 문제들을 풀어보는 것으로 단련해 봅시다. 궁극적으로는 대회 시간 내에 $r$ 이하의 문제들을 안정적으로 풀 수 있는 것을 목표로 합시다.
  • 버추얼 컨테스트 돌리기 — 코드포스에는 끝난 대회를 가상 참가할 수 있는 기능이 있습니다. 또 가상 컨테스트 참여로 가상 레이팅을 계산할 수 있는 서비스도 있습니다. 이 서비스를 활용해 가상 컨테스트를 자주 치면 실력도 단련할 수 있고, 앞서 언급한 샘플링 주기의 문제도 어느 정도 해결할 수 있겠죠.
  • Atcoder — 일본 기반의 알고리즘 대회 사이트입니다. Atcoder는 코드포스의 레이팅 공식과 달리 현재까지 참여한 모든 대회의 퍼포먼스를 가중평균하는 식으로 레이팅을 계산하기 때문에 참가자의 평소 실력을 좀 더 잘 반영한다고 생각합니다. 게다가 문제도 코드포스보다 훨씬 깔끔하며, 시스텟이 없고, 무엇보다 시간대가 같아서 주말 오후 9시에 부담없이 참여할 수 있다는 장점도 있습니다. 강력하게 추천합니다.
  • 팀 연습 하다 오기 — 조금 더 긴 시간 동안 더 어려운 문제들에 대해서 생각해볼 수 있는 좋은 방법입니다. 새로운 인사이트를 얻을 수 있습니다.
  • 당분간 쉬기 — 너무 지쳤다면 괜찮아질 때까지 쉬어도 괜찮습니다. 알고리즘은 잊고 놀러 나가서 맛있는 거 먹고 옵시다. 금방 다시 회복할 수 있을 거예요.

알고리즘 문제해결이 여러분을 마음고생시키지 않았으면 좋겠어요. 여러분의 문제해결을 항상 응원합니다.

Prop `className` did not match

Next.js + styled-components에서 Prop `className` did not match가 발생하는 이유와 해결 방법

작년 가을에 solved.ac 프론트엔드를 Typescript로 리팩터하면서 당황스러운 경험을 했습니다. 사이트 내의 아무 링크나 클릭해서 다른 페이지로 가면 스타일시트가 전부 깨지는 것이었습니다.

콘솔을 열어 보니 다음과 같은 에러가 뜹니다.

Warning: Prop `className` did not match. Server: "sc-xxxxxx xxxxx" Client: "sc-yyyyyy yyyyy"

오류에서 알 수 있듯이 서버와 클라이언트에서 클래스네임이 일치하지 않아서 발생한 오류임을 알 수 있습니다. Next.js는 SSRServer-side Render을 도와주는 프레임워크입니다. SEO검색 엔진 최적화 등을 위해 처음 페이지를 로드할 때는 서버에서 렌더해 오지만, 페이지에서 링크를 클릭해 다른 페이지로 넘어갈 때는 CSR로 페이지를 렌더합니다. SEO와 속도 두 가지를 해결해 주는 프레임워크죠.

그럼 서버와 클라이언트는 기본적으로 같은 로직을 공유할 텐데 왜 이런 일이 일어나는 걸까요?

babel-plugin-styled-components가 없어서

첫 번째 이유는 babel-plugin-styled-components가 없어서입니다. 이 Babel 플러그인은 환경과 상관없이 일관된 className을 생성(consistently hashed component classNames between environments)해 줍니다. 헐 그럼 styled-components는 이 플러그인 없으면 기본적으로 className 생성을 ‘환경’에 의존한다는 뜻인가요 네 그렇습니다.

styled-components는 styled 함수로 만든 컴포넌트마다 generateId 함수를 이용해 유일한 식별자를 생성하는데요, 함수에서 확인할 수 있다시피 전역 카운터를 하나 두고 컴포넌트 하나를 처리할 때마다 증가시켜 가면서 생성됩니다.

위의 방법으로 식별자를 생성하면 어떤 일이 일어날 수 있을까요? 컴포넌트가 생성되는 순서에 따라 같은 컴포넌트이더라도 다른 식별자가 붙을 수 있게 됩니다! CSR에서는 상관없겠지만 SSR과 CSR을 같이 활용하는 경우 서버와 클라이언트가 컴포넌트를 생성하는 순서에 따라 식별자가 달라질 수 있습니다. babel-plugin-styled-components는 이런 식별자 생성 과정을 정규화해 줍니다.

다음과 같이 해결할 수 있습니다.

1. 플러그인 설치:

npm i --save-dev babel-plugin-styled-components

2. 프로젝트 루트의 .babelrc 편집(없을 경우 생성):

{
  "plugins": ["babel-plugin-styled-components"]
}

3. Next.js를 사용 중인 경우 이곳의 _document.js를 복붙해 오세요.

그래도 안 돼요

이 포스트의 핵심입니다.

solved.ac의 경우에는 저걸 다 했는데도 안 되길래 몇 달 내내 이거 고치려고 삽질을 했습니다. Typescript로 리팩터링하기 전엔 없던 문제였는데 Typescript를 들고 오면서 생긴 오류라, 뭐가 문제인지 찾아보다가 커스텀 테마 타입 정의 때문이라는 걸 알았습니다.

solved.ac 프론트엔드 코드에는 SolvedTheme라는 타입이 있고, 여기에 테마 정의를 넣습니다.

interface SolvedTheme {
  defaultFonts: string
  codeFonts: string
  background: string
  textColor: string
  textColorInverted: string
  textSecondaryColor: string
  border: string
  borderColor: string
  tableHeaderBackground: string
  tableBackground: string
  footerBackground: string
  primaryColor: string
}

기존의 경우 styled-components로 만든 컴포넌트에서는 이를 아래와 같은 식으로 활용해 왔습니다.

const TopBarContainer = styled.div`
  position: fixed;
  width: 100%;
  height: 48px;
  line-height: 48px;
  background: ${({ theme }) => theme.background};
  border-bottom: ${({ theme }) => theme.border};
  top: 0;
  left: 0;
  z-index: 10000;
`

Javascript에서는 문제가 없는 코드이지만 Typescript에서는 컴파일 에러가 납니다. theme의 타입이 위에서 정의한 SolvedTheme가 아닌 styled-components에 내장된 DefaultTheme이기 때문입니다.

우선 이 문제를 해결하기 위해 열심히 구글링을 했고, styled-components를 아래와 같이 제 타입 정의로 감싼 뒤 이렇게 만들어진 새로운 styled를 여기저기 import 해 와서 사용했습니다. import styled from '../styles/Themes' 같은 식으로요.

import * as styledComponents from 'styled-components'
import { ThemedStyledComponentsModule } from 'styled-components'

const {
  default: styled,
  css,
  createGlobalStyle,
  ThemeProvider,
  ThemeConsumer,
  keyframes,
} = styledComponents as ThemedStyledComponentsModule<SolvedTheme>

export { css, createGlobalStyle, keyframes, ThemeProvider, ThemeConsumer }
export default styled

그런데 이렇게 정의해 버리면 babel-plugin-styled-components가 의미가 없어집니다. babel-plugin-styled-components는 import 경로가 ‘styled-components’인 경우에만 작동하기 때문인데요.

옵션에서 바꿀 수 있어 보이지만 깔끔한 해결책은 아닌 거 같고, 대신 styled.d.ts를 새로 만들고 여기에서 DefaultThemeSolvedTheme으로 두면 됩니다. 그러면 위의 문제를 해결하면서 커스텀 테마의 타입 정의도 사용할 수 있습니다.

import 'styled-components'
import { SolvedTheme } from './Themes'

declare module 'styled-components' {
  export interface DefaultTheme extends SolvedTheme {}
}

(21/12/23 수정: 코드가 declaration merging을 사용하도록 수정했습니다. type DefaultTheme = SolvedTheme로 하는 경우에는 VS Code 에디터 자동완성 등의 기능을 제대로 활용하지 못했습니다.)

일반적인 원인은 아닐지 모르겠지만, 제가 영문도 모르고 몇 달간 고생한 걸 다른 분들이 겪지 않았으면 하는 마음에서 제 사례를 소개했습니다.

참고한 리소스

UCPC 2020을 개최했습니다

UCPC 2020 개최 후기

기회가 되어 올해 전국 대학생 프로그래밍 대회 동아리 연합전대프연 회장을 맡아 UCPC 2020을 개최했습니다. 2019 서강대학교 프로그래밍 대회에 이은 두 번째 대회 운영입니다.

전대프연은 알고리즘 문제해결을 좋아하는 25개 대학교의 26개 동아리의 연합이고, UCPC는 전대프연에서 매년 개최하는 프로그래밍 대회입니다. 보통 가을에 열리는 국제 대학생 프로그래밍 경시대회 한국 리저널의 연습 격 대회로 시작해서, 지금은 국내에서 열리는 프로그래밍 대회 중에서 커뮤니티 대회로는 가장 큰 규모를 갖고 있습니다.

왜 하겠다고 했나요?

대회를 코디네이트하는 건 힘듭니다. 그래서 선뜻 총대를 매겠다고 나서는 경우는 드물고, 실제로 3년 전엔 대회가 안 열린 적도 있었습니다. 4월이 되어도 아무도 대회 총괄을 하려는 사람이 없어 올해는 제가 열어보겠다고 했습니다. 저는 당시 휴학 무직 백수로 즐겁게 하루종일 뒹굴뒹굴 감자칩 먹으면서 매일 컴퓨터랑 눈싸움이나 하고 있었는데, 아마 휴학하고 있지 않았다면 상당히 바빴을 테니 나서지도 않지 않았을까 싶습니다.

인수인계를 받자마자 대회 기획을 시작하고, 출제자를 모집했습니다. 그러나 올해는 큰 문제가 있었습니다. 경우에 따라 기획의 근간이 바뀔 수도 있는 아주 큰 문제였습니다. 바로..

준비되지 않은 우리 앞에 성큼 다가와 버린 코로나 시대

코로나 큐

2020년을 살아가는 여러분께서는 모두 마음 속에 우선순위 큐 하나쯤을 갖고 계실 겁니다. 바로 코로나 시대가 끝나면 할 일이라는 이름의 우선순위 큐입니다. 저는 벌써 원소가 120개를 넘어가려고 합니다. 코로나 끝나면 여행 가야지, 코로나 끝나면 맛집 탐방 다녀야지, 코로나 끝나면 못 봤던 친구들 만나서 밥 먹어야지, … 분명 4월즈음에만 해도 큐가 이렇게 커질 거라고는 생각하지 못했습니다. 상황이 괜찮아질 줄 알았으니까요.

UCPC도 마찬가지였습니다. 대회가 열릴 7월즈음에는 상황이 괜찮아지겠지-라는 막연한 기대가 있었습니다. 그래서 오프라인으로 대회를 진행하려고 계획했습니다. 오프라인으로 개최하는 것이 좋은 이유를 나열해 보자면:

  • UCPC는 프로그래밍 대회 동아리 회원들의 교류와 경쟁의 장을 목표로 하고 있습니다.
  • 부정행위 검사가 힘듭니다. 참가자가 다른 팀 코드를 베꼈는지는 쉽게 알 수 있습니다. 하지만, 예를 들어, 3인 팀 대회인 UCPC에서 4인 이상의 팀원이 코드를 작성한다던가, (진짜 정말 극단적인 예시로) 대회 중에 tourist에게 문제 해법을 물어보고 이를 이용해 해결하는 등의 부정행위는 막기 힘드며 검사하는 것도 거의 불가능에 가깝습니다.
  • UCPC와 같은 규모의 대회에는 운영비가 많이 필요합니다. 그래서 스폰서의 도움이 절실합니다. 하지만 온라인으로 진행할 경우 오프라인으로 진행하는 것보다 스폰서에게 후원에 대한 메리트를 어떻게 줄 수 있을지 생각해내고 이를 어필하는 것이 상대적으로 어렵습니다.

반면 온라인으로 개최하는 것도 나름의 장점이 있습니다.

  • 예산에서 대관료를 고려할 필요가 없어집니다.
  • 대회장에 오지 않아도 됩니다. 지방에서 서울로 올라와서 참가하시는 분들의 경우 대회 참여를 위해 만 하루를 잡고 참가하시는 경우가 흔하다고 들었습니다. 이런 모든 비용을 절감할 수 있습니다.

분명 온라인 대회로 진행해서 얻을 수 있는 장점들도 있지만, 오프라인 대회로 개최하는 것의 장점이 훨씬 크리티컬했기에 할 수만 있다면 오프라인으로 진행하고 싶었습니다.

그러나 모두가 아시는 대로…

…하루 10명대였던 확진 판정은 갑자기 다시 30명, 40명, 80명이 되었고, 오프라인 대회로 개최할 경우 스태프가 방역을 책임질 수 없겠다는 생각이 들어 오프라인 개최를 포기하게 되었습니다.

정작 이 글을 쓰고 있는 시점에서는 일일 확진자가 100명 넘게 발생하고 있네요.

온라인이기 때문에 할 수 있는 것을 하기

그래서 할 수 있는 거라도 최대한 재밌게 해 보기로 했습니다. 일단 위에서 오프라인 대회의 장점으로 언급되었던 것들을 온라인으로 어떻게 살릴 수 있을지에 대해 먼저 고민해 봤습니다.

  • 교류와 경쟁의 장 제공 – 기존에 대회장에서 하던 풀이 방송과 스코어보드 방송을 Twitch 온라인 방송을 통해 진행하기로 합니다. 물리적인 공간보다는 덜하겠지만, 실시간 댓글을 통해 교류할 수 있게 됩니다.
  • 스폰서 어필 – 온라인 방송 중 방송 화면의 공간을 일부 활용해 스폰서 로고를 지속적으로 노출합니다. 스튜디오가 구해진다면 후원 세션을 참가자들이 가장 많이 볼 시간대인 대회 종료 직후 ~ 문제 해설 전에 진행합니다.

부정행위에 대한 고민이 가장 많았습니다. 대략 다음과 같은 의식의 흐름을 거쳤습니다.

  • 웹캠이 있으면 부정행위를 막을 수 있을까?
    • 웹캠이 있다고 해도 스크린에 카카오톡 같은 걸 띄우면 충분히 부정행위를 할 수 있지 않을까? 그럼 스크린 녹화도 필요할까?
    • 스크린 녹화를 하더라도 다른 장비가 있으면 충분히 부정행위를 할 수 있지 않을까?
    • 애초에 참가팀 50팀이 동시 접속할 수 있는 화상 채팅 서비스가 존재할까?
    • 존재한다고 하든 안 하든 우리가 그 화면을 전부 모니터링할 수 있는 여력이 있을까?
  • 웹캠은 힘들 것 같으니 카피 체크를 하자
    • 팀 간의 복붙은 막을 수 있겠지만 4명 이상이 한 팀으로 친 경우는 어떻게 막을 수 있을까?
    • 4명 이상이 한 팀으로 치지 않았더라도, 예를 들어 누군가 대회 중에 대회 문제를 random Codeforces red한테 물어봐서 푼다면? 어떻게 막을 수 있을까?
    • 그 코드는 언제 다 읽을까?
  • 결국 어떻게 해도 부정행위를 막을 수는 없는 거 아닌가?
  • 근데 어차피 부정행위 해서 높은 점수 받고 못 보던 사람이 스코어보드 위에 있는 상황이 발생하면 다 티나지 않을까?

결론은 PS 커뮤니티를 믿고 코드 카피 체크 이외의 별도의 부정행위 검사를 하지 않는 것으로 났습니다. 커뮤니티 대회였기에 가능했던 결정이었습니다. 큰 상금이 걸린 기업 대회였다면 이런 상황에서 상당히 곤란했을 것입니다.

인터넷 방송

Twitch Sports: Getting Started | Twitch Blog
인터넷 방송 플랫폼 트위치

그렇게 결정하고 나니 인터넷 방송이 대회 기획에서 출제와 검수를 제외한 가장 중요한 요소가 되었습니다. 프로그래밍 대회에 많이 참여해 보셨고 (무려 ICPC 월드 파이널!) 관련 스트림도 자주 하시는, 세계적인 인기를 자랑하는 월클(World Class) 스타 정재헌Gravekper님께 참여해주실 수 있는지 여쭸고, 흔쾌히 승낙해 주셔서 함께 온라인 방송을 기획하게 되었습니다.

방송에서 뭘 다루면 좋을지, 방송을 언제부터 켜면 좋을지, 화면은 어떻게 구성하면 좋을지 등등을 대회 직전까지 열심히 논의했습니다. 인터넷 방송에는 문제 풀이, 스코어보드, 후원 세션은 필수로 들어가야 했고, 이외에 대회에 참여하는 사람들도, 참여하지 않는 사람들도 모두 볼 수 있다는 점을 감안하면서 대회 종료 전에 뭘 하면 좋을까를 고민했습니다. 이에 온라인 방송이 있는 다른 대회들을 참고했습니다.

  • ICPCIOI는 대회 중에 실시간 스코어보드와 문제 해설을 보여줍니다. ICPC 방송은 생각보다 재밌습니다. 그래서 사실 제가 하고 싶었던 이상에 가까웠던 방송 형태이긴 하나, 온라인 대회이고 웹캠 사용을 포기했기 때문에 화면에 보여줄 수 있는 게 없었고, UCPC 방송은 대회 참가자들도 볼 수 있는 방송이었기에 문제 해설도 보여줄 수 없었습니다.
  • 반면 Google Hash Code 방송은 참가자들이 대회 중에 시청할 수 있습니다. 그래서 대회 시작 전후에만 방송을 하고, 대회 중에는 아무것도 보여주지 않습니다.

하지만 대회 중에 아무것도 보여주지 않으면 심심하기 때문에 간단히 스코어보드를 띄워 두기로 결정했습니다.

문제 풀이와 후원 세션도 걱정이었습니다. 지금까지 UCPC 풀이는 출제자가 강단에 나와 슬라이드를 보여주는 식으로 진행했고, 후원 세션도 마찬가지였습니다. 근데 올해는 어쩌죠?

다행히 감사하게도 작년에 이어 고려대학교 SW중심대학사업단에서 장소를 제공해 주셔서, 고려대학교 정보대학의 대형 강의실 하나를 스튜디오로 사용할 수 있었습니다. 기존처럼 출제진이 강단에서 슬라이드로 발표하고 이를 카메라로 찍어 방송할 수 있었습니다.

출제와 검수

코로나 시대가 되어도 프로그래밍 대회에서 변하지 않는 것은 바로 출제와 검수입니다. 올해는 제가 여름에 회사에 갈 걸 우려해 대회 준비를 일찍 시작했습니다. 출제진은 우리나라 최대의 알고리즘 문제해결 커뮤니티인 BOJ Slack에서 모집했고, 이후에 추가로 call for tasks를 통해 문제 공모를 받았습니다. 올해는 공모받은 문제가 많아 출제진 풀이 상당히 컸습니다.

슬랙

기획을 포함해 모든 소통은 Slack으로 진행했습니다. Slack의 (무료 버전의) 최대 단점은 메시지가 10,000개 이상 쌓이면 이전 메시지들은 하나씩 못 보게 된다는 것인데요, 마침 코로나로 인해 Slack에서 3달간 무료로 Standard Plan을 제공해 주고 있어서 고민 없이 사용했습니다.

문제마다 하나의 채널을 만들어 최대한 맥락을 잃지 않고 대화할 수 있도록 했습니다. 또한 대회 전반적인 공지를 올릴 #general 채널, 인터넷 방송을 기획할 #broadcasting 채널, 컨테스트 도중 생기는 라이브 이슈에 대응할 #contest-finals / #contest-preliminaries 채널 등을 필요에 따라 주제 단위로 만들어 활용했습니다.

Zapier

특히 박수찬tncks0121님의 도움을 받아, Slack과 Zapier 연동을 사용해 call for tasks로 메일을 받으면 메일 내용을 자동으로 Slack 채널에 포워딩해 주도록 설정할 수 있었습니다. 다만 Zapier의 문제인지 후술할 UCPC 메일서버 문제인지는 모르겠지만 메일이 몇 개 누락되는 경우가 생겼습니다. 이런 경우엔 제가 UCPC 메일함에서 직접 공모받은 문제를 출제 채널에 배달해야 했습니다.

구글 드라이브

출제/검수 현황과 문제 자료 관리 등에는 Google Drive를 사용했습니다. G Suite에 제공되는 기능인 공유 드라이브를 적극적으로 활용했습니다.

출제

대회 분위기 정하기

출제 초기에는 예선과 본선 각각의 적절한 난이도 커브를 결정해 주는 것이 중요합니다. 문제들이 너무 쉬우면 대회 중에 문제를 전부 해결하는 팀은 대회가 끝날 때까지 할 게 없어서 심심해지고, 반대로 너무 어려우면 문제들에 압도당한 팀들이 좌절하게 되기 때문입니다. 그래서 먼저 난이도 커브를 정하고, 이에 맞춰서 어떤 문제를 내야 할지, 문제 풀에서 어떤 문제는 사용하고 어떤 문제는 사용하지 말아야 할지 등을 결정할 수 있습니다. 작년 서강대 대회 출제 후기에서 언급했던 것이기도 합니다.

UCPC 2020 출제 현황 시트 – 블로그 글의 이해를 돕기 위해 연출되었습니다

이와 관련해 작년 UCPC와 올해 UCPC의 가장 큰 차이는 문제의 난이도를 가늠할 수 있는 수단인 solved.ac의 존재였습니다. 서울 리저널의 난이도 분포를 참고해서 문제 풀에 있는 문제들의 난이도들을 각자 가늠해 보고, 예선과 본선 중 어느 쪽에 사용할지 플로우를 잘 돌렸습니다. 또한 시트에 추가적으로 알고리즘 분류를 적어 넣어, 한 분야에 너무 치우친 컨테스트가 되지 않도록 문제 배치를 잘 해주었습니다. 다만 검수 과정에서 난이도와 분류 정보를 보는 것은검수에 악영향을 끼칠 수 있어서 해당 시트는 출제진만이 편집했고, 검수 현황 시트를 따로 만들어 두었습니다.

문제 난이도를 가늠하는 현장

Call for tasks로 공모받은 문제들도 이렇게 출제진끼리 난이도를 가늠해 보고 대회에 필요하리라 생각된 문제들을 채용했습니다. 공모받은 문제들과 내부에서 출제한 문제들이 많아서 아쉽게도 사용할 수 없게 된 문제가 많았습니다.

디스크립션과 데이터 작성

Polygon

데이터의 무결성을 최대한 보장하기 위해 디스크립션 작성을 제외한 모든 작업은 Polygon에서 testlib을 사용해 진행했습니다. Polygon 서버가 다소 불안정해서 조마조마한 상황이 몇 번 있었고, 패키지 전체를 자주 백업했습니다.

solved.ac Overleaf

문제지는 solved.ac 서버에 올라가 있는 비밀의 시크릿 프린세스 self-hosted Overleaf에서 작업했습니다.

디스크립션데이터 작성에 있어서는 대회 참가자가 문제 디스크립션을 이해하거나 기타 문제에서 중요하지 않다고 생각되는 이슈들을 해결하는 데 시간을 소비하지 않도록 하게 하기 위해 다음 원칙에 따라 UCPC 출제 컨벤션을 만들고 이를 최대한 지키려 노력했습니다.

  • 일부러 디스크립션을 이해하기 어렵게 하는 컨셉의 문제가 아닌 경우, 디스크립션은 한 번만 읽어도 이해할 수 있을 정도로 이해하기 쉬워야 하며, 디스크립션이 문제 해결을 방해해선 안 됩니다.
    • 같은 맥락에서 어려운 수학 기호 및 개념은 가능할 경우 최대한 사용하지 않습니다. 갓 고등학교를 졸업한 사람이 봐도 이해할 수 있는 수준이어야 합니다. 이를테면, ‘$A$의 모든 원소들의 제곱의 합’이라고 적을 수 있는 것을 굳이 ‘$\sum_{a\in A} a^2$’라고 적지 않습니다.
    • 글과 문자가 쉽게 구분되면서 문자가 글을 읽는 데 방해가 되는 일이 없도록 해야 합니다. 따라서 모든 문자는 기울임꼴로 작성하고, 수식에는 띄어쓰기를 잘 하며, 기호는 정확한 것을 사용해야 합니다.
  • 입출력 변수의 범위는 입출력 섹션에 한꺼번에 명시하는 것이 가장 좋습니다.
  • 데이터는 무결해야 합니다. 명시한 형식과 다른 데이터가 있어서는 안 되며, 입력 데이터에 대한 정답이 아닌 데이터가 출력 데이터로 되어 있어서는 안 됩니다.
  • 생소한 입출력 방법 등으로 참가자가 고생하는 일이 없어야 합니다. 특히 EOF로 출력의 끝을 명시하는 입력 데이터들이 그렇습니다.

또한 디스크립션을 굳이 Polygon에서 작업하지 않은 이유가 있다면, BOJ의 문제 출제 플랫폼인 BOJ Stack의 존재 때문입니다. BOJ에서 대회를 개최하기 때문에 대회 전에 문제들을 전부 BOJ로 옮겨야 하는데요, 대회 직전에는 디스크립션 수정이 잦습니다. 근데 Polygon에서 디스크립션을 관리하게 되면 어차피 만들어야 하는 문제지에서도 디스크립션을 수정해야 하고, BOJ Stack에서도 디스크립션을 수정해야 합니다. 또한 BOJ Stack에서는 LaTeX을 최대한 쓰지 말아달라고 하기 때문에 TeX로 작성한 문제들을 전부 HTML로, 이를테면 $1 \leq N, M \leq 200\ 000$ $1 \leq N, M \leq 200\ 000$과 같은 식은 1 ≤ N, M ≤ 200 1 &le; <em>N</em>, <em>M</em> &le; 200 000으로 다시 포맷해야 하는데, 이는 생각보다 상당히 고통스럽습니다. 이런 공수를 줄이고자 Overleaf에서만 디스크립션을 관리했습니다.

물론 HTML로 포맷하는 공수조차 줄이고자 그냥 모든 문제에 TeX을 사용했습니다. 이렇게 할 경우 Overleaf에서 Stack으로 문제 본문을 복사+붙여넣기 하면 세팅이 끝납니다. 참 쉽죠.

문제 삽화가 그려지는 과정

문제와 해설에 사용될 그림의 경우, 그림을 요청하는 채널을 따로 만들어서 출제진의 요청을 받고 제가 그림을 열심히 제작했습니다.

마지막으로 정해는 ICPC 경향에 맞춰 C++과 Kotlin(또는 Java)으로 모두 작성했고, 해당 언어들로 문제를 해결 가능함을 보장했습니다.

검수

문제 초안이 완성되면, 문제를 검증하게 됩니다. 주로 다음과 같은 항목들을 검증해야 합니다.

  • 데이터와 디스크립션의 포매팅이 올바르고well-formed 무결한지 (UCPC 컨벤션을 지키는지)
  • 출제자의 풀이가 완벽한지
  • 출제자가 의도하지 않은 풀이로 풀리지는 않는지, 출제자가 의도하지 않은 풀이로 풀렸다면 그 풀이도 정답으로 허용할 것인지

검수진은 바로 위와 같은 항목들을 꼼꼼히 확인하는 역할을 합니다. 출제진들 사이의 교차 검수crosschecking 이외에도 외부 검수진을 모셔 와 검수를 진행했습니다.

검수의 흔적

참가팀들이 틀린 방법으로 접근할 것 같은 풀이(‘사풀이’라고도 합니다)를 미리 예상하고, 이를 적절히 막습니다. 방법은 여러 가지입니다. 예를 들어,

  • 어떤 자연수 $N$이 소수인지 판별해야 하는 문제에서, $N=1$이 입력으로 들어오는 경우를 제대로 처리하지 못하는 코드들을 틀리게 하기 위해 $N=1$인 데이터를 준비할 수 있습니다. (예외 처리 데이터)
  • 혹시라도 고려하지 못한 경우가 있을 수 있으니 랜덤에 의존해 제작한 일반적인 데이터를 추가로 더 준비할 수 있습니다.
  • 아예 틀린 방법으로 문제를 해결하는 코드가 준비한 데이터를 운좋게 전부 통과하는 경우가 있다면, 틀린 방법으로 풀면 틀리거나 시간 초과를 받는 데이터를 준비할 수 있습니다. (반례 데이터)
  • 출제자가 의도한 풀이보다 훨씬 쉬운 풀이로 풀리는 경우 시간 제한을 조정하거나 문제에 등장하는 상수들의 제한을 조정할 수도 있습니다. 의도한 풀이로 접근하면 풀리지만 의도하지 않은 풀이로 접근하면 시간 초과를 받도록 적절히 제한을 조정합니다.

등과 같은 과정을 거쳐 문제를 완벽하게 만들었습니다.

다들 모여

이 참가자는 WA를 받고 생존한 후에 다른 참가자를 소환합니다.

재작년과 작년의 참가 조건이 마음에 들었고, 그대로 유지했습니다. 석박통합과정 학생의 참가 조건만 명확하게 정했습니다.

  • 3명이 1개 팀으로 참가해야 함
  • 학부생이라면 재학과 휴학을 불문하고 참가 가능
  • 대학원생이라면 석사과정 또는 석박통합 2년차까지 참가 가능
  • 다른 학교 구성원끼리 팀을 이루어 참가 가능

수상 경력에 따라 제한 조건을 둘까도 생각해 봤는데, UCPC는 역시 한국 최강자전의 컨셉인 것도 있는 것 같아 딱히 두지 않았습니다. 총 299팀이 예선대회에 참가를 신청해 주셨습니다.

매년 하던 것처럼 Google Forms를 이용해 참가 신청을 받고 GMail을 통해 공지사항을 전송했는데, 대회 규모가 커지면서 이 방법을 계속 사용하기엔 다소 무리가 있는 것 같다는 생각을 했습니다.

  • 참가자 중 메일 주소에 오타를 낸 참가자들이 몇몇 계셨습니다. 실제 예시로, nvaer.comnaver.com, gamil.comgmail.com, kaist.co.krkaist.ac.kr 등으로 도메인에 오타를 낸 메일 주소들을 확인할 수 있었고, 제 수작업으로 고쳤습니다. 도메인 오타는 어찌저찌 고칠 수 있는데 @ 앞 부분에는 과연 오타가 없었을까요? 이메일 인증에 기반한 서비스를 사용하거나, 이를 직접 구현해야겠다고 느꼈습니다.
  • 예선 계정 정보 메일 299개를 하나하나 작성해 보냈습니다. 또한 GMail에 일일 전송 메일 수 제한이 있다는 사실을 이 대회 운영하면서 처음 알았습니다. 이 때 대량 자동 메일 전송 시스템을 구축했어야 했는데, 그러지 못했던 것이 후술할 예선대회 대참사로 이어집니다.

예산 확보

출제자 분들과 검수자 분들께 노력에 대한 합당한 대우를 드리고, 참가자 분들께 상을 드릴 수 있도록 예산을 정했습니다. 온라인 대회였기 때문에 장소나 비품, 식사 등에 대한 고려는 할 필요가 없다고 생각했으나.. 오산이었습니다. 온라인 방송을 할 장소와 장비가 필요했고, 상품이 있다면 상품을 배송할 비용도 필요했습니다. 대관료와 장비, 배송비 등을 종합해 보니 온사이트로 치뤄진 예년 예산만큼은 못해도 상당히 무거운 예산이 나왔습니다.

감사하게도 대회를 열겠다고 하자마자 케니소프트, 알고스팟, 스타트링크, 그리고 고려대학교 SW중심대학사업단에서 후원 의사를 보내 주셨습니다. 이후에도 여러 개발 기업에 무작정 메일을 보냈고(…) 마인즈랩네이버 D2에서 출제와 검수 비용을 지원해 주셨습니다. 대단히 감사합니다! (solved.ac의 경우 사실상 제 개인 후원이기 때문에 논외로 합니다)

온라인 대회여서 기존의 후원 세션을 기존처럼 진행할 수 없어 어떻게 어필할 수 있을까 고민했습니다만, 오히려 온라인 대회이고 공개된 온라인 방송으로 대회를 진행하기 때문에 굳이 참가자가 아니더라도 대회 방송을 볼 수 있고, 따라서 알고리즘 문제해결에 대한 충분한 관심이 있는 시청자들에게 기업을 홍보할 수 있다는 점을 어필하기로 했습니다.

사실 출제와 검수는 이전에 서강대 대회를 총괄해 본 적이 있었기에 어느 정도 익숙한 부분이었습니다. 하지만 서강대 대회는 학과 사업이어서 후원사를 구할 필요가 없었던 반면 UCPC의 경우에는 우여곡절이 많았고, 실수도 했습니다.

가장 큰 실수는 후원 조건을 명확하게 정하지 못했고, 또 이를 후원사에 제대로 공유하지 못했던 것이었습니다. UCPC에서는 홍보 기업 발표 세션을 진행하는데, 온라인 방송으로 홍보 세션을 진행하면 참가자들이 도중에 방송을 이탈해 효과가 반감될 것을 우려하여 후원 조건 금액을 높게 정했습니다. 그러나 죄송하게도 다른 바쁜 일들에 정신이 팔린 제 불찰로 인해 이를 공유받지 못한 후원사가 계셨습니다. 다음 대회부터는 이번 일을 반면교사로 삼고, 가능하다면 파이콘의 예처럼 후원 조건을 합당하고 명확하게 정하고 홈페이지에 공지하며 후원사와 긴밀히 소통할 수 있도록 해야겠습니다.

후원 기업들에 다시 한 번 무한한 감사를 드립니다.

예선 방송 리허설(7월 23일): 폭풍전야

대회 전에 리허설을 통해 방송 진행 계획을 구체화했습니다. 운영진들과 함께 안암의 명물 고고 인디안 쿠진에서 카레를 먹고, 대회 중 스튜디오로 사용될 고려대학교 정보대학 강의실에 숭고한 연합대회가 진행되는 도중 급습해 모여 강의실의 배치와 장비 등을 확인하고, 인터넷 속도는 방송을 송출하기에 충분한지, 강의실 구조 상 풀이 and/or 후원 세션은 어떻게 하면 좋을지 논의했습니다. 관련해서는 가장 고민을 많이 하신 재헌님의 UCPC 2020 방송 후기를 참고하시면 좋습니다.

OBS가 브라우저 화면을 겹쳐 띄워 둘 수 있다는 것을 이용해 기획한 대로 제가 대회 직전(당일 새벽 3시까지!)에 React로 간단하게 방송 씬을 만들었습니다. 코드는 여기 올라와 있습니다.

예선(7월 25일): 이 곳이 어둠의 기운으로 가득차 곧 무슨 일이 일어날 듯 합니다

방송 씬을 만드느라 날을 새고 10시에 고려대에 도착해서 세팅을 시작했습니다. 운영진들은 과연 올솔이 몇 팀이나 나오고 언제 제일 먼저 나올까 내기를 합니다.

막상 대회 시간이 다가오니까 대회 진행 플랫폼인 BOJ가 500 Internal Server Error와 502 Bad Gateway 에러를 뱉기 시작합니다. 어…? 이대로는 대회를 정상적으로 진행할 수 없겠다 싶어 대회 시작을 14:10으로 10분 연기했습니다.

그런데 좀 잠잠해지나 싶더니 14:07쯤 되니까 같은 현상이 다시 일어나는 거였습니다. 10분을 더 연기할까 고민하고 있던 찰나, BOJ Stack도 먹통이 되었습니다. 대회 정보는 BOJ Stack이라는 관리 페이지에서 수정해야 합니다. BOJ Stack이 접속이 막히면 운영진도 대회 시간을 수정할 수 없습니다.

Media Tweets by Haachama Sukidesu (@Haachama_Suki) | Twitter

’14:20에는 괜찮아지겠지? 그럼 종료 시간을 10분쯤 연장해야겠다’고 생각했습니다. 서버는 비웃기라도 하듯 계속 접속을 거부했습니다.그런 와중에 UCPC 관련 메일 아래에 적혀 있던 제 전화번호로 참가팀들의 전화가 걸려오기 시작했습니다. 운영진도 대회 서버에 접속할 수 없는 상황임을 알려 드렸습니다.

이제는 대회를 어떻게 할지 빠르고 공정하게 결정해야 했습니다. 특히 여러 지역에서 모여서 대회를 치기 위해 스터디룸을 빌리는 팀이 많다고 알고 있어, 이 분들의 피해가 최소화되도록 하려면 어떻게 해야 하나 고민했습니다. 그 와중에 대회 사이트에서 문제 제목을 읽은 팀이 있다는 제보를 받았습니다. 문제 제목을 읽은 팀이 있었다는 것은 문제를 읽은 팀이 있었을 수 있다는 뜻도 되므로 신중하게 결정해야 했습니다.

정말 다행히도 이번 UCPC는 온라인 대회였기에 공간의 제약을 받지 않았고, 본선에 몇 팀이 출전하더라도 수용할 수 있었습니다. 그래서 아예 기업 대회 Qualification 라운드의 형식으로 본선 커트라인을 명시하고 시간을 대폭 연장하기로 결정합니다. 그리고 단체 메일을 보냈습니다.

그런데, 감사하게도, 구글이 제가 아이패드(구글 계정 입장에서는 ‘새로운 기기’)로 대량의 메일을 보내려는 시도를 감지하고 전대프연 계정을 차단시켰습니다. 제가 회장이 되면서 바꾼 비밀번호로는 로그인이 안 됐고 이전 비밀번호로 인증을 받아야 했는데, 무려 제 전전전임 회장께서 설정하신 비밀번호였습니다. 당장 연락을 드렸지만 회신을 무작정 기다릴 수도 없는 상황이었어서, 제 개인 메일으로 단체 공지와 문제지를 전송했습니다. 이 때가 오후 3시였습니다.

서버 상황은 오후 4시를 즈음하여 개선되었고 코드를 제출할 수 있는 상황이 되었습니다. 예선대회에서도 해설과 스코어보드 공개를 할 예정이었고, 이를 위해 출제진들이 모여 있었으나, 안타깝게도 이후 방송은 진행하지 못했습니다. 여러모로 아쉬웠습니다. 예선 당일 서버 사고가 일어났던 이유는 여기에서 읽을 수 있습니다.

결과적으로 본선 진출 팀은 총 170팀이 되었고 의도치 않게 역대 최대 규모의 본선이 되었습니다. 컷을 5문제로 잡았으면 좋았겠다는 의견도 많았으나 안타깝게도 결정 당시에는 출전 팀들의 실력을 가늠하기 힘들었습니다.

본선도 규모가 예선 못지않게 커져버렸고, 본선대회에서도 같은 일이 되풀이되면 안 되었기에 만반의 준비를 했습니다. 우선 스타트링크와 함께 이런 일이 일어난 원인을 분석하고 당시 일어났던 상황이 재발되지 않게 하기 위한 기술적 조치를 취했습니다. 본선도 BOJ에서 치루는 것으로 결정했으나, 혹시 모를 사태에 대비하기 위해 UCPC 운영진도 DOMjudge 서버를 직접 구축해 대비했습니다.

본선(8월 1일):

이미지
대회 본부

정말 다행이게도 본선대회는 아무 문제 없이 순조롭게 잘 진행되었습니다.

서버 대비와 별개로 본선대회를 위해 준비한 것들이 몇 개 더 있었습니다. 그 중 가장 눈여겨볼만했던 건, 대회 중에도 공지했던 바 있지만, 이번 UCPC는 스코어보드 공개의 재미를 위해 프리즈 기준을 다소 특이하게 잡았던 것이었습니다.

프리즈 시간은 대회 종료 60분 전이었으나, 프리즈 시간과 관계없이 어떤 팀이 9문제를 해결한 순간 이후 그 팀의 모든 제출이 비공개되는 식이었습니다. 이를 위해 BOJ에서 스코어보드를 제공하지 않고 scoreboard.ucpc.me라는 별도의 사이트에 스코어보드를 띄웠습니다. 박수찬tncks0121님께서 운영자 스코어보드의 모든 제출을 $n$초마다 가져와서 가릴 건 가리고 공개 스코어보드에 보여주는 파이썬 스크립트를 짜 주셔서 가능했던 일이었습니다.

풀이는 원래 라이브로 방송하려 했으나, 풀이 슬라이드가 대회 중에 완성되기도 했고, 진행을 비교적 여유롭게 하기 위해 녹화방송으로 바꿔 진행했습니다. 풀이 슬라이드가 방송에서 사용한 것과 공개된 것이 다른데, 방송에서의 풀이 슬라이드는 출제진이 생각한 난이도 순서대로 문제가 정렬되어 있고, 공개된 풀이 슬라이드는 A, B, C.. 순입니다. 특별한 이유가 있다면 공개 슬라이드에서는 풀이가 필요한 문제를 더 빨리 찾게 하기 위함이었습니다.

본선 해설 및 스코어보드 공개 영상

본선대회를 성공적으로 종료하고 저를 제외한 운영진은 고기를 맛있게 먹으러 갔다고 합니다. 저는 안타깝게도 당일 너무 피로해서 그냥 집에 와서 곯아떨어졌습니다. 비극적인 엔딩이네요.

어땠나

힘들지만 의미있는 경험이었다고 말하면 식상할까요?

힘들었던 것들

전대프연 회장을 하는 것은 힘든 일이라고 익히 들어서 알고 있었지만 구체적으로 어떤 게 힘든 일인지는 잘 몰랐습니다. 이제 대략 알게 되었습니다.

  • 후원사를 구하기가 상당히 힘들었습니다. 온라인이어서 더 그랬습니다. 올해 ICPC도 후원 사정이 좋지 않다는 걸 생각하면 어디나 비슷한 것 같습니다. 그래서 개인적으로 옆 나라 리저널의 후원 사정이 꽤 부러웠습니다.
  • 상금 처리라던가 참가 상품을 택배로 보내야 했던 것도 힘든 점 중 하나였습니다.
  • 6월 말에 넥슨코리아 엔진스튜디오에 산업기능요원으로 입사하게 되었습니다. 6월까진 무직 백수여서 몰랐는데, 대회 코디네이팅과 왕복 3시간의 출퇴근 생활을 병행하는 것은 체력적으로 상당히 힘든 일이었습니다. 회식 도중에 나와서 대회 개최를 준비했던 적도 있습니다.
  • 이외에는, 참가자 등록이 번거로웠습니다. 특히 재학증명서와 휴학증명서 등을 일일이 확인하는 작업이 너무 번거롭고 힘들었습니다.
후원사 구하기와 재학증명서 처리는 사천왕 중에서도 최약체…

그렇지만 저는 온사이트 대회를 준비했던 건 아니었기 때문에 다른 해보다는 비교적 쉽게 준비한 것이 아닌가 싶습니다.

놓쳤던 것들

대회 중에 발생한 이런저런 예외적인 상황들에 대해 제대로 and/or 빠르게 대처하지 못했던 게 아쉬웠습니다. 앞서 언급했던 것들만 다시 언급하자면, 가령…

  • GMail은 하루 발신 제한량이 있었고, 제가 shiftpsh.com과 ucpc.me 도메인으로 발신하기 위해 개인적으로 월정액을 내고 사용했던 메일서버에도 마찬가지로 하루 발신 제한량이 있었습니다.
  • 사소하게는 call for tasks 메일 계정과 Slack을 연동시켜 주는 Zapier 스크립트가 간헐적으로 동작하지 않는 문제가 있어서 공모받은 문제를 확인하지 못할 뻔 하기도 했습니다.
  • 이메일 주소를 이메일 확인 등의 방법으로 검증하지 않아 메일 전송 과정 중에서도 누락되는 메일들이 발생했습니다. Google Forms를 사용하는 대신 직접 대회 등록 사이트를 만들었다면 좋았을 것입니다. 위의 이유와 맞물려 메일을 자동으로 발송해 주는 시스템이 있었다면 더 좋았을 것입니다.
  • 대회 서버가 다운되었을 때 의논할 시간이 부족한 상황에서 대회 진행 형식을 결정해야 했습니다. 이런 상황이 발생했을 때는 미리 어떻게 하면 좋겠다는 계획을 세웠더라면 참가자들의 피해와 스트레스를 줄일 수 있었을 것입니다.
  • 방송 계획과 대본을 미리 짜놓지 못해 다소 매끄럽지 못하게 진행된 것 같아 아쉬웠습니다.
  • (이건 예외적인 상황은 아니었고, 제가 정신없어서였지만) 제 불찰로 후원사와의 소통이 제대로 진행되지 못한 부분이 있었고, 안타깝게도 이로 인해 다소 불미스러운 일이 발생했습니다.

UCPC는 이제 예선 기준으로 참가 인원 1,000명을 바라보고 있을 정도로 커진 대회입니다. 코딩 테스트 열풍으로 인해 알고리즘 문제해결 및 경쟁 프로그래밍 입문자들이 갈수록 많아지고 있고, 이런 기조가 사그라들지 않는 한 대회 규모는 계속 커질 것으로 생각됩니다. 이런 규모의 대회라면, 이런 규모의 대회에서 일어날 수 있는 갖가지 상황들을 미리 파악하고 숙고하여 대비하는 것이 옳겠다고 뒤늦게 느낍니다.

그럼에도 좋았던 것들

우여곡절도 많았지만 전대프연으로써는 처음 시도했던 온라인 대회를 성공적으로 마무리할 수 있어서 뿌듯합니다. 코로나 시국도 프로그래밍 대회는 이기지 못했네요. 😎

대단하고 멋진 분들과 함께 최고의 커뮤니티 대회를 만들 수 있어서 즐겁고 뿌듯했습니다. 온라인 대회여서 안타깝게도 참가자 분들과는 만나지 못했지만요.

그래서 회장 1년 더 하나요?

이 팀은 사실 시프트를 제외한 레드시프트 팀인데, 제가 대회 같이 안 치고 혼자 운영하러 가서 삐진 나머지 이름을 이렇게 지었나 봅니다

사실 UCPC 2020 직후에도 SUAPC에서 운영과 출제를 했고, 신촌 캠프 대회와 SNUPC에서도 검수 및 조판으로 참여했습니다. UCPC에서 얻은 경험과 리소스가 상당히 많은 도움이 되었습니다.

운영진 16콤보

하지만 내년에도 회장을 할지는 잘 모르겠습니다. 일단 이제 직장에 다니고 있기도 하고, 무엇보다 결정적으로 휴학생 팀으로 나간 ICPC 2020 인터넷 예선에서 너무 처참한 성적을 받았기 때문입니다.

여러 대회를 운영하고 출제하고 검수하느라 바빴고, 게다가 solved.ac 개발로도 바빴던 나머지 제가 문제해결 연습을 할 시간이 부족해져서라고 생각했고, 지금은 다시 팀 연습도 하고 코드포스도 자주 나가고 BOJ 문제도 열심히 풀고 있습니다. 내년 대회에는 참가자로서 참여하고 싶습니다. 복학할 때 적의환향赤衣還鄕해서 레드시프트 이름값 해야죠.

이런 현실이… 이런 현실이 있단 말이냐?

결론은 내년 전대프연을 이끌어 주실 분을 모십니다. 뭐 없으면 어쩔 수 없고…

마치면서

전대프연과 UCPC에 특별한 관심을 갖고 지원해 주신 고려대학교 SW중심사업단, 마인즈랩네이버 D2, 그리고 알고스팟구종만님과 케니소프트박현민525hm님께 깊은 감사를 드립니다. 특히 예선 서버 문제로 새벽 코딩을 불사하며 끝까지 이슈 해결을 위해 수고해 주신, 전대프연의 초대 회장이자 이제는 스타트링크최백준baekjoon님께 각별한 감사를 드립니다.

검수는 물론 대회 운영 전반에 있어서 기술적으로 많은 도움을 주신 박수찬tncks0121님, 훌륭한 문제를 출제해 주신 김동현kdh9949님, 김창동sait2000님, 나정휘jhnah917님, 노영훈Diuven님, 모현ahgus89님, 문창현ckdgus2482님, 반딧불79brue님, 배근우functionx님, 심유근cozyyg님, 이동관windflower님, 이상헌evenharder님, 이종영moonrabbit2님, 정기웅QuqqU님, 조창민Ronaldo님, 그리고 열정적으로 검수해 주신 류호석rhs0266님과 홍은기pichulia님께 진심으로 감사의 말씀을 드립니다.

이외에도 대회 막바지에 운영에 큰 도움을 주신 공인호inh212님, 김영현kipa00님과, 실험적인 형태의 대회임에도 대회 진행자를 흔쾌히 맡아 주신 정재헌Gravekper님께도 대단히 감사드립니다.

마지막으로, UCPC 2020에 참가해 주신, 알고리즘 문제해결을 사랑해 주시는 참가자 여러분께 감사드립니다.


대회 리소스

다른 프로그래밍 대회를 개최하시는 데 도움이 될 수 있도록 UCPC 2020에서 사용된 자료들을 인터넷에 공개했습니다.

오픈소스

  • ucpcc/ucpc2020-site UCPC 2020 대회 사이트
    Jekyll로 제작한 정적 사이트입니다. 대회 공지사항 등을 적기 위해 만들었습니다.
  • ucpcc/problemsetting-guidelines UCPC 디스크립션 작성 및 포매팅 컨벤션
    UCPC 문제 제작을 위해 수립한 컨벤션입니다. 일관적인 데이터와 디스크립션 작성에 도움을 줄 수 있습니다.
  • ucpcc/ucpc2020-description-layout UCPC 2020 문제지 레이아웃
    마개조된 olymp.sty입니다. 2019 서강대학교 프로그래밍 대회 문제지 레이아웃을 바탕으로 제작했습니다.
  • ucpcc/ucpc2020-solutions-theme UCPC 2020 솔루션 Beamer 테마
    Beamer와 함께 사용할 수 있는 테마입니다.
  • ucpcc/ucpc2020-broadcast-scene UCPC 2020 방송 씬
    OBS가 씬에 웹 브라우저를 사용할 수 있다는 사실에 착안하여 React로 제작한 16:9 방송 씬입니다.

공유 문서

  • UCPC 2020 문제 출제 현황 시트
    대회 운영에 활용했던 출제 현황 시트 레이아웃입니다. 운영 당시 그대로의 시트는 아니고, 이해를 돕기 위해 체크박스 상황은 연출했으며 미사용 문제들은 다른 곳에서 사용될 수 있으므로 관련 정보를 지웠습니다. 사용하고자 하실 경우 파일 > 사본 만들기를 누르면 수정 가능한 사본을 만들어 사용해 주세요.

다른 글