Month: February 2021

solved.ac의 근간이 되는 두 가지 중요한 기능은 다음과 같습니다.

Baekjoon Online Judge 문제들에 난이도와 태그를 매겨서, BOJ에 있는 방대한 문제들 중 어떤 문제를 풀면 좋을지 훨씬 쉽게 고를 수 있는 수단을 제공합니다.
푼 문제 수가 아닌, 푼 문제들의 난이도의 구성을 바탕으로 한 실력 지표와 이를 기반으로 한 순위 등을 제공해, 알고리즘 문제해결 학습자들에게 더 흥미로운 문제를 해결할 동기를 부여합니다.

실력 지표의 경우, 기존에는 문제를 해결할 때마다 경험치가 쌓이고, 푼 문제들의 경험치의 총 합을 기준으로 실력 지표인 티어를 결정했습니다. 이 방식은 solved.ac가 처음 만들어진 2019년 6월 6일부터 2년 가까히 이어져왔습니다만, 오는 1일부터는 새로운 실력 지표인 AC RATING으로 티어를 결정하게 됩니다. AC RATING은 아래의 합으로 결정되며, 이론적으로 3,450 이하의 정수 값입니다.

푼 문제들을 난이도 순으로 내림차순 정렬했을 때, 상위 100개 문제의 난이도 값의 합 (최대 3,000)
CLASS에 따른 보너스 (최대 250)
푼 문제 수에 따른 보너스 (최대 175)
기여 수에 따른 보너스 (최대 25)

아니 잘 쓰던 경험치 냅두고 왜 이제 와서 이상한 조건의 레이팅을?이라고 생각하실까봐 레이팅제가 어떤 과정을 거쳐 탄생했는지에 대해 소개합니다.

경험치제의 문제점

기존의 경험치제를 간략하게 요약하면 이렇습니다.

브론즈 5 문제를 해결하면 320점을 주도록 합니다. 어떤 문제보다 1티어 높은 문제의 경우 약 1.5배의 경험치를 주도록 합니다.
브론즈 4 티어가 되려면, 브론즈 5 티어를 달성한 이후 브론즈 4 문제를 20문제 더 해결해야 하도록 합니다. 티어 $x$가 되려면, 티어 $x-1$을 달성한 후 난이도 $x$의 문제를 $n_x$개 더 해결해야 하도록 합니다.
기여 한 건마다 경험치 10,000을 줍니다.

이는 여러분께서 자신의 티어와 비슷한 난이도의 문제를 해결할 것으로 기대하고 기획한 것이었습니다. 하지만 여러 부작용이 있었습니다.

단적인 예로 아무것도 해결하지 않은 사람이 루비 1 문제 하나를 풀면 그 한 문제 덕분에 바로 다이아몬드 5가 됩니다. 알고리즘 실력을 키우고 싶은지 아닌지는 제쳐두고, 티어를 올리고 싶다면 힘들게 브론즈 실버를 캐면서 차근차근 올라갈 필요 없이 어려운 문제 하나만 풀면 되는 것입니다.

보통 그런 ‘어려운 문제’는 혼자 힘으로 해결하기 상당히 어렵기 때문에 인터넷을 참고해 해결하는 경우가 많고, 해결하는 순간 경험치 구성의 대부분을 차지해 버리게 됩니다. 이제 본인 실력의 문제를 해결하는 것으로는 경험치가 1%도 오르지 않습니다.

위 유저가 해결한 문제 중 가장 어려운 문제는 루비 V이고, 그 다음은 골드 II 한 문제, 골드 III 두 문제, 골드 V 열한 문제입니다.

기존 경험치제에서 이 유저의 티어는 플래티넘 V인데, 플래티넘 V 유저가 골드 V 한 문제를 풀어서 얻을 수 있는 경험치량은 0.411%입니다.

루비 V 한 문제를 풀지 않았다면? 이 유저의 티어는 실버 I이었을 것이며, 이 경우 골드 V 한 문제는 무려 6.02%의 경험치를 줍니다. 그러면 현재 루비 V 문제 하나를 해결한 상황에서 골드 V 문제를 푸는 게 과연 매력이 있을까요? 그렇다고 플래티넘 문제들을 푸는데 많은 시간을 소비할까요?

대부분의 경우, 의욕을 잃거나 새로운 어려운 문제를 찾아 떠나게 됩니다. 이런 점을 노린 코드 카피 어뷰징이 solved.ac가 등장한 이후 상당히 빈번하게 발생했습니다. solved.ac는 알고리즘 문제해결 학습자들의 학습 동기 증진을 목적으로 하는 사이트인데, 기존 경험치제가 학습자를 다소 좋지 않은 학습 방향으로 유도한다는 생각이 들었습니다.

