모스크바 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에 대해 어떻게 생각하시는지 댓글로 알려주세요!

조율자의 손길: 한별포스 이벤트를 돌아보며

solved.ac를 운영하면서 다양한 채널에서 사이트에 대한 의견들을 모으는 편입니다. 특히 그 중에서도 트위터 맞팔 분들께서는 저에게 창의적인 기능 아이디어들을 추천해 주고 계신데요, 몇 개만 봅시다.

솔브드 테라버닝
솔브드 1주년 코인샵
솔브드 스타포스

그래서 직접 만들어 봤습니다.

한별포스

2022년 4월 1일 정오부터 만우절 대회인 진짜 최종 구데기컵 2 2가 끝날 때까지 프로필 닉네임 위에 별을 25개 띄워봤습니다. 이게 대략 무슨 뜻인지 아시는 메이플 유저 분들께서는 대체 이게 왜 여깄지 하면서 당황하셨을 것 같습니다. 모르시더라도 마우스를 올리면 밑줄이 떠서 되게 클릭하고 싶게 만들었기 때문에 한번쯤은 클릭해보셨을 것 같아요. 이걸 클릭하면 한별포스 이벤트 페이지로 갑니다.

한별이

‘스타포스’라는 이름을 그대로 쓸 수는 없고…, solved.ac 길라잡이에 등장할 캐릭터 ‘한별이’의 이름을 빌려왔습니다. 귀엽지 않나요? 카카오 이모티콘으로 쓸 수 있어요.

여하튼 한별포스는 메이플스토리의 스타포스를 거의 그대로 가져온 이벤트였습니다. 프로필을 강화할 수 있습니다. 강화하면 프로필 위에 뜨는 별의 갯수가 변하는 것 이외엔 아무 일도 일어나지 않습니다.

스타포스?

스타포스 강화가 어떻게 돌아가는지를 요약해보면 이렇습니다.

  • 강화에 성공하면 별이 하나 늘어납니다.
  • 실패에는 세 가지 경우가 있습니다.
    • 별 개수가 유지됩니다. 10성까지에서 강화 시도에 실패한 경우 무조건 유지되며, 15성과 20성에서 실패한 경우에도 파괴되지 않았다면 무조건 유지됩니다.
    • 별이 하나 줄어듭니다. 10성까지 그리고 15성과 20성에서 강화 시도에 실패하는 경우에는 일어나지 않습니다.
    • 장비가 파괴됩니다. 12성 이상에서 강화를 시도하는 경우 드문 확률로 일어납니다. 이후 같은 장비를 준비해 장비를 복구할 수 있으며, 12성부터 다시 시작합니다.
  • ‘스타캐치’라는 미니게임을 통해 성공 확률을 1.05배로 올릴 수 있습니다.
  • 확률은 여기에서 참고할 수 있습니다.

스타캐치를 제외한 모든 요소를 그대로 가져와봤습니다. 스타캐치를 가져오지 않은 이유는 스타캐치에 성공했는지 아닌지를 서버에서 검증하기가 어렵기 때문인데, 대신 한별이가 그려진 배경을 프로필 배경으로 설정하면 같은 효과의 ‘한별캐치’를 적용해 줍니다.

이벤트 가격과 보상 설정

30일동안 매일 1문제씩을 푼다면 적당히 하루 75조각, 한 달 2,250조각을 얻는다고 봅니다(10일동안 매일 5문제 + 5기여를 해도 이 정도를 벌 수 있습니다). 그래서 일단 이런 유저가 22성까지 달성할 수 있는 것을 목표로 비용을 설정합니다.

이렇게 하려면 1번 강화 당 비용을 현저히 낮게 잡아야 합니다. 프로필 파괴 시 복구 비용도 없앴습니다. 기댓값을 보면서 강화 비용을 미세하게 조정했고, 정확한 비용은 아래와 같습니다.

  • 10성 이하를 목표로 강화: 별조각 1개
  • 15성 이하를 목표로 강화: 별조각 2개
  • 20성 이하를 목표로 강화: 별조각 3개
  • 25성 이하를 목표로 강화: 별조각 4개

