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

다른 글

SCPC 2020 2차 예선에 참가했습니다 (2/3)

2차 예선 – 750/1,000점

2차 예선에서 1, 2, 3, 5번을 풀어서 1,000점 만점에 750점을 받았습니다.

4번 문제보다 5번이 구현이 쉬워 보여서 5번을 먼저 해결했습니다. 이후 부분 점수를 보니 1번 + 2번 + 3번 + 4번 + 5번 47점 = 747점이었고, 이는 1번 + 2번 + 3번 + 5번 = 750점보다 적은 점수여서, 27위 안에 들었음을 확신하고 4번을 느긋하게 건들어 보다가 포기했습니다.

제 2차 1, 2, 3, 5번 풀이를 공유합니다. 4번 문제는 구현하지 않아서, 대략적인 아이디어만 갖고 있습니다.

2차 1번 – 실력 맞추기

각각 $N \leq 300\ 000$명의 멤버가 있는 A팀과 B팀이 있습니다. 멤버들은 각각의 실력 값을 갖고 있습니다. 이 때, A의 멤버를 최대 한 명까지 교체해서, A팀의 멤버 한 명과 B팀의 멤버 한 명씩을 매칭했을 때 전체 매칭의 실력 차의 합이 최소가 되게 하고 싶습니다.


두 가지 관찰을 할 수 있습니다.

  • A팀에서 멤버 교체가 일어나지 않는 경우에는, A팀의 실력 값과 B팀의 실력 값을 각각 정렬해서 큰 순서대로 한 명씩 매칭해주는 것이 최적임은 자명합니다.
  • 한 명을 교체하는 경우에는, 어떻게 교체하더라도 어떤 B팀 멤버가 있어서 그 멤버의 실력과 같도록 교체해 주는 것이 무조건 이득입니다. 그리고 이 경우 새롭게 매칭된 멤버들의 실력 차는 $0$입니다.

따라서 A팀에서 한 명을 교체한다기보다는, A팀과 B팀에서 한 명씩을 제외하고 나머지를 적절히 매칭하는 것을 생각할 수 있습니다. 이를 해결하기 위해 A팀과 B팀을 각각 정렬해 두고, 다음과 같은 다이나믹 프로그래밍을 생각할 수 있습니다.

  • $dp\left(i,0\right)$: A팀과 B팀의 $\left[0, i\right]$의 멤버들을 각각 매칭했을 때의 실력 차의 합의 최솟값.
    따라서 $dp\left(i,0\right) = dp\left(i-1,0\right) + \left|A_i-B_i\right|$입니다.
  • $dp\left(i,1\right)$: A팀 한 명을 제외하고, A팀의 $\left[0, i\right]$과 B팀의 $\left[0, i – 1\right]$의 멤버들을 각각 매칭했을 때의 실력 차의 합의 최솟값.
    따라서 $dp\left(i,1\right) = \min\left\{ dp\left(i-1,0\right), dp\left(i-1,1\right) + \left|A_i-B_{i-1}\right| \right\} $입니다.
  • $dp\left(i,2\right)$: B팀 한 명을 제외하고, A팀의 $\left[0, i – 1\right]$과 B팀의 $\left[0, i\right]$의 멤버들을 각각 매칭했을 때의 실력 차의 합의 최솟값.
    따라서 $dp\left(i,2\right) = \min\left\{ dp\left(i-1,0\right), dp\left(i-1,2\right) + \left|A_{i-1}-B_i\right| \right\} $입니다.
  • $dp\left(i,3\right)$: A팀과 B팀 중 각각 한 명씩을 제외하고, A팀과 B팀의 $\left[0, i\right]$의 멤버들을 각각 매칭했을 때의 실력 차의 합의 최솟값.
    따라서 $dp\left(i,3\right) = \min\left\{ dp\left(i-1,3\right), dp\left(i-1,1\right), dp\left(i-1,2\right) \right\}$입니다.

이를 전부 계산하고 나면, 정답은 $dp\left(n,0\right)$과 $dp\left(n,3\right)$ 중 작은 쪽이 됩니다. 저는 1-based index를 사용해 구현했습니다.

#include <bits/stdc++.h>

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

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

int a[200001], b[200001];
ll dp[200001][4];

const ll inf = 1e18;

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

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

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

        dp[1][0] = abs(a[1] - b[1]);
        dp[1][1] = 0; // ignore a[i - 1]
        dp[1][2] = 0; // ignore b[i - 1]
        dp[1][3] = 0;

        for (int i = 2; i <= n; i++) {
            dp[i][0] = dp[i - 1][0] + abs(a[i] - b[i]);
            dp[i][1] = min(dp[i - 1][0], dp[i - 1][1] + abs(a[i] - b[i - 1])); // ignore a[i - 1]
            dp[i][2] = min(dp[i - 1][0], dp[i - 1][2] + abs(a[i - 1] - b[i])); // ignore b[i - 1]
            dp[i][3] = min({dp[i][1], dp[i][2], dp[i - 1][3] + abs(a[i] - b[i])});
        }

        cout << min(dp[n][0], dp[n][3]) << endl;
    }

    return 0;
}

2차 2번 – 고구마

고구마 $N\leq 300\ 000$개가 일렬로 길게 연결되어 있습니다. 각 고구마의 가격은 $-10^{12} \leq A_i \leq 10^{12}$로 정해져 있습니다. 음수는 상품가치가 없어 발생하는 처리 비용입니다.

$M$만큼의 예산이 있어, 연결되어 있는 고구마 덩어리를 적절히 잘라 중간 덩어리를 사 가려고 합니다. 덩어리의 크기는 중요하지 않으나, 한 덩어리만 사갈 수 있습니다. 이 때 고구마를 적절히 잘라서, 예산 $M$을 넘지 않으면서 최대한 비싸게 사가고 싶습니다.

요약하면, 최대 구간합maximum subarray sum 문제인데, 합이 $M$보다 작거나 같으면서 최대한 큰 경우를 찾아야 합니다.


제한조건 때문에, 선형 시간에 최대 구간합 문제를 해결하는 Kadane’s 알고리즘은 사용할 수 없습니다. 다만 최대 구간을 구해야 한다는 점에서 구간합 배열prefix sum array을 이용해 접근해볼 수 있습니다.

구간합 배열 $P$를 만든 후, 현재 보고 있는 인덱스가 $i$라면, $P_i-P_j \leq M$이면서 $j < i$에 대해 $P_i-P_j$의 최댓값을 구해 주면 됩니다. 이는 std::set 자료 구조에 이전 인덱스까지의 구간합들을 전부 집어넣고, $\mathcal{O}\left(\log n\right)$이 걸리는 std::set::lower_bound을 사용해 쉽게 해결할 수 있습니다. 이유는 모르겠지만 저는 대회 당시에는 std::set::upper_bound를 사용해 구현했습니다.

#include <bits/stdc++.h>

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

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

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

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

        int n;
        ll m;
        cin >> n >> m;

        set<ll> s;
        s.emplace(0);
        ll mx = 0, prf = 0;
        for (int i = 0; i < n; i++) {
            ll x;
            cin >> x;
            prf += x;
            s.emplace(prf);
            ll v = *s.upper_bound(prf - m - 1);
            mx = max(mx, prf - v);
        }

        cout << mx << endl;
    }

    return 0;
}

2차 3번 – 아르바이트

안타깝게도 디스크립션이 정확히 기억나진 않는데요, $N \leq 200\ 000$ 크기의 배열 $A$가 주어지고, 특정 인덱스의 값을 바꾸는 연산을 $Q\leq 2\ 000$번 하려고 합니다. 이 때 각각의 연산마다 $A$의 길이 $K \leq \min\left\{200,N\right\}$의 모든 부분 배열의 구간합에 대해, 이들의 중앙값을 구해야 합니다. 단 가능한 부분 배열의 개수가 짝수 개라면, 중앙에 있는 두 값 중 더 큰 값을 구해야 합니다.


계속 변화하는 중앙값을 구해야 하는 문제로 BOJ 1572번이 있습니다. 이 문제의 경우 저는 크기가 같은 std::multiset을 두 개 만들어 두고, 한 쪽의 집합의 모든 원소가 다른 쪽의 집합의 모든 원소보다 작도록 유지해두는 방식으로 해결했습니다. 제 1572번 소스 코드는 여기에서 볼 수 있습니다.

원래 배열에 대한 생각은 접어 두고, 구간합들이 저장된 배열이 있다고 생각해 봅시다. 원래 배열에서 한 개의 원소가 바뀌면 구간합 배열에서는 최대 $K$개의 원소가 바뀝니다. $K \leq \min\left\{200,N\right\}$라는 조건 때문에, 전부 나이브하게 처리해 줘도 최대 $KQ \leq 400\ 000$번밖에 바뀌지 않으니 위와 같은 방법으로 열심히 짜면 맞을 수 있을 것이라 생각했고, 시간 초과를 받았습니다.

std::multiset의 삽입/삭제 연산의 복잡도는 $\mathcal{O}\left(\log n\right)$이지만, 상수가 크기 때문에 사용에 주의를 요합니다. 상수 커팅을 위해 다소 특이할 수 있는 세그먼트 트리를 생각해내 해결했습니다.

BOJ 1572번의 해법과 비슷하게, $mxt$와 $mnt$라는 세그먼트 트리를 각각 만들었습니다. $mxt$는 최댓값 세그먼트 트리, $mnt$는 최솟값 세그먼트 트리이며, 항상 $\max mxt \leq \min mnt$가 되도록 관리합니다. 그런데 이렇게 관리하려면, 만약 $\max mxt > \min mnt$일 때 $mxt$의 최댓값을 $mnt$의 최솟값과 바꿔 줘야 하고, 또한 특정 인덱스 $i$에 대해 값 업데이트도 가능해야 합니다.

이를 위해 트리의 노드에는 최대/최솟값과, 그 최대/최솟값이 들어 있는 배열에서의 인덱스를 저장하도록 했습니다. 또한, 랜덤 액세스를 쉽게 하기 위해, 두 세그먼트 트리의 크기는 $N-K+1$로 고정해 두고, 노드에 저장된 값이 $-1$인 경우 이 트리의 이 인덱스에 값이 존재하지 않음을 의미하도록 했습니다.

정해인지는 잘 모르겠습니다. 어떻게 잘 하면 느리게 갱신lazy propagation하는 테크닉을 섞어서 좀 더 빠르게 할 수도 있을 것 같기도 한데, 아래 코드도 만점을 받아서 더 이상 생각을 하지 않기로 했습니다.

들리는 말로는 크기 $NK$의 펜윅 트리로도 해결할 수 있다고 합니다. 하긴 펜윅이 빠르긴 빠르니까요.

#include <bits/stdc++.h>

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

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

struct node {
    int i, v;

    node() : i(0), v(0) {}

    node(int i, int v) : i(i), v(v) {}

    bool operator<(const node &rhs) const {
        return v < rhs.v;
    }
};

node mnt[524288], mxt[524288];
int a[200001], val[200001], vals[200001];
ll prf[200001];
int tn, mxs, mns;

node minimum() { return mnt[1]; }

node maximum() { return mxt[1]; }

node argmin(const node &lhs, const node &rhs) {
    if (lhs.v == -1) return rhs;
    if (rhs.v == -1) return lhs;
    return min(lhs, rhs);
}

node argmax(const node &lhs, const node &rhs) {
    if (lhs.v == -1) return rhs;
    if (rhs.v == -1) return lhs;
    return max(lhs, rhs);
}

void setn(int i, int v, int x = 1, int s = 0, int e = tn - 1) {
    if (s == e && s == i) {
        mnt[x].v = v;
        return;
    }
    if (i <= (s + e) / 2) {
        setn(i, v, x * 2, s, (s + e) / 2);
    } else {
        setn(i, v, x * 2 + 1, (s + e) / 2 + 1, e);
    }
    mnt[x] = argmin(mnt[x * 2], mnt[x * 2 + 1]);
}

void setx(int i, int v, int x = 1, int s = 0, int e = tn - 1) {
    if (s == e && s == i) {
        mxt[x].v = v;
        return;
    }
    if (i <= (s + e) / 2) {
        setx(i, v, x * 2, s, (s + e) / 2);
    } else {
        setx(i, v, x * 2 + 1, (s + e) / 2 + 1, e);
    }
    mxt[x] = argmax(mxt[x * 2], mxt[x * 2 + 1]);
}

void update(int i, int dx, int x = 1, int s = 0, int e = tn - 1) {
    if (s == e) {
        if (mxt[x].v != -1) mxt[x].v += dx;
        if (mnt[x].v != -1) mnt[x].v += dx;
        return;
    }
    if (i <= (s + e) / 2) {
        update(i, dx, x * 2, s, (s + e) / 2);
    } else {
        update(i, dx, x * 2 + 1, (s + e) / 2 + 1, e);
    }
    mxt[x] = argmax(mxt[x * 2], mxt[x * 2 + 1]);
    mnt[x] = argmin(mnt[x * 2], mnt[x * 2 + 1]);
}

void init(int x = 1, int s = 0, int e = tn - 1) {
    if (s == e) {
        mnt[x].i = mxt[x].i = s;
        if (s >= tn / 2) {
            mxt[x].v = -1, mnt[x].v = vals[s];
            mns++;
        } else {
            mnt[x].v = -1, mxt[x].v = vals[s];
            mxs++;
        }
        return;
    }
    init(x * 2, s, (s + e) / 2);
    init(x * 2 + 1, (s + e) / 2 + 1, e);
    mxt[x] = argmax(mxt[x * 2], mxt[x * 2 + 1]);
    mnt[x] = argmin(mnt[x * 2], mnt[x * 2 + 1]);
}

bool exchange() {
    const auto mx = maximum(), mn = minimum();
    if (mx.v <= mn.v) return false;
    // set mntree
    setn(mn.i, -1);
    setn(mx.i, mx.v);
    // set mxtree
    setx(mx.i, -1);
    setx(mn.i, mn.v);
    return true;
}

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

    int t;
    cin >> t;

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

        int n, k, q;
        cin >> n >> k >> q;
        tn = n - k + 1;

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

        for (int i = k; i <= n; i++) {
            val[i - k + 1] = prf[i] - prf[i - k]; // [1, n - k + 1]
            vals[i - k] = val[i - k + 1];
        }

        init();
        while (exchange());

        cout << minimum().v << ' ';
        while (q--) {
            int i, v;
            cin >> i >> v;
            int d = v - a[i];
            for (int j = max(0, i - k); j < min(i, tn); j++) {
                update(j, d);
            }
            while (exchange());
            cout << minimum().v << ' ';
            a[i] = v;
        }
        cout << endl;
    }

2차 4번 – 안전운전

도로의 왼쪽, 오른쪽 경계와 운전 경로가 주어집니다. 도로 정보와 운전 경로는 선분들로 이루어져 있으며, 각각 $x$축 또는 $y$축과 평행합니다. 이 때, 운전 경로 중 특정한 가로선 하나 이하에 대해, 그 이후의 경로를 적절히 선대칭시켜서, 도로 안에 포함된 운전 경로의 세로선들의 길이의 합이 최대가 되게 하고 싶습니다. 단, 선대칭 이후의 도로 경로가 더 길어져서는 안 됩니다.


좌표 압축 후 위에서부터 아래로 내려오면서 스위핑 or 1차 4번과 비슷한 식의 세그먼트 트리를 이용하면 풀릴 거라고 생각했습니다. 하지만 1, 2, 3, 5번을 해결한 시점에서 이미 2차 예선 26위 이상임이 확정되었기 때문에 구현하다 포기했습니다.

2차 5번 – 삼각형의 거리

꼭지점 $N \leq 300$개의 단순다각형simple polygon이 있습니다. 오목할 수도 있습니다. 이 다각형의 꼭지점들을 이어 전부 삼각형으로 분할하고자 합니다.

어떤 삼각형에서 다른 삼각형과 맞닿은 변만을 통해 이동한다고 할 때, 삼각형 간의 거리를 정의할 수 있습니다. 예를 들어, 현재 삼각형과 맞닿아 있는 삼각형까지의 거리는 1이 됩니다. 처음 주어진 다각형을 잘 분할해서, 두 삼각형 사이의 최대 거리가 최소가 되도록 하고 싶습니다.


이 문제의 Small 셋의 경우, 다각형이 볼록다각형이므로 ICPC 2019 Korea Regional J번과 같은 문제입니다. 실제 대회에서 제가 First Solve로 해결했던 문제라 기억에 잘 남아 있던 것이 도움이 되었습니다.

다각형의 삼각 분할은 모든 노드의 $\deg \leq 3$인 트리로 나타낼 수 있습니다. 삼각 분할을 트리로 나타냈을 때, 이 트리의 지름을 최소화하는 문제가 됩니다.

주어진 도형을 어떤 대각선 하나로 자르면, 그 대각선 오른쪽에 만들어질 삼각형은 대각선 왼쪽에 만들 삼각형과 무조건 이어집니다. 이걸 바탕으로 2차원 다이나믹 프로그래밍을 생각해볼 수 있습니다. 현재 $i$번째 점 $P_i$부터 $j$번째 점 $P_j$까지만을 사용해 만든 도형이 있고, $\overline{P_iP_j}$는 어떤 다른 삼각형과 맞닿아있다고 생각해 봅시다. 한 쪽이 뚫려 있는 다각형이라고 생각하면 됩니다. 아래 그림의 핑크색 부분이 되겠네요.

이제 $dp \left(i,j\right)$를 핑크색 도형을 어떻게 잘 삼각분할했을 때 $\overline{P_iP_j}$에서 다른 삼각형까지의 최단 거리라고 정의합시다. 그러면 모든 $i<k<j$에 대해, 삼각형 $P_iP_jP_k$가 원래 다각형 안에 포함되는 경우 그 삼각형으로 분할한 뒤 재귀적으로 DP 문제를 해결할 수 있겠습니다.

