코딩테스트 시간복잡도·공간복잡도 완벽 가이드: 실전 예제로 쉽게 이해하기

코딩테스트를 준비하면서 가장 먼저 부딪히는 벽이 있습니다. 바로 시간복잡도와 공간복잡도입니다. 처음에는 O(n)이 뭐고 O(n²)은 또 뭔지 감이 잘 안 오지만, 일단 한 번 이해하고 나면 문제 읽는 순간 대략적인 해법의 한계가 보이기 시작합니다. 이 글은 저도 다시 기초부터 복습한다는 마음으로, 공부하며 정리한 내용을 여러분과 함께 공유하는 방식으로 풀어가겠습니다. 불필요한 수학 공식은 최소화하고, 바로 손에 잡히는 코드 예제와 실전 체크리스트 위주로 정리했습니다.

왜 복잡도를 신경 써야 할까?

배열에서 특정 숫자를 찾는다고 가정해 봅니다. 정렬되어 있지 않다면 선형탐색으로 O(n)이 걸립니다. 하지만 한 번 정렬해 두고(대부분 O(n log n)) 이진탐색을 쓰면 탐색은 O(log n)으로 줄어듭니다. 데이터가 100만 개만 되어도 O(n)은 최악의 경우 백만 번 비교지만, O(log n)은 20번 남짓이면 충분합니다. 입력 크기가 커질수록 복잡도의 차이는 곧바로 합격/불합격을 가르는 시간초과로 돌아옵니다.

배열: [3, 1, 4, 1, 5, 9, 2, 6, 5]
찾는 값: 5
- 선형탐색 O(n): 최대 9회 비교
- 이진탐색 O(log n): 정렬 후 약 3~4회 비교

즉, 복잡도는 “지금 코드가 입력 n에 따라 얼마나 느려질지”를 미리 예측하게 해주는 필수 도구입니다. 코딩테스트에서 제한 시간과 입력 범위를 보고 바로 “가능한 해법”을 좁히는 능력이 여기서 나옵니다.

시간복잡도 핵심 정리

시간복잡도는 알고리즘이 처리해야 하는 연산의 대략적인 증가 추세를 나타냅니다. 정확한 연산 횟수보다 입력 크기가 커질 때 증가 속도가 어떤지(상수/로그/선형/이차/지수)를 보는 개념입니다.

• O(1): 상수 시간. 입력 크기와 무관하게 일정한 시간.
• O(log n): 로그 시간. 매 단계마다 문제 크기를 절반 등으로 줄이는 방식(이진탐색).
• O(n): 선형 시간. 입력을 한 번 훑는 수준의 반복.
• O(n log n): 선형 로그. 분할정복 정렬(병합/퀵 평균)에서 흔함.
• O(n²): 이차 시간. 이중 반복문이 대표적.
• O(2ⁿ), O(n!): 지수/팩토리얼. n이 조금만 커져도 실전 불가.

입력 n=1000을 대략 비교해 보면 O(log n)≈10, O(n)=1000, O(n log n)≈1만, O(n²)=100만 수준이 됩니다. 체감이 될 겁니다.

자주 나오는 Big O 예제 (Java)

O(1) — 상수 시간

배열에서 특정 인덱스로 접근하는 건 크기와 무관하게 항상 일정 시간입니다.

public int getFirstElement(int[] arr) {
    return arr[0]; // 배열 크기와 무관
}

O(n) — 선형 시간

배열을 한 번 훑는 합계 계산은 원소 개수에 비례합니다.

public int findSum(int[] arr) {
    int sum = 0;
    for (int x : arr) {
        sum += x;
    }
    return sum;
}

O(n²) — 이차 시간

이중 반복문은 곱으로 누적되어 금방 커집니다.

public void printAllPairs(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr.length; j++) {
            System.out.println(arr[i] + ", " + arr[j]);
        }
    }
}

O(log n) — 로그 시간

정렬된 배열에서 이진탐색은 범위를 절반씩 줄입니다.

public boolean binarySearch(int[] sorted, int target) {
    int l = 0, r = sorted.length - 1;
    while (l <= r) {
        int m = l + (r - l) / 2;
        if (sorted[m] == target) return true;
        if (sorted[m] < target) l = m + 1;
        else r = m - 1;
    }
    return false;
}

O(n log n) — 병합정렬 골자

분할(log n 단계) × 각 단계에서 병합(n) = n log n.

public void mergeSort(int[] a, int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(a, l, m);
        mergeSort(a, m + 1, r);
        merge(a, l, m, r);
    }
}

 

시간복잡도에서 자주 하는 실수