이 때의 기댓값은 이렇습니다. 이 블로그에서 기댓값 계산 매드무비를 찍고 싶었지만 이미 다른 분께서 작성해 주신 다른 매드무비가 있어서 생략합니다. 요약하면 이렇습니다. (한별캐치 없음 / 한별캐치 있음)

  • 0성 → 10성: 18조각 / 17조각
  • 0성 → 15성: 138조각 / 117조각
  • 0성 → 17성: 215조각 / 181조각
  • 0성 → 20성: 1,143조각 / 851조각
  • 0성 → 21성: 1,417조각 / 1,043조각
  • 0성 → 22성: 2,330조각 / 1,654조각
  • 0성 → 23성: 36,569조각 / 23,955조각

주의해야 할 점은 스타포스 기댓값은 편차가 굉장히 크다는 점이고, 여기는 알고리즘 문제해결을 공부하는 곳이고, 참가자들이 이벤트 시작 후 1시간 안으로 기댓값 테이블을 전부 계산해버릴 것이라는 점입니다. 메이플스토리 같은 경우에는 상위 95% 유저는 상위 50% 유저보다 2.5배 많은 재화를 소모해야 한다는 시뮬레이션이 있을 정도입니다. 만우절 이벤트인데 너무 스트레스를 받지는 않았으면 해서, 많은 유저들이 얻도록 하려는 22성 보상까지에 대해서는 기댓값의 2배에서 3배쯤이 되도록 설정했습니다.

1등 보상을 따로 둔 것은 나름의 실험 같은 거였는데, 기댓값에 따르면 21성까지는 성공 확률이 최소 30%여서 할 만 하고, 잔고가 3조각이어도 강화 버튼을 누르는 게 이득입니다. 하지만 22성에서 성공 확률 3%의 강화 버튼을 누르는 건 일반적으로 손해입니다. 1등이 22성으로 모두가 행복하게 별조각을 5,000개씩 더 받고 끝날지, 아니면 남들이 별조각 5,000개를 더 받는 걸 막기 위해 22성에서 버튼을 누를지 궁금했습니다.

23명의 23성

결과적으로 solvedac 계정을 제외하고 23성을 달성한 유저는 22명이었네요. 23성에서 강화 버튼을 눌러서 터진 분들도 계십니다. 무섭습니다…. 개인적으로는 23성이 나온다면 24성이 한 명 이하로 나온다고 예상했는데 24성은 나오지 않았네요.

얼마나 썼을까

CSV 덤프

통계를 따로 계산하지 않아서 로그를 CSV 덤프로 까봤습니다. 3,519명의 유저가 총 1,636,385번 강화를 시도했고, 4,762,579개의 별조각을 소모했습니다.

각 단계별 강화 시도 횟수는 이렇습니다.

n성에서 버튼을 누른 횟수
  • 0성에서는 3,677번의 강화 시도가 있었습니다. $\frac{3\,519}{3\,677}\approx 0.957$이므로, 한별캐치를 고려하면 대략 맞습니다.
  • 9성 이하에서는 모든 단계에서 7,000번 이하의 강화 시도가 있었고, 10성에서는 149,682번의 강화 시도가 있었습니다. 9성 이하로는 돌아올 수 없기 때문에 강화 시도가 적습니다.
  • 15성에서의 강화 시도가 가장 많습니다(340,776번). 15성과 20성 완충 구간의 경우 그래프가 폭 튀어나와 있습니다.
  • 20성에서의 강화 시도는 24,071번, 21성에서는 9,927번입니다.
  • 22성에서의 강화 시도는 2,040번이며 이 중 23성으로의 강화를 성공한 경우는 70번이었습니다.
  • 23성에서의 강화 시도는 37번이며 이 중 24성으로의 강화를 성공한 경우는 없었습니다.

이 이벤트에서 별조각을 가장 많이 쓰신 분은 별조각을 28,396개 소모하셨으며, 7,882번의 강화 시도를 했습니다. 이 분께서는 22성에서 강화 버튼을 16번 누르셨지만 23성에 도달하지 못하시고 17성으로 마감하셨습니다.

뼈아픈 기록

최종 22성 유저 중 가장 적은 별조각을 소모한 경우 겨우 64개를, 가장 많은 별조각을 소모한 경우 무려 21,364개를 소모하셨습니다. 물론 가장 많은 별조각을 소모한 경우는 22성에서 프로필이 파괴된 후 다시 돌아온 경우이긴 합니다. 17성의 경우는 최소 44개, 최대 28,396개였습니다.