따라서 $P_iP_jP_k$가 삼각형이 되는 모든 $i<k<j$들의 집합을 $K_{ij}$라 하면, 최단 거리는 $\overline{P_iP_k}$ 쪽에서 오거나 $\overline{P_kP_j}$ 쪽에서 오는 두 가지 경우가 있으므로, $dp\left(i,j\right)$는 다음과 같이 구할 수 있습니다.

\[dp\left(i,j\right)=\begin{cases} 0 & \textrm{if } i+1=j \\ \min_{k \in K_{ij}} \left\{ dp\left(i,k\right),dp\left(k,j\right) \right\}+1 & \textrm{otherwise} \end{cases}\]

하지만 이걸로는 트리의 지름을 구하기엔 역부족입니다. 왜냐하면, 이 다이나믹 프로그래밍의 경우 $\overline{P_iP_k}$에서 $\overline{P_iP_j}$ 쪽으로, $\overline{P_kP_j}$에서 $\overline{P_iP_j}$ 쪽으로 가는 건 고려하고 있지만, $\overline{P_iP_k}$에서 $P_iP_jP_k$를 거쳐 다시 $\overline{P_kP_j}$ 쪽으로 나가는 경로는 고려하지 못하고 있기 때문입니다.

점화식을 다시 정의해 봅시다. 어떤 값 $d$가 있어서, $dp_d \left(i,j\right)$를 다음과 같이 정의합니다.

\[dp_d\left(i,j\right)=\begin{cases} 0 & \textrm{if } i+1=j \\ \min_{k \in K_{ij}} \left\{ dp_d\left(i,k\right),dp_d\left(k,j\right) \right\}+1 & \textrm{if } dp_d\left(i,k\right)+dp_d\left(k,j\right) \leq d \\ \infty & \textrm{otherwise}\end{cases}\]

이제 이 점화식을 이용해 $dp_d\left(0,n-1\right)$를 구했고 그 값이 $\infty$가 아니라면, 트리의 지름이 $d$ 이하가 되도록 다각형을 삼각 분할할 수 있다는 뜻이 됩니다. 이제 이분 탐색으로 $d$의 최소값을 결정할 수 있습니다.

다이나믹 프로그래밍 한 번에 $\mathcal{O}\left(n^3\right)$이고, $0 \leq d \leq n-3$이므로 총 $\mathcal{O}\left(n^3 \log n\right)$만에 문제를 해결할 수 있습니다. 어떤 대각선이 오목다각형 안에 있는지 아닌지 판정하는 방법은 여러 가지가 있으나 문제의 포커스는 이게 아닌 것 같으므로 스킵하도록 합시다.

대회가 끝나고 안 사실인데 이 문제를 해결하는 논문이 있었다고 합니다.

#include <bits/stdc++.h>

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

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

struct point {
    int x, y;

    point() : x(0), y(0) {}

    point(int x, int y) : x(x), y(y) {}

    point operator*(const int &rhs) const {
        return {x * rhs, y * rhs};
    }

    point operator+(const point &rhs) const {
        return {x + rhs.x, y + rhs.y};
    }

    point operator-(const point &rhs) const {
        return *this + (rhs * -1);
    }
};


int ccw(const point &a, const point &b, const point &c) {
    point bb = b - a, cc = c - a;
    ll t = (ll) bb.x * cc.y - (ll) cc.x * bb.y;
    return t ? (t > 0 ? 1 : -1) : 0;
}

bool intersects(const point &la, const point &lb, const point &ma, const point &mb) {
    if (ccw(la, lb, ma) * ccw(la, lb, mb) != -1) return false;
    if (ccw(ma, mb, la) * ccw(ma, mb, lb) != -1) return false;
    return true;
}

point A[300];

const int inf = 1e8;

int dp[300][300], dg[300][300];

bool diag(int i, int j, int n) {
    if (i > j) swap(i, j);
    if (dg[i][j] != -1) return dg[i][j];
    if (i == j || i + 1 == j) return dg[i][j] = false;
    if (i == 0 && j == n - 1) return dg[i][j] = false;

    for (int v = 0, u = n - 1; v < n; u = v++) {
        if (intersects(A[i], A[j], A[u], A[v])) return dg[i][j] = dg[j][i] = false;
    }

    point V1 = A[(i + 1) % n] - A[i], V2 = A[(i + n - 1) % n] - A[i], V3 = A[j] - A[i];
    ll a = (ll) V1.x * V2.y - (ll) V1.y * V2.x;
    ll b = (ll) V1.x * V3.y - (ll) V1.y * V3.x;
    ll c = (ll) V3.x * V2.y - (ll) V3.y * V2.x;
    bool in = (a >= 0 && b >= 0 && c >= 0) || (a < 0 && !(b < 0 && c < 0));
    if (!in) return dg[i][j] = dg[j][i] = false;
    return dg[i][j] = dg[j][i] = true;
}

int f(int i, int j, int d, int n) {
    if (i + 1 == j) return dp[i][j] = 0;
    if (!(i == 0 && j == n - 1) && !diag(i, j, n)) return dp[i][j] = inf;
    if (dp[i][j] != -1) return dp[i][j];

    dp[i][j] = inf;

    for (int k = i + 1; k < j; k++) {
        if (!(i + 1 == k || diag(i, k, n))) continue;
        if (!(k + 1 == j || diag(k, j, n))) continue;
        if (f(i, k, d, n) + f(k, j, d, n) > d) continue;
        dp[i][j] = min(dp[i][j], max(f(i, k, d, n), f(k, j, d, n)) + 1);
    }

    return dp[i][j];
}

bool sat(int d, int n) {
    memset(dp, -1, sizeof dp);
    return f(0, n - 1, d, n) != inf;
}

int g(int x) {
    if (x == 3) return 0;
    if (x == 4) return 1;
    if (x == 5) return 2;
    return g((x + 1) / 2) + 2;
}

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

    int t;
    cin >> t;

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

        int n;
        cin >> n;

        memset(dg, -1, sizeof dg);

        for (int i = 0; i < n; i++) {
            cin >> A[i].x >> A[i].y;
        }

        if (n == 3) {
            cout << 0 << endl;
            continue;
        }

        int l = g(n), h = n - 3;
        while (l < h) {
            int m = (l + h) / 2;
            if (sat(m, n)) {
                h = m;
            } else {
                l = m + 1;
            }
        }
        cout << l << endl;
    }

    return 0;
}

회사 프로젝트에서 KaTeX를 한 번 사용해 본 이후로 제 블로그의 모든 수식을 KaTeX로 바꾸고 있습니다. 렌더 속도가 훨씬 빨라졌고, 모바일에서 수식 자동 줄바꿈이 잘 됩니다. 개인적으로는 여러 면에서 MathJax보다 좋은 라이브러리라고 생각합니다.

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

1차 예선 – 600/800점

1차 예선에서 1, 2, 3, 4번을 풀어서 800점 만점에 600점을 받았습니다. 부분 점수는 못 받았습니다.

다음 날 수술이 있었고, 4번까지 풀고 나니 새벽이어서 5번은 안 풀고 잤습니다. 전체적으로 디스크립션이 난해한 느낌이라 안타까웠습니다.

제 1차 1, 2, 3, 4번 풀이를 공유합니다.

1차 1번 – 다이어트

A 식당과 B 식당이 있고, 이 식당에는 각각 $N \leq 50\ 000$개의 메뉴가 있습니다. 이 메뉴들의 칼로리 값들이 주어집니다. $K$일동안 매일 A에서 한 끼를, B에서 한 끼를 먹을 때, 하루에 먹은 칼로리의 양의 최댓값이 최소가 되게 하고 싶습니다.


A 식당에서의 최대 칼로리의 음식을 순서대로, B 식당에서 최소 칼로리의 음식을 순서대로 $K$일간 하나하나 그리디하게 매칭해 주면 됩니다.

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;

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

int a[200000], b[200000];

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

    int tt;
    cin >> tt;
    for (int _ = 1; _ <= tt; _++) {
        cout << "Case #" << _ << "\n";

        int n, k;
        cin >> n >> k;

        for (int i = 0; i < n; i++) cin >> a[i];
        sort(a, a + n);
        for (int i = 0; i < n; i++) cin >> b[i];
        sort(b, b + n);
        int mx = 0;
        for (int i = 0; i < k; i++) mx = max(mx, a[i] + b[k - i - 1]);
        cout << mx << '\n';
    }


    return 0;
}

1차 2번 – 카드 게임

$N \leq 3\ 000$개의 카드가 쌓여 있는 두 덱 X와 Y가 있습니다. 각 카드에는 $K \leq 3\ 000$ 이하의 양의 정수가 적혀 있습니다. 두 명이 번갈아 카드를 가져가는데,

  • 꼭 한 개의 덱을 선택해서 위에서부터 한 장 이상을 가져가야 하며,
  • 가져간 카드의 합이 $K$ 이하여야 하고,
  • 마지막으로 카드를 가져가는 사람이 집니다.

내 턴에 덱 X에 $i$장의 카드가, 덱 Y에 $j$장의 카드가 남아 있는 상태를 $\left(i,j\right)$라고 한다면, $N$과 $K$가 정해져 있는 게임에 대해 중간 상태로 가능한 경우는 총 $\left(N+1\right)^2$개입니다. 각각의 상태에서 두 플레이어가 각각 최선의 방법으로 플레이했을 때 내가 반드시 이기는 경우와 반드시 지는 경우의 갯수를 세고 싶습니다.


Grundy number를 바로 떠올릴 수 있겠지만, 아쉽게도 마지막으로 카드를 가져가는 사람이 지는 게임(misère)이기 때문에 Grundy를 쓸 수 없습니다. Grundy로 접근하기 전에 ‘이게 1차 예선 2번에 나올 수 있을 만한 지식인가?’를 생각해 볼 필요가 있습니다.

대신 다이나믹 프로그래밍으로 접근할 수 있습니다.

  • 현재 상태 $\left(i,j\right)$에서 내가 어떤 덱에서 얼마나 많이 가져가더라도 다음 플레이어가 이기는 상태만 나온다면, 현재 상태는 내가 지는 상태입니다.
  • 그렇지 않다면, 내가 특정한 동작을 하면 다음 플레이어가 지는 상태를 만들 수 있습니다. 이런 경우 현재 상태는 내가 이기는 상태입니다.

따라서, DP 테이블을 만들어둔 후 가져간 카드의 합이 $K$ 이하가 되도록 X에서 하나씩, Y에서 하나씩 가져가면서 다음 플레이어가 이기는 상태가 있는지 확인해 주면 됩니다. 이 계산을 $\left(N+1\right)^2$개에 대해 하므로, $\mathcal{O}\left(N^3\right)$입니다.

$N \leq 3\ 000$이므로 Large 셋을 풀기에는 불충분합니다. 이는 Prefix sum을 이용해 $\mathcal{O}\left(N^2\right)$로 최적화할 수 있습니다.

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;

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

int x[3010], y[3010], xp[3010], yp[3010], xi[3010], yj[3010];
bitset<3010> dp[3010];
int prs[3010][3010];

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

    int tt;
    cin >> tt;
    for (int _ = 1; _ <= tt; _++) {
        cout << "Case #" << _ << "\n";

        memset(dp, 0, sizeof dp);
        dp[0][0] = true;

        int n, k;
        cin >> n >> k;

        for (int i = 1; i <= n; i++) {
            cin >> x[i], xp[i] = x[i] + xp[i - 1];
            int v = xp[i] - k - 1;
            int ii = upper_bound(xp, xp + i, v) - xp;
            xi[i] = ii;
        }
        for (int j = 1; j <= n; j++) {
            cin >> y[j], yp[j] = y[j] + yp[j - 1];
            int v = yp[j] - k - 1;
            int jj = upper_bound(yp, yp + j, v) - yp;
            yj[j] = jj;
        }

        int a = 0, b = 0;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                int xc = (prs[i][j + 1] - prs[xi[i]][j + 1] - prs[i][j] + prs[xi[i]][j]);
                int yc = (prs[i + 1][j] - prs[i + 1][yj[j]] - prs[i][j] + prs[i][yj[j]]);

                dp[i][j] = ((i - xi[i]) - xc) || ((j - yj[j]) - yc);
                dp[0][0] = true;
                (dp[i][j] ? a : b)++;
                prs[i + 1][j + 1] = dp[i][j] + prs[i][j + 1] + prs[i + 1][j] - prs[i][j];
            }
        }

        cout << prs[n + 1][n + 1] << ' ' << (n + 1) * (n + 1) - prs[n + 1][n + 1] << endl;
    }


    return 0;
}

1차 3번 – 사다리 게임

$N \leq 1\ 500$개의 세로선과 $K \leq 2\ 000$개의 가로선이 있는 사다리가 있습니다.

$M \leq 100\ 000$개의 쿼리가 들어옵니다. $\left(i,j\right)$의 형태입니다. 위의 $i$번 위치에서 시작해서 아래의 $j$번 위치에서 끝나도록 가로선을 적절히 없애 사다리를 조작하고 싶은데, 가로선을 최소한으로 없앴을 때 몇 개 없애야 하는지를 구해야 합니다.

Kotlin Heroes: Episode 4의 E번 문제와 상당히 비슷합니다.


가로선들이 그래프의 간선들이라고 생각하고 접근해서 최단 거리 문제로 해결했습니다.

$u$와 $v$를 잇는 가로선이 있다면, 가로선을 무시하는 경우($u \rightarrow u$, $v \rightarrow v$)를 가중치 $1$로, 무시하지 않는 경우($u \rightarrow v$, $v \rightarrow u$)를 가중치 $0$으로 하여 간선 $4$개로 만들어 줍니다.

정점은 $N$개를 처음에 만들어 주고, 가로선을 하나 처리할 때마다 가로선의 끝점에 각각 하나씩, 총 $2$개를 더 만들어 줍니다. 이렇게 그래프를 구성하면 노드는 총 $N+2K \leq 5\ 500$개가 됩니다.

이렇게 하면 각 시작점마다 Dijkstra 혹은 0-1 BFS를 돌리는 것으로 각 종점까지의 최단거리를 구하면, 그것이 시작점에서 종점까지 가면서 제거해야 하는 가로선의 개수의 최댓값이 됩니다. 이 방법을 이용해 쿼리 값들을 전부 전처리해둔 후, 쿼리가 들어오는 대로 전처리된 값들을 출력해 주려고 합니다.

만들어 준 그래프의 정점은 $N+2K$개, 간선은 $4K$개이므로 0-1 BFS의 경우 한 번에 $\mathcal{O}\left(N+K\right)$, Dijkstra의 경우 한 번에 $\mathcal{O}\left(K \log K\right)$입니다. 이를 모든 시작점에 대해 한 번씩 돌려주면 0-1 BFS의 경우 $\mathcal{O}\left(N^2+NK\right)$, Dijkstra의 경우 $\mathcal{O}\left(NK \log K\right)$만에 해결할 수 있습니다. 저는 그냥 Dijkstra로 해결했습니다.

DP로도 해결할 수 있다고 합니다.

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;

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

pii seg[2000];
int last[1500], dist[1500][1500], dtemp[9000];
bitset<9000> vis;

void dijk(int s, const vector<vector<pii>> &graph) {
    memset(dtemp, -1, sizeof dtemp);
    vis.reset();
    priority_queue<pii> pq;
    dtemp[s] = 0;
    pq.emplace(0, s);
    while (pq.size()) {
        int u = pq.top().second, d = -pq.top().first;
        pq.pop();
        if (dtemp[u] < d) continue;
        if (vis[u]) continue;
        vis[u] = true;
        for (const auto &kv : graph[u]) {
            int v = kv.first, c = kv.second;
            if (dtemp[v] == -1 || dtemp[u] + c < dtemp[v]) {
                dtemp[v] = dtemp[u] + c;
                pq.emplace(-dtemp[v], v);
            }
        }
    }
}

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

    int tt;
    cin >> tt;
    for (int _ = 1; _ <= tt; _++) {
        cout << "Case #" << _ << "\n";

        memset(dist, -1, sizeof dist);

        int n, k, q;
        cin >> n >> k >> q;

        vector<vector<pii>> graph(n);
        for (int i = 0; i < n; i++) last[i] = i;

        for (int i = 0; i < k; i++) {
            cin >> seg[i].first >> seg[i].second;
            seg[i].first--, seg[i].second--;
        }

        for (int i = 0; i < k; i++) {
            const auto &l = seg[i];
            int gn = graph.size();
            graph[last[l.first]].emplace_back(gn, 1);
            graph[last[l.second]].emplace_back(gn + 1, 1);
            graph[last[l.first]].emplace_back(gn + 1, 0);
            graph[last[l.second]].emplace_back(gn, 0);
            last[l.first] = gn;
            last[l.second] = gn + 1;
            graph.emplace_back();
            graph.emplace_back();
        }

        for (int i = 0; i < n; i++) {
            graph[last[i]].emplace_back(graph.size(), 0);
            last[i] = graph.size();
            graph.emplace_back();
        }

        for (int i = 0; i < n; i++) {
            dijk(i, graph);
            for (int j = 0; j < n; j++) dist[i][j] = dtemp[last[j]];
        }

        int s = 0;
        while (q--) {
            int u, v;
            cin >> u >> v;
            u--, v--;
            s += dist[u][v];
        }
        cout << s << endl;
    }

    return 0;
}

1차 4번 – 범위 안의 숫자

0에서 9까지의 숫자 $n \leq 50\ 000$개로 이루어진 문자열 $t$가 주어집니다. 길이가 $k \leq \min\left\{9,n\right\}$인 부분 문자열들을 수라고 생각하고, 모두 수직선 위에 둡니다.

이 때, 여기서 최대 한 글자까지를 1로 바꿔서, 어떤 정수 $a$에 대해 길이가 $m \leq 10^9$인 구간 $\left[a,a+m\right]$ 안에 속한 수의 개수의 최댓값이 최대가 되게 하고 싶습니다. 이 때의 최댓값을 구해야 합니다.


일단 $k$가 커봐야 $9$고, $n$도 그렇게 크지 않아서, 문자 하나를 1로 바꿀 수 있다는 것을 배제하고 생각하면 이 문제는 스위핑으로 해결할 수 있습니다. 부분 문자열의 값을 $x_i$라고 하면, 선분 $\left[x_i,x_i+m\right]$들을 수직선 위에 깔아 두고 가장 많이 겹쳤을 때의 선분의 갯수를 구하면 됩니다.