또한 한 문제를 풀면 경험치를 얼마나 주는지, 다음 티어로 올라가기 위해서는 총 경험치가 얼마쯤 되어야 하는지 혹은 어떤 문제를 얼마나 해결해야 하는지 알기가 어려웠다는 사소한 문제도 있었습니다. 더구나 현재 1위의 총 경험치의 자릿수는 11자리나 되어 상당히 비직관적입니다.

레이팅제의 목표

기존의 제도에는 이런 문제점들이 있었고, 이를 어느 정도 해결하기 위해 많은 고민 끝에 새로 레이팅 제도를 만들었습니다. 새 레이팅 제도의 목표는 아래와 같았습니다.

실력을 정확히 측정하는 것과 동기를 불러일으키는 것 사이 어딘가에서 적당히 줄다리기합니다. 둘 다 완벽하게 되면 더 좋고요.
낮은 티어의 유저들이 새롭고 다양한 알고리즘 분야를 접하는 것을 장려합니다.
푼 문제가 현저히 많다고 레이팅이 현저히 높아지거나, 어려운 문제 하나가 레이팅의 대부분을 차지하게 되는 현상을 최대한 완화합니다.
직관적인 값으로 보여지도록 합니다.
서버가 빠르게 계산할 수 있도록 합니다.

실력 측정 vs 동기 부여

기존의 경험치제나, 새로 도입하게 되는 레이팅제나 사용자의 정확한 실력을 반영해 주기 원하시는 분들이 많았습니다. 결론부터 말하자면 정확한 실력을 가늠하는 건 불가능했기 때문에, 레이팅과 실력과의 상관관계를 높이는 것은 목표로 하지 않았고, 기존과 같이 약한 상관관계를 보이게 하는 것으로 만족했습니다.

정확한 실력을 가늠하는 것이 불가능한 이유는 BOJ가 OJ이기 때문입니다. OJ에 등록된 문제들은 이미 어딘가에서 출제되었던 문제들이고, 많은 경우 쉽게 해설을 찾아볼 수 있습니다. 반면 대회 플랫폼의 경우 매번 새로운 문제들을 주고 틀린 횟수와 해결 시간을 바탕으로 실력을 계산합니다.

따라서 OJ 쪽은 대회 플랫폼에 비해 유저의 실력을 계산하기 위해 사용할 수 있는 정보와 그 정보의 신뢰도 모두가 현저히 떨어집니다. 심지어 대회 플랫폼의 레이팅도 정확한 실력을 반영한다고는 할 수 없습니다. 대회는 실력을 샘플링하는 것에 지나지 않기 때문입니다. 수능 모의고사에서 1등급을 받은 학생이 수능에서도 같은 등급을 받을 것이라는 보장이 없듯이요…

이런 이유로 레이팅과 실력과의 대략적인 상관관계는 기존 수준으로 유지하되 새 레이팅 제도가 목표로 하는 동기 부여적 측면을 더 부각시킬 수 있는 쪽으로 기획 방향을 정했습니다.

레이팅의 뼈대

무작정 높은 난이도의 문제를 푸려고 하게 되는 이유는, 높은 난이도의 문제가 푸는 데 오랜 시간이 걸림에도 불구하고 티어 상승이라는 측면에서 상당히 매력적으로 보이기 때문입니다.

기존 경험치제에서 루비 I 문제 하나를 푸는 것은 브론즈 V 문제 약 30만개를 푸는 것과 비슷한 경험치를 줬고, 이는 문제해결에 쏟는 시간 대비 엄청난 가성비를 보여줍니다. 모든 티어에서 상당히 매력적으로 보이는 게 당연합니다. 따라서 매력을 너프하기 위해서는, 일단 문제 해결로 얻는 경험치가 난이도에 따라 기하급수적으로 올라가는 식이 아니어야 합니다.

하지만 그렇게 되면 난이도에 관계없이 문제를 많이 해결한 사람이 무조건 유리해집니다. 레이팅이 적용된 다른 OJ들이나 비슷한 구조의 게임들이 이를 막는 방법은 크게 두 가지가 있습니다.

반영되는 문제 수에 제한을 둡니다. $n$문제를 반영한다면, 어떤 사용자가 난이도 $x$까지의 문제를 해결할 수 있을 때 이론적으로 받을 수 있는 최대치는 $nx$입니다.
모든 문제를 반영하되 적당한 상수 $0<r<1$을 정해서 첫 문제에는 $1$을, 두 번째 문제에는 $r$을, 세 번째 문제에는 $r^2$를 곱해나가는 식으로 합니다. 어떤 사용자가 난이도 $x$까지의 문제를 해결할 수 있을 때 이론적으로 받을 수 있는 최대치는 $\frac{x}{1-r}$입니다.