마지막으로 22성에 주차한 저는 2,264개의 별조각을 소모했습니다. 기댓값을 약간 상회합니다.

이모저모

솔브드가 메이플 인벤에 소개되는 신기한 경험을 했습니다. 댓글에 22성 인증이 꽤 올라오던데 알고리즘 문제 푸시는 분들과 메이플스토리 유저 간의 교집합이 어느 정도 되는 것 같습니다. 저도 그렇구요.

저희 학회에서도 문제는 안 풀고 한별포스하는 데 심취해 계셨다고 하고 들리는 소문으로는 SSAFY에서도 한별포스 강화전을 했다고 하네요.

백준님께서는 매크로를 짜서 강화를 시도하셨고…, 별조각을 15,630개 소모해 소모량 7위에 랭크되셨습니다. 안타까워요.

주절주절

작년엔 대규모 리팩터링을 하느라 만우절 이벤트를 못 했는데 올해는 뭔가 보여드릴 수 있었습니다. 재밌게 즐겨 주셨나요? 스타포스 추가해 달라는 걸 진짜 들어줄 줄은 몰랐나요? 솔브드는 알고리즘 문제해결을 재밌게 배울 수 있게 하자는 사명 아래 어떻게 하면 사이트를 좀 더 재밌게 만들 수 있을까 고민하다 보니 게임을 기획하듯이 기획하고 있습니다. 재밌게 즐겨주셨다면 다행입니다!

그치만 이번엔 너무 게임밖에 없었을지도 모르겠네요. 문제를 푸는 것과 연계해서 별조각을 더 다양한 방법으로 주고, 별조각을 사용할 만한 곳들이 많아졌으면 좋겠다는 생각을 하게 만들었던 이벤트였습니다. 앞으로 이런 방향으로 컨텐츠 업데이트를 해보고 싶어요.

이번 이벤트 참가해 주신 많은 분들께 정말 감사드립니다!

위드 코로나 체험판 다운로드 및 설치

2021년 회고

ICPC World Finals Moscow

코로나가 올해 12월에는 끝나있을 줄 알았죠. 일일 확진자 수가 최고치를 갱신 중이라는 작년 회고가 무색하게, 연말 확진자 수는 만 명에 가까워지고 있어요. 하지만 위드 코로나 체험판과 이런 시국에 다녀온 월드 파이널 덕분에 작년보다는 여기저기 많이 돌아다녔답니다.

덧없는 인생 목표

운좋게도 ICPC World Finals에 초청받게 되었습니다. 대회에 참여하려면 팀원 세 명이 모두 접종완료여야 하는데 한국의 백신 수급 상황이 좋았던 영향이었습니다. 모스크바 시내도 구경하고, 문제도 구경만 하다 왔어요.

2010년 이후로 11년만에 서강대학교 이름을 올렸습니다

2019년에는 월드 파이널을 그렇게 나가고 싶어했던 것 같은데, 월드 파이널 진출이 나름의 인생 목표였습니다. 그런만큼 엄청 멀게 느껴졌던 곳이기도 했구요. 그런데 이렇게 허무하게 달성해 버렸네요. 마음 한 켠에 애매함이 남습니다. 사실 제가 원했던 건 월드 파이널 진출 자체가 아니라 한국 리저널에서 월드 파이널에 진출할 만한 실력을 갖는 것이었는지도 모르겠습니다.

좋은 경험이었지만 87위라는 성적은 개인적으로는 정말 정말 많이 아쉬웠고, 비록 2019년 서울 리저널 상위 팀이었기에 기회를 잡았던 것도 맞는 말이지만 코로나 시국이 아니었다면 진출하지 못했을 것이기에 목표를 제대로 이루지 못한 것 같다는 생각이 계속 듭니다. 그래서 이미 이룬 목표지만 복학 후에 한 번 더 도전해 보려고 합니다. 아쉬움을 풀고 싶어요.

팀 레드시프트를 찾아보세요!

월드 파이널 참가 및 모스크바 여행 후기를 작성하고 있습니다. 기대해 주세요!

소프트웨어 개발

solved.ac

3.0.0

