빅오 표기법 쉽게 이해하기: 코딩테스트 시간복잡도 기초

코딩테스트에서 "시간 초과"가 뜨는 건 대부분 시간복잡도를 잘못 잡았기 때문입니다. 빅오 표기법은 입력이 커질 때 연산량이 얼마나 빨리 늘어나는지를 나타냅니다.

핵심 직관

빅오는 "정확한 횟수"가 아니라 증가 추세입니다. 입력 n이 10배 커지면 연산이 얼마나 늘어나는가?

복잡도	이름	n=1,000일 때 대략
O(1)	상수	1
O(log n)	로그	약 10
O(n)	선형	1,000
O(n log n)	선형로그	약 10,000
O(n²)	제곱	1,000,000

코드로 보는 복잡도

// O(1): 입력 크기와 무관
arr[0];

// O(n): 한 번 순회
for (const x of arr) sum += x;

// O(n²): 이중 반복 (주의!)
for (const a of arr)
  for (const b of arr)
    check(a, b);

// O(log n): 매번 절반으로 줄임 (이진 탐색)
while (lo <= hi) { const mid = (lo+hi)>>1; ... }

코딩테스트 감각: n 보고 복잡도 정하기

문제의 입력 크기를 보면 허용 복잡도를 역산할 수 있습니다(약 1초 = 1억 연산 기준).

• n ≤ 1,000,000 → O(n) 또는 O(n log n)
• n ≤ 100,000 → O(n log n)
• n ≤ 10,000 → O(n²)도 가능
• n ≤ 500 → O(n³)까지 가능

n이 10만인데 O(n²)을 쓰면 100억 연산 → 시간 초과입니다. 이때는 정렬·해시·투포인터로 줄여야 합니다.

자주 하는 실수

• 배열에 includes/indexOf를 반복 호출 → 내부가 O(n)이라 전체 O(n²). Set/Map으로 O(1) 조회
• 문자열을 +=로 반복 연결 → 비효율. 배열에 모아 join

마무리 체크리스트

• 빅오는 증가 추세, 상수는 무시
• 이중 반복은 O(n²) 경고등
• 입력 n으로 허용 복잡도 역산
• 반복 조회는 Set/Map으로 O(1)

복잡도 감각만 잡혀도 "시간 초과"의 절반은 예방됩니다.