백준 온라인 저지에서 푼 문제 수와 codeforce rating간 관계 (개발기)

(선 스포 후 설명)

0. 서론

안녕하세요, BOJ의 데이터를 긁긁하면서 BOJ계의 OP.GG 개발을 꿈꾸는(?) 사람입니다.

acmicpc.cc라는 사이트를 운영하고 있습니당. (그러나 현실은 귀차니즘에 찌들어 있어서 개발이 매우매우 느립니다.)

지금까지는 개인의 2주간 제출 통계를 보여주는 정도였습니다. 아래 처럼요.

이렇게 시각화된 정보를 보면서 본인이 요즘 얼마나 공부를 열심히 하고 있는지 확실히 느낄수 있게 하였죠.

(일도 안하고 공부도 안하고 나는 뭐하는건가....)

이 기능(이라고 하기도 뭣한 이것)을 만들고 2주동안 아무것도 하지 않았습니다..

만들고 싶은게 떠오르지 않았거든요.

그러다가 어느날 문득 BOJ에서 푼 문제 수와 codeforce 레이팅에는 어떤 상관관계가 있을까? 라는 어리석은 궁금증이 생겼습니다.

랭킹 2000등까지 푼 문제 수랑 codeforce 레이팅을 구해서 그래프에 점을 찍어보면 엄청 재밌을거 같다!!

이 생각은 최강 귀차니즘인 저를 움직였습니다.

그래서 만들어 보았습니다.

1. 데이터 모으기

(글이 꽤 깁니다... 삽질기가 별로 궁금하지 않으시면 스크롤을 내리셔도 됩니다.)

우선 BOJ의 랭킹 페이지가 어떻게 되어있는지 잘 봐야합니다.

랭킹 페이지의 주소는 https://www.acmicpc.net/ranklist/페이지수 로 되어있군요.

그리고 한 페이지 당 100명의 정보가 보여지므로 20페이지 까지 돌면 되겠습니다.

from bs4 import BeautifulSoup

for i in range(1, 21):
    url = "https://www.acmicpc.net/ranklist/" + str(i)

그리고 해당 url로 부터 beautifulsoup 객체를 얻어와야 합니다.

    soup = get_soup_from_url(url)

get_soup_from_url 함수는 제가 이전에 만들어뒀던 함수인데요, BOJ는 그냥 크롤링 하려고 하면 에러가 납니다.

우리가 어떤 사이트에 접속을 하면 우리 컴퓨터의 OS, 브라우저 버전 등의 정보를 보내는데요, 이를 User agent라고 합니다.

어떤 사이트들은 User agent가 불분명한 요청은 막아놓도록 설정이 되어있는데 BOJ도 그중 하나입니다.

그래서 임의로 User agent를 설정해주고 beatifulsoup 객체를 반환하는 것이 get_soup_from_url 함수의 역할입니다.