올해도 작년에 이어 solved.ac 개발에 많은 노력을 쏟았습니다. 올해에도 큼직한 기능들을 정리해 봅시다.

  • 출처 기반 문제 검색. (1월) 문제 출처를 기반으로 검색할 수 있습니다. from:sogang, from:ioi2021 같은 게 되죠.
  • AC 레이팅. (3월) 경험치 기반 티어 산정을 버리고 새로운 레이팅을 도입했습니다.
  • Express로 처음부터 끝까지 다시 구현된 백엔드. (6월)
  • solved.ac 디스코드 및 디스코드 연동. (6월) solved.ac 계정과 Discord 계정을 연결해 solved.ac에서 티어가 변경되면 Discord에서 역할이 바로 변경되게끔 했습니다. 본인의 solved.ac 닉네임을 채팅 닉네임으로 사용해야 하기 때문에 서버 채팅 관리 부담도 적죠.
  • 트위터 연동. (6월) 문제를 풀면 실시간으로 트윗을 올려 줍니다.
  • 스트릭. (7월) 연속으로 문제를 해결한 날짜 수를 계산해 줍니다. 스트릭이 생긴 이후로 문제를 풀고 싶은 마음이 더 생기지 않았나요?
  • 별조각. (10월) 문제를 풀고 기여를 하면 뭔가 재화를 드려요.
  • 문제 해결 이벤트. (11월) 우여곡절은 많았지만 빼빼로 데이 이벤트를 진행했습니다. 진짜 빼빼로를 보내드렸어요.
  • 코인과 코인샵. (11월) 프로필 배경과 스트릭 프리즈를 구매할 수 있어요.

정말 많네요!

3월에 AC 레이팅 업데이트를 하고 나서는 기존에 PHP로 짜여 있던 백엔드를 전부 Express.js로 포팅했는데요, 기존의 백엔드 서버가 EC2에 올라가 있고 제가 FTP로 수정했으며 버전 관리 같은 거 하나도 안 했다면 믿으시겠나요? 지금은 상상할 수도 없는 일이네요.

Github Actions

solved.ac의 API 셋은 기존에도 방대했어서 Express로 포팅하는 데에는 장장 3달이 걸렸습니다. 하지만 포팅이 완료된 6월 이후의 업데이트 내역들을 보면 DP를 참 잘 돌린 거 같아요. 시간이 된다면 포팅 후기도 작성해 보고 싶습니다. 사실 이렇게 말하면 나중에 결국 안 쓰게 되긴 합니다. 시간을 내서 써야 하는 건데 어렵더라구요.

백엔드를 포팅하고 나서 지금까지, 즉 3월부터 12월까지 새로 알게 된 큼지막한 기술과 방법론들을 정리해 보면

  • Github Actions: CI/CD
  • AWS ECR을 통해 ECS에 무중단 배포
    • Github Actions를 사용해 자동 배포까지
  • Sequelize: ORM
  • yarn 워크스페이스와 lerna를 이용해 모노레포 구축
    • 클라이언트와 서버 간 쉬운 코드 공유를 통해 효율적인 작업환경 구축
  • Express로 레이트 리미팅 미들웨어 제작
  • SQL optimizer hints를 이용한 쿼리 최적화 — 문제 고급 검색 속도를 엄청나게 향상했어요

정도가 있겠습니다. 저는 되게 야매로 개발한다고 주장하고 실제로도 그러고 있는데, 이제야 조금 제대로 뭔가를 만들고 있다는 느낌이네요. 그래도 아직 많이 부족하다고 느끼고, 더 성장하고 싶습니다. 이제는 TDD를 해보고 싶은데….

내년에는 새로운 기능 개발보다는 길라잡이를 작성할 수 있는 기반을 마련하는 데 열중하고 싶습니다. 길라잡이가 너무 너무 너무 너무 미뤄졌죠 죄송해요 내년에도잘부탁드려요

뭔가 (상대적으로) 챌린징한 프론트엔드 태스크와 챌린징한 백엔드 태스크를 매년 번갈아 하는 거 같은 느낌이네요. 내년에는 길라잡이 기반을 완성할 수 있을까요?

한국정보올림피아드 대회 프론트엔드

대회 시스템 사용 가이드

올해는 온라인으로 개최된 한국정보올림피아드의 대회 시스템 프론트엔드를 직접 설계 및 개발했습니다. 디자인도 다 했습니다.

