예제가 아닌, 문제의 조건에 맞는 코드를 작성해야 합니다.

알고리즘 문제는 일반적으로 어떠한 입력이 주어졌을 때, 그에 대한 올바른 정답을 출력하는 것으로 구성됩니다. 대부분의 문제에는 이러한 입력이 어떤 형식으로 주어지고 출력 형식이 어떻게 되어야 하는지에 대한 힌트를 주기 위해, 그리고 문제 이해를 돕고 몇 가지의 간단한 테스트를 해볼 수 있도록 하나 이상의 예제를 제공합니다. 여기서 중요한 부분이 있습니다. 굵은 글씨로 강조한 것처럼, 예제는 언제까지나 문제 풀이에 대한 힌트를 주고 몇 가지의 간단한 테스트용 예시를 제공할 뿐, 절대로 이들을 통과하기 위한 코드를 작성하라는 의미로 주는 것이 아닙니다.

 

그러면 문제를 풀 때에는 어디를 목표로 봐야 할까요? 바로 문제의 조건입니다. 문제의 조건이라는 것은 시간/메모리 제한, 주어지는 수의 최소/최대 범위, 문제 내용에 따른 추가적인 값의 제한 등을 말하는 것으로, 모든 것은 전부 문제 본문에 주어져 있습니다 (가끔 오래된 문제 중 테스트 케이스의 수의 최댓값을 알려주지 않는다든가 하는 경우는 있습니다). 어떤 문제를 풀기 위해 작성해야 할 코드는 해당 제한 내의 어떠한 입력이 주어지더라도 항상 올바른 답을 출력할 수 있는 코드여야 합니다. 채점은 예제만 하는 것이 아니라, 문제의 조건 내의 다양한 입력(일반적으로 수십~수천 개)들을 테스트하여 모든 경우에 항상 올바른 답을 내는지를 충분히 오래 검증하는 것으로 이루어지기 때문입니다.

 

예를 들어 어떤 문제에서 $N$이 입력으로 주어지고 그 후 $N$개의 수가 주어진다면, 그 코드는 $N$을 입력받고 $N$개의 수를 입력받고 $N$개의 수에 대해 연산을 해야 합니다. 예제에서 $N$이 5인 것만 주어졌다고 해서 수를 5개만 고정으로 입력받거나, 5개의 수에 대해서만 연산을 해서는 안 됩니다.

 

시간 제한이 1초, $N$개의 수가 주어지는 문제에서 $N$이 $1$ 이상 $100,000$ 이하라고 쓰여있다면 그 문제를 푸는 코드는 $1$ 이상 $100,000$ 이하의 어떠한 $N$에 대해서도 1초 안에 항상 올바른 답을 출력할 수 있어야 합니다. 하지만 조건이 이렇게 주어지는 문제라고 해도 여백이 부족하기 때문에 실제로 예제에 $N=100,000$인 경우를 주는 일은 없습니다. $N \le 10$인 예제에 대해 눈 깜짝할 사이에 답이 나오는 코드를 작성하는 것은 실제로 코드가 문제가 원하는 정도의 효율성을 갖추었다는 것을 전혀 보장하지 못합니다. 문제의 목표는 예제가 눈 깜짝할 사이에 나오는 코드가 아니라 $N=100,000$이 1초 내에 실행 가능한 코드가 되어야 합니다.

 

$N$개의 수가 주어지는데 각각이 $-1,000,000,000$ 이상 $1,000,000,000$ 이하로 주어진다면 그 수들이 해당 범위 내에서 어떠한 값을 가지든, 전부 같은 값을 가지든, 오름차순이나 내림차순으로 주어지든, 양수만 주어지든, 음수만 주어지든 항상 올바른 답을 출력할 수 있어야 합니다. 조건에서 음수가 주어질 수 있다고 했다면, 설령 예제에서 음수를 보여주지 않았다고 해도 음수를 처리할 수 있는 코드를 작성해야 합니다.

 

최대 $1,000,000$인 수에 대한 소수 판별을 해야 한다면 $1,000,000$ 이하의 어떠한 수에 대해서도 소수 판별을 할 수 있어야 하고, 예제에서 최대 두자릿수인 수만 줬다고 해서 2, 3, 5, 7 정도의 수로만 나누어보고 소수 판별을 잘 하는 것으로 생각해서는 안 됩니다. 백만 이하의 모든 수를 하나 하나 나누어보는 것으로 소수 판별을 하기 위해서는 적어도 997까지로는 나누어보아야 합니다.

 

따라서 문제를 풀 때에는 어떻게 하면 예제를 잘 나오게 할 수 있을까가 아닌, 어떻게 하면 문제 본문에 주어진 모든 조건을 만족하는 코드를 작성할 수 있을까를 생각해야 합니다. 문제 본문만 보고도 문제를 이해할 수 있다면 예제는 볼 필요도 없습니다. 예제는 문제 이해에 대한 힌트 정도로만, 그리고 일단 다 작성된 코드를 간단히 테스트해보는 용도 정도로만 사용하세요.

 

예제는 문제의 조건을 만족하는 무수히 많은 입력 중 크기가 매우 작은 극히 일부에 불과하기 때문에, 예제에 특화된 코드는 다른 아무런 랜덤 입력에서 틀릴 가능성이 매우 매우 매우 매우 높습니다. 게다가 예제는 극단적인 입력들을 제공해주지 않아 시간 복잡도, 배열 크기, 자료형의 크기 등의 오류를 테스트해주지 못하므로, 코드를 작성할 때에는 항상 이러한 요소들을 문제의 조건을 보고 신경써야 합니다. 특히 시간 복잡도는 알고리즘을 공부한다면 가장 먼저 알고 들어가야 하는 개념이므로, 아직 공부하지 않았다면 바로 좋은 자료를 찾아 습득하기를 강력히 추천합니다.