2019 ICPC Asia Seoul Regional에 다녀왔습니다

ICPC regional 본선으로는 두 번째고, 서울 본선으로는 첫 번째입니다. 아이러니게도 첫 번째 리저널 본선은 2019년 방콕 리저널이었습니다.

2018년에는 제가 1학년이었고, 코드포스 레이팅도 블루였고, 결정적으로 알고리즘 문제해결 자체를 시작한 지 채 1년이 안 되었을 때였기 때문에 그냥 ‘대회가 이렇게 돌아가는 거구나~’를 느끼기 위해 귀여운 새내기 동기들과 같이 나갔었는데요, 겨울에 코드포스로 나름의 하드 트레이닝을 해서 레이팅을 2000까지 끌어올린 뒤 올해는 수상을 목표로 준비하게 되었습니다. 따라서 ICPC를 진지하게 준비해본 건 올해가 처음이었고 예선부터 본선까지의 준비 기록을 한 번 정리해 보려 합니다.

팀 연습

팀 연습이라는 것을 해 본 적이 없는 저였기 때문에 팀원들에게 예전에 어떻게 했냐고 물어봤는데, 기억이 어렴풋했던 것 같습니다. 그래서 제가 어떻게든 진행을 해 봤습니다.

날짜와 장소 정하기

팀 연습은 조금 늦게 시작했던 것 같습니다. 개강하고 나서(적어도 9월에) 3명이 모두 참가할 수 있도록 날짜와 시간을 잡았습니다. 장소는 학회 아니면 PC방, 시간은 매주 2회 오후 7시 반이었습니다.

서강대학교의 경우 컴퓨터공학과 실습실 4곳을 스터디 학회들(ICPC Team, Release, CSPC Lab, CNU)이 각각 관리하는데, 실습실에 수업이 없을 경우에는 컴퓨터공학과 학생들이 자유롭게 사용할 수 있도록 되어 있습니다. 실습실을 학과에서 정해진 개방 시간 이외에 개방하는 것은 학회 자율이기 때문에 저녁 7시 30분에 연습을 시작해 새벽 12시 30분까지 문제를 풀고 에디토리얼까지 보고 집에 갈 수 있는 나름 좋은 환경이었습니다. 다만 실습실에 수업이 있는 날에는 PC방에서 연습을 해야 했는데, 가격도 가격이었지만 시끄러운 환경에서 머리 쓰는 건 나름 고역이었습니다. 뭐 어쩔 수 없었지요.

플랫폼 정하기

연습은 처음엔 Codeforces Gym에서 Virtual contest에 참가하는 방식으로 하다가 언젠가부터 BOJ 그룹의 연습 기능을 이용하게 되었습니다.

Codeforces Gym

Codeforces Gym은 Ghost라는 기능을 제공합니다. 실제 대회의 제출 기록을 스코어보드에 반영한 것인데, 실제로 해당 대회에 참가했다면 순위가 어땠는지를 가늠할 수 있다는 것이 장점인 것 같습니다. 다만 팀 연습 초기에는 제가 셋을 고를 때 너무 쉬운 셋이나 너무 어려운 셋만 골라서 별로 의미가 없었고, 그래서 오히려 스코어보드를 보고 스트레스를 받지 않기 위해 + 쉬운 문제를 빨리 찾아내는 훈련을 하기 위해 BOJ로 옮겼습니다.

BOJ 그룹 연습. 당연히 연습 중에 solved.ac는 껐습니다.

BOJ 연습 기능은 정말 간단하기 때문에 딱히 설명할 건 없는 듯 합니다. 연습 시간을 설정하고 문제를 미리 등록해 두면 됩니다. 물론 스코어보드는 그룹 내부 인원이 해당 시간에 연습에 참여한 것밖에 안 나옵니다. 쉬운 문제를 못 찾겠다면 대회 진행 1~2시간 후에 대회 공식 사이트에서 최종 스코어보드를 띄워놓는 식으로 연습했습니다. 좋은 방법은 아니었던 것 같습니다.

셋 고르기

역시 저는 ICPC 리저널에 대한 지식이 전무했기 때문에 처음에는 말 그대로 아무거나 골라 풀었습니다. 첫 두 팀 연습은 ICPC 리저널 셋이 아니었습니다. 첫 번째는 사설 대회였고 두 번째는 KAIST RUN 대회였던 것으로 기억합니다.

뭔가 제가 고른 셋이 전부 엄청 쉽거나 아니면 엄청 어렵다 보니까 이대로는 안 되겠다 싶어서 인터넷에서 여러 글을 찾아봤습니다. 이후로는 koosaga님의 내가 문제풀이를 연습하는 방법에서 ICPC-style 부분을 많이 참고했고, 유럽 리저널 특히 NWERC 위주로 골라 풀었습니다. Subregional은 너무 쉬웠고, regional 위주로 골라 풀었던 게 가장 적절한 난이도였던 것 같습니다. BOJ 슬랙에서 추천받은 셋들도 풀었습니다.