코드가 궁금하신 분은 (https://github.com/MoonHyuk/acmicpc.cc/blob/master/application.py) 에서 확인하시면 되겠습니다.

근데 막아놨는데 이렇게 막 크롤링 해도 됨?

이 주제는 우선 넘어가고 아래에서 다시 다루겠습니다.

그럼 이제 각 페이지에서 테이블을 읽어봅시다.

    table = soup.find(id="ranklist")
    trs = table.tbody.find_all('tr')

tr은 테이블에서 row 한줄 한줄을 의미합니다. 즉 유저 한명 한명이 되겠죠. trs는 그 tr들로 이루어진 리스트입니다.

    for tr in trs:

이러면 이제 각 페이지에서 유저 한명 한명을 돌게 되겠죠.

이제 각 유저마다 이 유저가 codeforce rating이 있는지, 있다면 정확히 몇인지 구해면 됩니다!!

rating이 있는지는 어떻게 알까요?

고맙게도 rating이 있는 유저들은 이름에 색이 있습니다.

요소 검새를 해보면,

codeforce 레이팅이 보이는 분들은 class 이름이 user-어쩌구저쩌구 로 되어있고,

TopCoder 레이팅이 보이는 분들은 class 이름이 coder어쩌구어쩌구 로 되어있죠.

그리고 레이팅이 없는 분들은 class가 비어있습니다.

랭킹에서 보여지기에는 TopCoder 레이팅이 보여지지만 그분들도 codeforce 레이팅을 갖고 있는 경우가 많으므로

우선은 단순히 class가 있는지 없는지로 유저들을 걸러내겠습니다.

        tds = tr.find_all('td')
        rating = tds[1].a.span['class'][0]
        if len(rating) > 0:
            num_solved = tds[3].a.string.strip()

tds 는 column들의 리스트입니다. 유저의 아이디는 두번째 column에 있으므로 tds[1] 을 보면 됩니다.

너무 자세히 설명하면 글이 길어지니 대충대충 넘어가겠습니당.

num_solved는 푼 문제 수 입니다.

자 거의 다왔습니다. 이제 이 유저의 codeforce 레이팅을 구해야 하는데, 그러려면 codeforce 아이디를 알아야 합니다.

그리고 codeforce 아이디를 알아내기 위해서는 그 유저의 프로필 페이지로 가야합니다.

프로필 페이지의 주소를 구하는 코드는 다음과 같습니다.

            if (rating == 'user-legendary'):
                user_id = tds[1].a.span.find(text=True, recursive=True) + tds[1].a.span.find(text=True, recursive=False)
            else:
                user_id = tds[1].a.span.string
            user_url = "https://www.acmicpc.net/user/" + user_id

if-else문이 나온 이유는 codeforce 레이팅이 Legendary Grandmaster이신 갓갓 분들은 유저 아이디가 일반적인 경우와 다르게 쓰여있기 때문입니다.

url을 알아냈으니 다시 유저 프로필 페이지에 대한 beaurifulsoup 객체를 얻어옵니다.

            user_soup = get_soup_from_url(user_url)

프로필 페이지를 들어가보면 이렇게 되어있는데요,

여기서 'Codeforces' 라는 text 옆에 있는 저 아이디를 읽어야 합니다.

            codeforce_th = user_soup.find('th', text='Codeforces')
            if codeforce_th:
                codeforce_url = codeforce_th.findNext('td').a['href']
            else:
                continue

else: continue 는 탑코더 레이팅은 있으나 codeforce 아이디를 등록하지 않은 사람들을 걸러냅니다.

으악! 이제 마지막 관문인 codeforce 프로필 페이지로 통하는 url까지 얻어냈어요.

            codeforce_soup = get_soup_from_url(codeforce_url)
            try:
                acc_rating = codeforce_soup.find('img', attrs={'title': 'User\'\'s contest rating in Codeforces community'}).findNext('span').string
            except:
                continue

acc_rating에 그토록 갈망했던 codeforce rating이 들어가게 됩니다.

try except 문이 나온 이유는....탑코더 레이팅은 있고 codeforces 아이디도 등록은 해놨는데 시험은 보지 않아 rating이 없는 분들이 에러를 발생시켜서 입니다.

이제 정말로 다 했군요.

마지막으로 num_problem과 acc_rating을 한줄 한줄 파일에 적는 코드를 추가하면 최종 코드는 다음과 같습니다.

import json
from application import get_soup_from_url

with open('ranking.txt', 'a') as f:
    for i in range(1, 21):
        url = "https://www.acmicpc.net/ranklist/" + str(i)
        soup = get_soup_from_url(url)
        table = soup.find(id="ranklist")
        trs = table.tbody.find_all('tr')
        for tr in trs:
            tds = tr.find_all('td')
            rating = tds[1].a.span['class'][0]

            ## Check if user has codeforce rating
            if len(rating) > 0:
                num_solved = tds[3].a.string.strip()
                print(num_solved)
                ## Get codeforce profile url
                if (rating == 'user-legendary'):
                    user_id = tds[1].a.span.find(text=True, recursive=True) + tds[1].a.span.find(text=True, recursive=False)
                else:
                    user_id = tds[1].a.span.string
                user_url = "https://www.acmicpc.net/user/" + user_id

                user_soup = get_soup_from_url(user_url)

                codeforce_th = user_soup.find('th', text='Codeforces')
                if codeforce_th:
                    codeforce_url = codeforce_th.findNext('td').a['href']
                    print(codeforce_url)
                else:
                    continue

                # Get accurate codeforce rating
                codeforce_soup = get_soup_from_url(codeforce_url)
                try:
                    acc_rating = codeforce_soup.find('img', attrs={'title': 'User\'\'s contest rating in Codeforces community'}).findNext('span').string
                except:
                    continue
                print(acc_rating)

                f.write(num_solved + ' ' + acc_rating + '\n')

이 코드를 실행시켜놓고 잠시 밥을 먹고 오면...!

4350 2855
4055 2611
3047 2919
2878 2003
2723 2917
2672 1944
2565 2044
2538 1977
2402 1935
2362 1993
2279 1901
2242 2308
2106 1644
2005 1984
1961 1955
1945 2315
1882 2823
...

이런 442줄의 텍스트 파일이 생깁니다!

2. 그래프 그리기

그래프는 chart,js 라는 javascript 라이브러리를 이용했습니다.

(생략)

그래서 그려보면...!

짜잔~~~!

축하합니다! .txt는(은) 멋진 그래프(으)로 진화했다!

(앞쪽에 레이팅 3600대 점수는 어떤 분이 codeforce 아이디에 tourist를 적으셨더군요ㅋㅋ)

3. 관찰

사실 애초에 저는 이 뻘짓이 의미있는 데이터를 보여줄거라고 크게 기대하지 않았습니다. BOJ 말고 다른 온라인 저지에서 실력을 키웠을 수도 있으며 단순히 문제를 많이 푼다고 레이팅이 높아진다는 건 말도 안되는 소리이며 또 codeforce 레이팅이 정확하다고 말할수도 없기 떄문입니다. 순전히 개인적인 호기심에서 시작한 일이지만 그래도 어느정도 결과가 선형적으로 나왔으면 싶은 마음이 있었으나...역시 현실은 그렇지 않군요.

레이팅 2500점 이상인 분들은 제 예상과는 전혀 다르게 100문제부터 4000문제까지 골고루 분포하고 있었습니다. 저만큼 문제를 풀고 저보다 레이팅이 훨신 높은 분들이 많다는 소리이죠. 혹시 부계정인가 싶어 codeforce 아이디의 중복을 제거해보기도 했지만 결과는 똑같았습니다.

그런데, 희망적인 것도 발견할 수 있습니다.

뭔가 lower bound가 있는 것처럼 보이지 않으시나요??

푼 문제 수가 500문제 이상인 분들은 모두 초록 등급 이상, 1500문제 이상인 분들은 파란색 등급 이상, 2100문제 이상 푼 분들은 모두 보라색 등급 이상입니다. 3000문제 이상 푼 분들은 모두 빨간색이군요!

역시 노력은 우리를 배신하지 않는걸까요?

저는 수학자도 아니고 데이터 과학자도 아니므로 저의 판단은 여기까지 하겠습니다.

그래도 알고리즘 공부를 하다가 "난 머리가 안좋은건가? 난 아무리 해도 안되나?" 하는 자괴감에 빠졌을 때 "2000문제 풀어나 보고 얘기하자" 라고 스스로 힘을 낼수 있을것 같습니다.

(혹시 저의 뻘짓을 이어서 이 데이터를 다뤄보고 싶으신 분이 계신다면 https://github.com/MoonHyuk/acmicpc.cc/blob/master/ranking.txt 에서 txt 파일을 다운 받으실 수 있습니다.)

4. 그래서 허락은 받고 하는건가요?

그렇기도 하고 아니기도 합니다.

2년전 백준님이 https://www.acmicpc.net/board/view/2308 에서

공식적으로는 사이트 정보를 크롤링해 재가공하는 것을 막지 않습니다. 일부 대학 동아리와 기타 단체에서 자체 사이트에 회원들의 정보를 크롤링해 관리하고 있는 것으로 알고있는데, 막을 생각은 없고 오히려 좋은 방향인 것 같습니다. 주로 푼 문제에 관한 정보를 가져가는 것으로 알고 있고요.

저는 막지 않는데, CloudFlare(DNS+CDN provider)에서 막을 수는 있습니다.

라고 하셨습니다. 직접적인 허락은 받지 않았으나 저 글을 믿고 일을 하는 중입니다.

처음에 크롤링 할때 막혔던 이유가 이 CloudFlare 때문인것 같네요.

2년 전 글이라서 지금은 생각이 달라지셨을 수도 있습니다. 만약 그러시다면 주저하지 않고 글을 삭제하고 acmicpc.cc 운영을 멈추겠습니다.

관심가지고 읽어주셔서 정말로 감사드립니다.

본문의 그래프는 http://acmicpc.cc/statistics 에서 원본을 보실 수 있습니다.

제 사이트가 힘들게 공부하시는 여러분들에게 재미와 힘이 되었으면 좋겠습니다.

어떤 내용이든간에 풀 리퀘스트나 메일 환영합니다.

♡.♡


댓글 (13개) 댓글 쓰기


ainch96 6년 전

그래프 우측 하단이 비어있다는 건 많은 노력을 하면 일정 수준의 실력을 갖출 수 있다는 것 일까요..? 뭔가 결과 가 멋있게 나온것 같아요..!


godmoon00 6년 전

네! 우연의 일치일 수도 있지만 포기하지 않을 이유가 하나 생겼네요


zlzmsrhak 6년 전

좋은 글 감사합니다. 많은 분들이 공부를 잘 하기 위해 어떤 것들을 해야 하는지에 대해 약간이나마 궁금증이 해소됐을 것이라고 생각됩니다.

조사 과정에서 아쉬운 점이 몇가지 있습니다. 첫 번째로, CF 레이팅은 매우 빠르고 급격하게 변합니다. 그렇기 때문에 역대 최고 레이팅으로 측정하는 것이 더 나은 것 같습니다. 대표적으로, @ainta 님은 한때 세계 4등, 3180정도의 레이팅이었지만 지금은 2700대까지 떨어졌고, 마찬가지로 @dotorya 님도 비슷한 현상을 보이고 있습니다. 이 현상은 전 레이팅대에서 나타날 것 같아 보입니다.

두 번째로, 모든 유저가 BOJ의 푼 문제수를 늘리기 위해 노력하고 있지는 않습니다. 때문에 푼 문제의 난이도 관련 차원이 추가되어야 할 것 같습니다. 레이팅 2700 정도의 사람들이 A+B를 풀까요? 대표적인 예시로 @sukh1222 (CF:gs12117) 님이 있습니다. BOJ가 주 연습처도 아닐 것 같고, 재능 가득한 사람이라 문제도 별로 안풀고? 여러 이유가 있겠습니다만, 어쨋거나 잘 하는 사람이어도 자신의 실력에 맞는 문제만을 푸는 경우도 꽤 있습니다.


하나씩 보겠습니다.

사실 애초에 저는 이 뻘짓이 의미있는 데이터를 보여줄거라고 크게 기대하지 않았습니다. BOJ 말고 다른 온라인 저지에서 실력을 키웠을 수도 있으며 단순히 문제를 많이 푼다고 레이팅이 높아진다는 건 말도 안되는 소리이며 또 codeforce 레이팅이 정확하다고 말할수도 없기 떄문입니다. 순전히 개인적인 호기심에서 시작한 일이지만 그래도 어느정도 결과가 선형적으로 나왔으면 싶은 마음이 있었으나...역시 현실은 그렇지 않군요.

  1. 먼 옛날 도블렛이 성행하던 시절에는 그렇지 않았겠지만, 지금 현재는 국내에서 BOJ가 독보적으로 많이 사용되고 있다고 생각합니다. 때문에, BOJ의 데이터 분석은 꽤 도움이 될 것처럼 보입니다... (상관관계가 없는 것도 관계이긴 하니까요)
  2. 개인적으로, CF 레이팅과 푼 문제수는 비례관계라고 생각합니다. CF는 구현속도가 매우 중요한 대회시스템이고, 천재적인 아이디어보다는 익숙한 아이디어, 약간씩 변형된 문제가 많이 나오는 편입니다. 이 경우에는 푼 문제수를 늘려 지식의 범위를 늘리는 것이 레이팅 상승에 도움이 될 것이라고 생각됩니다.
  3. 그럼에도 선형으로 결과가 나오지 않은 이유는 단순합니다. BOJ는 문제가 "너무" 많아서, 모든 문제를 푸는 것이 엄청나게 힘듭니다. A+B가 5문제나 있고, 별찍기가 20문제, 단순 BFS, DFS 구현문제는 넘쳐흐르고, ... 자신의 실력대에 있는 문제를 모두 풀려면, 엄청나게 시간을 부어야 하던가, 아니면 실력이 더욱 늘어온 뒤 돌아와야 합니다.

레이팅 2500점 이상인 분들은 제 예상과는 전혀 다르게 100문제부터 4000문제까지 골고루 분포하고 있었습니다. 저만큼 문제를 풀고 저보다 레이팅이 훨신 높은 분들이 많다는 소리이죠. 혹시 부계정인가 싶어 codeforce 아이디의 중복을 제거해보기도 했지만 결과는 똑같았습니다.

  1. 제가 레이팅 2500 이상의 분들을 모두 알고 있는데, 대부분 공부한 지 3년이 넘었고, 7년 이상도 꽤 많은 것 같습니다. 물론, 그 당시에는 BOJ가 알려지지 않았을 때라서 푼 문제수도 계산되지 않았습니다. BOJ에서는 문제를 적게 풀었어도, 그분들 모두 다른곳에서 적어도 2천문제 이상은 해결한 분들입니다.

그런데, 희망적인 것도 발견할 수 있습니다.

뭔가 lower bound가 있는 것처럼 보이지 않으시나요??

푼 문제 수가 500문제 이상인 분들은 모두 초록 등급 이상, 1500문제 이상인 분들은 파란색 등급 이상, 2100문제 이상 푼 분들은 모두 보라색 등급 이상입니다. 3000문제 이상 푼 분들은 모두 빨간색이군요!

역시 노력은 우리를 배신하지 않는걸까요?

  1. 적어도 CF 레이팅은 배신하지 않을 것으로 생각합니다만, 아직 표본이 없어서 궁금증으로 남아있습니다. 어쨋거나 lower bound가 있는 이유는, 시간을 매우 많이 쓰면 자신의 실력대의 문제를 모두 해결할 수 있기 때문입니다. 실력만큼 푼 문제수가 나오게 되는 거죠... 많은 시간을 써서 500문제를 푸신 분들이, 시간을 더 써서 푼 문제수를 늘려나갈 수 있다고 한다면, 꽤나 긍정적인 결과로 받아들여도 될 듯 합니다. (푼 문제수가 오르면 lower bound가 있으니 레이팅도 같이 오르겠죠?)

알고리즘 문제를 푸는 것은 크게 두 가지의 단계가 있습니다. 알고리즘을 생각하는 단계와, 그것을 구현하는 단계. 종이와 펜을 써서 문제를 푸는 단계와, 이것을 코드로 옮기는 단계입니다. 잠깐 다른 말을 하면, 재귀함수가 잘 이해되지 않아 구현에서 재귀함수를 사용할 수 없다면, 이것은 알고리즘 생각 단계에서 문제가 생기고 있는것이고 구현 문제가 아닙니다. "이해" 관련된 부분 전체가 생각 단계입니다.

알고리즘 문제의 풀이를 생각하는 것은, 수학의 영역입니다. IMO에서도 정올스러운 문제가 나오거나, ICPC에서 수학문제가 나오는 것들을 빼고서라도, 수학 문제를 푸는 과정과 알고리즘 문제의 풀이를 생각하는 것이 매우 비슷한 단계를 밟아 나갑니다.

풀이를 구현하는 것은, 개인적인 의견입니다만, 연습의 영역입니다. 평소에 얼마나 많이 코딩을 해보고, 깔끔하고 짧게 코딩하려면 어떻게 해야 하는지, 잘 틀리지 않게 코딩하려면, 등등... 연습하고 공부하면 느는 영역이라고 생각하고, 이 부분만큼은 테크닉과 연습입니다. BOJ에서 문제를 많이 해결한 분들의 코드를 읽어보는 것도 매우 좋은 습관이라고 생각합니다.

언제나, 누구나, 노력과 실력이 비례하는지에는 의문을 가지고 있는 것 같습니다. 그래도, 잘해져야 한다면, 한번 공부해 보는 것도 좋은 것 같습니다. 재미는 실력이 느는 만큼 더 느껴지는 것이니까요.


godmoon00 6년 전

허접한 저의 글에 이렇게나 좋은 살을 붙여주시다니 감사합니다..

PS에 입문한지 얼마 안되어 어떻게 하면 실력을 늘릴지 궁금해 하던 제가 개인적으로 반 장난삼아 시작한 일인데 zlzmsrhak님 덕분에 좀 더 심도있는 일이 될수 있을거 같군요.

codeforce 최고 레이팅을 반영하라는 말씀은 곧바로 수용하겠습니다. 늅늅이라 레이팅이 크게 요동치는지 몰랐네요.. 이외에도 제가 놓쳤던 부분들 짚어주셔서 감사합니다.

저도 한가지 살을 좀 더 덧붙이자면, '1만 시간의 법칙' 이라는 것을 저는 믿습니다. 그런데 1만 시간의 법칙이 마치 '어떤 식으로든 1만 시간을 투자하면 누구든지 경지에 오른다' 라는 듯이 오용이 되는 경우가 있는데, 실제 저자는 의도적인 연습을 강조합니다. 의도적인 연습이란 내가 부족한 것을 보충하기 위한 것이어야 하고, 연습의 성과와 방향에 대해 지속적으로 피드백을 받는 것이라고 합니다. 슬램덩크에서 강백호가 2만번의 슛 연습을 할 때 동영상으로 녹화하면서 자세를 피드백 받았던것 처럼요. 알고리즘 뿐만이 아니라 모든 분야에서 반복적인 연습과 그에 대한 피드백은 중요한것 같습니다.

부족하지만 감히 몇자 적어봤습니다. codeforce div2 라운드가 곧 시작이어서 전 이만...!!


twinparadox 6년 전

일전에 해당 사이트를 보고 깃허브 들어가서 스타 눌러드렸습니다 ㅎㅎ



joonas 6년 전

2-3주전에 우연히 발견했을때는 업적 나오는 것 밖에 없어서 contribute 하려다 파이썬이라 잠시 미루었는데. 벌써 그래프가 나오는군요. 기대됩니다 ㅎㅎ


cokcjswo 6년 전

와 사이트 이쁘네요 !! 점점 살이 붙어가길 기대합니다 ㅎ


withham1 6년 전

재미있는 사이트네요. 그래프로 한 눈에 보이니까 더 열심히 해야되겠다는 생각이 팍팍 드네요ㅎㅎ


leeking91 6년 전

사이트가 정말 흥미롭네요 ! 아주 좋습니다..

개인적으로 , 저는 그래프가 맞은 개수 위주로 했으면 좋겠다는 생각이 있습니다. 그리고 그 해당날짜에 마우스를 올렸을때 지금처럼 시간초과등등..정보가 나왔으면 좋겟다는 생각이 있습니다 ( 제가 틀린개 더 많아서 그런건..절대...ㅜㅜㅜ) 그래프가 좀 어지럽..(제가 많이 틀려서 그런겁니다)다고 느껴져서..이렇게나마 글남겨봅니다..

아니면 맞은개수 혹은 시도했지만 아직 풀지 못한문제 이렇게 두개를 구성해도 좋을것같습니다..


vl0612 5년 전

흥미로운 사이트네요! 매일 접속해서 확인하는 게 동기부여도 되고 재미있습니다 ㅋㅋ

" Accepted! History 저희 사이트에 처음 오셨군요! 내일부터 푼 문제수 그래프를 보실 수 있습니다. "

3일전 즈음에 접속했을 때에도 이 멘트가 떴었는데, 기능 업데이트가 되지 않았거나 중단된 부분인가요?? (궁금 'ㅁ' )