시간 초과는 컴파일 시간과는 무관합니다. 시간 초과는 프로그램이 실행되는 데에 걸리는 시간에 의해서만 발생합니다.
알고리즘에서 시간에 대해 가장 중요하게 보는 것은 시간 복잡도입니다. 따라서 문제들도 대부분 코드의 시간 복잡도가 나쁘지 않다면 구체적인 구현 코드는 웬만큼 비효율적이어도 통과가 될 수 있게끔 제한을 설정해 둡니다.
예를 들어, n <= 2만이고 시간 제한이 1초인 문제라면 정해가 O(n^2)이 아님은 쉽게 유추할 수 있습니다. 왜냐하면, n^2은 400억이고, 전체적인 코드의 효율성이 다른 코드보다 10배가 좋다고 하더라도 40억은 여전히 1초에 돌지 않기 때문입니다. 만일 그 문제가 O(n*log(n))의 풀이를 정해로 한다면, n*log(n)은 대략 400만이므로 이번에는 다른 코드보다 효율이 10배가 안 좋아도 4천만으로 시간 내에 충분히 돌 수 있을 것임을 알 수 있습니다.
이렇게 대부분의 문제에서 시간 초과가 발생하는 원인은 코드의 전반적인 로직이 틀렸기 때문에 발생하는 것이고, 따라서 이미 짜여진 코드에서 일부를 수정해서 시간 초과를 피하는 것은 어렵다고 보시면 됩니다. 문제의 제한 조건에 맞는 올바른 로직부터 생각하는 것이 더 좋은 공부 자세입니다. 만일 시간 복잡도를 계산해 봐도 문제가 없는 코드라면, 이번에도 단순한 효율성 문제보다는 코드의 어딘가가 계산한 시간 복잡도와는 달리 더 안 좋은 시간 복잡도를 가지고 있거나, 무한 루프를 도는 등 여전히 코드 로직의 문제일 가능성이 높습니다.
andymon 3년 전
요새 문제를 푸는데 시간초과가 너무걸립니다..
나름 열심히 짰는데도 시간초과가 너무 걸려서.. 혹시 이미 짜져 있는 코드에서 시간을 단축시키는 방법이 없을까요?
참고로 c언어 공부하고 있습니다.