시간 복잡도와 공간 복잡도 감각 만들기

문제를 풀기 전에 먼저 해야 할 질문

코딩 테스트에서 실력이 빨리 느는 사람은 문제를 읽자마자 코드를 쓰지 않습니다. 대신 아주 짧은 시간 동안 이런 질문을 던집니다.

"입력 크기가 얼마지?"

이 질문 하나가 풀이의 방향을 크게 바꿉니다. N이 20인 문제와 N이 100,000인 문제는 전혀 다른 문제입니다. 겉으로는 둘 다 "모든 경우를 확인하라"처럼 보일 수 있지만, 하나는 완전 탐색으로 충분하고 다른 하나는 정렬, 해시, 이분 탐색, 그리디, 동적 계획법 같은 더 효율적인 도구가 필요합니다.

시간 복잡도와 공간 복잡도는 어렵게 들리지만, 본질은 단순합니다. 시간 복잡도는 "입력이 커질 때 코드가 얼마나 더 오래 걸리는가"를 보는 기준이고, 공간 복잡도는 "입력이 커질 때 메모리를 얼마나 더 쓰는가"를 보는 기준입니다.

코딩 테스트에서 복잡도 감각이 생기면 문제를 보자마자 대략 이런 판단이 가능해집니다.

"N이 1,000이면 이중 반복문은 가능하겠네."

"N이 100,000인데 모든 쌍을 보면 안 되겠구나."

"간선 수가 많으니 인접 행렬은 메모리가 터질 수 있겠다."

"정렬 한 번 하고 훑으면 통과하겠다."

이 장의 목표는 복잡도를 수학 공식처럼 외우는 것이 아닙니다. 제한 조건을 보고 가능한 풀이와 불가능한 풀이를 빠르게 거르는 감각을 만드는 것입니다.

빅오 표기법은 '대략적인 증가 속도'다

시간 복잡도를 말할 때 흔히 O(N), O(N²) 같은 표현을 씁니다. 이것을 빅오 표기법이라고 합니다. 빅오 표기법은 코드가 정확히 몇 번 실행되는지를 세는 도구가 아니라, 입력 크기가 커질 때 실행량이 어떤 속도로 증가하는지 표현하는 도구입니다.

예를 들어 다음 코드를 봅시다.

count = 0
for i in range(n):
    count += 1

반복문은 n번 실행됩니다. 그래서 시간 복잡도는 O(N)입니다.

이번에는 다음 코드입니다.

count = 0
for i in range(n):
    for j in range(n):
        count += 1

바깥 반복문이 n번, 안쪽 반복문도 매번 n번 실행됩니다. 전체 실행 횟수는 n × n이므로 O(N²)입니다.

그런데 실제 코드에서는 다음처럼 상수가 붙는 경우도 많습니다.

for i in range(n):
    print(i)

for i in range(n):
    print(i * 2)

이 코드는 총 2N번 정도의 작업을 합니다. 하지만 빅오 표기에서는 보통 상수를 생략해 O(N)이라고 말합니다. 2N이든 5N이든 입력이 커질 때 증가하는 큰 흐름은 여전히 N에 비례하기 때문입니다.

마찬가지로 다음 코드는 N² + N 정도의 작업을 하지만, 가장 큰 영향을 주는 항은 N²이므로 O(N²)이라고 봅니다.

for i in range(n):
    for j in range(n):
        print(i, j)

for i in range(n):
    print(i)

복잡도를 읽을 때 중요한 습관은 "가장 빠르게 커지는 부분이 무엇인가?"를 찾는 것입니다. 작은 입력에서는 N과 N²의 차이가 별것 아닌 것처럼 보이지만, 입력이 커지는 순간 차이는 폭발적으로 벌어집니다.

주요 시간 복잡도의 실제 실행 규모

복잡도 감각을 만들려면 각 복잡도가 실제로 어느 정도의 규모까지 버틸 수 있는지 알아야 합니다. 다음은 자주 만나는 복잡도입니다.

