Table of Contents

코딩 테스트 시간복잡도, 비전공자도 이번엔 진짜 이해했어요

코딩 테스트 문제 풀다가 분명히 정답인데 “시간 초과” 뜬 경험 있으신가요?

저 처음에 진짜 멘탈 나갔어요. 로직은 맞고, 출력값도 맞는데 왜 틀리냐고요. 알고 보니 시간복잡도 문제였더라고요. 근데 그때 저는 시간복잡도가 뭔지도 제대로 몰랐어요. “코드가 빨리 돌아가야 한다” 정도만 알았지, 왜 내 코드가 느린지는 전혀 감이 없었죠.

비전공자 취준생으로서 시간복잡도를 이해하는 데 꽤 시간이 걸렸는데, 지금은 문제 데이터 크기만 봐도 어떤 알고리즘을 써야 할지 역추적이 될 정도가 됐어요. 오늘은 그 과정에서 진짜 도움 됐던 것들만 정리해볼게요.

시간복잡도가 대체 뭔데요?

결론부터 말하면, 시간복잡도는 “코드가 몇 초 걸리냐”가 아니라 “데이터가 늘어날 때 얼마나 급격히 느려지냐” 예요.

처음엔 저도 “그냥 빠른 컴퓨터 쓰면 되는 거 아냐?”라고 생각했어요. 근데 그게 아니더라고요. 코딩 테스트 채점 서버는 보통 1초에 약 1억 번 연산을 처리할 수 있어요. 데이터가 10만 개인데 2중 for문을 돌리면, 최악의 경우 10만 × 10만 = 100억 번 연산이에요. 아무리 빠른 서버도 이건 감당이 안 되죠.

여기서 핵심 개념이 나와요. 데이터 개수를 N이라고 했을 때, 내 코드가 N이 커질수록 얼마나 느려지는지를 표현하는 게 바로 시간복잡도예요.

한 줄 정리: 시간복잡도는 “데이터가 많아질수록 내 코드가 얼마나 버텨주냐”를 보는 지표예요.

빅오 표기법, 복사기로 이해했어요

빅오(Big-O) 표기법이라고 하면 괜히 어렵게 느껴지죠. 저도 그랬어요. 근데 복사기 비유로 이해하니까 바로 됐어요.

회사에서 문서를 복사한다고 생각해볼게요.

O(1): 디지털 파일 전송. 문서가 1장이든 1000장이든 클릭 한 번으로 끝. 데이터 크기에 상관없이 항상 같은 시간.
O(N): 일반 복사기. 문서가 100장이면 100번, 1000장이면 1000번. 데이터가 늘어난 만큼 시간도 늘어나요.
O(N²): 복사본을 또 복사하는 상황. 100장을 복사하는데, 그 복사본 각각을 또 100번씩 복사. 100장이 10,000번 작업이 돼버려요.
O(N log N): 복사하기 전에 문서를 절반씩 나눠서 정리하고 복사. O(N²)보단 훨씬 효율적이에요.

코딩 테스트에서 자주 만나는 건 이 네 가지예요. 이것만 감 잡아도 절반은 된 거예요.

한 줄 정리: 빅오 표기법은 데이터가 N배 늘었을 때 연산이 얼마나 늘어나는지를 표현하는 방식이에요.

N 크기 보고 알고리즘 역추적하는 법

이게 실전에서 진짜 유용했어요. 문제에서 데이터 크기 N을 보면, 쓸 수 있는 알고리즘이 역으로 좁혀지거든요.

데이터 크기 (N)	허용되는 시간복잡도	대표 알고리즘
N ≤ 10	O(N!)	완전 탐색, 순열
N ≤ 100	O(N³)	3중 반복문
N ≤ 10,000	O(N²)	2중 반복문
N ≤ 100,000	O(N log N)	정렬, 힙
N ≤ 1,000,000	O(N)	해시, 투포인터