이제 문자 하나를 1로 바꿀 수 있는 경우를 생각해봅시다. ‘문자 하나를 1로 바꾸는 것’이라는 행위에서 관찰 가능한 특별한 성질은 딱히 없다고 느꼈습니다. 다만, 문자 하나를 1로 바꾸면 다시 만들어줘야 하는 선분의 개수는 $9$개에 불과하다는 사실에 집중했습니다.

만약 다이나믹하게 선분을 제거하고 추가할 수 있는 스위핑이 있다면, 모든 위치의 숫자를 하나하나 1로 바꾸고 되돌리는 행위를 한다고 해도 추가/제거는 $\mathcal{O}\left(kn\right)$번만 일어나므로 시간 안에 해결할 수 있을 것 같습니다.

다행히도 그런 스위핑은 존재하는데요, 최댓값을 구하는 연산과 구간에 덧셈을 하는 연산(lazy propagation 등)을 수행 가능한 세그먼트 트리로 가능합니다.

다만 인덱스가 꽤 크기 때문에 다이나믹 세그먼트 트리를 구현하거나, 가능한 값들을 전부 좌표 압축한 후 처리하는 방법을 사용해야 합니다. 저는 후자로 구현했습니다. 총 시간 복잡도는 $\mathcal{O}\left(kn \log kn\right)$입니다.

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;

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

ll tree[1048576 * 2], lazy[1048576 * 2];

int c;

void _propagate(int x, int s, int e) {
    if (!lazy[x]) return;
    tree[x] += lazy[x];
    if (s != e) {
        lazy[x * 2] += lazy[x];
        lazy[x * 2 + 1] += lazy[x];
    }
    lazy[x] = 0;
}

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

void _update(int x, int s, int e, int l, int r, ll dv) {
    _propagate(x, s, e);
    if (l > e || r < s) return;
    if (l <= s && e <= r) {
        tree[x] += dv;
        if (s != e) {
            lazy[x * 2] += dv;
            lazy[x * 2 + 1] += dv;
        }
        return;
    }
    int m = (s + e) / 2;
    _update(x * 2, s, m, l, r, dv);
    _update(x * 2 + 1, m + 1, e, l, r, dv);
    tree[x] = max(tree[x * 2], tree[x * 2 + 1]);
}

ll maximum(int l, int r) {
    return _maximum(1, 0, c - 1, l, r);
}

void update(int l, int r, ll dv) {
    _update(1, 0, c - 1, l, r, dv);
}

ll zip(ll x, const vector<ll> &a) {
    return lower_bound(a.begin(), a.end(), x) - a.begin();
}

ll v[50000], v1[50000][10];

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

    int tt;
    cin >> tt;
    for (int _ = 1; _ <= tt; _++) {
        cout << "Case #" << _ << "\n";

        ll n, k, m;
        cin >> n >> k >> m;
        string t;
        cin >> t;

        // init values
        vector<ll> ps;
        ll curr = 0, mod = 1;
        for (int i = 0; i < k; i++) mod *= 10;
        for (int i = 0; i < k; i++) curr *= 10, curr += t[i] & 15, curr %= mod;
        for (int i = k; i <= n; i++) {
            v[i - k] = curr;
            ps.emplace_back(curr);
            ll l = curr, r = 0, p = 1;
            for (int j = 0; j < k; j++) {
                v1[i - k][j] = (l / 10 * 10 + 1) * p + r;
                ps.emplace_back(v1[i - k][j]);
                l /= 10, r += (curr / p) % 10 * p, p *= 10;
            }
            if (i == n) break;
            curr *= 10, curr += t[i] & 15, curr %= mod;
        }
        int ts = ps.size();
        for (int i = 0; i < ts; i++) ps.emplace_back(ps[i] + m);

        sort(ps.begin(), ps.end());
        ps.erase(unique(ps.begin(), ps.end()), ps.end());

        memset(tree, 0, sizeof tree);
        memset(lazy, 0, sizeof lazy);
        c = ps.size();
        // query
        for (int i = 0; i <= n - k; i++) {
            update(zip(v[i], ps), zip(v[i] + m, ps), 1);
        }

        ll mx = maximum(0, ps.size() - 1);

        for (int i = 0; i < n; i++) { // replace i-th number to 1
            // remove
            for (int j = 0; j < k; j++) {
                if (i - k + j < 0 || i - k + j > n - k) continue;
                update(zip(v1[i - k + j][j], ps), zip(v1[i - k + j][j] + m, ps), -1);
            }
            if (i <= n - k) {
                update(zip(v[i], ps), zip(v[i] + m, ps), -1);
            }
            // add
            if (i - k >= 0) {
                update(zip(v[i - k], ps), zip(v[i - k] + m, ps), 1);
            }
            for (int j = 0; j < k; j++) {
                if (i - k + 1 + j < 0 || i - k + 1 + j > n - k) continue;
                update(zip(v1[i - k + 1 + j][j], ps), zip(v1[i - k + 1 + j][j] + m, ps), 1);
            }
            // query
            mx = max(mx, maximum(0, ps.size() - 1));
        }
        cout << mx << endl;
    }

    return 0;
}

2019 서강대학교 프로그래밍 대회를 개최했습니다

제목이 곧 내용, 올해 서강대학교 교내대회를 개최했습니다. 제가 출제와 운영을 총괄했습니다! 진짜 구데기컵 2018(…)을 제외하면 제 첫 출제였고, UCPC 2018에 풍선 스탭으로 참여한 걸 제외하면 첫 운영이었습니다. 대회를 준비하고 진행하면서 느낀 점들을 적어보려 합니다.

어떤 걸 먼저 해야 하지

서강대학교의 경우 2005년부터 매년, ICPC Korea Regional에서 교내 랭킹 1~2위의 팀이 대회 운영과 출제를 해왔습니다. 대회는 보통 11월 말이고 ICPC 본선은 11월 초에 진행되기 때문에 보통 2~3주 정도의 준비 기간이 주어집니다. 아니 대회 운영하려면 뭐가 필요한지도 모르는데 2주만에 대회 준비를 어떻게 해요??

근데 사람 일이 다 그렇듯이 놀랍게도 대회 날짜가 다가오면 준비를 하게 되어 있더라고요. 학교에서 ICPC 본선에 3팀이 출전했는데, ‘그래도 우리 팀이 그 중에서 적어도 2위는 하겠지?’ 라는 행복회로를 돌리면서 김칫국 109 + 7사발 마시고 미리 대회 개최를 준비했습니다.

대회를 열기 위해 필요한 것들은 대략 다음과 같습니다.

  • 문제. 문제 푸려고 여는 대회인데 문제가 없으면 안 되죠.
    • 출제진. 애초에 출제진이 없으면 문제가 나올 수가 없죠.
    • 검수진. 물론 출제진이 검수해도 괜찮습니다.
  • 시간과 공간. 언제 어디서 개최할지 결정해야 합니다.
  • 참가자. 이건 제가 어쩔 수가 없고..
  • 포스터, 풍선, 간식 같은 거

이 중에 제가 그 시점에 할 수 있었던 건 문제 만들기였습니다. Redshift가 본선 교내 1~2등 안에 들면 세 명 모두 출제를 해야 했기에, 일단은 팀 내에서 문제를 뭐 낼지 어렴풋이 생각해 보기로 했습니다. 대충 이런 문제 아이디어가 나왔습니다.

  • 7-세그먼트 디스플레이 (shiftpsh 아이디어)
    • 개인적으로 좋은 문제라고 생각했어서 제네레이터까지 만들어 뒀습니다.
  • 올솔브 방지용 graph isomorphism 문제 (shiftpsh 아이디어)
    • Tree isomorphism 문제로 약화되어 출제되었습니다. 이거 오렌지 이상에선 웰노운이라더라고요. 왜 내가 웰노운이 아니라고 생각했던 건 다 웰노운이지??
  • 최단 경로 문제인데, 길이의 곱이 최단이 되어야 하기 때문에 간선 가중치에 전부 로그를 씌워 구하는 문제 (lvalue 아이디어)
    • 방콕 리저널 예비소집일에 나온 아이디어였는데, 다음날 본대회 F번?으로 실제로 나와버렸기 때문에 표절 의혹을 받을까봐 실제 대회에는 못 냈습니다.
    • 이 아이디어 덕분에 대회 당시 F번을 두번째로 빨리 푼 팀이 우리 팀이었는데, 역설적이게도 대회를 말아먹는 계기가 되었습니다. 이건 다른 포스트에 후술.

다행히도 Seoul Regional에서 교내 1등을 하는 데 성공했기 때문에 대회 운영에 참여할 수 있게 되었고, 이제 아까 언급한 ‘대회 운영에 필요한 사항’ 4개 전부를 고려해야 하는 상황이 되었습니다.

문제

각자 내고 싶은 문제들은 있겠지만, 실제로 모두가 각자 내고 싶은 문제만 낸다면 프로그래밍 대회가 아니라 빡구현 코딩테스트가 될 수도 있고, 고인물 자료구조 파티가 될 수도 있고, 계산수학 경시대회가 될 수도 있겠다고 생각했습니다. 그래서 아래와 같은 원칙을 두고 대회 문제들의 전체적인 틀을 정했습니다.

  • 출제되는 문제들의 주제는 균형적이어야 합니다.
    • 12문제 중 DP가 5문제고 그러면 좀.. (ICPC Seoul 예선 출제자님 듣고 계신가요)
  • 모든 문제를 푸는 사람은 없어야 하고 하나도 못 푸는 사람이 있어서는 안 됩니다.
    • ICPC 출제 기조라고 들었습니다.

개인적으로는 tree isomorphism 문제를 너무 내고 싶었기 때문에 디비전 당 8문제, 총 16문제를 내기로 정했습니다. 지금 생각해보면 그러지 말거나 아니면 디비전끼리 겹치는 문제를 내게 하거나 했어야 했는데 아무튼 그렇게 정했습니다.

구데기컵에서 문제 정리를 위한 스프레드시트를 팠던 기억이 있어서 저도 그렇게 했습니다.

쉬운그래프문제하나만더있으면좋겠다

20문제를 낸 후, 각각 solved.ac 기준 예상 난이도와 사용 알고리즘/자료구조를 적고 8개 문제씩 Champion/Master에 각각 배정해나가면서, 대회가 너무 어려워질 것 같아서 많이 등장한 주제의 문제 중 4문제를 뺐습니다. 그리고 동그라미를 하나씩 채워나가는 방향으로 문제를 준비했습니다.

예상 난이도를 정하는 것에 장점과 단점이 있었는데요,

  • 장점은 문제를 배정하기가 쉬웠다는 점이었고,
  • 단점은 문제 난이도를 잘못 예상해서 Master 디비전 스코어보드가 망했다는 점이었습니다.
    • 출제자 생각과 참가자 생각은 많이 다르다는 걸 깨달았고, 조금 더 참가자 입장에서 문제 난이도를 생각해 보려고 노력해야겠다고 느꼈습니다.

문제들을 배정하고 나서는 스테이트먼트와 정해 – 데이터와 테스트 – 제한 순서대로 문제를 만들었습니다.

스테이트먼트

참가자 입장에서 스테이트먼트는 명료할수록 좋습니다. 러시아의 모 사이트에서 열리는 대회에는 스테이트먼트가 애매하거나 이상한 경우가 종종 있었는데, 이로 인해 스트레스를 받은 경험이 있었기 때문에, 참가자가 문제를 푸는 데 방해가 되지 않도록 스테이트먼트를 구성하려고 노력했습니다. 출제 의도가 스테이트먼트를 길게 해서 일부러 문제풀이를 지연시키고자 하는 게 아니라면 쓸데없는 이야기는 줄이고 문법상의 오류나 비문은 최대한 없애고, 문장은 짧게 구성하도록 하고. 사실 글쓰기의 기본이죠.

스테이트먼트 원고는 각자 작성하고 Stack에 옮기면서 수정했습니다

아래는 카드 놓기의 스테이트먼트 원고와 최종본을 비교해 둔 것입니다.

첫번째 줄에는 N(1<=N<=1000000)이 주어진다.
두번째 줄에는 길이가 N인 수열 A가 주어진다.
Ai가 1이면 i번째로 카드를 내릴 때 1번 기술을 썼다는 뜻이다.
Ai가 2이면 i번째로 카드를 내릴 때 2번 기술을 썼다는 뜻이다.
Ai가 3이면 i번째로 카드를 내릴 때 3번 기술을 썼다는 뜻이다.
Ai는 1,2,3중 하나임이 보장된다.
An은 항상 1임이 보장된다.
첫 번째 줄에는 N (1 ≤ N ≤ 106)이 주어진다.
두 번째 줄에는 길이가 N인 수열 A가 주어진다. Aix이면, i번째로 카드를 내려놓을 때 x번 기술을 썼다는 뜻이다. Ai는 1, 2, 3 중 하나이며, An은 항상 1이다.

위와 아래 중 어떤 글이 더 이해하기 쉬운가요? (아래라고 해주세요)

  • 1000000은 한 눈에 봤을 때 정확히 얼마인지 가늠하기 어렵기 때문에, 1,000,000 또는 106으로 고쳐야 합니다.
  • <=은 정확한 표현이 아니기 때문에 ≤으로 고칩니다. 변수명은 일반적인 글과 구분하기 쉽게 하기 위해 기울임꼴으로 씁니다. 기울임꼴로 하는 편이 실제 수식에서 등장하는 문자들의 모양과 비슷하기도 하고요.
  • 쉼표로 나열된 항목들은 띄어쓰기로 구분해 줍니다(1,2,3 → 1, 2, 3).
  • 같은 의미의 글이 여러 번 반복되는 경우 간단하게 줄일 수 있는지 생각해 봅니다.

스테이트먼트를 그냥 읽어보면 모르겠지만, 계속 긴장 상태일 참가자 분들의 입장에서 편하게 읽힐 수 있도록 이렇게 나름대로 세심하게 편집하는 작업을 거쳤습니다.

대농부 김상혁
평행우주

또한 글만 적혀 있으면 문제를 이해하는 데 어려움이 있을 수도 있기 때문에 몇몇 문제에는 적절한 위치에 삽화들을 그려서 삽입했습니다. 다행히도 제가 그래픽 디자인을 할 줄 알았기 때문에 삽화는 제가 전부 그렸습니다.

정해

출제자의 정해가 틀리면 안 됩니다. 최근 열렸던 학교 대회 중에 출제자가 잘못된 풀이를 작성한 경우가 종종 있었고, 서강대학교만 해도 2017년에 출제자가 정해를 잘못 작성했던 적이 있었습니다. 특히 대회 준비 중에 열린 타 대학교 대회에서 이런 상황이 발생했기 때문에 각별히 신경써서 검수했습니다.

이건 어쩔 수 없지

학과에서는 외부 검수자를 초빙하지 말라고 했지만 2주 안에 16문제를 출제해야 하는데 출제 경험이 적은 6명이 오류를 안 내는 게 이상한 상황이었고, 결정적으로 스타트링크에서 검수자 초빙을 말 그대로 강력하게 권장했기 때문에 제 단독 판단으로 검수자를 초빙하기로 했습니다. 여러 대회에 검수자로 참가했던 분들이었기에 문제 보안에 대해서는 믿을 수 있었으며, 개인적으로는 잘못된 문제를 만들지 않는 것이 더 중요하다고 생각했기 때문입니다.

아니나다를까 색깔 하노이 탑 문제에서 출제자의 정해가 잘못되었음이 외부 검수자에 의해 발견되어 일찍 수정할 수 있었습니다. 검수자 분들께서는 후술할 데이터와 시간 제한에 대한 검증도 진행해 주셨습니다. 외부 검수자 분들께서 안 계셨다면 이번 대회도 문제 오류가 있는 대회가 될 뻔 했는데, 참 다행이라고 생각합니다. 이 글을 빌어 감사하다는 말씀을 다시 한 번 전해드리고 싶습니다.

데이터와 테스트

저는 Polygon을 이용해 데이터를 만들었습니다. Polygon은 Codeforces에서 프로그래밍 문제 제작을 도와주는 목적으로 만든 플랫폼입니다. 다음과 같은 것들이 가능합니다.

  • 데이터 생성 및 관리
  • 입출력 형식 검증
  • 출력 가능한 스테이트먼트 PDF 제작

특히 입력 형식의 무결성은 상당히 중요하기 때문에 Polygon을 사용합니다. 예를 들어 평행우주는 입력이 다음 조건을 만족함이 보장되어야 합니다.

  • 입력으로 들어오는 각각의 그래프는 연결되어 있어야 하며 트리여야 합니다. 노드가 s개라면 노드 번호는 0, 1, 2, …, s − 1로 주어져야만 합니다.
  • 입력으로 들어오는 트리의 개수는 106개 이하여야 합니다. 각 트리의 노드의 개수는 30개 이하여야 합니다. 또한 모든 트리의 노드 개수의 합도 106개 이하여야 합니다.
  • 당연하겠지만, 입력의 각 줄마다 맨 앞이나 맨 뒤에 공백 문자가 있어서는 안 되고, 공백이 두 개 들어가 있다거나, 맨 마지막 줄에 줄바꿈이 없다거나 하는 경우도 안됩니다. C/C++로는 어찌저찌 잘 풀릴지도 모르지만 Java와 Python에서 제대로 풀리지 않을 수 있기 때문입니다.

testlib.h는 위와 같은 무결성 체커를 간단하게 짤 수 있도록 해 줍니다. 또한 Polygon은 이렇게 짠 무결성 체커를 바탕으로 데이터를 제작할 때 모든 데이터에 대해 생성과 동시에 자동으로 무결성 체크를 해 주기 때문에 다른 더 중요한 것들에 집중할 수 있게 해 줍니다.

Polygon에 등록되어 있는 서강 프로그래밍 대회 문제들