그렇게 대회까지 총 13셋 정도를 풀었습니다. 개인적으로는 봄부터 연습을 시작했더라면 어땠을까 하는 후회도 없지 않습니다.

전략 세우기

혼자 나가는 대회가 아니다 보니 연습을 거듭할수록 누가 어떤 문제를 언제 풀지 스케쥴링하는 것도 상당히 중요하다는 걸 느꼈습니다. ‘분명히 이건 우리가 풀 수 있는 문제였는데 왜 못 풀었지?’ 같은 현상이 연습 중반까지 자주 일어났습니다. 대표적으로

  • 풀이는 맞는 거 같은데 자꾸 틀렸던 경우
  • 완벽한 풀이를 생각했는데, 다른 팀원이 디버깅을 하느라 시간이 다 가서 코드로 옮기는 것조차 하지 못했던 경우

가 있었습니다.

맞왜틀

첫 번째 경우에는 단순한 실수일 가능성이 크기 때문에, 보통 온사이트 대회에서는 코드 인쇄를 신청하고 다른 팀원이 다른 문제를 푸는 게 일반적입니다. 하지만 저는 그런 걸 몰랐고 더군다나 PC방에서는 인쇄가 안 되었기 때문에… PC방 모니터가 크다는 점을 이용해, 왼쪽에서는 다른 팀원이 다른 문제를 풀었고 오른쪽에서는 제 코드를 띄워 놓고 눈으로 디버깅했습니다. 온사이트에서 인쇄가 가능하다는 걸 빨리 알았으면 좋았을 것 같습니다.

두 번째 경우는 스케쥴링의 문제였습니다. 예를 들면 ‘나 E, F, H 풀이 생각났어!’인데 누군가 J를 계속 디버깅을 하는 케이스인 건데, J 때문에 E, F, H에 병목현상이 생겼습니다. 따라서 틀린 솔루션을 디버깅하는 것보다 확실한 솔루션을 짜는 쪽으로 우선순위를 뒀습니다. 그리고 컴퓨터는 한 명만 쓸 수 있기 때문에 최대한 컴퓨터 자리를 공석으로 두지 않도록 했습니다. 이렇게 전략을 짜니 ‘풀 수 있었는데 못 푼 문제’가 많이 줄었습니다.

실패로부터 배우기

마지막으로, 대회가 끝나면 에디토리얼을 꼭 읽었습니다. 우리가 알고 있는 테크닉이었는지, 알고 있었다면 어떤 걸 잘못해서 틀렸는지 분석했고, 모르고 있었다면 이런 테크닉도 있구나 하고 새로운 기술을 알아갔습니다. 모르던 테크닉이나 실수가 많았던 테크닉은 팀노트에 작성했습니다. 정작 대회에서는 팀노트가 필요없었던 것 같습니다만…

연습이 끝나고 풀지 못한 대회 문제들을 풀어보는 걸 업솔빙upsolving이라고 하는데, 에디토리얼을 다 읽고 어디서 틀렸는지 토론하다 보면 새벽 1시가 훨씬 넘었고, 낮에 다시 학교에 와야 했기 때문에 안타깝게도 무리였습니다. 여건이 된다면 이후 연습에서는 업솔빙까지 꼭 해보고 싶었습니다.

예선

예선은 가족같은 분위기의 학교에서 진행했습니다. 무려 학회 실습실. 항상 오던 곳이라 편안하게 칠 수 있을 줄 알았으나 서버 상태가 메롱이어서 편안하게 못쳤습니다. 여하튼.

예선 스코어보드

예선에서는 6문제를 빠르게 풀었습니다.

I. Registration (3분, shiftpsh): 2013년부터 꾸준히 나와 오고 있는 문제입니다. 아이디와 비밀번호를 출력하면 됩니다. 대회 시작 직후에 여기저기서 ‘야 등록 어딨어’ 같은 소리가 들렸던 거 같은데 제출 서버가 맛이 가서 의미가 없었습니다. 다들 등록 제출하느라 이런 거겠지 하고 생각했으나…

B. Balanced String (14분, semteo04): \(2^{\left\lfloor\frac{n+1}{2}\right\rfloor}\)를 계산하는 쉬운 문제였습니다. 쉬운 문제였는데 서버가 맛이 가서 실제로 푼 시각보다 5분쯤 늦게 제출하게 되었습니다.