저는 이걸 외우고 나서부터 문제 접근이 달라졌어요. N이 10만이면 2중 for문은 무조건 아니구나, 이게 바로 보이는 거예요.

예를 들어 N = 100,000이면 O(N²)은 100억 번 연산이라 시간 초과가 나요. O(N log N)으로 줄여야 통과할 수 있어요. 문제 풀기 전에 N 확인하는 습관, 진짜 중요해요.

한 줄 정리: N 크기 → 허용 시간복잡도 → 알고리즘 선택, 이 순서로 역추적하세요.

파이썬 코딩 테스트에서 저 낚였던 함정

비전공자 파이썬 유저라면 꼭 알아야 하는 게 있어요. 저 이거 모르고 한동안 계속 시간 초과 맞았거든요.

바로 숨겨진 반복문 문제예요.

my_list = [1, 2, 3, ..., 100000]
  
  if x in my_list:  # 이게 O(N)이에요!
      print("있음")

in 연산자가 리스트에 쓰이면, 파이썬은 앞에서부터 하나씩 다 확인해요. 코드 딱 한 줄인데 O(N)이 숨어있는 거예요. 이걸 반복문 안에서 쓰면 O(N²)이 되는 거죠.

해결법은 간단해요. set이나 dict으로 바꾸면 O(1)이 돼요.

my_set = {1, 2, 3, ..., 100000}  # set으로 변환

  if x in my_set:  # 이건 O(1)이에요!
      print("있음")

set은 내부적으로 해시 테이블 구조라서, 데이터가 몇 개든 찾는 속도가 일정해요. 코드 한 줄 차이인데 성능이 완전히 달라지더라고요.

# 시간 초과 나는 코드
  for i in range(n):
      if target in my_list:  # O(N) × O(N) = O(N²)
          ...
          
  # 통과하는 코드
  my_set = set(my_list)  # 한 번만 변환
  for i in range(n):
      if target in my_set:  # O(1) × O(N) = O(N)
          ...

여러분도 이런 경험 있으시죠? 분명히 로직은 맞는데 시간 초과 뜨는 거요. 한 번쯤 in 연산자가 어디 쓰였는지 확인해보세요.

한 줄 정리: 리스트의 in은 O(N), set/dict의 in은 O(1). 이 차이가 코딩 테스트 합불을 가릅니다.

시간복잡도 공부, 어떻게 시작하면 좋을까요?

저는 이 순서로 공부했어요.

1단계: O(1), O(N), O(N²), O(N log N) 개념만 먼저 확실히 잡기. 이 네 가지가 90% 이상이에요.

2단계: 백준이나 프로그래머스에서 이미 풀었던 문제를 다시 보면서, 내 코드의 시간복잡도를 직접 분석해보기. “이 반복문이 몇 번 도는 거지?” 이 질문 습관이 중요해요.

3단계: N 크기 보고 알고리즘 역추적하는 표 외우기. 처음엔 표 보면서 풀어도 괜찮아요.

솔직히 처음엔 막막했어요. 비전공자라서 CS 기초가 없으니까 용어 하나 이해하는 데도 시간이 두 배로 걸렸거든요. 근데 복사기 비유처럼 일상 언어로 먼저 이해하고, 그 다음에 코드로 확인하는 방식으로 하니까 훨씬 빨리 잡혔어요.

한 줄 정리: 개념 → 내 코드 분석 → 역추적 표 활용, 이 순서로 3주만 하면 감 잡혀요.

마무리하면서

시간복잡도는 코딩 테스트에서 “왜 틀렸지?”의 절반을 설명해주는 개념이에요.

비전공자라서 어렵게 느껴지는 건 당연해요. 저도 그랬으니까요. 근데 핵심만 알면 생각보다 빨리 쓸 수 있어요. 데이터가 많아질 때 내 코드가 얼마나 버텨주는가, 이 질문 하나만 머릿속에 들고 다니세요.

빅오 표기법 완전 정복, 비전공자도 3주면 쓸 수 있어요