testlib.h는 데이터 생성기를 제작할 때도 사용할 수 있습니다. 안타깝게도 다른 출제자 분들께서는 Polygon 사용 경험이 없었고, 출제 시간도 2주로 상당히 촉박해서 급한 대로 testlib.h를 쓰지 않는 제네레이터를 만들었습니다. 실제로 도중에 입력 조건에 맞지 않는 데이터가 업로드되었는데, 무결성 체커가 없어서 찾아내기 어려웠습니다. 다행히도 대회 직전에 찾아서 삭제했습니다.

하지만 Polygon 자체도 문제 제작자가 짠 코드에 의존하기 때문에, 대부분의 실수를 잡아낼 수 있다고 하더라도 잡아내기 어려운 실수들도 있습니다. 가령 평행우주의 경우는 날 새가면서 정신없이 문제를 만들다 보니 제가 10만과 106을 헷갈렸나 봅니다. 문제에는 별의 수와 별자리의 수가 106을 넘지 않는다고 되어 있습니다만 실제로는 각각이 105을 넘지 않는 약한 데이터만을 준비했던 사실을 시상식 때가 되어서야 깨달았습니다.

데이터 자체는 무결했으니 문제나 데이터의 오류는 아니었지만, 의도하지 않은 풀이가 통과할 수도 있었던 상황이었습니다. 대회 당시 맞은 사람이 없었어서 다행이었을까요? 곧 데이터를 추가할 예정입니다.

제한

시간 제한과 메모리 제한

의도한 풀이는 통과하고, 의도하지 않은 풀이는 통과하지 않도록 제한을 잘 설정해야 합니다. 그런데 이게 은근 어려운 게,

  • 언어마다 실행 시간에 차이가 있습니다.
    • Python에서 최적의 솔루션이 동작하는 시간이 C++에서 나이브한 솔루션이 동작하는 시간보다 느릴 수도 있습니다.
  • 같은 언어의 같은 풀이라도 입력 방식에 따라 실행 시간에 많은 차이가 생깁니다.
    • 느린 입력 방식 기준으로 시간 제한을 설정하면, 빠른 입력 방식을 사용했지만 느린 알고리즘을 사용한 코드가 시간 안에 통과하는 상황이 생길 수도 있습니다.

solved.ac는 어떤 방식으로 정렬을 해도 괜찮은 문제이지만, 원래는 인덱스 소트를 이용해 O(n)으로 정렬해야만 하는 문제로 기획되었습니다. 그래서 기존에는 제한이 n ≤ 107이었습니다. 하지만 C++에서 빠른 입력을 쓰고 std::sort를 사용한 코드가 500ms 좀 넘게 돈 반면, Java에서 인덱스 소트를 이용한 코드가 800ms가 나오길래, 그냥 포기하고 쉽게 바꿨습니다.

작년 대회와 다르게 이번 대회에서는 Python을 사용할 수 있도록 했지만 정작 모든 문제가 Python으로 풀릴 것이라고 보장하지는 않았습니다. 대회 규칙에는 ‘출제진이 모든 문제를 C++과 Java 혹은 Kotlin으로 풀었음이 보장됩니다’라고 적었고, 실제로 C++과 Java 혹은 Kotlin으로 모든 문제를 검증했으나 Python으로는 풀리지 않는 문제도 있었습니다. Python은 현저히 느리기 때문에 Python 기준으로 시간 제한을 잡으면 C++ 나이브 코드가 통과할 수도 있기 때문이었습니다. 이는 ICPC World Finals 규칙과도 같습니다.

메모리 제한은 전부 1024MB로 설정했습니다. 여러 테스트를 돌려 보면서 틀린 코드가 맞거나 맞은 코드가 틀리는 등의 상황이 발생하면 제한을 조절하거나 데이터를 보강하는 등의 작업을 진행하면서 문제를 완성시켜 나갔습니다.

완성된 시트

그렇게 시트를 전부 동그라미로 만든 후에는 한 숨 돌릴 수 있었습니다.

운영

문제를 다 만들어갈 때쯤에는 대회 운영에 대한 것도 생각해야 했습니다. 다행히도 학과에서 다년간 대회 운영을 도와주고 계셨기 때문에 이런 것들은 별 고민 없이 해결되었습니다.

대회 진행 전

  • 장소. 실습실은 학교가 관리하고 있기 때문에 대여도 학과에서 처리해 주셨습니다.
  • 풍선. 역시 학과에서 지원해 주셨습니다.
    • 헬륨 풍선이 생각보다 비쌌습니다. 하나에 1,500원이었는데, 대회 끝나고 못 나눠준 풍선은 다 터뜨려야 한다고 생각하니 좀 안타까웠습니다.
  • 간식. 이것도 학과에서 지원해 주셨습니다.

포스터는 학과에서 인쇄만 해 주기 때문에 제가 만들어야 했습니다. 팀노트에 있던 디닉 코드를 가져와서 3시간동안 간단히 만들었습니다.

애프터 이펙트로 간단하게 배경을 만들고
포토샵으로 글씨를 얹었습니다

학내 이곳저곳에 포스터를 붙이고, 참가자는 학교 커뮤니티에 게시글을 올려 모집했습니다. 총 91분께서 참가 신청을 해 주셨습니다. 안타깝게도 당일에 안/못 오신 분들이 많아서 실제 대회 당일에는 약 70분 가량 참여해주셨습니다.

이미지
문제지

문제지도 만들었습니다. 문제지는 LATEX로 타입세팅해 대회 전날에 인쇄했습니다. 학과사무실에서 인쇄해 제본과 운반을 전부 수작업으로 했는데, 대회 운영 중 가장 힘들었던 일이 아니었을까 싶습니다.

대회 당일

이미지
데스크

대회 당일 운영은 순조로웠습니다. 다만 실습실에 PyCharm과 IntelliJ를 설치하느라 시간이 오래 걸렸는데, 전날에 미리 설치해 뒀다면 좋았겠다 싶었습니다. 실습실이어서 학생들이 작성한 코드가 남아 있었고 이들을 전부 지우기 위해 현장에서 배치 파일(.bat)을 급조해 모든 컴퓨터에서 돌렸습니다.

이미지
이 많은 풍선들 중 단 하나만이 참가자의 손에 들어갔다는 슬픈 소식

풍선을 나눠주려면 자리표가 있어야 편한데 이 사실을 간과했습니다. 자리표도 현장에서 가나다순으로 급조했습니다. 이런저런 일들로 인해 대회 초반에 풍선이 늦게 나가는 일이 있었습니다.

Champion 디비전은 별 일이 없었지만 Master 디비전 스코어보드는 꽤 오랫동안 많은 사람들이 1솔브에서 머물러 있었습니다. B번 문제의 난이도를 잘못 생각했음을 직감했습니다. 다음날 진행된 Open Contest에서도 B번 문제가 많이 풀리지 않았습니다. 심지어 ainta님은 A~P를 전부 푼 후 마지막에 B를 푸셨을 정도.

많은 사람들이 겹받침이 등장할 때 도깨비불 현상이 일어난다는 걸 간과한 듯했고, 대회가 시작한 후 꽤 지나서 공지사항으로 추가 테스트 케이스를 제공했습니다. 이 테스트 케이스 덕분에 B를 맞게 된 분들이 몇 분 계셨지만 애초에 Master B번으로 낼 만한 수준의 문제가 아니었다는 걸 생각하지 못했던 건 아쉬움으로 남습니다. 초보자에게 문자열 처리는 생각보다 어려운 주제인가 봅니다.

대회 운영진은 참가자의 소스코드를 전부 읽어볼 수 있기 때문에, 채점 현황에서 여러 코드를 읽어봤습니다. 혹시 맞는 코드인데 틀린 건 아닌지, 틀린 코드인데 맞은 건 아닌지 등을 확인하기 위해서입니다. 코드를 확인하다 보니 cout << fixed를 하지 않아 문제를 아깝게 틀린 경우도 있었습니다. 안타까웠지만 어쩔 수 없었습니다.. 다행히도 틀린 코드가 통과하거나 맞은 코드가 통과하지 않는 경우는 없었습니다.

Master는 A, B, D, G, H의 5문제가, Champion은 A, B, C, D, F의 5문제가 각각 풀렸습니다. Champion 쪽은 제가 예상한 대로였으나 Master에서 문제가 많이 풀리지 않아 아쉬웠습니다. 과연 모두 재밌게 즐길 수 있을 만한 대회였을까요? Champion은 그랬던 것 같습니다. 안타깝게도 Master는 난이도 예상을 너무 잘못했던 것 같습니다.


이후 오픈 콘테스트도 순조롭게 진행되었고, 문제 오류는 딱히 없었기 때문에 바로 문제들을 공개했습니다. 제가 출제해 제일 어려운 문제로 기획했던 평행우주가 문제 공개 후 (고인물들에게) 나름대로의 인기를 끌고 있어 뿌듯합니다. 그렇다고 내년 ICPC Seoul Regional에 tree isomorphism이 나오는 걸 보고 싶진 않은데요.. 뭐 여하튼.

대회 운영과 문제 출제가 생각보다 어려운 것임을 깨닫게 해 준 계기가 되었습니다. 좋은 대회를 여는 건 정말 힘들다는 것도요. 생각해야 될 게 정말 많았습니다. 제가 했던 고민들이 대회를 여시려고 하시는 분들께 도움이 되었으면 좋겠습니다.

내년엔 아마도 회사에 가게 되기 때문에, 대회 출제는 3년 후에나 다시 하게 될 것 같습니다. 그 때는 난이도 조절에 조금 더 신경을 쓰고 싶습니다. 같이 출제해 주신 서강대학교 학우님들, 검수를 도와주신 분들과 참가자 분들께 모두 감사드립니다.

solved.ac 개발기 2: 더 많은 사람이 쓸 수 있게 해 보기

이 글은 solved.ac 개발기 1: 학회에서 사용할 서비스 만들기에서 이어집니다.

학회에서 사용할 수 있을 만한 서비스가 드디어 완성되었습니다. 하지만 안타깝게도 서강대학교에는 PS를 잘하는 사람이 그렇게 많지 않습니다.

Theorem 1. 서강대학교 구성원만으로 BOJ 문제들에 난이도를 일관되게 많이 달기는 힘들다.

Lemma 1. 서강대학교에는 PS를 잘하는 사람이 그렇게 많지 않다.

Proof of lemma. 애초에 시프트부터가 PS를 못한다. ∎

Proof of theorem. By Lemma 1, it’s trivial. ∎

집단지성으로 난이도를 붙이려는 시도는 이렇게 무너지고 마나요? 아니죠, 집단이 충분히 커지면 괜찮아요.

기존에 짜여 있었던 갱신 로직은 단체 랭킹 페이지를 긁어와서 갱신하기 쉽도록 되어 있었고, 더구나 전체 유저를 스크레이핑할 경우 서비스 자체가 차단될 수도 있겠다고 생각했기에, 일단은 랭킹 페이지가 있는 단체들에 제공하면 좋겠다고 생각했습니다. 다른 많은 학교들과 함께 기여해 나가면 됩니다.

집단지성

다만, 학회에서 쓸 거라고 생각했기에 신경쓰지 않은 부분이 많았습니다. 일단 전 포스트에서 언급했듯이 푼 문제 정보를 업데이트하는 속도가 초당 150문제밖에 되지 않았습니다.

오늘 기준으로 서강대학교 학생들이 맞은 문제 수를 전부 합히면 80,989문제입니다. 초당 150문제라면, 9분만에 처리할 수 있는 수준입니다. 갱신 주기가 1시간이라면 봐줄 수 있는 갱신 시간이죠.

서울의 대학교 지도

하지만 여기에 맞은 문제 132,249개의 서울대학교가 추가된다면 어떨까요? 거기에 더해 다른 학교가 열 곳, 스무 곳 이상씩 추가된다면? 아마 업데이트 시간으로 1시간은 턱없이 부족할 겁니다. 분명히 갱신 시간을 더 줄일 수 있을 텐데, 줄일 구석은 어디에 있을까요?

갱신 시간

갱신 작업은 여러 개의 작은 작업들로 나눌 수 있습니다.

문제 리스트 스크레이핑해서 문제 목록 받아오기
→ 단체 랭킹 리스트 스크레이핑해서 유저 목록 받아오기
→ 유저 페이지 스크레이핑해서 맞은 문제 목록 받아오기
→ 맞은 문제 정보를 토대로 경험치 계산
→ 맞은 문제 정보를 solved.ac 서버로 전송

줄일 구간이 어떤 게 있을까 하고 각각 단계별로 걸리는 시간을 계산해봤습니다.

  • 스크레이핑은 단체 랭킹이나 유저 페이지나, 1페이지당 1초를 넘기지 않았습니다(300ms~700ms). 다만 한 단체를 400명이라고 했을 때 단체 내의 모든 유저 페이지를 스크레이핑하는 건 약 3.6분 가량이 걸렸습니다.
  • 특히 문제 목록 스크레이핑은 전체 문제 페이지가 160페이지 가량이다 보니, 전부 스크레이핑하는 데 약 1~2분 정도가 걸렸습니다.
  • 경험치 계산도 오래 걸리지 않았습니다. 전체 문제 목록을 스크레이핑할 때 문제 난이도 정보도 solved.ac에서 가져왔기 때문입니다. 전체 문제 m개의 목록과 유저가 맞은 문제 n개의 목록은 모두 정렬된 상태였기 때문에, O(m)만에, 그리고 n이 충분히 작다면 O(n log m)만에 경험치를 계산할 수 있습니다. 2,000문제 가량을 맞은 제 유저 페이지를 기준으로, 경험치를 계산하는 데 겨우 13ms 가량이 걸렸습니다.
  • 맞은 문제 정보 갱신은 생각보다 오래 걸렸습니다. 위에서 언급했듯이 초당 150문제를 처리할 수 있는데, 제 페이지의 경우 1350ms 가량이 걸렸습니다.

결국 한 번 업데이트하는 데 맞은 문제 정보 갱신유저 페이지 스크레이핑, 그리고 문제 목록 스크레이핑 순서로 많은 시간을 쓰고 있음을 알 수 있었습니다. 경험치를 계산하는 로직에서는 더 줄일 수 있는 게 딱히 보이지 않았습니다. 이걸 어떻게 줄일 수 있을까요?

문제 목록 스크레이핑

‘이건 줄일 수 있겠다!’고 생각한 것 중 가장 먼저 생각난 것은 문제 목록 스크레이핑이었습니다. BOJ에는 1만 6천개 가량으로 많은 문제들이 있지만, 그렇다고 해도 문제가 1시간 단위로 추가되거나 하지는 않기 때문이죠.

그래서 다소 시간이 걸리는 문제 스크레이핑은 사용자 수가 가장 적을 매일 오전 6시에만 하도록 했습니다.

-reload 플래그가 있으면 문제 목록을 업데이트하게 했습니다

이를 통해 일단 2분 가량을 아낄 수 있었습니다.

유저 페이지 스크레이핑

지난 1시간 동안 푼 문제가 없는데도 업데이트를 해야 할까요? 푼 문제가 없다면 업데이트하지 않아도 되지 않을까요?

유저 페이지 스크레이핑 시간을 줄이려면 유저 페이지 자체를 들어가지 않아야 합니다. 다행히도 유저 페이지를 들어가지 않고도 푼 문제 수가 변했는지 확인할 수 있습니다. 애초에 랭킹 페이지를 스크레이핑해 오기 때문인데요,

학교 랭킹 페이지

랭킹 페이지에는 다행히도 맞은 문제 수와 제출 수가 있습니다. 이를 서버에 캐싱해 두고, 변동이 있을 경우에만 유저 페이지에 직접 들어가서 스크레이핑합니다. 참고로 재채점 등으로 인해 맞은 문제 수가 줄어들 수도 있으므로 맞은 문제 수와 제출 수를 동시에 확인해야 해요.

BOJ가 가장 활성화되는 시간인 오후 12시~1시 사이에도, 서강대학교에서는 8% 이하의 유저만이 맞은 문제 수 또는 제출 수에 변화가 있었습니다. 이런 식으로 모든 유저가 항상 BOJ를 붙들고(?) 있진 않기 때문에, 이 방법을 적용하고 스크레이핑 시간을 현저히 줄일 수 있었습니다. 학교 당 12배 정도였습니다. 게다가 BOJ 서버에 전송하는 리퀘스트 수도 획기적으로 줄이는 효과를 누렸습니다.

맞은 문제 정보 갱신

가장 많은 시간이 걸렸던 맞은 문제 정보 갱신 로직도 시간을 줄일 수 있었습니다. DB에 수많은 레코드들을 업데이트하는 건 시간이 꽤 걸리므로, solved.ac에 저장된 맞은 문제 정보와 스크레이핑해온 맞은 문제 정보를 가져와서, 차이가 있는 것들만 DB에 넣어주도록 바꿨습니다.

예를 들어 이런 경우라면 1004번과 8481번만 DB에 업데이트해 주면 됩니다.

유저 정보를 처음 가져올 때는 여전히 많은 시간이 걸렸지만, 한 명이 한 시간에 몇백 개의 문제를 풀 리가 없으므로 (과연?) 처음 유저 정보를 가져온 이후에는 푼 문제 수에 비해 엄청나게 적은 레코드를 업데이트하게 되어 갱신 시간이 상당히 줄어들게 되었습니다.

이 세 가지 방법을 적용했더니, 결과적으로 390명을 9분만에 처리하는 수준에서 8,000명을 평균적으로 5분만에 처리하는 수준까지 개선할 수 있었습니다. 처리 속도가 약 37배 빨라진 셈입니다. 이 방법을 적용하고 나서, 홍익대학교, 서울대학교, KAIST 등의 순서로 차례차례 학교를 등록해 나갔고 지금 현재 37개의 단체가 별 무리없이 갱신되고 있습니다.