실제 숫자로 보면 차이가 더 선명합니다. N = 100,000이라고 해봅시다.

O(N)과 O(N log N)은 충분히 가능해 보입니다. 하지만 O(N²)은 100억 번입니다. 제한 시간이 1초나 2초라면 거의 불가능합니다.

이번에는 N = 20이라고 해봅시다.

N = 20이면 2ⁿ도 경우에 따라 가능합니다. 그래서 N이 작을 때는 백트래킹, 비트마스크, 완전 탐색이 정답인 경우가 많습니다.

여기서 중요한 결론이 나옵니다. 복잡도의 좋고 나쁨은 문제의 입력 크기와 함께 판단해야 합니다. O(N²)이라고 무조건 나쁜 것도 아니고, O(2ⁿ)이라고 무조건 틀린 것도 아닙니다. N이 얼마인지가 핵심입니다.

제한 시간으로 허용 연산량 추정하기

코딩 테스트에서는 보통 문제에 제한 시간이 주어집니다. 예를 들어 "시간 제한 1초"라고 되어 있으면 우리는 대략적인 허용 연산량을 추정해야 합니다.

많은 코딩 테스트 환경에서 1초에 처리 가능한 단순 연산은 대략 수천만 번에서 1억 번 사이로 생각할 수 있습니다. 다만 언어, 서버 성능, 입출력 방식, 연산 종류에 따라 차이가 큽니다. 파이썬은 C++보다 느린 편이고, 문자열 처리나 해시 충돌, 객체 생성이 많으면 단순 반복보다 훨씬 느려질 수 있습니다.

그래서 실전에서는 보수적으로 생각하는 편이 안전합니다. 특히 파이썬을 기준으로 한다면 1초에 1억 번을 기대하기보다, 수천만 번 이하로 맞추는 것이 좋습니다. 복잡한 연산이 섞여 있다면 그보다 더 낮게 잡아야 합니다.

대략적인 기준은 다음처럼 잡을 수 있습니다.

이 표는 절대적인 법칙이 아니라 출발점입니다. 예를 들어 N = 1,000이고 시간 제한이 0.5초라면 O(N²)도 위험할 수 있습니다. 반대로 N = 2,000이고 시간 제한이 넉넉하며 C++을 사용한다면 간단한 O(N²)이 통과할 수도 있습니다.

문제에서 제한 조건을 보면 먼저 이렇게 생각해보세요.

N = 100,000이고 모든 쌍을 비교해야 한다면 N² = 10,000,000,000입니다. 이때는 "아, 이중 반복문은 아니구나"라고 바로 판단해야 합니다. 그다음에는 정렬해서 인접한 것만 볼 수 있는지, 해시로 빠르게 찾을 수 있는지, 투 포인터로 한 번에 훑을 수 있는지 떠올리면 됩니다.

복잡도 감각은 풀이를 찾는 나침반입니다. "어떤 알고리즘을 써야 할까?"라는 질문 전에 "어느 정도 복잡도까지 허용될까?"를 먼저 계산하면, 가능한 후보가 크게 줄어듭니다.

예제로 보는 판단 과정

문제에서 다음 조건이 주어졌다고 합시다.

1 ≤ N ≤ 100,000
정수 배열 A가 주어진다.
두 수의 합이 X가 되는 쌍의 개수를 구하라.

가장 먼저 떠오르는 풀이는 모든 쌍을 확인하는 방법입니다.

count = 0
for i in range(n):
    for j in range(i + 1, n):
        if a[i] + a[j] == x:
            count += 1

이 코드는 모든 쌍을 확인하므로 O(N²)입니다. N = 100,000이면 약 50억 쌍입니다. 시간 제한이 아무리 넉넉해도 일반적인 코딩 테스트에서는 어렵습니다.

그렇다면 필요한 복잡도는 무엇일까요? N = 100,000이면 O(N log N)이나 O(N) 정도를 노려야 합니다. 여기서 가능한 접근은 두 가지입니다.

