모바일앱/알고리즘

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

GeekCode 2025. 3. 29. 20:34
반응형

 

 

 

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

 

문제의 난이도는 종종 입력의 크기(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, 정렬, 이진 탐색, 힙 등
    자료구조와 알고리즘 조합으로 성능을 끌어올리는 건 실전에서 큰 차이를 만든다.

 

 

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

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

 

 


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

 

 

 

 

반응형
저작자표시