코딩테스트 시간 초과 방지 방법

🚀 코딩 테스트에서 시간 초과 여부를 예측하는 방법

코딩 테스트에서는 주어진 입력 크기(예: 10억) 에 따라 실행 시간을 예측하고,
시간 초과를 방지하는 알고리즘을 선택하는 능력이 중요합니다.

---

✅ 1. 기본적인 실행 속도 기준 (1초 ≈ 1억 연산)

• 보통 1초 안에 실행되려면 약 1억 번(10⁸) 이하의 연산이 가능
• 0.25초 제한이라면 약 2,500만(2.5 × 10⁷) 이하의 연산이 안전한 범위
• 10억(10⁹) 이상의 연산을 직접 반복문으로 처리하면 시간 초과 가능성 높음

📌 실행 시간 예측법

연산 횟수 예상 실행 시간

10^6 (100만)	빠름 (0.01초 미만)
10^7 (1천만)	보통 (0.1초 내외)
10^8 (1억)	거의 한계 (1초 내외)
10^9 (10억)	거의 불가능 (10초 이상)

---

✅ 2. 입력 크기(N)를 보고 적절한 알고리즘 선택

문제에서 주어진 입력 크기(N) 에 따라 가능한 알고리즘의 시간 복잡도를 예측해야 함.

입력 크기 (N) 추천 시간 복잡도 설명

N ≤ 1,000,000,000 (10⁹)	O(log N) 또는 O(1)	O(N) 이상이면 시간 초과 위험
N ≤ 10⁶	O(N) 또는 O(N log N)	빠른 정렬, 누적 합 가능
N ≤ 10⁵	O(N log N) 가능	정렬 알고리즘 활용 가능
N ≤ 5000	O(N²) 가능	완전 탐색, 브루트포스 가능
N ≤ 100	O(N³) 가능	플로이드-워셜, DP 가능
N ≤ 20	O(2ⁿ) 가능	백트래킹, 비트마스킹 가능

✔ 코딩 테스트 문제를 보면 입력 크기(N)를 먼저 확인하고,
✔ 적절한 시간 복잡도를 가진 알고리즘을 선택해야 함.

---

✅ 3. 코딩 테스트에서 시간 초과 방지 방법

🔹 1. O(N) 반복문이 너무 많지 않은지 확인

• 예: N = 10⁹이면 while문을 쓰지 말고 수식으로 해결해야 함.
• ✅ O(1)이나 O(log N) 풀이법을 고려.

🔹 2. 리스트 vs 딕셔너리 사용 비교

• list 탐색 O(N) → 느림
• set & dict 탐색 O(1) → 빠름

if value in my_dict:  # O(1) 연산

🔹 3. 정렬이 필요하면 sorted() 사용 (O(N log N))

• Python sorted()는 Timsort(빠른 정렬) 기반이라 빠름.

🔹 4. 반복문이 3중 이상이면 재귀, DP, 수식으로 해결 가능할지 고민

• ✅ O(N³) → O(N²)으로 최적화 가능할지 확인.

---

✅ 4. 직접 연산 횟수 예측하는 방법

예제 문제:

N = 1,000,000,000 (10⁹), while 반복문을 사용하여 1씩 증가시키며 N까지 도달할 때 걸리는 시간은?

❌ 잘못된 코드 (O(N))

n = 1_000_000_000
count = 0
while count < n:
    count += 1

• 반복문이 10억 번 실행됨 → 시간 초과 (10초 이상 예상).

✅ 수식으로 해결 (O(1))

import math

n = 1_000_000_000
result = math.ceil(n / 1000)  # O(1) 해결

✔ 반복문 없이 O(1) 연산으로 해결 → 즉시 계산 가능! 🚀

---

🚀 결론

✔ 입력 크기(N)를 보고 예상 실행 시간을 미리 예측
✔ 1초 ≈ 1억 번 연산 가능 → 10억이면 무조건 시간 초과 위험
✔ 반복문이 많다면 O(1), O(log N), O(N log N) 해결법 고려
✔ 시간 초과를 방지하려면 반복문 대신 수학적 풀이도 활용해야 함!

📌 이제 코딩 테스트에서 시간 초과를 미리 예측할 수 있습니다! 🎯🔥