하지만 현재 업데이트되는 사용자 규모는 10,000명 정도에 불과하고, BOJ 전체 유저는 16만 명 정도이므로 전체 사용자를 대상으로 갱신한다면 아마 이걸로도 부족할 것입니다. BOJ에 리퀘스트를 날리면서, 동시에 맞은 문제 차이를 계산하고, 동시에 solved.ac 서버에 업데이트하도록 백엔드를 파이프라인화시키는 것도 고려하고 있으나 애초에 서버의 vCPU 수가 2개밖에 안 되는지라 효과적일지는 모르겠네요..

여담으로, solved.ac 한 달 광고 수익은 제가 2,500원짜리 학식 라면을 꼭 5번 먹을 수 있을 정도에 불과해요. 저도 중학생 때 캐놓은 비트코인 같은 거라도 있었더라면 좋았겠네요 ㅠ


고려하지 못했던 것

그렇게 많은 학교를 추가하고 한동안 여러 기능들을 추가하면서 평화롭게(?) 지냈습니다. 모든 기능이 문제없이 잘 돌아가고 있었습니다. 근데 원래 모든 게 잘 돌아가면 어딘가 불안해집니다. 저만 그런가요?

아무튼 그렇게 매일 새벽까지 개발하고 늦잠 자고 아침강의도 없겠다 늦게 일어나고 하는 평화로운 나날을 보내고 있었습니다. 이런 메시지를 받기 전까지는요.

아니 대체 왜?

갑자기 로그인이 안 될 이유가 딱히 없는데 로그인이 안 된다고 합니다. 음 뭐지?

No space left on device라고 합니다. df 명령어로 남은 공간을 확인해봤는데 공간은 아직 많이 남아 있습니다. 진짜 뭐지??

구글링 끝에 알게 되었습니다. ext4 파일시스템에는 파일의 메타데이터를 저장하는 inode가 있는데, 이 수에 제한이 있다고 합니다. df -hi로 inode 사용량을 분석할 수 있습니다.

역시 inode 사용량이 가득 찼던 거였습니다. Inode가 가득 찼다는 건 파일을 엄청 많이 만들었다는 뜻이 될 거 같은데, 파일을 그렇게 많이 만든 적이 없었던 거 같은데 대체 어느 부분에서 이렇게 되었을까요?

바로 세션 정보들이었습니다. 세로로 긴 이미지 하나 보고 갑시다.

많이 삭제한 게 이 정도입니다.’

세션 파일이 몇백만 개나 있었습니다. 이 세션 파일들이 inode 개수를 다 잡아먹고 있었습니다.

커스텀 세션 핸들러

불행 중 다행으로 PHP는 세션 핸들러를 직접 만드는 게 가능했습니다. 기존 세션 파일들을 전부 삭제하고, MySQL을 사용하는 세션 핸들러를 만들어 교체해 줬더니 세션들이 전부 DB에 저장되었고, inode 폭발 현상이 다시 일어나는 일은 없었습니다.


다음에 한가할 때는 프론트엔드를 짜면서 했던 고민들에 대해 이야기해 보고자 합니다. 최근 solved.ac에 제출된 난이도 의견 수가 12,000건을 넘겼습니다. 학회에서만 사용하려고 했는데 어쩌다 보니 여기까지 올 수 있게 되었습니다. 사이트에 관심 가져 주셔서 정말로 감사하고, 알고리즘 문제해결을 공부하는 사람들의 길잡이가 될 수 있는 좋은 커뮤니티 프로젝트가 되도록 노력을 아끼지 않겠습니다.

감사합니다!

solved.ac 개발기 1: 학회에서 사용할 서비스 만들기

병역특례 인원이 축소된다는 분위기입니다. 알 수 없는 위기감이 맴돕니다. Sogang ICPC Team에서 (학회장 한다는 사람이 없으면) 제가 졸업할 때까지 학회장을 하려고 했는데, 지금 병역 문제를 해결하지 않으면 졸업한 후에 어떻게 될 지 모르기 때문에 이번 학기를 마치고 산업기능요원으로 가기로 결심했습니다. 누가 뽑아줘야 가겠지만..,

여하튼 학회장으로 있으면서 해 보고 싶은 일은 많았는데, 당장 이번 학기가 끝나고 제가 사라지게 되어서 가장 해 보고 싶었던 일을 해 보리라 마음먹었습니다.

TMI가 많습니다(이거 동어반복인가요?). 각오하시고 읽어 주세요!

acm이 icpc와 관련 없는 단체가 되어서 지금은 학회 이름이 ‘Sogang ICPC Team’이 되었습니다.

Sogang ICPC Team은 서강대학교 컴퓨터공학과의 알고리즘 문제해결 소학회입니다. 알고리즘 문제해결 학회라면 목적에 맞게 알고리즘 문제들을 해결해야겠죠? 우리 학회는 Baekjoon Online Judge(BOJ)라는 플랫폼을 문제은행으로 쓰고 있습니다.

문제는 BOJ가 다 좋은데 ‘문제 난이도’라는 지표가 없다는 것입니다. 애초에 BOJ에는 여러 대회들에서 가져온 14,000개가 넘는 문제들이 등록되어 있고, 이 수많은 문제들에 일관된 난이도 기준으로 난이도를 매기는 건 상당히 어렵기 때문일 것입니다.

하지만 ‘문제 난이도’라는 정보가 없어서 처음 시작한 학회원들이 공부를 시작하기가 어려웠습니다. 물론 jh05013님의 단계별로 풀어보기도 있지만 단계별로 문제가 그렇게 많진 않아서 충분히 연습하기는 곤란했습니다. 대신 문제집을 만들 수는 있어서, 지금까지 우리 학회는 수많은 문제들을 대략적인 난이도 그룹으로 나누고 문제집을 많이 만들어 이런 식으로 관리하고 있었습니다.

네 저 그리디 못해요

이 방법은 처음엔 좋았으나 문제집이 추가될수록 여러가지 문제가 생겼습니다.

  • 문제집이 너무 많아졌습니다. 지금 학회 그룹에 등록된 문제집 수는 64개입니다.
  • 한 문제집에는 문제를 100개까지밖에 못 넣습니다. BOJ에는 다이나믹 프로그래밍 문제만 500개가 넘게 있습니다.
  • 문제를 푼 직후 문제집에 문제 하나를 추가하려면 적어도 다섯 번은 클릭해야 합니다.(‘그룹’ – ‘ICPC Team’ – ‘문제집’ – ‘수정’ – ‘확인’) 생각보다 상당히 번거로운 작업입니다.

결국 문제 하나하나에 난이도를 매길 수 있는 크롬 확장 프로그램을 만들자는 결론에 다다랐습니다. 더 나아가서 푼 문제들의 난이도에 따라 개개인마다 레벨을 부여한다면 문제를 풀 동기도 마련해 줄 수 있겠다는 생각이 들었습니다. 당장 착수했습니다.

첫 버전

시험기간 버프로 이틀만에 첫 버전이 나왔습니다. PHP로 간단하게 백엔드를 만들었습니다. 크롬 플러그인은 예전에 만들어 본 적 있어서 어렵지 않게 새로 만들 수 있었습니다.

문제 목록. 지금 쓰는 난이도 아이콘이 없었고, 전부 텍스트였습니다.

난이도 투표 스크린입니다. 역시 디자인은 신경쓰지 않았습니다.

작년(2018년)에 숭실대학교 최고의 동아리 SCCC가 우리에게 시비를 걸었던 적이 있는데, 그냥 두고 볼 수 없었던 저는 서강대학교가 아직 못 푼 문제들을 정리해 두는 서비스를 간단히 만들었습니다. 그 때 만들어 두었던 문제 데이터베이스를 수정해 ‘문제 난이도’라는 칼럼을 하나 만들고, 투표하면 값을 넣는 식으로 구현했습니다. 당연히 한 명만 투표가 가능했습니다.

하지만 제가 어렵다고 생각한 문제를 최고의 임원 raararaara 선배께서는 쉽다고 생각하실지도 모르는 일입니다. 한 명만 투표할 수 있는 건 뭔가 아닌 거 같습니다. 여러 명이 투표할 수 있게 하되 최종 문제 난이도는 여러 명의 투표값의 평균으로 하기로 계획했습니다. 이를 구현하려면 생각해야 될 사항들은 아래와 같습니다.

  • 투표를 저장하는 데이터베이스 구조는 어떻게 해야 할까? 기존 투표도 수정할 수 있어야 하고…
  • 내가 투표했다고 치면, 투표한 사람이 진짜 shiftpsh인지 아닌지는 어떻게 검증할 수 있을까? 클라이언트는 절대 믿으면 안 되니까 페이지에서 유저네임을 그냥 뽑아오는 방법은 안 될 텐데… (실제로 개발자 도구를 열어 HTML을 조작한다면 이 방법은 정말 쉽게 파훼가 가능합니다)

데이터베이스 구조는 그다지 어렵지 않았습니다. 유저와 문제 번호마다 하나의 난이도 값이 있는 테이블을 새로 만들었습니다. 투표한 사람을 검증하는 일은 생각을 해 봐야 했습니다. 당시에는 임원들만 난이도 투표를 하게 할 생각이었어서 큰 고민은 아니었습니다. 후술하겠습니다.

티어 계산

[속보] ICPC Team 학회장 임원 디스코드 유출
 

임원 분들과 열심히 난이도를 매긴 결과 600문제 정도에 난이도가 붙게 되었습니다. 전체 문제의 4%밖에 안 되지만 다들 많이 푸신 문제들 위주로 매겼다보니 이 정도면 티어 계산을 해도 되겠다는 생각이 들었습니다.

티어를 계산하려면 고려해야 될 것들에는 이런 것들이 있습니다.

  • 경험치 테이블. 레벨 업 기준들과 문제당 경험치. 문제 난이도와 티어는 각각 30단계씩이 있습니다. 어려울수록 경험치를 많이 주고 싶지만 한 티어 높은 문제를 풀었다고 보상을 엄청 많이 주긴 좀 그렇고, 그렇다고 브론즈 5 문제만 엄청 풀어서 플래티넘 가게 하고 싶진 않았습니다.
  • 사용자가 푼 문제 정보 가져오기: 한 단어로 크롤링입니다. BOJ는 사이트에 부담이 가는 크롤링을 허용하지 않고 있습니다. 지금은 백준님께서도 이 사이트의 존재를 알고 계시지만 당시에는 비밀스럽게 진행했던 프로젝트였어서 BOJ에 최대한 요청을 적게 보내면서 크롤링을 해야 했습니다.
  • 사용자가 푼 문제들의 정보를 저장하는 데이터베이스의 구조도 생각해야 했습니다.

초기에는 난이도가 한 단계 올라가면 받는 경험치가 1.4배가 되도록 테이블을 설정했습니다. 레벨 업 조건은 총 경험치가 (전 티어 경험치) + (현 티어와 같은 난이도의 문제를 풀면 주는 경험치) * (상수)로 정했습니다. 현재는 조금 다르게 정해져 있습니다.

문제 난이도가 내려가지 않는 한 티어가 떨어질 일도 없습니다. 티어가 떨어질 일이 별로 없다는 것은 어려운 문제에 많이 도전할 충분한 동기 부여가 됩니다.

서강대학교 랭킹

테이블은 잘 정했지만 크롤링이 문제였습니다. 일단 BOJ에 등록되어 있는 서강대학교 구성원은 당시 약 390명이었습니다.

코틀린으로 짠 크롤링 프로그램은 문제 리스트 전체(약 160페이지)와 서강대학교 구성원 전체를 파싱합니다. 한 번 실행에 총 550번의 리퀘스트를 보내는 셈입니다. 실시간성을 위해 1분에 1번 업데이트한다고 생각하면 하루에 BOJ 서버에 792,000개의 리퀘스트를 날린다는 계산이 나왔습니다. 이건 밴 당할 게 분명합니다.

그래서 일단 실시간성을 포기하고 1시간에 1번 업데이트하는 것으로 정했습니다. 하루 13,200개의 리퀘스트는 여전히 많지만, 79만 개보단 훨씬 적기 때문에 ‘음.. 문제 열심히 푸는 사람이라면 하루에 리퀘스트 1만 개 정도는 보낼 수 있지 않을까?'(불가능합니다) 같은 막연한 생각으로 cron 태스크를 만들었습니다. 1시간에 1번씩 잘 돌아갔습니다.

어떻게 이걸 효율을 높일 수 있지

그런데 예상하지 못한 문제가 또 있었습니다. 파싱은 잘 됐는데, 데이터베이스에 푼 문제들을 등록하는 게 너무 오래 걸렸습니다. 문제를 많이 푼 순으로 위에서 15명이 푼 문제 정보를 데이터베이스에 등록하는 데 무려 12분이 걸렸습니다. 54문제를 등록하는 데 1초 걸린 셈입니다. 뭔가 방법이 잘못되었다는 걸 직감했습니다.

트위터 찬스를 썼습니다.

무려 새벽 1시 반에 트윗을 남겼음에도 불구하고 트위터에 인생을 파신 개발자 분께서 바로 대답해 주셨습니다.

하지만 A는 문자열이었습니다. 저는 문자열이 primary key가 될 리가 없다고 생각하고 ‘A가 스트링이죠’라고 답글을 보냈습니다. primary key와 인덱스가 여러 칼럼에 걸릴 수 있다는 것도 몰랐습니다. 답글로 얻어맞게 됩니다.

그냥 제가 SQL을 모르는 거였습니다. 당장 유저명과 문제 번호에 primary key, unique, index를 걸었고 쿼리 속도가 초당 150문제 정도로 개선되었습니다.

쿼리 속도가 세 배 개선되었습니다

PK를 적용하고 나니 서강대학교 전체를 업데이트하는 데엔 6분 가량이 걸리게 되었습니다. 여전히 조금 느렸지만, 서강대학교만 쓰던 당시로서는 만족할 수 있었던 성능이었기에 나중에 생각하기로 했습니다.

푼 문제들을 파싱했으니 난이도 순으로 정렬된 유저 페이지를 만들 수 있을 거 같아서 이것도 만들었습니다. CSS는 ask.shiftp.sh의 것을 가져와서 개조했기 때문에 만드는 데 오래 걸리진 않았습니다. 이거 발전시키면 개인적으로 프레임워크같이 쓸 수 있을 거 같다는 생각도 하는 중입니다.

초기 푼 문제 목록 페이지

이 날 랭킹 페이지도 새로 만들었습니다.

본인 확인

앞에서 난이도 투표를 한 사람이 누군지 검증할 수 없는 문제가 있었다고 언급했습니다. 이를 해결하기 위해 일단 solved.ac에 따로 회원가입 시스템을 만들었습니다.

플러그인에서 로그인하면 서버에서 토큰을 발급해 주고, 이를 로컬에 저장해 뒀다가 문제 난이도를 매길 때 인증 정보로서 서버에 다시 보내는 식으로 구현하는 것으로 해결했습니다.

문제는 solved.ac에 가입하는 사람이 BOJ의 그 사람이 맞는지 아닌지 검증하기가 곤란하다는 건데, 디스코드에 있는 외국 알고리즘 문제해결 커뮤니티 CP Community의 한 봇에서 영감을 얻을 수 있었습니다.

CP Community는 러시아의 Codeforces 플랫폼을 기반으로 활동하는데, 이 디스코드 서버는 특정 문제에 컴파일 에러가 나는 코드를 제출하게 해서 본인임을 확인합니다.

초기 본인 인증

BOJ에는 소스를 공개적으로 공유할 수 있는 기능이 있습니다. 이 기능을 이용해 공유된 소스는 문제를 풀지 않았거나 심지어 로그인하지 않았더라도 누구나 열람할 수 있습니다.

따라서 틀려도 부담되지 않을 만한 문제를 골라 서버에서 랜덤하게 생성한 문자열을 입력하고, 그 소스를 공유해 소스 주소를 서버에 보내면 서버가 이를 검증하는 방식으로 본인인지 아닌지는 확인할 수 있습니다. 이를 통해 투표하는 사람이 누구인지에 대한 걱정도 해결했습니다.

이렇게 학회 내부에서 사용할 서비스가 완성되었습니다.

한계

이 서비스는 분명한 한계가 있었습니다. 기술적인 한계는 아닙니다. 서강대학교는 사람이 적어서 많은 사람들이 학교 리스트에 등록될 리 없기 때문입니다. 다만 사람이 적기 때문에 난이도 의견 자체가 적었습니다. 활발하게 난이도를 매기는 사람들은 저를 포함한 임원들이나 문제를 많이 풀어본 사람들 뿐이었고, 그분들마저도 일정 수준 이상의 문제에 난이도를 매기는 건 역부족이었습니다.

해결방법은 서강대 밖의 많은 고수들을 끌어모으는 것이었습니다. 하지만 많아봐야 고작 100명 정도의 학회원들이 사용하는 서비스를 수천 명이 사용하는 서비스로 개조하기 위해서는 생각을 많이 해야 했습니다.

이번 포스트에서는 ‘제가 SQL을 정말 몰랐네요’, ‘본인확인 이렇게 하는데 어때요 멋지죠?’ 말고 별다른 기술적인 내용을 다루지 않아 결국 일상 포스팅 같은 게 되었지만, 다음 포스트에서는 solved.ac를 수천 명이 사용하는 서비스로 개조하면서 한 생각들을 다뤄볼 생각입니다.

인터넷에서 북한 acm-icpc 문제를 찾았습니다

[mathjax]

인터넷에서 acm-icpc 2016 평양 리저널 문제를 찾았습니다. 북한 문제는 어떤 수준인지, 컴퓨터 과학 용어는 우리와 얼마나 많이 차이나는지 궁금해서 저화질의 사진을 보기 쉽게 글로 다시 정리해 보았습니다. 줄바꿈과 일부 기호는 임의로 수정했습니다.

총 12문제로 구성되어 있습니다. 개인적으로는 Mathforces 대회 같은 느낌의 문제들이라고 생각됩니다.

모든 문제는 ICPC Live Archive에서 풀어볼 수 있습니다. 시간제한이 다릅니다.


문제 1. 배렬전도수

  • 시간 제한: 1초
  • 메모리 제한: 64MB

설명