수많은 챌린징한 프론트엔드 태스크를 다뤘습니다. 예를 들어…

  • 웹소켓을 통한 실시간 채점 정보 취득
  • 언어 서버가 없어서 완벽하지는 않지만, 약간의 편의를 제공하는 자동완성
  • 크기 조절이 가능한 문제 스테이트먼트 / 코드 에디터 2분할 화면, 너무 길어지면 잘리며 버튼을 누르면 열고 닫을 수 있는 코드 블록, LaTeX 렌더가 가능한 스낵바, 비버챌린지(유저가 상호작용할 수 있는, 캔버스에 랜더하는 자바스크립트 코드를 동적으로 엠베드하기) …
  • 부정행위 예방을 위한 화면 녹화 및 기타 여러 솔루션

등이 있습니다. 더 자세하게 말하지는 못하지만 정말 힘들었던 프로젝트였습니다. 제가 대학생이 되어서 알고리즘 문제해결을 시작해서 그런지 정보올림피아드에 나가보지 못한 걸 아쉬워했는데요, 이렇게라도 참가하게 되어 뿌듯했던 프로젝트였습니다. NYPC도 마찬가지구요!

준비되지 않은 나 앞에 성큼 다가와 버린

파트장

왠진 모르겠는데 회사를 다니다 보니까 직함이 생겼어요…. 와아….

부족한 실력으로 면접관도 되어 보고 회사의 여러 일들에 관여하게 되다가 12월에 파트장으로 발령받았어요. 작은 파트긴 하지만 처음으로 해 보는 매니징이라 잘 해낼 수 있을지 겁나네요.

저 잘 하고 있는 걸까요? 그렇지 않더라도 저를 믿어 주고 계시는 분들께 실망이 되지 않도록 잘해내봐야겠어요

새삼 이 때가 얼마나 좋았는지 실감이 나요. 사실 아직은 저거 ‘팀장님’으로 바꾸면 유효하긴 한데

대회 프로그래밍

NYPC

NYPC 시스템 개발에 이어 올해는 출제를 했습니다.

저는 예선 1번 계단예선 7번 루트가 많은 트리를 냈습니다. 계단 문제는 제가 계단을 하루에 100층씩 오르면서 살을 뺐던 걸 문제로 만든 거고, 루트가 많은 트리는 회사에서 의자에 앉아서 빙글빙글 돌다가 어 이거 괜찮네 하고 낸 문제입니다. 최고의 대회에 제 문제들을 선보일 수 있어서 너무 영광이었습니다!

영상에서 저를 찾아보세요!

대회 운영 참여

작년만큼은 아니지만 올해도 많은 대회의 운영에 참여했습니다.

대신 작년보다 훨씬 많은 문제를 출제했습니다. 이제 문제 은행을 만들어 놓고 대회에 필요할 때마다 하나씩 꺼내 쓰고 있어요.

SPC 2021

특히 NYPC와 SPC는 온사이트로 치뤄져서 즐거웠습니다. 이대로 위드 코로나를 이어가서 Hello 2022를 온사이트로 열면 좋았겠다는 생각은 있었지만 정말 안타깝게도 새로운 변이가 나타나 버렸네요…. 다음 온사이트 대회는 언제 열릴 수 있을까요.

코드포스

2021년의 코드포스 기록

어쩌다 운 좋게 찍은 오렌지를 박제해 두고 기고만장했던 것 같습니다. 1월 28일에 대회를 한 번 치고 11월까지 안 치다가 다시 쳤더니 퍼플을 넘어 블루를 다녀왔습니다.

1년을 잃어버렸습니다. 다시 마음을 다잡아야겠습니다.

대회 참가

올해는 UCPC에 참가자 신분으로 출전했습니다. 의외로 참가자로서는 처음 본선을 나가 봤고, 5등상(12등)이라는 괄목할 만한 성적을 냈습니다.

코드잼 3라운드와 SCPC 수상이 올해의 작은 목표였지만…

SCPC는 잘 모르겠고, 코드잼은 어이없는 실수를 해서 3라운드에 진출하지 못하게 됩니다.

3년 연속으로 코드잼 2라운드에 SCPC 파이널리스트인데요, 올해 목표 내년에는 제발 제발 이룰 수 있었으면 좋겠습니다. 노력해야겠습니다.

