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

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

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

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

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

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

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

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

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

첫 버전

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

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

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

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

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

티어 계산

임원 분들과 열심히 난이도를 매긴 결과 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초 걸린 셈입니다. 뭔가 방법이 잘못되었다는 걸 직감했습니다.

트위터 찬스를 썼습니다.

현재 해야 되는 것
DB에 3개의 필드가 있는데 A B C라 하면
– 새 데이터와 A B가 일치하는 기록이 있을 경우 C 업데이트
– 없을 경우 새로 추가
인데.. 이짓거리를 시간당 10만 레코드에 대해 해야 돼요 (A B C 전부가 일치하는 경우가 대부분)

— shift* (@shiftpsh) July 2, 2019

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

(a,b)를 pk로 잡으시면 되겟다 (훈수충)

— 썩죠👀 (@suckzo_o) July 2, 2019

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

스트링두 pk 되자너요

— 썩죠👀 (@suckzo_o) July 2, 2019

그냥 제가 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를 수천 명이 사용하는 서비스로 개조하면서 한 생각들을 다뤄볼 생각입니다.