당신들은 모두 배렬1의 전도수에 대하여 알것이다. 배렬 \(\left\{ a_1, a_2, \cdots, a_n \right\} \)의 전도수는 \(i < j\)이고 \(a_i > a_j\)인 \(\left(i, j \right)\)의 쌍의 개수로 정의한다.

한민이는 총명한데 지금 새로운 배렬의 전도수를 생각하고있다.

만일 \(i\) 와 \(j\) 의 짝홀성이 같으면서 \(a_i > a_j\)이면 그는 \(\left(i, j \right)\)를 전도된 쌍으로 생각한다. 한편 짝홀성이 다르면서 \(a_i < a_j\)이면 그는 이런 쌍\(\left(i, j \right)\)도 전도된 쌍으로 생각한다. 다른 말로 말한다면 첨수쌍2 \(\left(i, j \right)\)는 \(i\) 와 \(j\) 의 짝홀성이 같을 때 \(a_i > a_j\)이거나 다를 때 \(a_i < a_j\)이면 전도된 쌍이다.

당신은 한민의 딱친구3이고 배렬의 전도된 쌍의수를 계산할데 대한 부탁을 받았다. 당신은 풀수 있는가?

입력

입력파일의 첫행은 입력자료4개수 \(T \left(1 \leq T \leq 5\right)\)로 되어있다.

매입력자료의 첫행은 한개의 옹근수5 \(N \left(1 \leq N \leq 5000\right)\)을 포함하는데 그것은 배렬의 길이이다.

다음행에 \(N\) 개의 실수가 공백단위로 분리되어 들어온다.

출력

당신은 매 입력자료별로 한행에 전도수를 찍는다.

표준입력

1
5
1 4 3 2 5

표준출력

5

문제 2. \(B_N\)

  • 시간 제한: 1초
  • 메모리 제한: 128MB

설명

총명한 학생 리기웅은 물리를 아주 잘하지만 수학은 잘하지 못한다. 그의 동무 신영진은 반대로 수학을 잘하고 물리를 잘하지 못한다. 그래서 리동무는 신동무의 물리숙제를 도와주고 신동무는 리동무의 수학숙제를 도와준다.

오늘 리동무는 아주 힘든 수학문제를 받아가지고 와서 신동무에게 물어보았다. 그러나 신동무는 아주 바빠서 그는 당신에게 풀어줄것을 부탁하였다. 당신은 신동무의 딱친구이며 반드시 그것을 풀어야 한다. 문제는 다음과 같다.

배렬 \(\left\{ A_1, A_2, \cdots, A_n \right\} \)이 주어졌다. 새로운 배렬 \(\left\{ B_1, B_2, \cdots, B_n \right\} \)은 다음의 공식에 따라 정의된다.

\[ B_N = \left( \sum_{\substack{i_1+i_2+\cdots+i_k=N \\ 1\leq k \leq N}} A_{i_1}A_{i_2}\cdots A_{i_n} \right) \% 1000000007 \]6

물론 \(1 \leq i_1, i_2, \cdots, i_k \leq n\) 이다. \(u \neq v\)에 대하여 \(i_u = i_v\)도 가능하다. 실제로 \(B_3 = A_1 \times A_1 \times A_1 + A_1 \times A_2 + A_2 \times A_1 + A_3\)이다. 당신은 반드시 주어진 \(N\)에 대하여 \(B_N\)을 계산해야 한다.

당신은 그들을 도와줄수 있는가?

입력

입력파일의 첫행은 입력자료개수 \(T\)로 되어있다.

매 자료의 첫행은 두개의 옹근수 \(n\) 과 \(N\)으로 되어있다. \(\left(1 \leq n \leq 100, 1 \leq N \leq 100\right)\)

다음행에는 \(n\) 개의 옹근수가 공백단위로 분리되어 들어온다.

출력

문제의 결과를 출력하시오.

표준입력

1
2 5
3 2

표준출력

495

문제 3. 행렬검사

  • 시간 제한: 1초
  • 메모리 제한: 512MB

설명

정교수는 제 41 차 국제대학생프로그람아시아평양지역경연 문제출제자이다. 그는 100개조의 2016 × 1946 행렬과 1946 × 2016행렬의 곱하기를 끝냈다. 물론 결과는 2016 × 2016행렬식이다. 계산하는데 거의 10일 걸렸다. 결과는 100개조이고 문제 C의 입출력자료로 될것이다.

계산이 끝난 후 정교수는 잠들었고 그의 아들이 결과에 손을 댔다. 그는 어느 한 수의 하나의 자리를 지우고 수자7 1을 써넣었다.

다음날 정교수는 매우 성났다. 그러나 아들애는 겨우 2살이어서 모든것을 기억하지 못한다.

정교수는 그의 아들의 말을 들어보고 세부를 검사한다. 그래서 그는 아들이 매 조의 한수의 하나의 자리수를 변화시켰고 그 수자가 2, 0, 1, 6 중의 하나라는것을 알았다. 그리고 그는 아들이 변화시킨 위치가 행번호와 렬번호가 70 이하라는것을 알았다. 행렬의 왼쪽웃구석의 번호는 (1, 1) 이다. 첫 첨수는 행번호이고 다음번호는 렬번호이다.

그는 입출력을 오늘중으로 전송하여야 한다. 그래서 그는 결과를 검사할 결심을 하였다. 당신은 그의 우수한 학생이다. 정선생을 도우시오.

입력

입력파일은 꼭 100조의 입출력자료로 되어있다. 매 조는 다음과 같이 정의되었다.

첫행은 5개의 옹근수 \(a_1, a_2, a_3, a_4, a_5\)로 되어있다. 당신은 다음과 같이 행렬 \(A\)를 얻을수 있다.

\[A_{ij} = (a_1 \times i^4 + a_2 \times i^3 + a_3 \times j^2 + a_4 \times j + a_5) \% 1946002016\]

다음행은 5개의 옹근수 \(b_1, b_2, b_3, b_4, b_5\)로 되어있다. 당신은 다음과 같이 행렬 \(B\)를 얻을수 있다.

\[B_{ij} = (b_1\times i^4 + b_2\times i^3 + b_3\times j^2 + b_4\times j + b_5) \% 1946002016\]

다음 왼쪽웃구석의 70 × 70 옹근수 행렬이 있다. 당신은 이 행렬식을 검사하여야 한다.8

당신은 두 행렬을 곱할 때 행렬을 반드시 2016011010에 관하여 나머지를 취한다.

출력

당신은 어느 입력조가 아들에 의해 변화되었는가를 출력해야 한다. 입력의 번호는 1부터 100까지 이다. 당신의 출력은 반드시 증가순서로 출력해야 하며 공백단위로 분리되어있어야 한다. 만일 모든 입력조들이 변화되지 않았다면 0을 출력하시오.

입력과 출력의 실례

입력과 출력이 너무 커서 우리는 당신들에게 입력과 출력의 실례를 보여줄수 없다. 당신은 입출력의 형식을 담보해야 한다.


문제 4. 사과나누기

  • 시간 제한: 8초
  • 메모리 제한: 512MB

설명

현일은 도덕있는 학생이다. 그는 항상 그의 학급동무들과 친구들을 자기자신처럼 대해준다. 하루는 그가 맛있고 큰 사과를 가져와 그의 친구들에게 나누어주려고 한다. 흥미있는것은 사과가 타원모양이라는것이다.

그는 항상 두가지 조작을 진행한다.

첫번째는 사과의 \(L\)부터 \(R\)각도사이의 남은 면적을 계산하는것이다.

둘째는 \(L\)부터 \(R\)각도사이의 모든 사과쪼각들을 주는것이다.

현일은 사과를 데카르트자리표계9에 놓았으며 결과 사과는 타원 \(\frac{x^2}{a^2}+\frac{y^2}{b^2}=1\) 에 자리잡고있다.

현일의 형인 당신은 어린 동생의 계산능력을 시험해보려고 하는데 당신은 모든 질문들에 반드시 대답해야 한다.

할수 있는가? 있다.

아, 한가지 조건이 또 있는데⋯ \(prev\)는 마지막으로 출력된 수이며 실제 \(L\)과 \(R\)은 다음의 공식에 의해 계산된다.

\[L_{real} = \left( L_{given} + prev \right) \% 360, R_{real} =\left( R_{given} + prev \right) \% 360\]

만약 \( L_{real} > R_{real} \)이면 당신은 두값을 바꾸어야 한다. 당신은 조작을 \(L_{real}\)과 \(R_{real}\), 두값을 가지고 해야 한다. 처음에 \(prev = 0\)이다.

입력

입력파일의 첫행은 세옹근수를 포함한다. – \(a\) \(b\) \(n\) \(\left( 1 \leq a, b \leq 100, n \leq 300000 \right)\)

\(a\)와 \(b\)는 우에서 설명한 수이고 \(n\)은 조작회수이다.

다음의 \(n\)개 행은 세 수 “\(type\) \(L\) \(R\)”을 포함한다. (\(1 \leq type \leq 2\), \(L\)과 \(R\)은 임의의 실수이다.) \(0 \leq L + prev,0 \leq R + prev\) 라는것은 담보할수 있다.

출력

모든 조작1에 대해서 결과를 계산해야 한다. 소수점아래 5자리에서 반올림하여 출력하시오.

표준입력

10 10 3
1 10.00000 30.00000
2 40.00000 70.00000
1 10.00000 300.00000

표준출력

17.45329
226.89280

주해

문제가 쉬워 지도록 \(L\)과 \(R\)도 소수점아래 5자리로 주어진다. 그리고 \(prev\)는 마지막으로 출력된 첫번째 질문의 값이다. 실례로 \(prev = 17.45329\) 이지만 실제 대답은 \(17.453297519943295769236907684886\cdots\)이다.10


문제 5. 쉬운 기하문제

  • 시간 제한: 1초
  • 메모리 제한: 32MB

설명

\(ABCD\)는 4면체이며 \(\overline{DA} = a\), \(\overline{DB} = b\), \(\overline{DC} = c\), \(\angle BDC = \alpha\), \(\angle ADC = \beta\), \(\angle ADB = \gamma\)로 주어진다. 당신은 \(ABCD\)의 내접원11반경을 계산해야 한다.

입력

첫행은 입력자료개수 \(T (1 \leq T \leq 100000)\)로 되어있다.

매 입력자료는 6개의 수 \(a, b, c, \alpha, \beta, \gamma\) \((1 \leq a, b, c \leq 100, 0 < \alpha, \beta, \gamma < 360)\) 을 포함한다.

출력

내접원의 반경을 소수점아래 6자리에서 반올림하여 출력하시오.

표준입력

1
10 10 10 90 90 90

표준출력

2.113249

문제 6. 가장 좋은 경로찾기

  • 시간 제한: 4초
  • 메모리 제한: 256MB

설명

비트시는 바이트랜드의 수도이다. 비트시에는 현대적인 고속도로체계가 있으며 그 체계는 자주 갱신되는데 고속도로들이 체계에 추가된다. 체계는 교차점들을 연결하는 고속도로들로 이루어져있다.

운수회사 사장인 당신은 어느 한 교차점에서 다른 곳으로 콤퓨터들을 수송하려고 한다. 그런데 바이트랜드에서 휘발유값이 너무 비싸 당신은 한대의 화물자동차로만 나르려고 한다. 당신은 가능한껏 많은 콤퓨터들을 나르려고 하지만 모든 고속도로들은 \(W\)대이상의 콤퓨터들은 나를수 없다는 제한을 가지고있다.

당신은 나를수 있는 콤퓨터의 최대값을 계산해야 한다. 당신의 초기의 고속도로체계상에서 임의의 두 교차점사이로 이동할수 있다. 다시말하여 원래 체계는 연결되었다.12

입력

첫행은 입력자료개수 \(T (1 \leq T \leq 3)\)로 되어있다.

매 입력자료는 교차점과 도로수를 의미하는 두 옹근수 \(N\)과 \(M\)으로 시작된다. \((3 \leq N \leq 70000, N-1 \leq M \leq 150000)\)

다음의 \(M\)개행은 \(a\)와 \(b\)사이에 도로가 있으며 제한은 \(c\)임을 의미하는 세개의 옹근수 \(a\) \(b\) \(c\)를 포함한다. \((1 \leq a, b \leq N, 1 \leq c \leq 10000)\)

다음 행은 질문의 개수를 의미하는 하나의 옹근수 \(Q (1 \leq Q \leq 105000)\)를 포함한다. 모든 질문은 다음의 두 종류중 하나이다.

  1. \(a\) \(b\) \(c\): \(a\)와 \(b\)사이에 도로를 련결하며 제한은 \(c\)이다.
  2. \(a\) \(b\): \(a\)로부터 \(b\)로 나를수 있는 콤퓨터의 최대개수를 계산하시오. \((1 \leq a, b \leq N, 1 \leq c \leq 10000)\)

두 교차점사이에는 둘 혹은 그 이상의 도로가 있을수 있다.

출력

둘째 종류의 매 질문에 대해 나올수 있는 콤퓨터의 최대대수를 출력하시오.

표준입력

1
5 6
1 2 2
1 3 3
2 4 7
2 5 1
3 4 6
3 5 5
4 
2 2 5
1 4 5 8
2 2 5
2 3 4

표준출력

5
7
6

문제 7. 좋은 날들

  • 시간 제한: 1초
  • 메모리 제한: 64MB

설명

당신은 두개의 날자 \(\texttt{y/m/d}\)와 \(\texttt{yy/mm/dd}\)를 입력 받는데 하나는 첫번째 좋은 날이고 하나는 마지막 좋은 날이다. 그것들사이의 모든 날들도 역시 좋은 날이며 다른것들은 그렇지 않다. 당신은 좋은 날자수를 계산해야 한다.

입력

첫행은 입력자료개수 \(T (1 \leq T \leq 10000)\)로 되어있다.

매 입력자료는 6개의 옹근수 \(y\) \(m\) \(d\) \(yy\) \(mm\) \(dd\)로 되어있다. \((1 \leq y, yy \leq 5000)\)

출력

좋은 날자수를 출력하시오.

표준입력

1
2016 11 8 2016 11 11

표준출력

4

문제 8. 효성과 광성

  • 시간 제한: 1초
  • 메모리 제한: 256MB

설명

영어소문자로 이루어진 긴 문자렬 \(S\)가 있다. 두 소년 효성이와 광성이는 재미난 경기를 한다. 경기규칙은 다음과 같다.

초기에 심판원 학명이가 그들에게 비지 않은 \(S\)의 부분문자렬을 준다. (우리는 그것을 \(P\)로 표시하자.) 두명의 경기자는 교대로 뒤에 한개의 문자를 추가하여 새로 생긴 문자렬이 \(S\)의 부분문자렬이 되게 한다. 만일 그들이 문자를 추가하지 못하면 경기는 끝난다.

효성이는 마지막 문자렬이 가능한껏 짧게 하려고 하고 광성이는 문자렬이 가능한껏 길게 하려고 한다. 효성이는 첫 경기자이다. 만일 그들이 최량13으로 경기를 한다면 매 문자렬에 대하여 추가되는 문자의 수를 추측할수 있다. (우리는 그것을 \(f(P)\)로 표시하자.)

부분문자렬 \(A\)는 만일 \(f(A) < f(B)\) 이거나 \(f(A) = f(B)\)이고 \(A\)가 \(B\)보다 사전순으로 앞에 놓이면 부분문자렬 \(B\)보다 작다고 정의한다.

주어진 옹근수 \(K\)에 대하여 문자렬 \(S\)의 \(K\)-번째로 작은 문자렬을 찾으시오. 찾아낼수 있는가?

입력

첫행은 한개의 문자렬로 되어있는데 그것의 길이는 500000 이하이다.

두번째행은 하나의 옹근수 \(K (1 \leq K \leq 1000000000)\)로 되어있다.

출력

결과 문자렬에 대하여 그것에 추가되는 문자의 수와 결과문자렬을 공백단위로 분리하여 출력하시오.

표준입력

aababb
8

표준출력

1 abab

문제 9. 국제망봉사

  • 시간 제한: 1초
  • 메모리 제한: 256MB

설명

지구상에는 수많은 망봉사기14들이 있다. 모든 수 \(i\)에 대하여 \(i\)번째 망봉사기는 “반경” 이라고 불리우는 지수값 \(R_i\)를 가지고있으며 봉사기는 자기로부터 떨어진 거리가 \(R_i\)이하인 모든 점들까지 봉사15할수 있다.

일부 점들은 많은 봉사기들로부터 봉사받을수 있다. 너의 과제는 최대로 많은 개수의 봉사기로부터 봉사받을수 있는 점을 찾는것이다.

지구는 6370의 반경을 가진 완전구로 보며 지구겉면의 구 점사이거리는 유클리드거리가 아니라 겉면상에서의 거리이다.

문제를 쉽게 하기 위해 망봉사기들의 반경을 2012 부터 2016 사이로 한다. (2012와 2016 포함)

입력

첫행은 입력자료개수 \(T (1 \leq T \leq 6)\)로 되어있다.

매 입력자료의 첫행은 봉사기의 대수 \(N (1 \leq N \leq 1000)\)을 포함한다.

다음 \(N\)개 행은 봉사기의 경도와 위도, 반경을 나타내는 세 옹근수를 포함한다. (0 ≤ 경도 < 360, -90 < 위도 < 90)

출력

문제의 답을 출력하시오.16

표준입력

1
2
0 0 2012
0 1 2016

표준출력

2

문제 10. 보석통

  • 시간 제한: 3초
  • 메모리 제한: 256MB

설명

성영은 아무런 수학문제도 아주 빨리 풀수 있다. 그의 형 최광은 비싼 보석들을 보관할수 있는 빈 \(N\)개의 보석통들을 가지고있다.

하루는 최가 보석상점에서 \(N\)개의 보석을 가져왔다. 최는 모든 보석들을 한통에 한개씩 넣을것이다. 다시말하여 그는 매통에 오직 하나의 보석을 보관할것이다.

모든 보석들은 4개의 수를 가지고있는데 보관번호 \(p\), 통에 도착하는 시간 \(t\), 그리고 2가지 값 \(a\)와 \(b\)를 가진다. \((p, t, a, b)\)에대한 설명을 하자.

