코딩 면접 풀이 전략 안내서 · 4/6
면접에서 복잡도는 계산만 맞으면 되는 것이 아니라 말로 설명할 수 있어야 합니다. "O(n)입니다"라는 한마디보다 "n이 무엇이고, 어떤 연산이 몇 번 일어나서 그렇다"는 설명이 훨씬 설득력 있습니다. 이 장에서는 복잡도를 소리 내어 설명하는 방법, 입력 크기로 목표 복잡도를 가늠하는 법, 풀이 사이의 트레이드오프를 다룹니다.
복잡도를 말할 때는 다음 세 가지를 차례로 밝힙니다.
예를 들어 앞 장의 중복 없는 가장 긴 구간 풀이는 이렇게 설명합니다. "n은 문자열 길이입니다. right는 n번 움직이고, left는 앞으로만 움직이므로 전체 이동도 n번 이하입니다. 각 단계의 딕셔너리 조회와 갱신은 평균 O(1)이므로 시간은 O(n)입니다. 딕셔너리에는 서로 다른 문자만 들어가므로 공간은 O(min(n, σ))입니다."
제약 조건은 출제자가 기대하는 복잡도를 알려 주는 힌트입니다. 컴파일 언어는 1초에 대략 10⁸번 안팎의 단순 연산을, Python은 그보다 수십 배 적은 연산을 처리한다고 보면 어림잡기 좋습니다. 정확한 수치는 환경마다 다르므로 자릿수만 참고합니다.
| n의 크기 | 대체로 통하는 복잡도 | 떠올릴 방법 |
|---|---|---|
| 10 안팎 | O(n!) | 순열 백트래킹 |
| 20 안팎 | O(2ⁿ) | 부분 집합, 비트마스크 |
| 500 안팎 | O(n³) | 3중 반복, 구간 동적 계획법 |
| 5,000 안팎 | O(n²) | 2중 반복, 2차원 동적 계획법 |
| 10⁵ ~ 10⁶ | O(n log n), O(n) | 정렬, 힙, 투 포인터, 해시 맵 |
| 그보다 큼 | O(log n), O(1) | 이분 탐색, 수식 |
"배열에 합이 target인 두 수가 있는가"를 세 가지로 풀어 보고 비교합니다.
def has_pair_brute(nums: list[int], target: int) -> bool:
# O(n²) 시간, O(1) 추가 공간
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return True
return False
def has_pair_sorted(nums: list[int], target: int) -> bool:
# O(n log n) 시간, 정렬 사본 O(n) 공간(제자리 정렬이면 추가 공간이 거의 없다)
arr = sorted(nums)
lo, hi = 0, len(arr) - 1
while lo < hi:
total = arr[lo] + arr[hi]
if total == target:
return True
lo, hi = (lo + 1, hi) if total < target else (lo, hi - 1)
return False
def has_pair_hash(nums: list[int], target: int) -> bool:
# O(n) 평균 시간, O(n) 공간
seen: set[int] = set()
for x in nums:
if target - x in seen:
return True
seen.add(x)
return False
for f in (has_pair_brute, has_pair_sorted, has_pair_hash):
print(f.__name__, f([4, 7, 1, 9], 10), f([4, 7, 1, 9], 2))| 풀이 | 시간 | 추가 공간 | 원래 인덱스 유지 | 이런 때 고른다 |
|---|---|---|---|---|
| 2중 반복 | O(n²) | O(1) | 예 | n이 아주 작거나 정답 확인용 |
| 정렬 + 투 포인터 | O(n log n) | O(1) ~ O(n) | 아니요 | 메모리가 빠듯하거나 이미 정렬됨 |
| 해시 집합 | 평균 O(n) | O(n) | 예(맵을 쓰면) | 가장 빠른 평균 시간이 필요할 때 |
면접관이 "메모리를 O(1)로 줄일 수 있나요?"라고 물으면, 해시 집합에서 정렬 + 투 포인터로 바꾸는 트레이드오프를 설명하면 됩니다. 해시 테이블은 평균 O(1)이지만 최악에는 충돌 때문에 느려질 수 있다는 점도 함께 언급하면 정확합니다.
슬라이딩 윈도우는 for 안에 while이 있어 O(n²)처럼 보이지만, 안쪽 while이 움직이는 left는 전체 실행 동안 최대 n번만 증가합니다. 이렇게 전체 작업량을 합산해 평균을 내는 방법을 분할 상환 분석이라고 합니다. 직접 세어 보면 분명해집니다.
def count_moves(nums: list[int], target: int) -> tuple[int, int]:
left = total = 0
right_moves = left_moves = 0
for value in nums:
right_moves += 1
total += value
while total >= target:
total -= nums[left]
left += 1
left_moves += 1
return right_moves, left_moves
print(count_moves([1] * 1000, 3)) # (1000, 998): 두 포인터 합쳐 2n 이하복잡도 분석이 맞아도 언어의 연산 비용을 잘못 알면 느린 코드가 됩니다. 다음은 자주 틀리는 예입니다.
from collections import deque
items = list(range(10))
# list.pop(0)은 뒤의 원소를 모두 당기므로 O(n)이다
queue = deque(items)
first = queue.popleft() # deque는 양 끝 연산이 O(1)
# 리스트에서 in은 O(n), 집합에서 in은 평균 O(1)
lookup = set(items)
print(7 in lookup)
# 슬라이싱은 길이만큼 복사한다: nums[i:j]는 O(j - i)
window_sum = sum(items[2:5])
# 문자열을 반복해서 +=로 붙이면 느려질 수 있으니 join을 쓴다
text = "".join(str(x) for x in items)
print(first, window_sum, text)복잡도는 변수 정의, 지배적인 연산, 추가 공간 순서로 말합니다. 제약 조건에서 목표 복잡도를 거꾸로 추정하면 어떤 패턴을 써야 할지 빨리 좁힐 수 있습니다. 같은 문제에도 시간과 공간을 맞바꾸는 여러 풀이가 있으므로, 하나를 고른 이유와 다른 선택지를 함께 설명할 수 있어야 합니다.
댓글 0개
로그인 · 로그인하면 댓글을 남길 수 있습니다.