Category: Competitive Programming

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가 주어진다. Ai가 x이면, 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(n + 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!}\)

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

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

OpenJDK의 StrictMath 네이티브 코드가 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에도 채용되어 왔습니다.

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