지수적 레이팅은 문제의 난이도를 표현하는 데에는 선형에 비해 보다 이상적일 수 있습니다. 실제로 solved.ac 초창기에는 사용자의 티어를 지수적 형태의 경험치의 합산으로 나타내기도 했었습니다. 하지만, 현재 그러지 않는 데에는 다음과 같은 이유들이 있다고 생각합니다.
- 지수적 레이팅을 사용할 경우 최상위 몇 문제에 의해 해당 사용자의 티어의 대부분이 결정되어 버립니다. 그 몇 문제로 해당 사용자의 실력을 온전하게 평가할 수 있다면 좋겠으나, 현실적으로는 어려운 면이 많습니다. 예를 들어, 매우 어려운 문제 몇 개의 풀이를 찾아보고 그대로 구현하는 것만으로도 자신의 실력으로 조금 낮은 레벨의 문제 수십 개를 푼 사용자의 레이팅을 쉽게 넘어설 수 있게 됩니다. 이를 오랜 시간을 들이지 않고도 남용할 수 있게 되면 레이팅의 상위권에는 진짜 실력자가 아닌 풀이를 검색하여 소위 레이팅을 '파밍'한 유저들이 올라오게 될 가능성이 있습니다.
- 문제의 체감 난이도는 사용자마다 크게 다르며, 투표한 사람에 따라 몇 레벨 이상이 왔다갔다할 수 있습니다. 지수적 레이팅을 사용할 경우 이 레벨간의 레이팅 차이는 금세 눈에 띄게 차이나게 됩니다. 그러면 결국 다양한 문제를 잘 푸는 것이 아니라 오로지 자신의 입맛에 맞는 종류의 문제 몇 개만을 풀어내는 것으로 알고리즘 전체 실력을 평가받게 되는 문제가 발생합니다.
- 상위 100문제라는 비교적 많은 문제를 요구하는 이유도 이와 비슷합니다. 알고리즘 문제는 세부 분야가 매우 다양하며, PS를 잘 한다고 불리는 사람들은 대다수의 유형에서 상당한 수준의 실력을 요구받을 것입니다. 만일 이 레이팅이 단 상위 10개 문제에 의해 좌지우지된다면 자신 있는 한 분야의 어려운 문제 10개를 해결하는 것만으로 매우 높은 티어에 도달할 수 있게 되지만, 이 사용자가 과연 그 분야가 아닌 알고리즘 전반에 대한 실력자라고 불릴 수 있을지는 의문입니다. 이러한 현상은 어차피 많은 문제들을 풀었을 최상위권보다는 중하위권에서 눈에 띄게 나타날 것입니다.

hndada 4년 전 12
안녕하세요. 최근에 백준을 시작하여 재밌게 문제를 풀고 있습니다. solved.ac에서 제공하는 레이팅 시스템은 경쟁심을 자극해 큰 동기부여가 되고 있습니다. 다만 현재 시스템은 레이팅이 제 본 실력을 나타내기까지 100문제 +a의 문제를 풀어야 하고 상위 레이팅 유저일 경우 레이팅이 잘 늘어나지 않는 문제점이 있습니다. 그래서 위 문제점을 해결하고자 새 레이팅 시스템을 만들어서 계산해보았습니다.
첫번째로, 문제 난이도 증감에 따른 레이팅 증감에 지수적 요소를 추가하였습니다. 기존 레이팅 체계에선 레벨 1(Bronze V)은 1을, 레벨 30(Ruby I)은 30의 레이팅을 가지는 선형적 요소만 있었습니다. 저는 이 값을 좀 더 벌리고 싶어서 지수적 요소를 추가하였습니다. 레이팅 만점은 기존처럼 3000에서 조금 넘는 값에 근접하게 하도록 계수를 결정하였습니다. 식은 다음과 같습니다:
(레이팅) = (레벨)0.90+0.02(레벨)+(클래스)*(보너스)
(클래스): floor(레벨/5)
(보너스): 0.2*(클래스)
아래 표는 위 식에 따라 난이도(레벨)에 따른 레이팅을 계산한 표이며 그 아래 그림은 기존 레이팅(빨강 직선)과 제 레이팅(검정 / 빨강 계단)의 값 양상 변화를 보여주는 그래프입니다.
두번째로, 문제 레이팅을 상위 100개 난이도 합에서 내림차순으로 정렬된 전체 레이팅에 대한 가중치 합(Weighted sum)으로 계산하였습니다. 새로 제안한 방법의 장점은 효과적인 레이팅 획득을 위해 100개 전체를 관리하지 않아도 된다는 점입니다. 지금까지 풀어왔던 문제보다 약간 더 어려운 문제를 풀 시 레이팅이 많이 올라가는 구조입니다. 이는 사용자의 실력 상향 평준화를 가져올 것으로 기대합니다. 아울러 모든 문제가 레이팅에 반영이 된다는 점도 있습니다. 가중치 합에서 가중치 공비(decay factor)는 n번째 원소의 가중치 및 누적 합을 비교하여 0.95로 결정하였습니다. 아래는 가중치 공비에 따른 i번째 원소가 가질 가중치 및 그의 누적합을 나타낸 표입니다.
그 외에도 푼 문제 수 레이팅 (이하 보너스 레이팅)의 최댓값을 175에서 100으로 줄였고 클래스 레이팅과 기여도 레이팅은 반영하지 않았습니다.
문제 난이도는 solved.ac 에서 제공하는 정보를 사용하였습니다. 크롤링은 익숙지 않아 많은 시행착오를 겪었으나 알음알음 배워가며 데이터를 얻어냈습니다. 아래는 백준 상위 10등 유저의 새 레이팅들입니다. 중간의 이름들(ekwoo, bnb2011, bamgoesn)은 제 소속 학교(DGIST)의 상위 레이팅 유저 및 지인입니다. 백준 랭킹은 푼 문제수로만 결정되기에 새 레이팅에서 손해를 본 탑10 유저가 있었습니다.
이후 solved.ac 탑10 유저들을 추가하여 새 레이팅을 계산해보았습니다. yclock 님의 반동이 눈에 들어옵니다. 확인해보니 해당 유저는 최고 난이도의 문제(Ruby I)을 다수 풀었으나 상위 100문제에 상대적으로 하위 난이도(Diamond) 문제가 포함되어 있어 기존 레이팅에서 손해를 본 것 같습니다.
이후 자동으로 랭킹판을 갱신시켜 표출하는 웹 서비스를 만들면 재밌지 않을까 생각합니다. 완성되면 다시 글 써보도록 하겠습니다.
감사합니다.