코딩 면접 풀이 전략 안내서 · 4/6

복잡도 설명과 트레이드오프

면접에서 복잡도는 계산만 맞으면 되는 것이 아니라 말로 설명할 수 있어야 합니다. "O(n)입니다"라는 한마디보다 "n이 무엇이고, 어떤 연산이 몇 번 일어나서 그렇다"는 설명이 훨씬 설득력 있습니다. 이 장에서는 복잡도를 소리 내어 설명하는 방법, 입력 크기로 목표 복잡도를 가늠하는 법, 풀이 사이의 트레이드오프를 다룹니다.

소리 내어 설명하는 순서

복잡도를 말할 때는 다음 세 가지를 차례로 밝힙니다.

변수 정의: "n은 배열 길이, m은 질의 개수입니다"처럼 무엇을 기준으로 세는지 먼저 말합니다.
지배적인 연산: "바깥 반복이 n번, 안에서 해시 맵 조회가 평균 O(1)입니다"처럼 가장 많이 일어나는 일을 짚습니다.
공간: 입력을 제외한 추가 메모리를 말합니다. 재귀라면 호출 스택 깊이도 포함합니다.

예를 들어 앞 장의 중복 없는 가장 긴 구간 풀이는 이렇게 설명합니다. "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)이지만 최악에는 충돌 때문에 느려질 수 있다는 점도 함께 언급하면 정확합니다.

반복문이 겹쳐도 O(n)인 경우

슬라이딩 윈도우는 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 이하

Python에서 숨은 비용

복잡도 분석이 맞아도 언어의 연산 비용을 잘못 알면 느린 코드가 됩니다. 다음은 자주 틀리는 예입니다.

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)

정리

복잡도는 변수 정의, 지배적인 연산, 추가 공간 순서로 말합니다. 제약 조건에서 목표 복잡도를 거꾸로 추정하면 어떤 패턴을 써야 할지 빨리 좁힐 수 있습니다. 같은 문제에도 시간과 공간을 맞바꾸는 여러 풀이가 있으므로, 하나를 고른 이유와 다른 선택지를 함께 설명할 수 있어야 합니다.

이 장에 대해 질문이 있나요?