"1억 번"의 법칙? 코딩 테스트에서 시간 복잡도를 읽는 눈을 키우자

 

 

 

코딩 테스트를 풀다 보면 자주 마주치는 고민이 있다.
“이 코드, 시간 안에 돌아갈까?”

 

문제의 난이도는 종종 입력의 크기(N)와 제한 시간(보통 1~5초)에 따라 결정되는데,
이를 가늠할 줄 아는 능력은 실력의 기준선이 된다.

 

이번 글에서는 코딩 테스트에서 반드시 알고 있어야 할
시간 제한 기준과 시간 복잡도 판단법을 정리해본다.

 

 

 

---

🚦 시간 제한 1초 = 약 1억 번 연산 가능

코딩 테스트 환경은 보통 아래 기준으로 설계된다.

• 제한 시간: 1~5초
• 1초에 약 1억 번 연산 가능 (기준 CPU 성능 가정)

즉, 입력 크기 N이 주어졌을 때,
내가 짜려는 알고리즘이 몇 번 연산을 수행할지 미리 감을 잡아야 한다.

 

 

 

 

---

⏱️ 시간 복잡도별 연산 가능 횟수

시간 복잡도	1초 기준 연산량	설명
O(N)	약 1억 번	선형 탐색, 단순 순회
O(N²)	약 10,000 번	이중 루프
O(N³)	약 500 번	3중 루프
O(2^N)	약 20 번	완전탐색, DFS 등
O(N!)	약 10 번	순열/조합 전수 탐색

 

 

 

 

---

📌 N의 크기에 따른 전략

입력 크기 N만 잘 봐도, 시간 복잡도를 예측할 수 있다.

N의 최대값	선택 가능한 시간 복잡도
500	O(N³) 이하
2,000	O(N²) 이하
100,000	O(N log N) 이하
10,000,000	O(N) 이하
10,000,000,000	O(log N) 이하

예: N이 100,000인데 내가 짜는 알고리즘이 O(N²)?
→ 100,000² = 100억 번 → 1초 안에 절대 안 돌아감!

---

⚙️ 실전에서 자주 만나는 시간 복잡도들

연산 또는 함수	시간 복잡도	설명
for loop	O(N)	단순 순회
이중 for loop	O(N²)	완전 탐색
array.contains()	O(N)	배열 탐색
set.contains()	O(1)	해시 기반 탐색
dictionary[key]	O(1)	키-값 조회
sort() (Swift)	O(N log N)	퀵정렬 기반
binary search	O(log N)	정렬 배열 탐색
heap.pop()	O(log N)	우선순위 큐
queue.pop() / stack.pop()	O(1)	선형 자료구조

 

 

 

---

🔍 탐색은 Set 또는 Dictionary로 최적화하자

가장 자주 만나는 실수 중 하나는

array.contains(x)

를 여러 번 돌리는 것. 이건 매번 O(n)이기 때문에,
데이터가 많고 반복 탐색이 필요하다면 느릴 수밖에 없다.

 

 

해결 방법

배열을 처음에 한 번 Set 또는 Dictionary로 변환하고,
이후 탐색은 O(1)로 빠르게 처리한다.

let arr = [1, 2, 3, 4, 5]
let set = Set(arr)

set.contains(3) // O(1)

 

 

 

 

 

---

시간 복잡도를 읽는 눈이 실력을 만든다

• 문제를 보면 먼저 N의 크기를 확인하자.
• 그다음 시간 복잡도를 예측해서, 어떤 방식이 살아남을지 판단한다.
• Set, Dictionary, 정렬, 이진 탐색, 힙 등
  자료구조와 알고리즘 조합으로 성능을 끌어올리는 건 실전에서 큰 차이를 만든다.

---

 

 

🧠 “코드는 맞는데 시간 초과”라는 문장을 줄이고 싶다면?

이 글을 북마크하고 자주 복습하자.

 

 

📌 다음 글에서는 알고리즘별 시간 복잡도 계산법과 예제들을 더 정리해볼게요.
궁금한 주제가 있다면 댓글로 남겨줘요!