Ch.1 빅오와 복잡도 분석
면접에서 복잡도 분석 말하는 법 — 4단계 프레임워크
코드를 짜는 건 절반. **설명**이 나머지 절반.
알고리즘을 완벽히 풀었는데 '이 코드의 복잡도가 뭐예요?'라는 질문에 우물쭈물했다면? 아는 것과 말하는 것은 다릅니다.
복잡도를 알아도 면접에서 어떻게 표현해야 할까?
4단계 프레임워크: 접근법 → 시간 → 공간 → 최적화 가능성 — 이 순서대로 말하면 됩니다.
핵심 개념
ATSO 프레임워크
Approach(접근법) → Time(시간) → Space(공간) → Optimize(최적화)
핵심 내용
면접에서 복잡도를 말할 때는 ATSO 프레임워크를 따르세요
이 순서대로 말하면 구조적으로 소통할 수 있어 면접관에게 좋은 인상을 줍니다
실전 예시로 4단계를 적용해봅시다
def find_max(arr):
max_val = arr[0]
for x in arr:
if x > max_val:
max_val = x
return max_valA: 배열을 한 번 순회하며 최댓값을 갱신합니다 T: for 루프가 n번 → O(n) S: 변수 max_val 하나 → O(1) O: 모든 원소를 한 번은 봐야 하므로 O(n)이 최적입니다
면접 단골 문제 Two Sum으로 연습합시다
# Two Sum: 두 수의 합이 target인 인덱스 찾기
def two_sum(nums, target):
seen = {} # {값: 인덱스}
for i, x in enumerate(nums):
comp = target - x
if comp in seen:
return [seen[comp], i]
seen[x] = i
return []A: 해시맵에 값을 저장하며, 보수(target-x)가 존재하는지 O(1)로 확인합니다 T: for 루프 n번, 해시맵 조회 O(1) → 전체 O(n) S: 해시맵에 최대 n개 저장 → O(n) O: 이중 for문(O(n²))에서 해시맵으로 O(n)까지 최적화했습니다
nums = [2, 7, 11, 15], target = 9 한 줄씩 추적합니다
2번째 원소에서 바로 답을 찾았습니다. 해시맵 덕분에 O(1) 조회!
면접에서 자주 하는 3가지 실수를 피하세요
코딩 전에 '접근법을 먼저 설명드리겠습니다'라고 시작하면 프로 느낌!
ATSO 프레임워크에서 'T'는 무엇을 의미하나요?
Two Sum을 해시맵으로 풀 때 시간 복잡도는?
면접에서 복잡도 분석 시 시간과 ___을 모두 말해야 한다
시간과 ___을 모두 분석해야 한다
면접 소통 마스터
핵심 용어
A: Approach
접근법을 한 줄로 설명
T: Time
시간 복잡도와 그 이유
S: Space
공간 복잡도와 그 이유
O: Optimize
더 나은 방법이 있는지 언급
실수 1
복잡도를 말하지 않고 코딩만 함
실수 2
시간만 말하고 공간을 빼먹음
실수 3
'빠릅니다'라고만 하고 Big-O를 안 씀
정리 노트
면접에서 복잡도 분석 말하는 법
ATSO 프레임워크
- A (Approach)
- 접근법을 한 줄로 설명
- T (Time)
- 시간 복잡도 + 이유
- S (Space)
- 공간 복잡도 + 이유
- O (Optimize)
- 더 나은 방법 가능 여부
실수 방지
- 실수 1
- 복잡도를 말하지 않고 코딩만 하지 말 것
- 실수 2
- 시간만 말하고 공간을 빼먹지 말 것
- 실수 3
- '빠릅니다' 대신 Big-O로 표현
코딩 전에 '접근법을 먼저 설명드리겠습니다'로 시작하면 구조적인 인상을 준다!
시각 자료
핵심 정리
- 1ATSO: Approach → Time → Space → Optimize
- 2코딩 전에 접근법부터 설명
- 3시간과 공간 복잡도 모두 언급
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 레슨 시작