• 정렬이 필요한데 무심코 O(n²) 정렬(버블/선택/삽입)을 구현.
• 해시로 풀 수 있는데 정렬+이중 루프를 써서 O(n log n) 또는 O(n²)로 끌어올림.
• 재귀를 편하게 썼다가 깊이만큼의 호출 스택을 간과(공간 O(n), 시간도 커짐).
• 입력 범위를 안 보고 O(n²) 풀이를 선택해 시간초과 발생.

실전에서는 라이브러리 정렬(예: Java Arrays.sort)은 평균 O(n log n)이라 믿고 쓰는 게 안전합니다. 직접 정렬을 구현해야 한다면 이유가 분명해야 합니다.

지수 시간은 왜 위험할까?

피보나치 수를 단순 재귀로 구현하면 동일 부분 문제를 반복 계산하여 O(2ⁿ)까지 치솟습니다. n=30만 되어도 호출 수가 수백만을 넘겨 시간초과가 당연해집니다.

// 절대 실전에서 이렇게 쓰지 마세요
public int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

동적 계획법(DP)이나 반복문으로 중복 계산을 없애면 O(n)으로 개선됩니다.

public int fibDP(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        int c = a + b;
        a = b;
        b = c;
    }
    return b;
}

 

Big O 표기 — 어느 경우를 기준?

일반적으로 Big O는 최악의 경우(worst case)를 기준으로 말합니다. 예를 들어, 선형탐색은 첫 원소에서 바로 찾으면 O(1)로 끝나지만, 보통은 O(n)으로 표기합니다. 면접에서도 “최악의 경우 O(n)”으로 설명하면 됩니다. 평균/최선의 경우를 별도로 묻는다면 그때 구분해서 답하면 충분합니다.

public int indexOf(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) return i; // 최선 O(1)
    }
    return -1; // 최악 O(n)
}

 

공간복잡도 핵심 정리

공간복잡도는 알고리즘이 추가로 사용하는 메모리의 성장 추세입니다. 입력 자체를 담는 공간은 보통 제외하고, 추가로 사용하는 배열/맵/스택/재귀 깊이 등을 따집니다.

• O(1): 변수 몇 개로 처리(스와핑, 누적합 등).
• O(n): 입력 크기에 비례한 추가 배열/리스트/맵을 사용.
• O(log n): 분할정복 재귀 깊이(균형적으로 절반씩 줄이는 경우).
• O(n): 선형 재귀(끝까지 내려가는 경우)나 스택에 n개 쌓이는 경우.

예시들

// O(1) 공간: 최대값 찾기
public int maxOf(int[] arr) {
    int max = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > max) max = arr[i];
    }
    return max;
}

// O(n) 공간: 배열 복제
public int[] cloneArr(int[] arr) {
    int[] copy = new int[arr.length];
    System.arraycopy(arr, 0, copy, 0, arr.length);
    return copy;
}

// O(n) 공간: 선형 재귀 스택
public int sumRec(int[] arr, int i) {
    if (i == arr.length) return 0;
    return arr[i] + sumRec(arr, i + 1);
}

 

자료구조 별 연산 복잡도 감각

• 배열: 인덱스 접근 O(1), 탐색 O(n), 정렬 O(n log n).
• 동적 배열(ArrayList): 끝 삽입 평균 O(1), 중간 삽입/삭제 O(n).
• 연결 리스트: 임의 접근 O(n), 앞 삽입/삭제 O(1).
• HashMap/HashSet: 평균 삽입/탐색 O(1), 최악 충돌 시 O(n).
• TreeMap/TreeSet: 삽입/탐색 O(log n), 정렬 유지.
• 우선순위 큐(힙): 삽입/삭제 O(log n), 최댓값/최솟값 추출 용이.

정렬 필요 + 빈번 탐색이면 정렬 구조(TreeSet/TreeMap) 또는 정렬+이진탐색, 존재 여부만 빠르게 보면 해시가 대체로 유리합니다.

실전 패턴과 선택 기준

정렬이 필요한가?

정렬이 필요하면 바로 O(n log n)을 염두에 두고 라이브러리 정렬을 사용하세요. Java에서는 Arrays.sort가 평균 O(n log n)이고 충분히 빠릅니다.

import java.util.Arrays;

int[] a = {5, 1, 9, 2, 6, 5};
Arrays.sort(a); // 평균 O(n log n)

탐색만 빠르게 하고 싶은가?

한 번 정렬 후 이진탐색을 쓰거나, 값의 존재 여부/중복 체크가 잦다면 HashSet/HashMap으로 O(1) 평균 시간을 확보합니다.

import java.util.*;

public int[] intersection(int[] A, int[] B) {
    Set<Integer> s = new HashSet<>();
    for (int x : A) s.add(x);
    Set<Integer> r = new HashSet<>();
    for (int y : B) if (s.contains(y)) r.add(y);
    return r.stream().mapToInt(i -> i).toArray();
}

