startlink   3달 전

안녕하세요. Baekjoon Online Judge의 최백준입니다.

지난 9년간 이 사이트는 자동 채점 방식을 이용해서 제출된 소스를 채점하고 있었습니다. 채점 방식을 간단하게 생각해보면, 다음과 같은 과정을 거칩니다.

유저의 제출 -> 채점 서버에서 컴파일 -> 컴파일 성공/실패

여기서 컴파일 실패가 나는 경우 컴파일 에러를 받게 됩니다. 컴파일 성공한 소스는 준비된 데이터 N개를 이용해 채점받게 됩니다. 데이터 1개를 채점하는 과정은 아래와 같습니다.

데이터 복사 -> 실행 -> 미리 준비한 정답과 비교 또는 스페셜 저지

이 방식은 대부분의 온라인 저지에서 사용하는 방식입니다. 이 방법은 다음과 같은 단점이 있고, 아래와 같이 해결할 수 있습니다.

  1. 데이터의 개수가 너무 많은 경우에 채점이 너무 오래걸림 -> 채점 서버를 더 켬
  2. 틀린 소스인데 데이터의 부족으로 인해서 맞았습니다!!를 받음 -> 데이터를 추가함
  3. 런타임 에러가 발생한 경우에 왜 어떤 이유로, 코드의 몇 번째 줄이 원인을 발생시키는지 알 수 없음 -> 언어를 Java, Python 계열로 바꾸거나, gdb를 돌려봐야 함

채점 서버를 더 켜면 사이트 운영 비용이 늘어납니다. 데이터를 추가하면, 기존의 제출을 재채점해야 하고, 특정 N일때만 잘못된 답을 출력하는 소스는 틀리게 만들기 매우 어렵습니다. 재채점을 하면 채점 서버를 더 켜야 하기 때문에 운영 비용이 늘어납니다.

오늘 사이트 운영 비용과 위와 같은 단점을 극복하기 위해서 채점 방식을 변경하기로 했습니다.

지난 몇 년간 저는 코드를 눈으로 보고 5초 안에 컴파일 성공 여부를 판단하는 연습을 하고 있었습니다. 코드가 그렇게 길지 않다면, 그냥 쓱 쳐다보는 것만으로도 컴파일 에러의 유무를 파악할 수 있습니다. 이 연습을 하면서 머리속으로 실행시켜보는 능력도 연습을 했습니다. 컴파일 성공 여부를 판단과 동시에 이 소스가 이 문제를 풀 수 있는 소스인지도 파악할 수 있게 되었습니다.

위의 단점은 이 방식을 이용해 추가적인 비용없이 해결할 수 있게 됩니다. 더불어 채점 서버가 필요없기 때문에, 사이트 운영 비용이 큰 폭으로 줄어들게 되었습니다.

앞으로는 모든 제출을 제가 눈으로 보고 채점 결과를 보내드리려고 합니다.

  1. 데이터의 개수가 너무 많은 경우에 채점이 너무 오래걸림 -> 데이터가 필요 없기 때문에, 채점 속도가 매우 빠름
  2. 틀린 소스인데 데이터의 부족으로 인해서 맞았습니다!!를 받음 -> 지난 몇 년간의 연습으로 데이터 없이 채점하는 능력을 얻어서 이런 일이 없음
  3. 런타임 에러가 발생한 경우에 왜 어떤 이유로, 코드의 몇 번째 줄이 원인을 발생시키는지 알 수 없음 -> 역시 연습을 통해 이 능력도 얻게 되었음

현재 사이트의 이용자 정도면 제가 눈으로 소스를 읽고, 채점 결과를 쿼리로 입력하는 시간은 자동 채점보다 훨씬 더 빠릅니다. 걱정되는 것은 쿼리를 입력하는 시간인데, 이를 극복하기 위해 저는 극한의 타이핑을 연습했습니다. 아래 동영상은 저의 타이핑 수련 동영상입니다. 역시 이것도 문제 없습니다.