H. Four Squares (24분, shiftpsh): 라그랑주의 네 제곱수 정리를 풀어본 적이 있어서 금방 짰습니다.

C. Byte Coin (32분, lvalue): 쉬운 그리디여서 금방 짰습니다. 역시 채점 서버 때문에 제출이 몇 분 늦어졌습니다.

L. Two Machines (73분, semteo04): 냅색 DP였습니다. 냅색이라는 건 알았는데 제가 풀이가 갑자기 생각이 안 나서 저는 못 짜겠다고 선언했습니다.

D. Canal (117분, shiftpsh): 제가 고민중이었는데, semteo04가 이분 탐색이라고 하길래 multiset을 믿고 짰습니다. 이 문제는 대회 서버 때문에 대회가 끝나고 나서도 한두시간 동안 채점 결과를 받아보지 못했는데, multiset이 터졌다는 다른 팀의 증언을 듣고 상심하고 여의도 불꽃놀이나 보면서 심신을 안정시키기로 했습니다.

서강대에서 서강대교까지는 그렇게 멀지 않기 때문에 학교에서 아무 생각 없이 서강대교까지 걸어가서 불꽃을 혼자 구경했습니다. 서강대교에 도착하기 직전에 채점 결과가 공개되었는데, 이 때 D가 맞았다는 걸 알게 되어 안도했습니다. 프리즈 전에는 9등이었다고 합니다.

이미지
프리즈 전 스코어보드

Convex hull trick이라는 걸 알고도 못 푼 J가 너무 아쉬웠는데, 팀노트 코드를 베끼려고 보니 팀노트에 적혀 있던 코드가 그냥 특공대 솔루션이었습니다. 이후 본선에는 보완해 들고 갔는데 본선에는 CHT 안 나오더라고요. 너무하네

A가 LR flow인 걸 몰랐던 것도 아쉬웠습니다. 근데 어차피 서버 나가서 코드를 더 짰어도 문제를 더 맞았을 확률은 희박했을 거라고 생각합니다.

빨리감기해서…

본선 전날

본선은 온사이트 대회고, 온사이트 대회에 가면 인터넷에서나 볼 수 있었던 많은 분들을 뵐 수 있기 때문에 전날에는 수다 떠느라 안타깝게도 따로 연습은 못 했습니다.

한양대학교의 Twitter HLD 팀, POSTECH의 JonMatTaeng 팀과 함께 대회 전날 저녁식사를 했습니다. 레스토랑 이름이 기억이 안 나는데 꽤 맛있었습니다. 서강대 앞에도 점포 내줘요.

연세대/이화여대 상권에 뭔가 다 몰려 있어서 서강대생들은 뭘 먹거나 뭘 하려면 신촌 쪽으로 내려가야 하는데, 여기도 건대 상권에 거의 다 몰려 있어서 아마도 세종대생들도 건대 쪽으로 내려와야 하는 게 아닐까 하는 생각을 했습니다. 제 생각이 맞다면 서강대와 세종대가 의외로 이런 비슷한 점이 있는 거 같습니다. 서강대가 학교 규모는 훨씬 작지만…

다음날 대회가 아침에 있어서, 근처 호텔에서 묵었습니다. 가고 싶은 공연이 있었지만 대회 일정 때문에 신청을 못 했는데, 알고보니 묵던 호텔 바로 옆 건물에서 하더랍니다. 나한테 왜 그래

본선

일단 일어나서 초콜릿 도핑을 많이 했습니다. 빼빼로데이 시즌이길래 페레로 로쉐 2+2 행사를 하고 있었는데 사재기해 둘걸 그랬네요…

팀원 중 한 명은 본선대회일에 쳐야 하는 시험 때문에 숙소에 안 오고 학교에서 공부를 하다가 늦잠을 잤습니다. 다행히도 택시아저씨께서 존경스러운 속도로 운송(?)해 주셔서 실격은 면했습니다.

본선 스코어보드

본선에서는 7문제를 풀었습니다. 개인적인 목표가 7문제였는데 달성해서 상당히 기뻤습니다. 추가로 C와 J를 처음으로 풀었습니다.

J. Triangulation (11분, shiftpsh, First to solve): A가 상당히 쉬운 문제였어서 lvalue가 바로 솔루션을 생각해내 구현을 시작했는데, 제가 J를 보다가 그림 하나를 그려보고…

이미지
J번 풀이 (재연)

…이게 다른 어떤 문제보다 구현이 훨씬 더 쉬울 거 같아서 인터셉트해 제출했습니다. 아이디어를 빨리 생각해내서 운좋게 퍼스트 솔브를 했습니다. 서버 이슈가 없어서 다행이라고 생각했습니다.

이미지
순간 1등

