100%에서 틀리는 것의 의미

BOJ의 질문 게시판 공지사항에서는 "몇 %에서 틀렸다는 내용을 올리지 마세요"라고 적혀있지만, 개인적으로는 몇 %에서 틀렸는지는 때때로 좋은 힌트가 된다고 생각합니다. 그 중 가장 영양가 높은(?) 것이 바로 100%에서 틀리는 경우입니다.

 

채점 프로그램의 대략적인 동작 방식은 50%에서 틀리는 것의 의미 글에서 설명했으니 여기서는 100%에서 틀리는 것이 무슨 의미를 가지는지에 대해서만 알아보겠습니다. 모든 경우에 해당되는 것은 아니지만, 대부분의 경우에 유의미한 힌트를 줍니다.

 

BOJ에서 데이터를 정렬하는 방법에는 몇 가지가 있는데, 그 중 가장 일반적인 기본값은 데이터의 크기의 내림차순입니다. BOJ 자체에서 여는 대회 문제들을 제외하고, 출처가 따로 없거나 외부 대회가 출처인 문제들의 경우 대부분 이 방식을 따릅니다.

 

그렇다면 100%에서 틀렸다는 것은 직관적으로 생각했을 때 데이터의 크기가 가장 작은 것입니다. 그 앞의 모든 평범하고 거대한 케이스는 다 맞았고, 정말 정말 정말 정말 작은 케이스 하나를 틀린 것입니다. 그리고 그것이 정말 유일한 반례일 가능성 또한 적지 않습니다. 즉, 최소 크기의 데이터 하나에 대한 예외 처리가 제대로 이루어지지 않아서 받게 되는 결과라고 볼 수 있습니다.

 

조금 더 케이스를 구체화하자면 다음과 같이 나누어볼 수 있습니다.

• $N=1$ 등에서 답이 달라지는 경우를 내 코드가 처리하지 못하고 있을 수 있습니다. 아주 대표적이고 가장 흔한 케이스가 바로 소수를 구하는 문제에서 1을 소수로 판정하고 있는 것 등입니다. 나머지 모든 수는 "2부터 $\sqrt(N)$까지의 자연수로 나누어떨어지지 않으면 소수"를 만족하지만, 1은 그럼에도 소수가 아닙니다. 에라토스테네스의 체를 돌리더라도 1은 건너뛰고 나머지에 대해서만 '소수가 아님'을 체크하고 있을 가능성도 높습니다. 다른 흔한 경우로는 dp 배열의 [1], [2] 인덱스를 처음에 강제로 채우는 코드에서, 처음에 dp 배열의 크기를 N으로 동적할당하여 [2] 인덱스 자체가 존재하지 않아 런타임 에러가 발생하는 경우 등이 있습니다.
• $N=1$ 등에 대한 예외 처리를 잘못된 형태로 하고 있을 수 있습니다. 예외 처리를 한 곳이 있다면 반드시 그 예외 처리가 정말 맞는지에 대한 검증 또한 필요합니다. 대표적으로 1로 만들기 문제에서 1을 1로 만드는 데에 필요한 연산 횟수는 0인데 이 경우를 예외 처리하겠다고 1로 출력하는 사례가 굉장히 많이 보입니다.

 

언제나 그렇듯이 C/C++ 코드에서 undefined behavior가 있다면 내 컴퓨터에서는 잘 돌아가는데 제출하면 틀리는 경우가 얼마든지 있을 수 있으므로, 해당 케이스를 입력해보는 것을 넘어 그 코드가 UB를 일으키지 않는지 코드를 눈으로 읽는 연습 또한 필요합니다.

 

꼭 정확히 100%가 아니더라도 80~90%대의 높은 %에서 틀렸다면 비슷한 케이스들을 의심해볼 수 있습니다. 데이터셋에 따라 다르겠으나, 그 정도까지 갔으면 이미 한자릿수대의 $N$값에 대한 작은 케이스들에서 예외가 발생하고 있을 가능성이 높습니다. 이러니저러니 해도, 결국 다양한 케이스들을 직접 만들어 입력해보는 것이 문제점을 찾는 가장 기초적이고 빠른 방법입니다.