두 방법은 사실상 같습니다만 첫 번째 방법은 서버가 계산하기 쉬운 대신 특정 난이도 이상의 문제를 풀지 않으면 아무리 문제를 풀어도 레이팅이 아예 오르지 않는다는 단점이 있고, 두 번째 방법은 문제를 풀면 레이팅이 계속 오르겠다는 믿음을 주는 대신(실제로는 1점 올리기는 상당히 어렵습니다) 서버가 레이팅을 계산하는 코스트가 조금 더 든다는 단점이 있습니다.

그래서 문제를 풀면 레이팅이 오르겠다는 믿음은 다른 방법으로 주기로 하고 첫 번째 방법을 택했습니다. 100문제를 해결하면 레이팅이 수렴했다고 보고, 푼 문제들을 난이도 순으로 정렬해 상위 100개 문제의 난이도 값의 단순합을 레이팅의 가장 많은 부분을 차지하도록 했습니다. 공교롭게도 solved.ac의 문제 난이도는 0부터 30까지라서 이렇게 하면 총 3,000점이 되고, 다른 대회 플랫폼들의 4자리수 레이팅과 비슷한 값이 되어 직관적이게 됩니다.

여기에 문제 해결 수에 따른 보너스 레이팅을 $\left\lfloor 175\left( 1-0.995^n \right) \right\rceil$만큼 주어 약 1,200문제를 해결할 때까지 어느 문제나 해결해도 레이팅이 오른다는 믿음을 주도록 유도했습니다. 다만 실제로 믿으실지는 모르겠습니다. 믿어 주세요.

기존 기획은 이 100문제를 (5년간 출제된 OI/ICPC 문제) 50개와 나머지 문제 50개를 반영하려 했으나, 그렇게 할 근거가 부족하여 100문제를 합하는 것으로 선회했습니다.

새롭고 다양한 알고리즘 문제해결 장려

solved.ac에는 티어 외에도 CLASS라는 실력 지표가 있습니다. 실력대별로 미리 정해진 48문제 중 20문제 이상을 해결하면 얻을 수 있습니다.

CLASS 문제들은 수준에 따라 교육적인 목적을 갖고 정해져 있습니다. 예를 들어,

CLASS 1는 프로그래밍 혹은 알고리즘 문제해결 입문자가 풀어보면 좋을 만한 문제들로 구성했습니다.
CLASS 2는 코딩 테스트나 프로그래밍 대회 등에서 자주 등장하는 주제들 중 초심자가 이해하고 구현하기 쉬운 주제들로 구성했습니다. (브루트포싱, 기초 수학, 정렬, 큐, 스택, 덱)
CLASS 3은 CLASS 2에서 등장한 주제들을 전부 이해하고 나서 시도하면 좋을 만한 주제들로 구성했습니다. (그래프, 그래프 탐색, 힙, 우선순위 큐, 다이나믹 프로그래밍 등)
CLASS 4는 CLASS 3과 비슷하지만 더 어렵다고 느껴지는 주제들을 담았습니다. (백트래킹, 최단 경로 문제, 어려운 구현, 어려운 다이나믹 프로그래밍, 어려운 그래프 문제 등)

낮은 CLASS 문제들은 ‘단계별로 풀어보기’와 비슷한 구성으로 초심자가 가면 좋을 만한 길을 추천해 주는 것을 목표로 했습니다. 이를 더더욱 권장하기 위해 레이팅에 CLASS 보너스를 추가했습니다. 다만, 새 레이팅과 실력과의 괴리가 생길 것을 감안해 낮은 티어에서는 CLASS 보너스가 매력적으로 보이지만 높은 티어에서는 CLASS 보너스의 유무가 랭킹에 큰 차이를 주지 않도록 다음과 같이 정했습니다.

CLASS 1, 2: +25점
CLASS 3, 4, 5: +50점
CLASS 6~: +10점

CLASS 6부터는 주로 프로그래밍 대회에만 등장하는 어려운 주제들을 다루고 있습니다. 또한 CLASS 6 이상을 취득할 수 있는 실력의 사람이라면 CLASS 5 정도는 쉽게 취득할 수 있고, 굳이 CLASS 문제를 해결하지 않더라도 실력을 늘릴 방법을 많이 알고 있을 것이라고 생각했기 때문에 CLASS 6 이상에서의 레이팅 보상은 랭킹에 크게 영향을 미치지 않는 방향으로 결정했습니다.

레이팅 컷

레이팅에 따른 티어는 크게 두 가지 요소를 고려해 정했습니다.

티어 $x$의 유저 입장에서 티어 $x+1$로 가기 위한 과정에서의 경험은 적절한가
티어에 따른 유저 비율이 어떻게 변화할 것인가

특히 새로운 레이팅 제도에서는 상위 100문제를 반영하고 있는데, 알고리즘 공부를 막 시작한 입장에서는 100문제를 해결하는 것부터 버거울 수 있겠습니다. 따라서 ‘몇 CLASS이길 기대하는가?’와 더불어 낮은 티어의 경우 ‘몇 문제를 해결하는 것을 기대하는가?’를 고려했습니다. 예를 들자면