보석\((p, t, a, b)\)이 도착하면 최는 이미 도착한 보석들가운데서 가장 잘 결합되는 보석을 찾아내야 한다. 가장 잘 결합되는 보석\((p_1, t_1, a_1, b_1)\)은 다음의 조건을 만족시켜야 한다.

  1. 그것은 반드시 새 보석보다 먼저 도착하여야 한다. 다시말하여 \(t_1 < t\).
  2. 그것의 통번호는 \(p\)보다 작아야 한다. 다시말하여 \(p_1 < p\).
  3. 결합효과가 최대로 되어야 한다. 결합효과는 다음과 같이 정의한다. \(a_1 \times a + b_1 \times b\).

그리고 최는 그 통의 뚜껑에 보석들의 결합효과를 써넣으려고 한다. 그래서 최는 성영에게 매통의 뚜껑에 수를 계산하여 써놓을것을 부탁했다. 성영을 도와주자.

입력

첫행은 옹근수 \(N (1 \leq N \leq 100000)\) 을 포함하는데 이것은 보석통의 개수이다.

그리고 다음 \(N\)개의 행이 있다.

\(p\)번째행은 3개의 변수 \(t\) \(a\) \(b\)를 포함한다. – 그곳은 보석 \((p, t, a, b)\)를 의미한다. \((1 \leq t \leq 1000000000, 1 \leq a, b \leq 1000000)\)

어느 두개의 보석도 동시에 도착하지는 않는다.

출력

\(N\)개의 옹근수들을 출력하시오. \(p\)번째수는 \(p\)번째 뚜껑에 써넣을 수이다.

표준입력

3
1 1 1
2 2 2
3 3 3

표준출력

0
4
12

문제 11. K번째 그라프 절단

  • 시간 제한: 3초
  • 메모리 제한: 512MB

설명

지성은 그라프리론17을 배우기 좋아한다. 처음 그는 최소생성나무18에 대하여 배웠다. 다음 그는 최단경로에 대하여 배웠다. 그리고 그는 지금 그라프의 절단문제에 대하여 배우고있다.

무게붙은 방향그라프19(그것은 연결이 아니어도 된다)와 원천과 목적지가 주어진다. 말할 필요는 없지만 원천과 목적지는 그라프의 한개 정점이다.

다음 당신은 그라프에서 원천지와 목적지사이에 아무런 경로도 없게 그라프에서 마디20를 없애야 한다. 그때 제거한 마디들의 무게 합을 “절단” 이라고 부른다.

지성은 이미 일반그라프에서 최소절단이 원천지와 목적지사이의 최대흐름과 같다는것을 알고있다. 그리고 그는 지금 \(K\)째 최소절단에 대해서 알고싶어한다. 그는 \(K\)째 최소생성나무와 \(K\)째 최단경로를 구할수 있지만 \(K\)째 최소절단을 구할수 없다. 그를 도와주자.

입력

첫행은 5개의 옹근수 \(N\) \(M\) \(K\) \(S\) \(T\)를 포함한다.

\(N (1 \leq N \leq 100)\) – 그라프의 정점수를 의미한다.

\(M (1 \leq M \leq 1000)\) – 그라프의 마디수를 의미한다.

\(K (1 \leq K \leq 100)\)

\(S (0 \leq S < N)\) – 원천지의 정점번호.

\(T (0 \leq T < N)\) – 목적지의 정점번호. \((S \neq T)\)

다음 \(M\)개 행은 3개의 옹근수 \(a\) \(b\) \(c\)를 포함한다. – \(a\)와 \(b\)사이의 미디이며 그것의 무게는 \(c\)이다. \((0 \leq a, b < N, a \neq b)\)

문제를 쉽게 하기 위하여 매 \(i (0 \leq i < N, i \neq S, i \neq T)\)에 대하여 \(i\)와 \(T\)사이에 적어도 하나의 마디가 있다.

출력

문제에 대한 답을 출력하시오.

만일 \(K\)째 최소절단이 없다면 -1을 출력하시오.

표준입력

3 3 3 0 2
0 1 1
0 2 3
1 2 2

표준출력

6

문제 12. 긴옹근수 인수분해

  • 시간 제한: 1초
  • 메모리 제한: 256MB

설명

나는 대수를 아주 좋아하는데 특히 인수분해를 좋아한다. 긴옹근수 인수분해는 나에게 즐거움을 주지만 그것은 힘든 문제다.

나의 선생님은 새 인수분해 문제를 주었다. “옹근수 \(N\)이 주어졌을 때 큰 옹근수 \(N^4 + 64\)을 인수분해해야 한다.”

첫단계로 나는 \(N^4 + 64\)을 2개의 옹근수 \(a\) \(b\)의 적21으로 표시하고싶다. 물론 \(1 < a, b < N^4 + 64\)이다.

나는 이것을 할수 있지만 바쁘다. 나를 도울수 있는가?

입력

첫행은 입력자료의 개수 \(T (1 \leq T \leq 10000)\)를 포함한다.

매 입력자료는 한개의 옹근수 \(N (1 \leq N \leq 10000)\)을 포함한다.

출력

\(N^4 + 64 = a \times b\)를 만족하는 \(a\)와 \(b\)를 출력하시오. 만일 여러가지 경우가 있다면 그중 하나를 출력하시오.

표준입력

1
1

표준출력

5 13

2018 서강대학교 프로그래밍 대회에서 우승했습니다

11월 23일에 2018 서강대학교 프로그래밍 대회가 3시간동안 열렸습니다. 매년 서강대학교 학부생을 대상으로 열리는 개인 단위의 ACM-ICPC 스타일 알고리즘 대회입니다. 올해로 14년째입니다. (2016년에 제 12회였으니까 아마 올해가 14번째겠죠 ..? 잘 모르겠지만 그럴거에요)

1~2학년만 참가할 수 있는 Master 디비전과 전학년이 참가할 수 있는 Champion 디비전이 있습니다. 저는 오프라인 대회 경험이 별로 없는 새내기라서 Master 디비전에 참가했습니다. 내년부터 알고리즘 학회장을 하게 되기 때문에 교내 대회를 참가자로서 참여하는 건 이번이 처음이자 마지막일지도 모르겠네요 😄

문제는 디비전마다 6문제, 총 12문제였어요. Baekjoon Online Judge에서 오픈 컨테스트를 풀어볼 수 있어요. Master 디비전에는 오픈 컨테스트의 A, C, D, E, G, I 번 문제가, Champion 디비전에는 B, F, H, J, K, L 번 문제가 출제되었습니다.

ACM-ICPC 스타일 대회에서는 문제를 풀 때마다 푼 문제 색상에 맞는 풍선을 달아주는 문화(?)가 있어요

여름에 2018 전국 대학생 프로그래밍 대회 동아리 연합 대회(UCPC 2018)에서 풍선 스탭으로 일하면서 참가자 분들 책상에 풍선을 달아드렸는데, 이번엔 제 책상에 풍선이 달리는(?) 입장이었어요. 제가 풍선을 달 때는 참가자 분들이 신경쓰이실까봐 다소 걱정도 했지만 문제를 푸는 입장이 되어 보니 생각보다 신경쓰이진 않았어요!

풍선이 많이 달리면 대회장이 예뻐져요. 이런 문화 좋아요!

대회에서 Kotlin을 못 써서 조금 아쉬웠어요. 제 주력 언어는 Kotlin이고, 제가 BOJ에서 푼 문제 중 90% 넘는 문제는 Kotlin으로 풀었거든요. 하지만 학회에서 스터디 하면서 C++에 어느 정도 익숙해져서 딱히 무리는 없었어요. Kotlin은 icpc 월드 파이널 나갈 일이 있다면 거기서 써서 제트브레인의 관심을 한 몸에 받는 거로 만족하고 싶어요. 근데 뭐 일단 월드 파이널을 나갈 수가 있어야..

아무튼 이런 대회가 처음인 새내기의 잡소리는 치워 두고, 문제 이야기를 해 봐요!

문제 이야기

경고: 이 밑에는 솔루션이 있습니다.

솔루션은 제가 문제를 푼 순서입니다.

C. 어려운 소인수분해 / BOJ #16563

A번 풀이가 의외로 곧바로 생각나지 않아서 C부터 풀었습니다. 에라토스테네스의 체는 자신있었거든요.

2와 500만 사이의 자연수가 들어오기 때문에 먼저 $\sqrt{5000000} \approx 2236$까지의 소수를 에라토스테네스의 체로 전처리해 둡니다. 대회에서는 정확하게 500만의 제곱근을 하는 대신 대략 3000으로 잡았습니다. $\pi (2236)=331$이기 때문에, 대략 350개가 안 되는 소수를 얻을 수 있습니다.

어떤 수 n을 입력받습니다. 이제 소수 p에 대해 n이 p로 안 나눠질 때까지 n을 p로 나누고, 동시에 p를 출력합니다. p를 2부터 점점 늘려가다가 n이 $p^2$보다 작아질 경우엔 더 이상 p로 나눠질 리가 없다고 판단하고 루프를 빠져나옵니다. 2236까지의 모든 소수로 나눠봤는데도 n이 1이 아니면, 남아 있는 n 자체가 소수라는 뜻이기 때문에 이 때는 n을 추가로 출력합니다. 이렇게 하면 소인수분해를 해야 되는 수의 개수가 100만 개이더라도 나눗셈을 시도하는 소수 p의 개수가 얼마 안 되기 때문에 큰 걱정이 없습니다. 대회 시작 9분 후 퍼스트 솔브.

A. 3의 배수 / BOJ #16561

의외로 이 문제는 처음에 문제를 잘못 이해해서 고민을 많이 했어요. 자연수 3개로 분할해야 하는데 그걸 놓쳐서 그냥 자연수를 분할하는 갯수로 이해해버렸어요. 아무튼.

문제를 읽어보면 알겠지만 n이 3의 배수인 건 별 의미가 없죠? 사실 $\frac{n}{3}$을 자연수 3개로 분리하는 것과 같습니다. 근데 순서가 상관이 있다고 하네요. 어떻게 분리해야 될까요?

일단 3을 3개로 분리하는 건 1 + 1 + 1 하나밖에 없죠. 4를 3개로 분리하는 건 2 + 1 + 1을 순서를 적절히 바꿔서 3개가 나오고, 5를 3개로 분리하는 건 3 + 1 + 1과 2 + 2 + 1을 순서를 적절히 바꿔서 6개가 나오고… 그러면 이 문제는 공 $\frac{n}{3}$개를 3개의 서로 다른 상자에 각각 1개 이상씩 나눠 담는 경우의 수를 구하는 문제로 생각할 수도 있겠네요! 이건 중복조합 $$\textstyle\left\langle{3\atop {\frac{n}{3}-3}}\right\rangle\left(=_{3}\mathrm{H}_{\frac{n}{3}-3}\right)$$과 같습니다. 계산해 보면 간단히 $$\frac{(\frac{n}{3}-1)(\frac{n}{3}-2)}{2}$$이고, 이렇게 풀면 AC를 받아요!

물론 저는 고등학교 확률과 통계는 잊어버린 지 오래이기 때문에 3, 4, 5, 6을 분할해 보고 각각 1, 3, 6, 10개가 나오는 걸 보고 ‘이건 뭔가 nCr이겠구나!’ 싶어서 바로 그렇게 짰더니 맞았습니다. 대회 시작 14분 후 정답.

B. 친구비 / BOJ #16562

간단한 그래프 문제였어요. 연결 요소들을 찾고, 그 중 최소인 값들만 다 더해주면 됩니다. 연결 요소들은 BFS로 찾든 DFS로 찾든 별 상관은 없고, 모든 노드를 한 번씩만 방문하기 때문에 $O(N)$으로 뚝딱 풀려요. 이 합이 K보다 클 때만 “Oh no”를 출력하면 됩니다. 대회 시작 21분 후 정답.

D. 히오스 프로그래머 / BOJ #16564

팀 목표레벨 T를 0과 $2 \times {10}^{9}$ 사이에서 이진 탐색하는 방식으로 풀었어요. 사실 대회에서는 T의 이론적 최댓값을 신경쓰지 않고 0과 ${10}^{12}$ 사이에서 탐색했어요. 왠진 모르겠지만 범위를 어디까지 잡아야 될지 감이 잘 안 와서..

탐색할 때마다 목표 레벨이 T일 때 올려야 하는 레벨 총합 $\sum \mathrm{max} (0, T-X_i)$를 K와 비교하는 방식이었어요. N이 1백만 이하이고 K가 10억 이하라서 int로 풀면 터지겠죠? 당연히 long long을 썼습니다.

올려야 하는 레벨 총합을 구하는 건 $O(N)$이고 목표 레벨 T를 탐색하는 건 $O\left(\log\left(2\times{10}^{9}\right)\right)$입니다. 따라서 이 문제도 선형 시간 안에 풀립니다. 이진 탐색 범위를 잘못 잡아줘서 한 번 틀리고, 대회 시작 32분 후 퍼스트 솔브.

E. N포커 / BOJ #16565

확률과 통계 문제입니다. 문제지에 숫자를 많이 끄적이게 됐던 거 같아요.

7개를 고를 때를 예로 들어볼게요. 문제의 그림에서 13개의 줄 중 세로줄을 한 개 고르고, 나머지 48장의 카드 중 3장을 고르면 됩니다. 이 때에는 경우의 수가 총 $$\binom{13}{1}\binom{48}{3}$$가지에요.

하지만 11개를 고른다면 어떻게 될까요? 일단 문제의 그림에서 세로줄을 한 개 고르고, 나머지 48장의 카드 중 7개를 고른다고 치면 고른 7장의 카드 중에 또 세로줄을 만드는 경우가 생길 수도 있어요. 이 때엔 세로줄을 두 개 고르고, 나머지 44장의 카드 중에 3장을 고르는 경우를 빼면 됩니다. 경우의 수는 $$\binom{13}{1}\binom{48}{7}-\binom{13}{2}\binom{44}{3}$$가지가 나오겠네요!

15개를 고른다면 어떻게 될까요? 위와 같이 생각한다면 중복을 빼 줄 때 세로줄이 3개 나오는 경우도 빠져버립니다. 따라서 세로줄이 3개 나오는 경우의 수를 다시 더해준다면 $$\binom{13}{1}\binom{48}{11}-\binom{13}{2}\binom{44}{7}+\binom{13}{3}\binom{40}{3}$$가지가 나옵니다.

이쯤 하면 대충 감이 오죠? 일반화할 수 있을 것 같아요. 위의 패턴을 보면 임의의 n에 대해 우리가 구하고자 하는 경우의 수는 $$\sum_{i=1}^{\lfloor n/4 \rfloor} {(-1)}^{i-1} \binom{13}{i}\binom{52 – 4i}{n – 4i}$$가지가 될 것 같고, 실제로도 그래요!

이항 계수를 구하는 게 또 문제인데요, 팩토리얼을 구해 나누는 걸로는 이항 계수를 구할 수가 없어요. long long의 범위는 $2^{63}-1$까지인데, $21! \approx 2^{65.46} $에서 이미 이 범위를 아득히 넘어버리기 때문에 위에 나온 $\binom{48}{7}$을 구하는 건 생각조차 할 수 없을 거에요. long double은 범위는 long long보다 크긴 한데, 엄청 커지면 정확도가 long long보다 못한 것도 있고요. 대신 재귀식 $$\binom nk = \binom{n-1}{k-1} + \binom{n-1}k$$을 쓰면 n ≤ 52, k ≤ 52, k ≤ n에 대해 이항 계수를 다이나믹 프로그래밍으로 전처리해 둘 수 있을 거에요. 숫자가 너무 커질 수도 있간 한데, 어차피 결과는 10,007로 나눈 나머지만 출력하면 되니까 모듈로 연산의 성질을 이용해 전처리할 때 모든 이항 계수는 10,007로 나눈 나머지를 저장하면 돼요.

이렇게 전처리해 둔 이항 계수를 이용하면 n이 얼마가 들어오더라도 최대 13개의 항만 더해서 $O(\lfloor n/4 \rfloor)$에 해결 가능합니다. 식을 잘못 짜서 맞기 전에 3번 틀리고, 대회 시작 1시간 1분 후 퍼스트 솔브.

F. 카드 게임 / BOJ #16566

나중에 알았는데, 이 문제는 원래 Champion 디비전의 F번으로 계획되었다고 합니다. 하지만 이 문제가 더 쉽다고 생각해서 Champion의 F랑 Master의 F를 바꿨다는 것 같습니다. (어쩐지 카드 문제만 연속으로 두 개가 나오더라고요)

여하튼, 처음엔 ‘아 이거 바이너리 서치 트리인가..?’ 하고 한 10분 동안 바이너리 서치 트리를 구현해 보려고 했는데, 트리 연습을 진짜 너무 안 했기 때문에 (게다가 위에서 언급했듯이 Kotlin 하느라 C++에서 struct 짤 일이 별로 없었기 때문에) 포기하고 ‘뭐 어차피 원래 목표는 5등 안에만 드는 거였으니까’ 하고 던지듯이 풀었어요. 근데 맞았습니다!! 이건 데이터가 좀 약했던 것 같아요.

일단 민수가 가져간 카드들을 정렬합니다. 그리고 M의 카드가 쓰였는지 안 쓰였는지 저장하는 플래그 배열을 하나 만듭니다. 이제 철수가 내는 카드의 값을 x라고 할 때, 민수의 카드에서 lower_bound로 x + 1을 찾아봅니다. 이게 아직 안 쓰였다면 바로 출력합니다. 쓰였다면 안 쓰인 카드가 나올 때까지 index를 하나씩 증가시켜 보고, 찾으면 출력합니다.

사실 이 방법은 최악의 경우 $O\left(K^2\log M\right)$이고 TLE가 나도 이상하지 않은 복잡도에요. 그냥 운이 좋았던 것 같아요! 문제를 제대로 풀었다고 말하긴 힘들 거 같지만 여하튼 대회 시작 1시간 47분 후 퍼스트 솔브.

