50%에서 틀리는 것의 의미

BOJ에서 문제를 풀다 보면 50%에서 오답을 받는 경우를 심심찮게 볼 수 있습니다. 일반적으로 이런 경우는 문제가 "입력은 여러 개의 테스트 케이스로 이루어져 있다"와 같은 형식일 때입니다. 언뜻 보면 퍼센트가 반이나 올라갔으니까, 반은 맞은 건가? 하고 생각하기 쉽습니다. 하지만 대개의 경우, 진실은 그렇지 않습니다. 이게 무엇을 의미하는지 이해하려면 우선 BOJ의 채점 원리를 알아야 합니다.

 

자세한 동작 원리는 https://help.acmicpc.net/judge/info 에 설명되어 있으니, 여기에서는 짧게 필요한 것만 요약하겠습니다.

 

BOJ 채점 프로그램에서 보여주는 %는 하나의 데이터에 대해 프로그램이 실행하는 단계와 그 실행 결과에 대한 판정을 내리는 2개의 단계로 나누어져 있습니다. 예를 들어, 문제에 2개의 데이터가 있다면, 25%는 첫 번째 데이터에 대해 프로그램을 실행하는 도중 보여지고, 50%는 첫 번째 데이터에 대한 프로그램의 실행 결과에 대한 판정을 내리는 과정이고, 75%는 두 번째 데이터에 대한 프로그램의 실행, 100%는 두 번째 데이터에 대한 실행 결과 판정 때 보여집니다. 

 

그런데, 여기서 든 예시처럼 단 2개의 데이터로 신뢰성 높은 채점을 하는 것이 가능할까요? 2개의 데이터로는 너무 허술한 것이 일반적일 것입니다. 하지만 그렇지 않은 경우가 있는데, 바로 처음에 언급한 하나의 데이터가 '여러 개의 테스트 케이스로 이루어진' 문제인 경우입니다. 많은 경우, 이런 문제는 다음과 같은 2개의 데이터로 채점합니다.

 

1. 예제가 아닌 데이터
2. 예제

여기서 예제가 아닌 데이터는 단 한 개의 입력이지만, 실제로는 그 자체가 다수의 테스트 케이스, 적게는 10개 단위에서 많게는 1000개 이상으로 이루어져 있기 때문에 단 한 번의 프로그램 실행으로 실제로는 아주 많은 종류의 입력에 대해 검사를 하고 있는 것입니다. 그 중 단 한 개의 케이스에서라도 정답을 출력하지 못한다면 판정은 50%에서 오답으로 결정이 날 것입니다. 몇 번째 케이스에서 문제가 발생했는지는 이것만으로는 알 수가 없습니다. 첫 번째 케이스에서 틀린 것일 수도 있고, 123번째 케이스일 수도 있고, 100개의 케이스에 대해 그 전부를 다 틀린 것일 수도 있으며, 또는 그냥 입력을 받는 방식 자체가 꼬인 것이 원인일 수도 있습니다.

 

그러므로 이러한 문제에서 50%에서 틀린 것을 보고 굉장히 많은 케이스를 맞았는데 뭔가 엄청난 예외가 있는 것이라고 기대하면 안 됩니다. 사실상 이 코드가 틀렸다는 것 외에는 별다른 정보를 제공하지 않는, 아주 일반적인 오답 판정일 뿐입니다.

 

+ 일부 문제의 경우 이 현상이 50%가 아니라 100%에서 나타날 수도 있습니다. 예를 들어 Google Code Jam 문제들의 경우 예제를 아예 채점하지 않기 때문에, 50%에서 프로그램이 실행되고, 100%에서 이 유일한 데이터에 대한 채점을 합니다. 그래서 모든 오답 판정은 전부 100%에서 받게 됩니다.

 

+ 물론, 여기에서 말한 다중 테스트 케이스 문제가 아니라 진짜로 %가 여러 단계에 걸쳐 쭉 올라가다가 50%에서 틀린 것이라면 이 글에 해당되지 않습니다.