정렬 후 투 포인터를 쓰면 O(N log N)에 풀 수 있습니다. 정렬이 O(N log N)이고, 양끝에서 포인터를 움직이며 배열을 한 번 훑는 과정은 O(N)입니다.

해시를 쓰면 평균적으로 O(N)에 풀 수도 있습니다. 각 숫자 v를 보면서 x - v가 이전에 나왔는지 확인하면 됩니다.

이처럼 제한 조건을 먼저 보면 풀이 후보가 정리됩니다. "이중 반복문으로 될까?"를 오래 고민하지 않아도 됩니다. 숫자가 이미 답을 말해주고 있기 때문입니다.

중첩 반복문의 복잡도 읽기

복잡도를 읽을 때 가장 자주 만나는 형태는 반복문입니다. 단일 반복문은 보통 O(N)입니다.

for i in range(n):
    do_something()

반복문이 두 개 중첩되어 있고 둘 다 n에 비례하면 O(N²)입니다.

for i in range(n):
    for j in range(n):
        do_something()

하지만 반복문이 중첩되어 있다고 해서 언제나 O(N²)인 것은 아닙니다. 다음 코드를 봅시다.

for i in range(n):
    for j in range(3):
        do_something()

안쪽 반복문은 항상 3번만 실행됩니다. 전체 실행 횟수는 3N이므로 O(N)입니다. 상수는 생략하기 때문입니다.

또 다른 예를 보겠습니다.

for i in range(n):
    for j in range(i + 1, n):
        do_something()

겉보기에는 안쪽 반복 횟수가 매번 다릅니다. 첫 번째는 N - 1번, 두 번째는 N - 2번, 마지막은 거의 0번입니다. 전체 횟수는 대략 N(N - 1) / 2입니다. 최고차항은 N²이므로 O(N²)입니다.

이번에는 조금 다른 형태입니다.

for i in range(n):
    j = 1
    while j < n:
        j *= 2

바깥 반복문은 N번입니다. 안쪽 반복문은 j가 1, 2, 4, 8처럼 두 배씩 커집니다. N에 도달하기까지 약 log N번 실행됩니다. 따라서 전체 시간 복잡도는 O(N log N)입니다.

여기서 중요한 관찰은 "반복 변수가 어떻게 변하는가"입니다. 1씩 증가하면 보통 선형이고, 2배씩 증가하거나 절반씩 줄어들면 로그가 등장합니다.

재귀 코드에서 복잡도 읽기

재귀는 초보자에게 복잡도 계산이 가장 헷갈리는 영역입니다. 하지만 핵심은 반복문과 같습니다. "함수가 몇 번 호출되는가?"와 "각 호출에서 얼마나 일하는가?"를 보면 됩니다.

가장 단순한 재귀부터 보겠습니다.

def countdown(n):
    if n == 0:
        return
    countdown(n - 1)

n, n - 1, n - 2처럼 하나씩 줄어들며 호출되므로 총 N번 정도 호출됩니다. 각 호출에서 하는 일이 상수라면 시간 복잡도는 O(N)입니다.

이번에는 매번 절반으로 줄어드는 재귀입니다.