정해는 index sort를 사용하는 것이라고 합니다. M ≤ N ≤ 4,000,000이라서 가능한 것 같은데, 정해로 다시 풀어봐야겠어요.


6문제를 전부 풀어 Master 디비전에서 우승했어요. 참가자로서 아마 처음이자 마지막일 교내대회에서 우승한 것이라 개인적으로도 의미가 큽니다. 참가자, 출제진 모두 수고하셨습니다. 좋은 대회 만들어 주신 운영진 분들께 감사합니다!

코딩하다 중간에 백스페이스가 안 먹어서 고생했지만 (나중에 알고 보니 일부 유학생 분들께서 키보드 언어 설정을 자국 언어로 바꿔 두셔서 그랬다는 것 같습니다) 오랜만의 오프라인 대회 너무 재밌었어요. 내년부터는 출제진이 될 것 같은데, 저도 노력해서 모두 재밌게 즐길 수 있을 만한 대회를 만들어보겠습니다 😊

수고하셨어요! 🎈

컴퓨터는 삼각함수를 어떻게 계산하는가

주의: 이 포스트는 약간의 미적분학 지식이 있어야 이해하기 쉽습니다. 그래도 설명을 위해 약간의 증명은 들어가 있으니, 아는 부분은 스킵하셔도 됩니다.

우리는 언제나 직각과 직사각형이 편합니다. 인류는 직교좌표계를 발명했습니다. 그리고 컴퓨터 모니터의 픽셀 배열은 대부분 가로세로 수백~수천 개 픽셀로 이루어진 격자로 이루어져 있고, 이는 직교좌표계로 접근할 수 있습니다. 직교좌표계로 화면을 그리면 픽셀 하나하나를 관리하기가 제일 쉽고 자유로워서가 아닐까 싶습니다.

만약에 누군가가 사칙연산만 제공되는 엔진으로 게임을 개발한다고 생각합시다. 직교좌표계 위에 그려진 어떤 도형이 있는데 이 도형을 회전시켜야 한다고 합니다. 어떻게 하면 될까요?

사실 수학은 이미 답을 알고 있습니다. 어떤 픽셀의 좌표 \(\left ( x, y\right )\)에 대해 회전된 좌표 \(\left ( x′, y′\right )\)는
\[\begin{bmatrix}\cos \theta & -\sin \theta \\ \sin \theta & \cos \theta\end{bmatrix}\begin{bmatrix}x\\y\end{bmatrix}=\begin{bmatrix}x′\\ y′\end{bmatrix}\]
다른 말로 \[\begin{cases}x′=x \cos \theta-y\sin \theta\\ y′=x \sin \theta+y \cos \theta \end{cases}\] 임이 자명합니다. 이걸 회전하기 전의 이미지의 모든 픽셀의 \(\left ( x, y\right )\)에 대해 한 번씩 해 주면 회전한 이미지가 나옵니다. 참 쉽죠?

사칙연산만 갖고 삼각함수를 계산하라고요?

컴퓨터가 어떻게 삼각함수를 계산하는지를 논하기로 했으니까, 컴퓨터가 할 수 있는 연산만을 이용해야겠습니다. 아주 기본적인 연산만 사용 가능한 프로세서에서 말입니다.

그럼 대체 삼각함수는 어떻게 근사할 수 있을까요? \(\sin\)과 \(\cos\)를 구하면 \(\tan\) 등은 나눗셈으로도 구할 수 있으니까 \(\sin\)과 \(\cos\)를 구하는 데 집중해 봅시다.

삼각함수를 다항함수로 근사하면 되지 않을까요?

다항함수는 사칙연산만으로 계산할 수 있으니 삼각함수의 그래프와 비슷한 다항함수를 만들어서 거기다 집어넣으면 되겠네요!

근데 그 다항함수는 대체 어떻게 구할까요? 여기서 테일러 급수가 등장합니다.

테일러 급수

테일러 급수를 이용하면 어떤 미분 가능한 함수라도 다항함수로 근사해 버릴 수 있습니다. 세상에 그런 흑마법이 존재하냐고요? 네, 놀랍게도 존재합니다!

증명

우선 어떤 함수 \(f^\prime\left(x\right )\)를 \(a\)부터 \(x\)까지 정적분해 봅시다. 미적분의 정의에 의해 아래 식과 같이 표현할 수 있습니다.
\[\int_{a}^{x}f^\prime\left(t\right )\mathrm{d}t=f\left(x\right )-f\left(a\right )\]
그리고 위 식을 변형해 봅시다.
\[\int_{a}^{x}f^\prime\left(t\right )\mathrm{d}t=\int_{a}^{x}\left(-1\right )\left(-f^\prime\left(t\right )\right )\mathrm{d}t\]
이제 \(-1\)을 적분하고 \(-f^\prime\left(t\right )\)를 미분해 부분적분법을 씁시다. 이 때 \(f\left(x\right )\)가 무한히 미분 가능하다면, 부분적분법도 무한히 써 버릴 수 있습니다. 그러니까
\[\cdots = \left.\begin{matrix}\left (-\left ( x-t \right )f^\prime\left ( t \right )- \dfrac{\left( x-t \right )^2}{2}f^{\prime\prime}\left ( t \right )- \dfrac{\left( x-t \right )^3}{6}f^{\prime\prime\prime}\left ( t \right )- \cdots\right )\end{matrix}\right|_{a}^{x}\]
가 됩니다. 이 때 적분변수 \(t\)와 관계없는 \(x\)는 상수취급됩니다. 이 식을 전개해 보면
\[\cdots =\left ( x-a \right )f^\prime\left ( a \right )+ \dfrac{\left( x-a \right )^2}{2!}f^{\prime\prime}\left ( a \right )+ \dfrac{\left( x-a \right)^3}{3!}f^{\prime\prime\prime}\left ( a \right )+ \cdots\\ \]
\[= f\left ( x \right )-f\left ( a \right )\]
마지막으로 \(f\left ( a \right )\)를 이항하면
\[f\left ( x \right ) =f\left ( a \right )+ \left ( x-a \right )f^\prime\left ( a \right )+ \dfrac{\left( x-a \right )^2}{2!}f^{\prime\prime}\left ( a \right )+ \dfrac{\left( x-a \right )^3}{3!}f^{\prime\prime\prime}\left ( a \right )+ \cdots\]
즉 \(f^{\left( n \right)}\)이 \(f\)를 \(n\)번 미분한 함수라고 할 때
\[f\left ( x \right ) = \sum_{n=0}^{\infty}\dfrac{f^{\left ( n \right )}\left ( a \right )}{n!}\left( x-a \right )^n\]
가 유도됩니다. 이 때 \(a\)에 어떤 수를 넣어도 근사됩니다.

그래서 이게 삼각함수랑 무슨 상관이에요!

삼각함수는 무한히 미분 가능합니다. 그러니까, \(f\) 대신 삼각함수를 넣으면 삼각함수를 다항함수로 근사할 수 있습니다. 어떤 삼각함수 \(f\left ( x \right )\)에 대해 \(a\)에 \(0\)을 대입해 보면
\[f\left ( x \right ) =f\left ( 0 \right )+ \left ( x-0 \right )f^\prime\left ( 0 \right )+ \dfrac{\left( x-0 \right )^2}{2!}f^{\prime\prime}\left ( 0 \right )+ \dfrac{\left( x-0 \right )^3}{3!}f^{\prime\prime\prime}\left ( 0 \right )+ \cdots\]
\[=f\left ( 0 \right )+ x f^\prime\left ( 0 \right )+ \dfrac{x^2}{2!}f^{\prime\prime}\left ( 0 \right )+ \dfrac{x^3}{3!}f^{\prime\prime\prime}\left ( 0 \right )+ \cdots\]
인데요, \(f\left ( x \right ) = \sin x\)라고 하고 대입해 보면
\[\sin x =\sin\left ( 0 \right )+ x \sin^\prime\left ( 0 \right )+ \dfrac{x^2}{2!}\sin^{\prime\prime}\left ( 0 \right )+ \dfrac{x^3}{3!}\sin^{\prime\prime\prime}\left ( 0 \right )+ \cdots\]
\[=0+ \left ( x \cdot 1 \right )+ \left ( \dfrac{x^2}{2!}\cdot 0 \right )+ \left ( \dfrac{x^3}{3!}\cdot -1 \right )+ \left ( \dfrac{x^4}{4!}\cdot 0 \right )+ \left ( \dfrac{x^5}{5!}\cdot 1 \right )+ \cdots\]
정리하면
\[\therefore \sin x =x- \dfrac{x^3}{3!}+ \dfrac{x^5}{5!}- \dfrac{x^7}{7!}+ \dfrac{x^9}{9!}+ \cdots\]
마찬가지로
\[\cos x =1-\dfrac{x^2}{2!}+\dfrac{x^4}{4!}-\dfrac{x^6}{6!}+\dfrac{x^8}{8!}+ \cdots\]
이 됩니다. 중간 과정에 비해서 정말 간단한 식이 되었습니다. 더구나, 우리의 궁극적인 목표인 사칙연산만으로 삼각함수 표현하기에 성공했습니다! (팩토리얼은 곱셈의 연속일 뿐이니까요!)

근데, 식이 참… 무한합니다. 이건 어떻게 하면 좋을까요? 우리는 어차피 floating-point 변수들은 굉장히 정확하지 않다는 걸 잘 알고 있습니다. 그러니까 저 식을 어디까지만 계산하고 그 이후의 오차는 무시해 버려도 됩니다.

위에서 구한 다항식을 최고차항이 \(n\)인 항까지만 계산하고, 그 이후는 무시해버립시다. 그리고 이걸 \(n\)차 근사식이라고 합시다. 이제부터 차수를 올려나가면서 \(n\)차 근사식의 그래프를 그려보겠습니다.

그래프

▶ 1차 근사식: \(f\left ( x \right ) = x\)

… 하나도 비슷해보이진 않습니다. 다음!

▶ 3차 근사식: \(f\left ( x \right ) = x-\dfrac{x^3}{3!}\)

앞에서는 감을 좀 잠은 거 같기도 한데, 겨우 \(\dfrac{\pi}{2}\)도 가기 전에부터 조금씩 이상하더니 아래로 곤두박질쳐버리는군요. 다음!

▶ 5차 근사식: \(f\left ( x \right ) = x-\dfrac{x^3}{3!} + \dfrac{x^5}{5!}\)

이제 \(\dfrac{\pi}{2}\)에서도 비슷해졌네요! 다음!

▶ 7차 근사식: \(f\left ( x \right ) = x-\dfrac{x^3}{3!} + \dfrac{x^5}{5!}- \dfrac{x^7}{7!}\)

\(pi\) 근처까지도 꽤 비슷해졌습니다. 몇 개만 더 해 봅시다.

▶ 9차 근사식: \(f\left ( x \right ) = x-\dfrac{x^3}{3!} + \dfrac{x^5}{5!}-\dfrac{x^7}{7!} + \dfrac{x^9}{9!}\)

거의 원본 함수와 같아졌습니다. 사실 여기부터는 이제 \(0 < x < \pi\)일 때는 그냥 가져다 써도 오차는 크지 않을 것 같습니다. 어차피 \(sin\)은 주기함수이고 대칭함수이니까 \(0 < x < \dfrac{\pi}{2}\)에서만 정확해도 다른 범위에서는 함수의 특징을 이용해 계산해내면 됩니다.

▶ 11차 근사식: \(f\left ( x \right ) = x-\dfrac{x^3}{3!} + \dfrac{x^5}{5!}- \dfrac{x^7}{7!} + \dfrac{x^9}{9!}- \dfrac{x^{11}}{11!}\)

차이가 얼마나 나는지 점점 이렇게 봐서는 확인하기가 어렵습니다. 마지막으로 13차 근사식까지만 그려보겠습니다.

▶ 13차 근사식: \(f\left ( x \right ) = x- \dfrac{x^3}{3!} + \dfrac{x^5}{5!}- \dfrac{x^7}{7!} + \dfrac{x^9}{9!}- \dfrac{x^{11}}{11!} + \dfrac{x^{13}}{13!}\)

그래프 범위 내에서는 거의 똑같은 곡선이 그려집니다.

프로그래밍 언어에서의 구현 사례

OpenJDKStrictMath 네이티브 코드가 13차 근사식을 통해 삼각함수를 구현하고 있습니다. 정확성을 위해서 13차 근사식을 그대로 사용하진 않고, 이렇게 조금 변형해서 사용합니다.
\[\sin x \sim x- \dfrac{x^3}{3!} + \dfrac{x^5}{5!}- \dfrac{x^7}{7!} + \dfrac{x^9}{9!}- \dfrac{x^{11}}{11!} + \dfrac{x^{13}}{13!}\]
\[\frac{\sin x}{x} \sim 1- \dfrac{x^2}{3!} + \dfrac{x^4}{5!}- \dfrac{x^6}{7!} + \dfrac{x^8}{9!}- \dfrac{x^{10}}{11!} + \dfrac{x^{12}}{13!}\]
그러므로 \(r\)을 이렇게 정의할 때
\[r = x^3 \left(\dfrac{1}{5!} + x^2 \left(-\dfrac{1}{7!} + x^2 \left(\dfrac{1}{9!} + x^2 \left(-\dfrac{1}{11!} + {x^{2}} \cdot \dfrac{1}{13!}\right)\right)\right)\right)\]
\(\sin x\)는 이렇게 표현할 수 있습니다.
\[\sin x \sim x + x^3 \cdot \left(-\dfrac{1}{3!} + x^2 r \right)\]
예를 봅시다. sin 함수에서 __kernel_sin 함수를 호출할 때 코드에서 \(|x| \prec \pi/4\)라면 y, iy의 값은 모두 0입니다. 이외의 범위에서는 적절한 범위로 평행이동시켜 __kernel_sin 혹은 __kernel_cos 함수값을 구합니다.

#include "fdlibm.h"
#ifdef __STDC__
    static const double
#else
    static double
#endif
half = 5.00000000000000000000e-01, /* 0x3FE00000, 0x00000000 */
S1 = -1.66666666666666324348e-01, /* 0xBFC55555, 0x55555549 */
S2 = 8.33333333332248946124e-03, /* 0x3F811111, 0x1110F8A6 */
S3 = -1.98412698298579493134e-04, /* 0xBF2A01A0, 0x19C161D5 */
S4 = 2.75573137070700676789e-06, /* 0x3EC71DE3, 0x57B1FE7D */
S5 = -2.50507602534068634195e-08, /* 0xBE5AE5E6, 0x8A2B9CEB */
S6 = 1.58969099521155010221e-10; /* 0x3DE5D93A, 0x5ACFD57C */

#ifdef __STDC__
    double __kernel_sin(double x, double y, int iy)
#else
    double __kernel_sin(x, y, iy) double x,y; int iy; /* iy=0 if y is zero */
#endif
{
    double z,r,v; int ix;
    ix = __HI(x)&0x7fffffff; /* high word of x */
    if(ix < 0x3e400000) /* |x| < 2**-27 */ {
        if((int)x==0) return x;
    } /* generate inexact */
    z = x*x;
    v = z*x;
    r = S2+z*(S3+z*(S4+z*(S5+z*S6)));
    if(iy==0) return x+v*(S1+z*r);
    else return x-((z*(half*y-v*r)-y)-v*S1);
}

소스에서
\(S1 = -\dfrac{1}{3!} \approx -1.66666667 \times {10}^{-1}\)
\(S2 = \dfrac{1}{5!} \approx 8.33333333 \times {10}^{-2}\)
\(S3 = -\dfrac{1}{7!} \approx -1.98412698 \times {10}^{-4}\)
\(S4 = \dfrac{1}{9!} \approx 2.75573137 \times {10}^{-6}\)
\(S5 = -\dfrac{1}{11!} \approx -2.50521084 \times {10}^{-8}\)
\(S6 = \dfrac{1}{13!} \approx 1.58969099 \times {10}^{-10}\)
으로 근사식의 계수들이 근사되어 하드코딩되어 있는 것을 알 수 있습니다. 또한 \(z=x^2\), \(v=zx=x^3\)으로 계산하고 있습니다. 13차 근사식을 그대로 쓴다면 항마다 1번, 3번, 5번, …, 13번의 곱셈을 해야 하지만 \(x^2\)를 새 상수로 두면 곱셈을 줄일 수 있어서 이런 방법을 사용하지 않았을까 하는 생각입니다.

다른 방법으로도 계산할 수 있나요?

물론 다른 방법들도 있습니다. 예를 들어 볼더가 1956년에 고안한 CORDIC(COordinate Rotation DIgital Computer) 알고리즘을 이용해 삼각함수의 값을 근사하는 것도 가능합니다.

간단하게 설명하자면, 맨 위에서 회전을 하기 위해 곱하는 행렬을
\[\begin{bmatrix}\cos \theta & -\sin \theta \\ \sin \theta & \cos \theta\end{bmatrix}\]
으로 소개했습니다만, CORDIC 알고리즘은 이를 \(\tan\) 함수만으로 표현해
\[R_i = \dfrac{1}{\sqrt{1 + \tan^2 \left(\gamma_i\right)}}\begin{bmatrix}1 & -\tan \left(\gamma_i\right) \\\tan \left(\gamma_i\right) & 1\end{bmatrix}\]
로 변형하고, 컴퓨터가 빠르게 계산할 수 있도록 \(\tan \left(\gamma_i\right) = \pm2^{-i}\)가 되는 \(\gamma_i\), 즉 \(\arctan\left(2^{-i}\right)\)의 값들과 이 때의 \(\dfrac{1}{\sqrt{1 + \tan^2 \left(\gamma_i\right)}}\)의 값들을 하드코딩해 두고 원하는 각도에 가까워질 때까지 \(i\)를 하나씩 증가시키면서
\(\arctan\left(2^{-i}\right)\)를 더하거나 빼면서 행렬 계산을 해나가는 알고리즘입니다.

이 알고리즘은 계산기에 주로 쓰이고 있고, 인텔의 8087 ~ 80486 CPU에도 채용되어 왔습니다.

컴퓨터는 이렇게 삼각함수를 계산합니다.