TLE가 발생하는 이유와 발견 방법

TLE는 시간 제한 초과를 뜻합니다. 코드가 정확하지만 너무 느리다는 의미입니다. 대회에서 초보자가 가장 흔하게 마주치는 장벽입니다. ⏰

TLE는 거의 항상 n에 비해 복잡도가 너무 높아서 발생합니다. n = 10^6에서 O(n^2) 아이디어를 사용하면 매번 시간 예산을 초과합니다.

가장 알아차리기 어려운 TLE 원인은 눈치채지 못한 반복문입니다. 반복문 안의 메서드 호출 자체가 반복할 수 있어 O(n)이 O(n^2)으로 바뀔 수 있습니다.

리스트에서 x의 포함 여부를 확인하는 데는 매번 O(n)이 걸립니다. 반복문 안에서 사용하면 이차 시간이 됩니다. 포함 여부 확인에는 집합을 사용하여 O(1)로 바꾸십시오.

반복문에서 +로 문자열을 연결하면 매번 전체 문자열이 복사됩니다. 이 숨은 비용은 O(n^2)이므로 부분을 모은 뒤 한 번만 join하십시오.

일반적인 input()으로 대량 입력을 읽으면 입력 자체 때문에 TLE가 발생할 수 있습니다. 큰 테스트에서는 sys.stdin을 사용하여 모든 데이터를 빠르게 가져오십시오.

같은 값을 계속 다시 계산하면 시간이 낭비됩니다. 누적 합과 같은 결과를 캐시하면 반복되는 O(n) 작업을 O(1)로 바꿀 수 있습니다.

채점기가 판단하기 전에 TLE를 찾아내십시오. 복잡도에 따른 연산량을 계산하여 10^8과 비교하십시오. 초과한다면 제출하기 전에 다시 설계하십시오.

TLE가 발생하면 가장 깊이 중첩된 반복문을 찾아 실제로 몇 번 실행되는지 물어보십시오. 거의 항상 그 지점에서 시간이 새어 나갑니다.

TLE를 해결하려면 보통 미세 조정보다 더 나은 알고리즘이 필요합니다. 중첩된 순회를 정렬, 해시 맵 또는 투 포인터로 바꾸십시오.

제한을 조금 초과한 경우 빠른 입출력과 같은 작은 상수 배수 개선이 도움이 될 수 있습니다. 하지만 먼저 빅오 자체가 올바른지 확인하십시오.

TLE는 정확하지만 느리다는 뜻입니다. 숨은 반복문을 찾고, 리스트를 집합으로 바꾸고, 문자열은 한 번만 join하며, 빅오를 낮추십시오. 먼저 예측한 다음 제출하십시오. 🛠️