세계에서 처음으로 시도해보는 채점 방식 앞으로 많이 응원해주세요. 

이 방식의 채점은 채점 번호 12506377부터 시작합니다.

감사합니다.

최백준 드림.

dyk777   3달 전

:fan:이에요

djm03178   3달 전

도주님 팬이에요

djm03178   3달 전

+:doju:

eovh1962   3달 전

출력형식이 잘못된건 캐치못하는듯...

jung2381187   3달 전

난 차라리 웃고 있는

djm03178   3달 전

정채망자가 좋더라

startlink   3달 전

출력 형식이 잘못된 것도 당연히 할 수 있습니다.

subinium   3달 전

살려주세요. 스타트링크 ㅅㅏ무실에서 코드만 보ㄱㅗ 있습니ㅏ...
후원은 하나 187 910160 96507 입ㄴㅣ다 

startlink   3달 전

하나 165 910528 67507가 올바른 계좌번호입니다.

whddls9632   3달 전

커엽

bedrock17   3달 전

맥북도 돌려주세요

moa2app   3달 전

호우!!!

zxcvber   3달 전

앞으로 제출할 때마다 공중제비 한번씩 하겠습니다 안 틀리게 해주세요

tourist   3달 전

Is it rated?

1ilsang   3달 전

올해 하는일 다 잘되게 해주세요

singun11   3달 전

성지 방문하고 갑니다.

중간고사 A+ 나오게 해주세요

jh05013   3달 전

안녕하세요. 새 채점 방식에 버그가 발생한 것 같아서 문의드립니다.

아래는 오늘 제출한 A+B 문제 코드입니다.  https://www.acmicpc.net/source/share/19945f00ea5340af89a8613f652fa26a

소스가 약 1 MB 정도 되므로 내용을 요약하면, x와 y가 주어졌을 때 x와 y에 의해 결정되는 유사-난수로 z를 계산한 후, x, y, z에 의해 결정되는 유사-난수로 '0'과 '1'로 이루어진 길이 2x+y의 문자열 S를 만든 후, 특정 프로그램을 건설한 뒤, 그 프로그램이 "S를 출력하는 가장 짧은 프로그램"인지 판별한 후 그 프로그램이 출력할 문자열을 시뮬레이션으로 얻어내 그 길이를 출력하는 프로그램입니다.

이 코드로 "맞았습니다!!"를 받았으나, 사실 "가장 짧은 프로그램인지 판별", 즉 콜모고로프 복잡도모고로프 복잡도를 계산하는 작업은 uncomputable이므로 이 소스는 성립할 수 없습니다. 아래 논문은 이 "읽고 채점" 채점 방식의 취약점을 다룬, 마침 어제 나온 논문입니다. 제 소스와 비슷한 방식을 쓰지만 저와 달리 라이스 정리를 사용한 것으로 보입니다.

https://arxiv.org/abs/1903.12188

백준님의 훌륭한 채점 실력을 잘 인지하고 있으나 마이크 미르자야노프 교수처럼 이 방식에 근본적인 한계점이 드러날 수도 있음이 염려되어 조심스럽게 글 남겨 봅니다. 감사합니다.

jh05013   3달 전

오타가 났네요. "콜모고로프 복잡도" 링크 뒤에 중복된 "모고로프 복잡도"는 무시해 주세요.

greghahn   3달 전

올해 모든 일 잘 되게 해주세요

malkoring   3달 전

팬이에요.

싸인받아주세요.

qusgkfls93   3달 전

만우절 이벤트 특이하게 하시네요 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

keist99   3달 전

:fan:

YunGoon   3달 전

싸인이에요.

팬해주세요.

GGuu   3달 전

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 삼성가게해주세요

minsung05   3달 전

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

startlink   3달 전

당연히 만우절 이벤트(?) 입니다.

bedrock17   3달 전

(아쉽)

qodydgk8624   3달 전

만연히 당우절 이벤트 입니다.

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