프로그램의 실행 시간은 원래 일정하지 않습니다.

"같은 코드를 여러 번 냈는데 왜 실행 시간이 달라지나요?"

 

정상입니다. 프로그램의 실행 시간은 원래 일정하지 않기 때문입니다.

 

똑같이 프로그램을 실행한다고 해도 그 때의 컴퓨터의 상태가 완전히 같을 수는 없습니다. 메모리의 상태가 다르고, OS가 하고 있던 일이 다르고, 백그라운드 서비스들의 상태가 다르고, CPU의 온도가 다르기 때문입니다. 또한 실행 중에도 이 상태는 얼마든지 중간에 변할 수 있고, 이로 인해 같은 코드를 실행하더라도 프로그램이 눈에 띄게 더 빠르거나 느리게 동작할 수 있습니다. 기본적으로 시간이 오래 걸리는 코드라면 이 실행 시마다의 오차는 더 커지게 됩니다. 예를 들어 평균 300ms 정도가 걸리는 코드가 ±20ms 정도의 오차를 보인다면, 평균 3초가 걸리는 코드는 ±200ms 이상도 충분히 발생할 수 있습니다.

 

우리가 평소에 게임을 하든, 문서 작업을 하든, 매번 똑같은 것을 해도 어떨 때는 빠르고 어떨 때는 느리거나 렉이 걸리죠? 문제 풀이도 똑같습니다. 물론 일상적인 PC 사용 상황에 비해서는 변수가 적겠으나, 같은 코드가 항상 같은 시간에 실행되지 않는다는 점은 동일합니다.

 

 

 

"같은 코드를 여러 번 냈더니 하나는 시간 초과를 받았고 하나는 통과했는데 왜 그런가요?"

 

같은 코드에 대한 실행 시간은 매번 달라질 수 있기 때문에 때로는 그 차이가 시간 초과와 정답을 가르기도 합니다. 그런데, 이때는 한 가지 중요하게 얻어갈 것이 있습니다. 이러한 경우에는 보통 그 풀이는 상당히 비효율적이며, 출제자가 통과를 의도하지 않은 정도의 나쁜 시간 복잡도를 가진 풀이일 가능성이 높다는 것입니다. 정답을 받은 코드도 그냥 정답이구나 하고 넘어갈 게 아니라, 몇 ms가 기록됐는지 확인해 보세요. 문제에 주어진 시간 제한에 매우 근접해있을 가능성이 큽니다. 보통 대부분의 문제의 시간 제한은 출제자가 의도한 시간 복잡도의 풀이라면 웬만큼 비효율적으로 작성하더라도 여유 있게 통과가 가능하게끔 설정해 놓는데, 통과했더라도 소요 시간이 그 제한에 가깝게 나왔다면 그 풀이는 아마도 출제자가 의도한 것보다 비효율적인 시간 복잡도를 가지지만, 출제 시점보다 컴퓨터/컴파일러의 성능이 좋아졌거나, 언어별 보너스 시간 등에 의해 의도치 않게 통과되었을 가능성이 높습니다. 즉, 그런 경우에는 시간 초과가 난 코드가 운이 없었던 게 아니라, 통과된 코드가 운이 좋았다고 생각하는 편이 좋습니다.

 

 

 

"같은 코드가 하나는 0ms고 하나는 4ms가 나왔는데, 너무 차이가 크지 않나요?"

 

BOJ 채점 서버가 측정하는 시간의 최소 단위가 4ms이기 때문에, 0ms와 4ms는 실제로는 0.00000001초 차이일 수도 있습니다. 말 그대로 둘 사이의 경계선상에서 털끝만큼이라도 시간이 덜 걸리거나 더 걸리면 0ms와 4ms로 갈라지는 것이기 때문에 이것만 보고 실행 시마다의 오차가 크다고 볼 수는 없습니다.

 

참고로, Codeforces의 시간 측정은 단위가 더 커서 15~16ms 정도가 최소 차이입니다. 아주 오래 전 윈도우즈의 clock()이 그런 행동을 보였던 기억이 있는데, 아마 코포도 비슷한 환경이지 않을까 싶네요.