J를 푼 직후 아주 잠시동안 1위였습니다. 스크린샷을 찍어 뒀고 대회가 끝난 뒤 휴대폰으로 컴퓨터 화면을 찍었습니다.

A. Fire on Field (13분, lvalue): 구현하라고 하는 걸 구현하면 되는 쉬운 문제였습니다. 제가 J를 짜려고 인터셉트했을 때 A 코드도 거의 다 짜여져 있던 상태였으므로 바로 제출해 맞았습니다.

L. What’s Mine is Mine (36분, semteo04): 간단한 유형의 DP라서 semteo04가 금방 풀었습니다.

I. Thread Knots (47분, shiftpsh): 그림만 봐도 이분 탐색의 냄새가 나는 문제였습니다. 바로 뚝딱 짰습니다.

B. Gene Tree (103분, semteo04): Tree DP라는 건 알았는데 제곱이 섞여 있어서 식이 괴랄하게 나왔습니다. 제가 식을 열심히 전개하면서 ‘이렇게 분해해서 생각하면 되지 않을까?’ 같은 식의 말을 했더니 semteo04가 뭔가 생각난 듯 열심히 구현했고, 제출해서 맞았습니다.

H. Strike Zone (164분 +2, semteo04): Kadane’s와 세그먼트 트리를 잘 섞으면 되지 않을까 싶어서 일단 제가 짜서 두 번 제출했는데 틀렸습니다. 알고 보니 KOI 2014 중등부의 금광 문제와 똑같은 문제였습니다. lvalue와 저는 정보올림피아드 준비/출전 경험이 없어서 몰랐지만 경험이 있던 semteo04가 제 코드를 버리고 새로 짜 순식간에 맞췄습니다.

C. Islands (204분 +6, lvalue, First to solve): 남은 문제 중에 풀만한 문제가 없어서 lvalue가 잡았는데, 솔직히 왜 맞았는지 아직도 아는 사람이 없습니다. 풀이가 맞는 게 맞는지 아니면 데이터가 약한 건지…

K번 Washer는 뭔가 3차원을 다루는 거 같아서 제가 3차원 벡터 연산하는 코드를 짜고 있었는데, 대회 15분 전에 ‘평면으로 잘라서 \(\binom{100}{3}\times 2^3\) 브루트포싱하면 되지 않을까?’라는 생각이 들어서 그 방향으로 구현했으나 WA를 계속 받았습니다. BOJ에 데이터가 올라온 후 제가 같은 방법으로 다시 구현해서 제출했더니 AC를 받아서 너무 안타까웠습니다. 아마 외적을 잘못 구현했거나 출력 포맷을 잘못 지켰던 것 같습니다…

최종 순위는 팀 랭킹 15위, 학교 랭킹 8위였습니다. 서강대학교가 학교 순위가 1자리수였던 건 2015년(6위) 이후 4년만이라 결과는 만족스러웠습니다. 색깔과 닉네임을 붙여서 팀명을 지으면 수상한다는 낭설도 지켰습니다(2017년 BlueJoker, 2015년 PurpleNoon).

개인적으로는 제가 푼 게 많지 않아서 + K를 결국 풀지 못해서 조금 아쉽긴 했습니다. 그래도 제가 어시스트를 많이 했으니 괜찮지 않았을까 싶어요 ..?

스코어보드를 시상식 이후에 공개하는 게 아쉬웠습니다. 꼭 이렇게 해야 했나… 그래도 본선대회 운영은 전반적으로 만족스러웠고(특히 CLion이 있었다는 점에서!), 다과와 저녁은 맛있었습니다. 감사합니다.

Image result for take my money
Take my money

사실 해외 리저널에 참가비가 있다는 건 방콕 대회 때문에 알았는데, 오히려 우리나라가 특이하게 참가비가 없었던 것이었습니다. 내년부터는 참가비가 생긴다는데, 참가비는 얼마든지 괜찮으니 예선 서버 이슈같은 문제만 되풀이되지 않았으면 좋겠습니다.

당분간 휴학할 예정이라 다음에는 2022년 혹은 2023년 리저널에 참가하게 되지 않을까 싶습니다. 팀명처럼 진짜 레드 만들어 와서 월드 파이널에 꼭 한 번 나가보고 싶네요!

수고하셨습니다. 🎈

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건을 넘겼습니다. 학회에서만 사용하려고 했는데 어쩌다 보니 여기까지 올 수 있게 되었습니다. 사이트에 관심 가져 주셔서 정말로 감사하고, 알고리즘 문제해결을 공부하는 사람들의 길잡이가 될 수 있는 좋은 커뮤니티 프로젝트가 되도록 노력을 아끼지 않겠습니다.

감사합니다!