이외에도 ICPC 월드 파이널에 참가했습니다.

그래픽 디자인

블렌더

올해는 처음으로 3D를 만져봤습니다. 간단하게 solved.ac 프로필 배경들을 만들어봤습니다.

또 위에도 언급했지만 정보올림피아드 프론트엔드 UI/UX 디자인을 했습니다. 재밌었어요.

올해도 포스터를 만들었습니다.

이외에

심심했던 작년과 달리 올해는 인생 이벤트가 참 많았던 해였습니다.

어쩌다 보니 좋아하는 사람이 생겨서 사귀게 되었습니다.

같이 파스타도 먹으러 가고 돈까스도 먹으러 가고 곰탕도 먹으러 가고 김치찌개도 먹으러 가고 치맥도 하러 가고 카페도 가고 칵테일바도 가고 모든 순간을 함께하고 있습니다. 최고로 행복한 나날들을 보내고 있어요.

그리고 최고의 생일축하를 받았습니다. 절대 잊지 못할 거 같아요.

원래 부모님과 같이 살았는데, 회사가 너무 멀어서 낙성대에서 자취를 시작했습니다. 출퇴근 시간이 왕복 1.5시간 정도 줄었고, 샤로수길에서 배달이 됩니다.

다만 이게 문제가…. 12월부터 6월까지 매일 계단을 100층씩 오르면서 살을 15kg나 뺐는데, 자취 시작하고 나서 배달 음식 자주 먹고 애인과 여기저기 같이 다니다 보니 딱 뺀 만큼 다시 쪄버렸습니다. 다시 빼버리겠다는 결심으로 매일 집 뒷편 산을 오르고 있습니다.

자취하면서 마파두부랑 카르보나라를 자주 해먹었습니다. 요리 실력이 늘었어요. 카르보나라는 크림 카르보나라는 아니고 노른자랑 치즈로만 맛을 내는 카르보나라인데, 많이 연습했더니 이제 노른자를 익히지 않고도 따뜻한 카르보나라를 만들 수 있게 됐습니다. 자취방이 인덕션이 1구라 여전히 조금 어렵긴 해요.

노트북이 고장나서 새로 샀습니다. 메인 작업 컴퓨터로 이미 맥을 쓰고 있긴 하지만, 맥북은 하이퍼커넥트에서 인턴할 때 잠깐 써 본 걸 제외하면 인생 처음으로 써 보네요. 일정 성능 이상이라면 배터리가 오래가는 게 제일 중요하다고 생각해서 14인치 프로 모델로 샀습니다. 잘 산 거 같아요.

마지막으로 한동안 잘 안 보였던 한별이가 올해 다시 돌아왔습니다. 엄청 귀엽지 않나요? 언젠가는 라이브2D를 보고 싶다는 나름의 염원이 있었는데 올해 드디어 이뤄졌습니다.

귀여운 그림도 많이 추가되었어요. solved.ac 프로필 배경에도 많이 등록되었습니다.


올해 신년 목표는 ‘한 해 적당히 잘 보내기’였습니다. 이 정도면 적당히 잘 보냈을까요? 전혀 예상하지 못했던 행복한 일들도 많았고, 제 기고만장함을 반성하게 되는 일들도 있었네요.

내년엔 산업기능요원 복무가 만료됩니다. 회사를 계속 다닐지 복학해서 공부를 일찍 마칠지, 복학한다면 복수전공을 할지 대학원을 준비할지 머릿속에서 고민이 끊이지 않네요.

새해 복 많이 받으세요! 내년에는 위드 코로나 정식판을 즐길 수 있으면 좋겠습니다. 🔔

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시에 부담없이 참여할 수 있다는 장점도 있습니다. 강력하게 추천합니다.
  • 팀 연습 하다 오기 — 조금 더 긴 시간 동안 더 어려운 문제들에 대해서 생각해볼 수 있는 좋은 방법입니다. 새로운 인사이트를 얻을 수 있습니다.
  • 당분간 쉬기 — 너무 지쳤다면 괜찮아질 때까지 쉬어도 괜찮습니다. 알고리즘은 잊고 놀러 나가서 맛있는 거 먹고 옵시다. 금방 다시 회복할 수 있을 거예요.

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