Ch.1 빅오와 복잡도 분석
왜 효율성이 중요한가? — 10만 vs 10억
코드 한 줄이 서버를 멈춘다?
10만 건의 데이터에서는 1초 만에 끝나던 프로그램이, 10억 건이 되자 3일이 걸렸습니다. 대체 무슨 일이 벌어진 걸까요?
같은 코드인데 왜 데이터가 커지면 급격히 느려질까?
입력 크기(n)가 커질수록 연산 횟수가 어떻게 증가하는지 — 이것이 복잡도 분석의 핵심입니다.
핵심 개념
시간 복잡도
입력 크기(n)에 따른 연산 횟수의 증가 패턴
알고리즘 효율성
같은 결과를 더 적은 연산으로 내는 능력
핵심 내용
실리콘밸리의 한 스타트업이 서비스를 출시했습니다
유저 100명일 때는 완벽했습니다. 검색도 빠르고, 서버도 안정적이었죠
그런데 유저가 100만 명이 되자 서버가 멈춰버렸습니다
원인은 코드 버그가 아니었습니다. 알고리즘의 효율성 문제였습니다
데이터 크기에 따른 처리 시간을 비교해봅시다
O(n) 알고리즘 — 10만 → 0.1초 / 10억 → 1,000초 (17분) O(n²) 알고리즘 — 10만 → 3시간 / 10억 → 317년
n이 10,000배 커지면 O(n)은 10,000배, O(n²)은 1억 배 느려집니다
같은 문제를 푸는 두 가지 코드를 비교합니다
# 느린 방법: O(n²) — 중복 확인
def has_duplicate_slow(arr):
for i in range(len(arr)):
for j in range(i + 1, len(arr)):
if arr[i] == arr[j]:
return True
return False# 빠른 방법: O(n) — set 활용
def has_duplicate_fast(arr):
seen = set()
for x in arr:
if x in seen:
return True
seen.add(x)
return False두 코드 모두 정답을 줍니다. 하지만 n=100만일 때 하나는 0.1초, 하나는 3시간입니다
O(n²) 알고리즘이 왜 느린지 한 줄씩 따라가봅시다
4개 원소에 6번 비교했습니다. n개면 약 n²/2번 비교합니다
면접관이 진짜 보는 것은 동작하는 코드가 아닙니다
면접관이 보는 3가지: 1. 정확성 — 올바른 답을 내는가 2. 효율성 — 최적의 시간/공간 복잡도인가 3. 소통력 — 복잡도를 설명할 수 있는가
면접에서 O(n²) 풀이만 내면 불합격, O(n)으로 최적화하면 합격입니다
n개의 데이터에서 중복을 찾을 때, set을 활용하면 시간 복잡도는?
O(n²) 알고리즘은 데이터가 10배 커지면 100배 느려진다
효율성의 세계
핵심 용어
시간 복잡도
입력 크기(n)에 따른 연산 횟수의 증가 패턴
알고리즘 효율성
같은 결과를 더 적은 연산으로 내는 능력
정리 노트
왜 효율성이 중요한가?
핵심 개념
- 시간 복잡도
- 입력 크기(n)에 따른 연산 횟수의 증가 패턴
- O(n)
- n이 10배 → 시간도 10배
- O(n²)
- n이 10배 → 시간이 100배
실전 팁
- 중복 탐지
- 이중 for문(O(n²)) 대신 set 활용(O(n))
- 면접 포인트
- 정확성 + 효율성 + 소통력
면접에서는 '동작하는 코드'가 아니라 '효율적인 코드'가 합격 기준!
시각 자료
핵심 정리
- 1알고리즘의 속도는 입력 크기(n)에 따라 극적으로 변한다
- 2O(n²) → O(n) 최적화가 면접 합격의 핵심
- 3면접관은 정확성·효율성·소통력을 본다
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 레슨 시작