이중 루프를 없앨 수 있는가?

두 배열의 쌍을 모두 비교하는 O(n²) 로직은 해시나 투 포인터로 자주 줄일 수 있습니다. 정렬 후 투 포인터를 쓰면 O(n log n) + O(n)으로 개선되기도 합니다.

복잡도 분석 체크리스트

1. 루프 중첩은 몇 겹인가? 1겹은 O(n), 2겹은 O(n²), 3겹은 O(n³) 위험.
2. 분할정복을 쓰는가? 절반으로 나누면 log n이 곱해진다.
3. 추가로 잡는 메모리는? 새 배열/맵 크기가 n에 비례하면 공간 O(n).
4. 자료구조 연산 비용은? 해시 평균 O(1), 트리 O(log n), 배열 탐색 O(n).
5. 입력 제약은? n ≤ 1,000이면 O(n²)도 가끔 통과, n ≥ 100,000이면 O(n log n) 이하 추구.

코딩테스트에서 바로 쓰는 감속 공식

• 중복 체크/존재 확인 → HashSet/HashMap으로 O(1) 평균.
• 가장 큰/작은 k개 → 힙(우선순위 큐)로 O(n log k).
• 연속 부분합/윈도우 → 투 포인터/슬라이딩 윈도우로 O(n).
• 정렬 + 탐색 → 정렬 O(n log n) + 이진탐색 O(log n).
• 그래프 최단거리(가중치 양수) → 다익스트라(힙) O((V+E) log V).
• 사이클/연결요소 → 유니온파인드 거의 상수 시간(α(n)).

실전 예제: 시간초과 줄이기 리팩토링

문제 1: 중복 원소 여부

나쁜 풀이(O(n²))

public boolean hasDupBad(int[] a) {
    for (int i = 0; i < a.length; i++) {
        for (int j = i + 1; j < a.length; j++) {
            if (a[i] == a[j]) return true;
        }
    }
    return false;
}

개선 풀이(O(n))

import java.util.*;

public boolean hasDup(int[] a) {
    Set<Integer> seen = new HashSet<>();
    for (int x : a) {
        if (!seen.add(x)) return true;
    }
    return false;
}

문제 2: 두 배열 교집합 크기

정렬 + 투 포인터(O(n log n) + O(n))

import java.util.*;

public int interSize(int[] A, int[] B) {
    Arrays.sort(A);
    Arrays.sort(B);
    int i = 0, j = 0, cnt = 0;
    while (i < A.length && j < B.length) {
        if (A[i] == B[j]) { cnt++; i++; j++; }
        else if (A[i] < B[j]) i++;
        else j++;
    }
    return cnt;
}

해시 기반(O(n))

import java.util.*;

public int interSizeHash(int[] A, int[] B) {
    Set<Integer> s = new HashSet<>();
    for (int x : A) s.add(x);
    int cnt = 0;
    for (int y : B) if (s.contains(y)) cnt++;
    return cnt;
}

 

면접에서 복잡도 설명하는 요령

• 먼저 올바르게 동작하는 기준 풀이 제시 → 복잡도 명확히 말하기.
• 시간/공간 트레이드오프를 언급(예: 해시로 시간↓, 메모리↑).
• 입력 제약으로 풀이 선택 정당화(“n이 2e5라 O(n²)은 불가”).
• 대안 비교: 정렬+이진탐색 vs 해시, 힙 vs 정렬 후 슬라이싱 등.
• 최악/평균/최선 구분 질문에 대비(특히 해시 최악 O(n) 언급).

공부하며 느낀 점

복잡도를 잘 아는 것만으로 정답이 되는 건 아니지만, 실전에서 가능한 풀이를 빠르게 “제한”해 주는 아주 강력한 필터라는 걸 절감했습니다. 처음부터 최적화를 강박적으로 하려다가 시간을 다 쓰는 것보다는, 일단 맞는 풀이를 만든 뒤 입력 범위를 보며 병목을 잡아가는 게 합격 확률을 높였습니다. 무엇보다도 자주 풀수록 감이 확실히 올라갑니다. 문제를 볼 때마다 “이건 대략 O(뭐)”인지 입으로 말해 보세요. 며칠만 해도 속도가 느는 게 체감됩니다.
 
이 글을 쓰면서 저도 다시 기초 체력을 다졌습니다. 오늘부터는 해시, 투 포인터, 정렬+이진탐색, 힙 네 가지 축을 매일 섞어 풀어보려 합니다. 여러분도 각자 취약한 한 가지를 골라 오늘 한 문제만이라도 손으로 풀어 보세요. 작은 반복이 코딩테스트를 통과시키는 가장 확실한 지름길이었습니다. 화이팅!

입사 코딩테스트 필수 알고리즘 10가지: 완벽 정복 가이드