통합 요약노트
Ch.1 빅오와 복잡도 분석
O(1), O(n), O(n²) — 효율성을 수치로 말하는 법
이 챕터의 내용
왜 효율성이 중요한가? — 10만 vs 10억
입력 크기(n)가 커질수록 연산 횟수가 어떻게 증가하는지 — 이것이 복잡도 분석의 핵심입니다.
실리콘밸리의 한 스타트업이 서비스를 출시했습니다
유저 100명일 때는 완벽했습니다. 검색도 빠르고, 서버도 안정적이었죠
그런데 유저가 100만 명이 되자 서버가 멈춰버렸습니다
- 알고리즘의 속도는 입력 크기(n)에 따라 극적으로 변한다
- O(n²) → O(n) 최적화가 면접 합격의 핵심
- 면접관은 정확성·효율성·소통력을 본다
Big-O 표기법 — 알고리즘의 성적표
Big-O는 '최악의 경우 연산 횟수가 n에 비례해서 어떻게 증가하는가'를 한마디로 표현합니다.
Big-O는 알고리즘의 성적표입니다
시험에서 점수가 아니라 등급을 매기듯, 알고리즘도 등급이 있습니다
데이터가 아무리 많아도 딱 한 번만 실행
- Big-O = 최악의 경우 연산 증가 차수
- 상수와 낮은 차수 항은 무시
- O(1) < O(log n) < O(n) < O(n²)
로그의 마법 — O(log n)과 이진탐색
매번 반을 버리면 남는 양이 기하급수적으로 줄어듭니다. 이것이 log n의 비밀입니다.
업다운 게임을 해봅시다. 1~100 중 숫자를 맞추세요
50! → '업' → 75! → '다운' → 63! ... 매번 범위가 절반으로 줄어듭니다
n이 2배가 되어도 log n은 1만 증가합니다
- O(log n) = 매번 반을 버리는 알고리즘
- 이진탐색: 10억 개도 30번이면 충분
- 전제: 배열이 정렬되어 있어야 한다
공간 복잡도 — 메모리도 자원이다
대부분의 알고리즘은 시간과 공간 사이에서 트레이드오프를 합니다. 이 균형을 아는 것이 면접의 핵심입니다.
시간 복잡도가 '얼마나 오래 걸리나'라면 공간 복잡도는 '메모리를 얼마나 쓰나'
변수 몇 개만 쓰면 O(1) 새 배열을 만들면 O(n)
중복 탐지 문제로 트레이드오프를 이해합시다
- 공간 복잡도 = 추가 메모리 사용량
- 시간-공간 트레이드오프가 핵심
- 재귀 깊이 = 콜 스택 공간
면접에서 복잡도 분석 말하는 법 — 4단계 프레임워크
4단계 프레임워크: 접근법 → 시간 → 공간 → 최적화 가능성 — 이 순서대로 말하면 됩니다.
면접에서 복잡도를 말할 때는 ATSO 프레임워크를 따르세요
이 순서대로 말하면 구조적으로 소통할 수 있어 면접관에게 좋은 인상을 줍니다
실전 예시로 4단계를 적용해봅시다
- ATSO: Approach → Time → Space → Optimize
- 코딩 전에 접근법부터 설명
- 시간과 공간 복잡도 모두 언급
챕터 1 종합 퀴즈 — Big-O & 복잡도 총정리
실전 면접 수준의 문제들로 자신감을 키워봅시다.
O(3n² + 2n + 100)을 Big-O로 단순화하면?
다음 코드의 시간 복잡도는? for i in range(n): for j in range(n): print(i + j)
100만 개의 정렬된 데이터에서 이진탐색 시 최대 비교 횟수는?
- 알고리즘 효율성이 면접 합격의 핵심
- Big-O: O(1) < O(log n) < O(n) < O(n²)
- 공간 복잡도와 시간-공간 트레이드오프
- ATSO 프레임워크로 구조적 소통
핵심 용어 모음
시간 복잡도
입력 크기(n)에 따른 연산 횟수의 증가 패턴
알고리즘 효율성
같은 결과를 더 적은 연산으로 내는 능력
Big-O
최악의 경우 연산 횟수의 증가 차수를 나타내는 표기법
상수 무시
Big-O는 계수와 낮은 차수 항을 무시한다
O(1)
1번 — 즉시
O(log n)
20번 — 매우 빠름
O(n)
100만 번 — 적절
O(n log n)
2,000만 번 — 보통
O(n²)
1조 번 — 위험
이진탐색
정렬된 배열에서 중간값 비교로 범위를 줄이는 탐색법
n = 1,000
log n ≈ 10
n = 1,000,000
log n ≈ 20
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 코스 시작하기