hndada   4년 전

안녕하세요. 최근에 백준을 시작하여 재밌게 문제를 풀고 있습니다. solved.ac에서 제공하는 레이팅 시스템은 경쟁심을 자극해 큰 동기부여가 되고 있습니다. 다만 현재 시스템은 레이팅이 제 본 실력을 나타내기까지 100문제 +a의 문제를 풀어야 하고 상위 레이팅 유저일 경우 레이팅이 잘 늘어나지 않는 문제점이 있습니다. 그래서 위 문제점을 해결하고자 새 레이팅 시스템을 만들어서 계산해보았습니다.

첫번째로, 문제 난이도 증감에 따른 레이팅 증감에 지수적 요소를 추가하였습니다. 기존 레이팅 체계에선 레벨 1(Bronze V)은 1을, 레벨 30(Ruby I)은 30의 레이팅을 가지는 선형적 요소만 있었습니다. 저는 이 값을 좀 더 벌리고 싶어서 지수적 요소를 추가하였습니다. 레이팅 만점은 기존처럼 3000에서 조금 넘는 값에 근접하게 하도록 계수를 결정하였습니다. 식은 다음과 같습니다:  

(레이팅) = (레벨)0.90+0.02(레벨)+(클래스)*(보너스)

(클래스): floor(레벨/5)

(보너스): 0.2*(클래스)

아래 표는 위 식에 따라 난이도(레벨)에 따른 레이팅을 계산한 표이며 그 아래 그림은 기존 레이팅(빨강 직선)과 제 레이팅(검정 / 빨강 계단)의 값 양상 변화를 보여주는 그래프입니다.

preview preview

두번째로, 문제 레이팅을 상위 100개 난이도 합에서 내림차순으로 정렬된 전체 레이팅에 대한 가중치 합(Weighted sum)으로 계산하였습니다. 새로 제안한 방법의 장점은 효과적인 레이팅 획득을 위해 100개 전체를 관리하지 않아도 된다는 점입니다. 지금까지 풀어왔던 문제보다 약간 더 어려운 문제를 풀 시 레이팅이 많이 올라가는 구조입니다. 이는 사용자의 실력 상향 평준화를 가져올 것으로 기대합니다. 아울러 모든 문제가 레이팅에 반영이 된다는 점도 있습니다. 가중치 합에서 가중치 공비(decay factor)는 n번째 원소의 가중치 및 누적 합을 비교하여 0.95로 결정하였습니다. 아래는 가중치 공비에 따른 i번째 원소가 가질 가중치 및 그의 누적합을 나타낸 표입니다.

preview

그 외에도 푼 문제 수 레이팅 (이하 보너스 레이팅)의 최댓값을 175에서 100으로 줄였고 클래스 레이팅과 기여도 레이팅은 반영하지 않았습니다.

문제 난이도는 solved.ac 에서 제공하는 정보를 사용하였습니다. 크롤링은 익숙지 않아 많은 시행착오를 겪었으나 알음알음 배워가며 데이터를 얻어냈습니다. 아래는 백준 상위 10등 유저의 새 레이팅들입니다. 중간의 이름들(ekwoo, bnb2011, bamgoesn)은 제 소속 학교(DGIST)의 상위 레이팅 유저 및 지인입니다. 백준 랭킹은 푼 문제수로만 결정되기에 새 레이팅에서 손해를 본 탑10 유저가 있었습니다.

preview

이후 solved.ac 탑10 유저들을 추가하여 새 레이팅을 계산해보았습니다. yclock 님의 반동이 눈에 들어옵니다. 확인해보니 해당 유저는 최고 난이도의 문제(Ruby I)을 다수 풀었으나 상위 100문제에 상대적으로 하위 난이도(Diamond) 문제가 포함되어 있어 기존 레이팅에서 손해를 본 것 같습니다.  

preview

이후 자동으로 랭킹판을 갱신시켜 표출하는 웹 서비스를 만들면 재밌지 않을까 생각합니다. 완성되면 다시 글 써보도록 하겠습니다. 

감사합니다. 

djm03178   4년 전

지수적 레이팅은 문제의 난이도를 표현하는 데에는 선형에 비해 보다 이상적일 수 있습니다. 실제로 solved.ac 초창기에는 사용자의 티어를 지수적 형태의 경험치의 합산으로 나타내기도 했었습니다. 하지만, 현재 그러지 않는 데에는 다음과 같은 이유들이 있다고 생각합니다.

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

djm03178   4년 전

이러한 문제는 지수적 경험치를 사용하던 solved.ac에서 이미 겪었던 것들이고, 그러한 문제들을 해결하기 위해 여러 차례 조정을 거친 끝에 만들어진 것이 현재의 레이팅 시스템입니다.

djm03178   4년 전

또한 제안하신 0.95배의 가중치 합은 리듬게임 osu!에서 사용하여 유명해진 방식인데, 위에서 언급한 것과 같이 풀이를 찾아볼 수 있는 점이나 분야가 매우 다양한 점 등 때문에 PS에서도 똑같이 적용하기에는 다소 괴리감이 있다는 생각입니다.

hndada   4년 전

의견 감사합니다. 경험치는 이미 문제 1개마다 지수적 증가가 전부 반영되어 있어서 (Ruby I의 경험치 ~= Bronze V의 경험치 * 1.5529) 경험치의 합산으로 티어를 결정하게 되면 문제 1개 내지 2개 정도의 치팅만으로 레이팅이 크게 바뀌는 문제가 발생할 것으로 생각합니다. 이는 하위권의 레이팅 사용자일수록 그 효과가 클 것입니다. 단, 제가 제안한 레이팅에서는 푼 문제 전체에 대해서 감쇠적인 지수적 요소가 들어있어 치팅 하나 둘로 티어가 크게 바뀌진 않을 것 같습니다. 

치팅 문제 하나에 대한 현재 레이팅과 제 레이팅, 경험치 합에서의 영향을 예시를 통해 확인해봤습니다. Bronze V 문제만 20개 정도를 푼 유저가 Ruby I 문제 하나를 치팅하였을 때, 그에 따른 Ruby I의 영향은 현재 레이팅에서 60%, 제 레이팅에서 93.3%, 과거 경험치 합 시스템에선 99.99%였습니다. 경험치 합에선 속수무책이었고 현재 레이팅 체계도 우수하게 영향을 덜 받고 있으나 제 레이팅 역시 극단적인 예시 치고도 큰 영향을 받지 않은 것으로 생각합니다.  

preview

사실 어떤 체계에서든 치팅이 한 두개로 끝나지 않고 그 이상 이루어진다면 레이팅은 본래 실력보다 훨씬 높게 책정될 것입니다. 치팅에 덜 민감하다고 버리기엔 초기 레이팅의 획득 속도 가 느린 점, 상위 레이팅 유저의 레이팅 획득 체감 속도가 느린 점 등의 문제점을 잘 해결하고 있는 것 같습니다. 저는 현 solved.ac의 레이팅 시스템을 존중하며 위 레이팅 계산 시스템은 별도의 웹페이지로 서비스하고자 합니다.  

댓글을 작성하려면 로그인해야 합니다.