기존 경험치제의 브론즈 구간에서는 실력에 맞는 문제를 약 30문제 정도를 해결하는 것을 기대했습니다. 새로운 레이팅제에서는 CLASS 1~2를 해결하는 여정을 고려하여 레이팅 컷을 정했습니다.
골드 구간부터는 100문제 이상 해결을 기대하고, 상위 100문제에서 기대하는 난이도 평균을 고려했습니다. 예컨대 골드 III 유저는 평균적으로 클래스 2~3에 실버 II에서 골드 V 수준의 문제를 쉽게 해결할 수 있을 것으로 생각했습니다. 클래스 5를 달아 레이팅 100~150을 챙기고, 클래스 5를 풀면서 골드 상위~플레 하위 문제들에 익숙해져 상위 100문제를 그렇게 구성한다면 어느새 플래티넘이 되어 있을 것입니다.
이론적인 레이팅 만점은 3450이지만 루비 구간의 문제들이 부족하고 상위 100문제가 이미 다이아몬드와 루비로 꽉 차 있는 상황에서 더 어려운 루비 문제를 해결하는 것 자체가 상당히 어려운 과정임을 감안해 루비 구간은 촘촘하게 나눴습니다.

그렇게 하면서도 레이팅 컷이 직관적인 수가 되도록 했습니다 – 브론즈 30, 실버 200, 골드 800, 플래티넘 1600, 다이아몬드 2200, 루비 2700. 이렇게 각각의 티어에서 많은 고민 끝에 레이팅 컷을 정했습니다.

플래티넘, 골드, 실버, 브론즈가 각각 상위 10%, 33%, 67%, 100%가 되는 것이 이상적이라고 생각하고 있습니다만, 당시 레이팅 공식이 공개되지 않았음을 고려해 기존보다 약간 더 어렵게 설정했습니다. 레이팅 공식이 공개되는 것이 유저 비율에 영향을 미칠 수 있어서입니다.

레이팅 vs 기존 실력 지표

(왼쪽) 새 티어와 코드포스 레이팅의 상관관계, (오른쪽) 기존 티어와 코드포스 레이팅의 상관관계

신규 레이팅제에서, 코드포스 아이디가 존재하는 상위 569명을 대상으로 코드포스 레이팅과 새 티어를 비교한 결과 기존 티어에 비해 상관관계가 약해졌습니다만, 기존과 같이 어느 정도의 상관관계는 유지하는 양상을 보였습니다. Inversion count도 기존 148,135회에서 161,462로 증가했습니다. 기존 경험치제의 문제점을 해결하기 위해 실력과의 상관관계를 다소 희생했으나, 여전히 어느 정도 유의미한 상관관계를 가진다고 해석했습니다.

극복해야 할 과제

새로운 레이팅제도 완벽하진 않습니다. 대표적으로 1,200문제를 해결해 문제 수 보너스 175점을 모두 받은 유저의 경우, 새 레이팅제에서는 상위 100문제보다 낮은 난이도의 문제를 해결하는 것의 의미가 없어집니다. 충분히 흥미로운 문제가 있을 수도 있지만요. 또한 CLASS 보너스 레이팅을 산입하는 것이 좋은 선택인가에 대한 논의도 있었습니다.

이런 부분들에 대해서는 레이팅제로 운영해보면서 어떻게 개선할 수 있을지에 대해 고민해 보기로 했습니다. 길라잡이 컨텐츠를 잘 만드는 것 등 레이팅 공식 외적으로도 개선할 수 있는 부분이 있을지도 모르겠습니다.

티어를 어떻게 결정할지를 정하는 것은 solved.ac 전체를 통틀어 가장 어려운 기획입니다. 그만큼 수많은 고민 끝에 만들어진 기획인데, 고민한 만큼 긍정적으로 정착하면 좋겠습니다.

이후 계획

제가 직장인이 되었고 또 여러가지 일들로 바빠지다 보니 solved.ac에 새로운 컨텐츠를 만들 시간이 상대적으로 부족해졌습니다. 현재 계획하고 있는 것들은 이렇습니다.

백엔드 리팩터링(~6월). 프론트엔드에 이어 백엔드입니다. 현재 백엔드는 PHP인데, 유지보수가 너무 어려운 상황이라 Express로 다시 짜고 있습니다. solved.ac를 처음 만들 시절엔 이렇게 커질 줄 몰랐으니까 어쩔 수 없는 것 같습니다. 프로젝트를 시작할 때부터 기반을 잘 닦읍시다.
길라잡이(~9월).
투표 개편(~9월).

앞으로도 많은 관심과 기대 부탁드리겠습니다!