def divide(n):
    if n == 1:
        return
    divide(n // 2)

N이 절반씩 줄어드므로 호출 횟수는 O(log N)입니다.

그렇다면 다음 코드는 어떨까요?

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

이 재귀는 하나의 호출이 다시 두 개의 호출을 만듭니다. 그리고 그 호출들이 또 여러 호출을 만듭니다. 같은 값이 반복해서 계산되기 때문에 호출 수가 매우 빠르게 증가합니다. 정확한 분석은 더 깊게 들어갈 수 있지만, 코딩 테스트 관점에서는 지수 시간에 가까운 매우 비효율적인 재귀라고 이해하면 충분합니다.

이런 코드를 보면 "중복 계산이 많다"는 신호를 잡아야 합니다. 이후 동적 계획법을 배울 때 이 문제를 다시 만나게 됩니다. 한 번 계산한 값을 저장하면 지수 시간에 가까운 풀이를 O(N)으로 줄일 수 있습니다.

재귀 복잡도를 볼 때는 다음 질문을 던지면 좋습니다.

"한 번 호출하면 다음 호출이 몇 개 생기는가?"

"문제 크기는 얼마나 줄어드는가?"

"같은 상태를 반복해서 계산하고 있지는 않은가?"

이 세 질문만으로도 많은 재귀 문제의 시간 복잡도를 대략 판단할 수 있습니다.

정렬과 탐색의 복잡도 감각

코딩 테스트에서 정렬은 매우 강력한 도구입니다. 정렬을 하면 데이터의 순서가 생기고, 순서가 생기면 탐색과 비교가 쉬워집니다.

일반적으로 파이썬의 sort()나 sorted() 같은 내장 정렬은 O(N log N)으로 생각하면 됩니다. N = 100,000 정도라면 대부분의 상황에서 충분히 사용할 수 있습니다. 그래서 문제를 보고 O(N²)이 안 될 것 같을 때, 정렬 후 한 번 훑는 방식으로 바꿀 수 있는지 생각해보는 습관이 중요합니다.

예를 들어 두 수의 차이가 가장 작은 쌍을 찾아야 한다고 합시다. 모든 쌍을 비교하면 O(N²)입니다. 하지만 배열을 정렬하면 차이가 가장 작은 두 수는 정렬된 배열에서 서로 이웃해 있을 가능성이 있습니다. 따라서 정렬 후 인접한 원소만 비교하면 됩니다. 전체 복잡도는 O(N log N)입니다.

탐색도 마찬가지입니다. 배열에서 특정 값을 찾는 단순 탐색은 O(N)입니다.

for x in arr:
    if x == target:
        return True

하지만 정렬된 배열이라면 이분 탐색을 사용할 수 있습니다. 이분 탐색은 탐색 범위를 매번 절반으로 줄이므로 O(log N)입니다.

left, right = 0, n - 1
while left <= right:
    mid = (left + right) // 2
    if arr[mid] == target:
        return True
    elif arr[mid] < target:
        left = mid + 1
    else:
        right = mid - 1

N = 1,000,000이어도 log₂N은 약 20 정도입니다. 백만 개 중에서 찾는데 20번 정도의 비교로 충분하다는 뜻입니다. 이분 탐색이 강력한 이유가 여기에 있습니다.

다만 이분 탐색은 아무 배열에나 쓸 수 없습니다. 보통 데이터가 정렬되어 있거나, 답의 후보 범위에서 "가능하다/불가능하다"가 한 방향으로 바뀌는 구조가 있어야 합니다. 이 부분은 탐색을 다루는 장에서 더 자세히 살펴보겠습니다.

공간 복잡도는 메모리 사용량의 증가 속도다

시간만큼 중요한 것이 메모리입니다. 공간 복잡도는 입력 크기가 커질 때 추가로 필요한 메모리가 얼마나 늘어나는지 나타냅니다.

예를 들어 배열의 합을 구하는 코드를 봅시다.

total = 0
for x in arr:
    total += x

입력 배열 arr은 이미 주어졌다고 보고, 추가로 사용하는 변수는 total 하나입니다. 이 경우 추가 공간은 O(1)입니다.

반면 다음 코드는 같은 크기의 배열을 하나 더 만듭니다.

b = []
for x in arr:
    b.append(x * 2)

입력 크기 N에 비례하는 새 배열을 만들었으므로 추가 공간은 O(N)입니다.

많은 초보자는 시간 복잡도만 신경 쓰다가 메모리 제한에서 실패합니다. 특히 그래프 문제, 큰 2차원 배열, 해시를 많이 쓰는 문제에서 이런 일이 자주 생깁니다.

메모리 제한을 숫자로 읽는 법

메모리 제한이 128MB라고 합시다. 128MB는 대략 1억 3천만 바이트입니다. 만약 정수 하나를 4바이트로 저장하는 언어라면 단순 계산으로 약 3천만 개 정도의 정수를 담을 수 있습니다. 하지만 실제 프로그램에서는 배열 관리 비용, 객체 비용, 기타 변수, 런타임 메모리도 필요합니다. 특히 파이썬의 정수 객체와 리스트는 훨씬 많은 메모리를 사용하므로 훨씬 보수적으로 잡아야 합니다.

예를 들어 N = 100,000, M = 100,000 정도의 그래프를 저장한다고 합시다. 이때 정점 간 연결 정보를 저장하는 방법은 크게 두 가지가 있습니다.

인접 행렬은 N × N 크기의 2차원 배열을 만듭니다. 두 정점 u, v가 연결되어 있는지 O(1)에 확인할 수 있지만, 메모리가 O(N²)입니다. N = 100,000이면 말 그대로 불가능합니다.

인접 리스트는 각 정점마다 연결된 정점만 저장합니다. 메모리는 보통 O(N + M)입니다. 간선 수 M이 100,000이라면 훨씬 현실적입니다.

그래서 그래프 문제에서 N이 크고 간선 수가 상대적으로 적으면 인접 리스트를 먼저 생각해야 합니다. 반대로 N이 작고 두 정점의 연결 여부를 매우 자주 확인해야 한다면 인접 행렬이 유리할 수 있습니다.

배열, 해시, 그래프 저장 방식 선택하기

자료구조 선택은 시간과 공간을 함께 고려해야 합니다.

배열은 순서가 있고 인덱스로 빠르게 접근할 수 있습니다. arr[i]처럼 위치를 알고 접근하면 O(1)입니다. 하지만 어떤 값이 배열 안에 있는지 찾으려면 보통 처음부터 훑어야 하므로 O(N)입니다.

해시는 값의 존재 여부를 빠르게 확인할 때 강력합니다. 파이썬의 set, dict는 평균적으로 삽입, 삭제, 조회가 O(1)입니다. 그래서 "이 값이 이미 나왔는가?", "이 이름의 개수는 몇 개인가?" 같은 문제에 자주 사용합니다. 다만 해시는 내부적으로 여유 공간을 두고 저장하기 때문에 배열보다 메모리를 더 많이 쓰는 편입니다.

그래프는 저장 방식에 따라 성능이 크게 달라집니다. 정점 수가 작으면 인접 행렬이 단순하고 빠를 수 있습니다. 하지만 정점 수가 크고 간선이 드문 그래프라면 인접 리스트가 거의 필수입니다.

예를 들어 정점이 10,000개이고 간선이 20,000개인 그래프가 있다고 합시다. 인접 행렬은 1억 칸이 필요합니다. 반면 인접 리스트는 정점 목록과 간선 정보만 저장하면 되므로 훨씬 적은 메모리로 충분합니다.

반대로 정점이 300개이고 두 정점이 연결되어 있는지 수십만 번 확인해야 한다면 인접 행렬이 편리할 수 있습니다. matrix[u][v]로 바로 확인할 수 있기 때문입니다.

결국 자료구조 선택은 다음 질문으로 정리할 수 있습니다.

"빠르게 접근해야 하는 것은 인덱스인가, 값인가?"

"데이터가 빽빽한가, 드문드문한가?"

"시간을 아끼기 위해 메모리를 더 써도 되는가?"

좋은 풀이는 보통 이 질문들에 균형 있게 답합니다.

코드 조각으로 복잡도 읽는 연습

복잡도 감각은 많이 읽어볼수록 좋아집니다. 다음 코드들을 보며 직접 판단해봅시다.

for i in range(n):
    print(i)

이 코드는 O(N)입니다. 입력 크기만큼 한 번씩 실행됩니다.

for i in range(n):
    for j in range(m):
        print(i, j)

이 코드는 O(NM)입니다. 두 입력 크기가 다르면 무조건 O(N²)이라고 쓰면 안 됩니다. N과 M이 각각 독립적으로 주어졌다면 둘을 구분해야 합니다.

arr.sort()
for x in arr:
    print(x)

정렬이 O(N log N), 반복문이 O(N)입니다. 더 큰 쪽은 O(N log N)이므로 전체 복잡도는 O(N log N)입니다.

for i in range(n):
    if i in arr:
        print(i)

이 코드는 조심해야 합니다. arr가 리스트라면 i in arr는 내부적으로 배열을 훑으며 찾기 때문에 O(N)입니다. 바깥 반복문도 N번이므로 전체는 O(N²)입니다.

하지만 arr가 집합이라면 이야기가 달라집니다.

s = set(arr)
for i in range(n):
    if i in s:
        print(i)

집합 조회는 평균적으로 O(1)입니다. 집합을 만드는 데 O(N), 반복문도 O(N)이므로 전체는 O(N)입니다. 같은 로직처럼 보여도 자료구조 하나가 복잡도를 바꿉니다.

숨은 비용을 조심하라

복잡도를 계산할 때 눈에 보이는 반복문만 세면 실수할 수 있습니다. 함수 호출이나 연산 안에 숨은 비용이 있을 수 있기 때문입니다.

예를 들어 파이썬에서 리스트의 앞쪽 원소를 제거하는 코드를 생각해봅시다.

arr.pop(0)

겉보기에는 한 줄이지만, 첫 원소가 빠진 뒤 뒤쪽 원소들을 모두 한 칸씩 당겨야 합니다. 따라서 O(N)입니다. 이 작업을 반복문 안에서 계속하면 전체가 O(N²)이 될 수 있습니다. 이런 경우에는 deque를 사용하는 것이 좋습니다.

문자열도 주의해야 합니다.

s = ""
for word in words:
    s += word

문자열은 보통 한 번 만들어지면 내부 내용을 직접 바꾸기 어렵습니다. 그래서 +=를 반복하면 매번 새 문자열을 만들며 이전 내용을 복사하는 비용이 생길 수 있습니다. 많은 문자열을 합칠 때는 리스트에 모았다가 마지막에 join하는 방식이 안전합니다.

parts = []
for word in words:
    parts.append(word)
s = "".join(parts)

코딩 테스트에서 시간 초과는 거창한 알고리즘을 몰라서만 발생하지 않습니다. pop(0), 리스트에서의 반복적인 in, 문자열 누적처럼 작은 습관 때문에 발생하기도 합니다.

복잡도 감각으로 풀이 후보 줄이기

문제를 읽은 뒤에는 다음 순서로 생각해보면 좋습니다.

먼저 입력 크기를 확인합니다. N, M, 문자열 길이, 쿼리 수, 값의 범위를 봅니다. 특히 쿼리 수가 크면 "매 쿼리마다 선형 탐색해도 되는가?"를 꼭 확인해야 합니다.

그다음 제한 시간을 봅니다. 시간 제한이 1초인지 5초인지, 언어가 무엇인지에 따라 여유가 달라집니다. 그래도 처음에는 보수적으로 판단하는 것이 좋습니다.

이후 가능한 복잡도를 정합니다. N = 100,000이면 O(N²)은 지우고, O(N log N) 또는 O(N) 접근을 찾습니다. N = 20이면 완전 탐색이나 백트래킹도 후보에 넣습니다.

마지막으로 자료구조를 고릅니다. 값의 존재 여부가 중요하면 해시를 생각하고, 순서가 중요하면 정렬이나 배열을 생각합니다. 그래프라면 정점 수와 간선 수를 보고 인접 리스트와 인접 행렬 중 하나를 선택합니다.

이 과정은 처음에는 번거롭게 느껴질 수 있습니다. 하지만 익숙해지면 문제를 읽는 동시에 자동으로 일어납니다. 마치 운전할 때 신호등과 차선을 동시에 보는 것처럼, 제한 조건을 보는 순간 가능한 풀이의 윤곽이 보이기 시작합니다.

자주 하는 오해

복잡도를 처음 배울 때 흔히 하는 오해가 있습니다.

첫 번째는 "반복문이 하나면 무조건 O(N)"이라고 생각하는 것입니다. 반복문 안에서 list.index, in, 슬라이싱, 정렬 같은 비싼 작업을 하면 전체 복잡도는 더 커질 수 있습니다.

두 번째는 "정렬은 느리다"는 오해입니다. 물론 정렬은 O(N)보다 느립니다. 하지만 O(N²) 풀이를 O(N log N)으로 줄여준다면 정렬은 매우 좋은 선택입니다. 코딩 테스트에서 정렬은 문제를 단순화하는 강력한 도구입니다.

세 번째는 "메모리는 넉넉하니 신경 쓰지 않아도 된다"는 생각입니다. 작은 문제에서는 맞을 수 있지만, 큰 2차원 배열이나 그래프 인접 행렬을 만들면 순식간에 메모리 제한을 넘을 수 있습니다. 특히 파이썬에서는 객체 하나하나의 메모리 비용이 크기 때문에 더 조심해야 합니다.

네 번째는 "빅오만 맞으면 무조건 통과한다"는 오해입니다. 같은 O(N)이라도 상수가 큰 코드와 작은 코드는 차이가 납니다. 입출력이 느리거나, 불필요한 객체를 많이 만들거나, 해시 연산을 지나치게 많이 하면 예상보다 느릴 수 있습니다. 빅오는 방향을 알려주는 지도이지, 실제 주행 시간을 완벽히 보장하는 내비게이션은 아닙니다.

실전에서 바로 쓰는 복잡도 체크리스트

문제를 풀기 전에 다음 질문을 빠르게 확인해보세요.

"입력의 최대 크기는 얼마인가?"

"시간 제한 안에서 O(N²)이 가능한가?"

"정렬 O(N log N)은 가능한가?"

"매 쿼리마다 처음부터 탐색하면 총 몇 번이 되는가?"

"배열을 하나 더 만들어도 메모리가 괜찮은가?"

"2차원 배열이나 인접 행렬을 만들면 크기가 얼마인가?"

"리스트 대신 집합이나 딕셔너리를 써야 하는 조회가 있는가?"

이 질문들은 단순하지만 강력합니다. 코드를 작성하기 전에 30초만 투자해도 시간 초과와 메모리 초과를 크게 줄일 수 있습니다.

감각은 계산에서 시작해 경험으로 완성된다

복잡도는 처음에는 계산입니다. 반복문이 몇 번 도는지 세고, N의 최댓값을 넣어보고, 제한 시간과 비교합니다. 하지만 문제를 많이 풀다 보면 계산은 점점 감각이 됩니다.

N = 1,000을 보면 "이중 반복문 가능"이라는 생각이 들고, N = 100,000을 보면 "정렬이나 해시가 필요하겠네"라는 생각이 듭니다. N = 20을 보면 "부분집합을 모두 봐도 될까?"를 떠올리고, 그래프에서 N = 100,000, M = 200,000을 보면 자연스럽게 인접 리스트를 선택합니다.

이 감각은 코딩 테스트에서 매우 큰 무기가 됩니다. 왜냐하면 문제 풀이 시간의 상당 부분은 "어떤 접근을 선택할지"에서 쓰이기 때문입니다. 복잡도를 빠르게 판단할 수 있으면 틀린 길에 오래 머무르지 않습니다. 처음부터 통과 가능한 길을 향해 걸어갈 확률이 높아집니다.

다음 장부터는 실제 구현의 기본기를 다룹니다. 입력을 빠르게 받고, 문자열과 배열을 다루며, 문제의 요구사항을 코드로 정확하게 옮기는 연습을 하게 됩니다. 그때도 오늘 배운 복잡도 감각은 계속 따라다닙니다. 좋은 구현은 단지 맞는 코드가 아니라, 제한 시간과 메모리 안에서 끝나는 코드이기 때문입니다.