시간 복잡도란?

[코딩테스트] 시간복잡도와 O(1) 완벽 정리 - 초보자도 이해하는 Big O 표기법

코딩테스트를 준비하면서 가장 많이 듣는 말이 "시간복잡도를 고려해야 한다"이다. 오늘은 시간복잡도가 무엇인지, 특히 O(1)이 왜 중요한지 아주 쉽게 설명할 예정이다.

---

📌 시간복잡도란?

시간복잡도(Time Complexity)는 간단히 말해서 "프로그램이 얼마나 오래 걸리는가?"를 나타내는 방법이다.

좀 더 정확히 말하면, 데이터의 양이 늘어날 때 실행 시간이 어떻게 변하는지를 수학적으로 표현한 것이다.

예를 들어보자. 이름이 적힌 카드 더미가 있다고 가정하자.

• 카드가 10장일 때: 찾는데 1초 걸림
• 카드가 100장일 때: 찾는데 10초? 100초? 아니면 여전히 1초?

이렇게 데이터의 양(카드 수)에 따라 시간이 어떻게 증가하는지를 나타내는 것이 시간복잡도다.

왜 중요한가?

• 같은 문제를 푸는 방법이 여러 개 있을 때, 어떤 방법이 더 빠른지 비교할 수 있다.
• 내가 작성한 코드가 데이터가 많아졌을 때도 잘 작동할지 미리 예측할 수 있다.
• 코딩테스트에서는 시간 제한이 있기 때문에, 시간복잡도를 고려하지 않으면 시간 초과로 틀릴 수 있다.

---

🔍 Big O 표기법

시간복잡도를 표현할 때 O(뭔가) 형태로 쓴다. 이것을 "빅오 표기법(Big O Notation)"이라고 부른다.

O(1), O(n), O(n²), O(log n) ...

각 부분의 의미:

• O(): "Order of"의 약자로, "대략적인 크기"를 의미한다.
• n: 입력 데이터의 개수를 나타낸다. 예를 들어 배열의 길이, 리스트의 원소 개수 등이다.
• 괄호 안의 식: 데이터 개수(n)에 따라 연산이 몇 번 실행되는지를 나타낸다.

쉬운 예시:

• O(1): 데이터가 몇 개든 1번만 실행 → 가장 빠름
• O(n): 데이터가 n개면 n번 실행 → 데이터 100개면 100번
• O(n²): 데이터가 n개면 n×n번 실행 → 데이터 100개면 10,000번

Big O는 최악의 경우를 기준으로 한다. 즉, 데이터가 최악의 상황일 때 얼마나 오래 걸리는지를 나타낸다.

---

⚡ 시간복잡도 순위 (빠른 순서대로)

1. O(1) - 상수 시간 (가장 빠름)

핵심: 데이터가 10개든 100만개든 항상 같은 시간이 걸린다.

생활 속 예시:
책장에 꽂힌 책 중 맨 앞에 있는 책을 꺼낸다고 생각해보자. 책장에 책이 10권 있든, 1000권 있든 맨 앞의 책을 꺼내는 시간은 똑같다.

코드 예시:

// 예시 1: 배열의 특정 위치 접근
int first = arr[0];  // 배열이 100개든 100만개든 첫 번째 요소를 가져오는 시간은 동일

// 예시 2: 변수에 값 저장
int x = 10;  // 다른 데이터와 무관하게 바로 실행

// 예시 3: 두 숫자 더하기
int sum = a + b;  // 다른 데이터의 양과 관계없이 즉시 계산

왜 O(1)인가?
데이터의 양(n)과 상관없이 실행 횟수가 일정하기 때문이다. 배열에 원소가 10개든 100만개든, 첫 번째 원소에 접근하는 것은 메모리 주소를 통해 바로 접근하므로 1번의 연산이면 충분하다.

---

2. O(log n) - 로그 시간

핵심: 데이터가 늘어나도 시간은 조금만 증가한다. 데이터가 2배가 되어도 실행 시간은 +1번만 증가한다.

생활 속 예시: 끝말잇기 사전에서 단어 찾기

정렬된 사전에서 "사과"라는 단어를 찾는다고 하자. 전체 페이지를 처음부터 보지 않고 다음처럼 찾는다:

1. 사전 중간을 펼친다 → "자"로 시작하는 단어 발견 → "사"는 앞쪽에 있으니 앞쪽만 보면 된다
2. 앞쪽 절반의 중간을 펼친다 → "마"로 시작 → "사"는 뒤쪽에 있으니 뒤쪽만 보면 된다
3. 그 범위의 중간을 펼친다 → "사"로 시작하는 단어 발견!

이렇게 매번 절반씩 줄여나가는 방식이 O(log n)이다.

왜 빠른가?

• 페이지가 100장 → 약 7번만 찾으면 됨
• 페이지가 1,000장 → 약 10번만 찾으면 됨
• 페이지가 100만 장 → 약 20번만 찾으면 됨

데이터가 1,000배 늘어나도 실행 횟수는 2배만 늘어난다!

코드 예시: 이진 탐색

// 정렬된 배열에서 특정 값 찾기
int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;

    while (left <= right) {
        int mid = (left + right) / 2;  // 중간 위치

        if (arr[mid] == target) {
            return mid;  // 찾았다!
        } else if (arr[mid] < target) {
            left = mid + 1;  // 오른쪽 절반만 보기
        } else {
            right = mid - 1;  // 왼쪽 절반만 보기
        }
    }
    return -1;  // 못 찾음
}

데이터 증가에 따른 실행 횟수:

• 데이터 100개 → 최대 7번 비교
• 데이터 1,000개 → 최대 10번 비교
• 데이터 100만개 → 최대 20번 비교

100만개의 데이터를 20번만 비교하면 찾을 수 있다!

---

3. O(n) - 선형 시간

핵심: 데이터가 2배가 되면 시간도 정확히 2배가 걸린다. 가장 일반적인 시간복잡도다.

생활 속 예시: 출석 부르기

선생님이 학생 이름을 하나씩 부른다고 하자.

• 학생이 10명 → 10번 호명
• 학생이 20명 → 20번 호명
• 학생이 100명 → 100번 호명

학생 수가 2배가 되면 호명 횟수도 정확히 2배가 된다.

코드 예시:

// 예시 1: 배열의 모든 요소 출력
for (int i = 0; i < n; i++) {
    System.out.println(arr[i]);
}
// 배열 크기(n)만큼 반복 → O(n)

// 예시 2: 배열에서 최댓값 찾기
int max = arr[0];
for (int i = 1; i < n; i++) {
    if (arr[i] > max) {
        max = arr[i];
    }
}
// 모든 요소를 한 번씩 확인 → O(n)

// 예시 3: 특정 값 찾기 (정렬 안된 배열)
for (int i = 0; i < n; i++) {
    if (arr[i] == target) {
        return i;
    }
}
// 최악의 경우 끝까지 봐야 함 → O(n)

왜 O(n)인가?
배열의 모든 요소를 한 번씩 확인해야 하므로, 데이터가 n개면 n번 실행된다.

---

4. O(n log n)

핵심: O(n)보다는 느리지만, O(n²)보다는 훨씬 빠르다. 효율적인 정렬 알고리즘에서 주로 나타난다.

생활 속 예시: 카드를 빠르게 정렬하기

섞인 카드를 정렬할 때, 그냥 비교하면 O(n²)이 걸린다. 하지만 "분할 정복" 방식을 쓰면:

1. 카드를 반으로 나눈다
2. 각각을 정렬한다
3. 정렬된 두 묶음을 합친다

이 과정을 반복하면 O(n log n)에 정렬할 수 있다.

코드 예시:

// Java의 기본 정렬 (Timsort, Dual-Pivot Quicksort 등)
Arrays.sort(arr);  // O(n log n)

// Python의 기본 정렬
// sorted(list)  // O(n log n)

왜 O(n log n)인가?

• 데이터를 반으로 나누는 과정: log n번
• 각 단계에서 모든 데이터를 처리: n번
• 총: n × log n = O(n log n)

속도 비교:

• 데이터 1,000개: 약 10,000번 연산
• 데이터 100만개: 약 2,000만번 연산

O(n²)보다 훨씬 빠르므로, 큰 데이터를 정렬할 때는 반드시 O(n log n) 알고리즘을 써야 한다.

---

5. O(n²) - 제곱 시간

핵심: 데이터가 2배가 되면 시간은 4배가 걸린다. 데이터가 많으면 매우 느려진다!

생활 속 예시: 모든 학생끼리 악수하기

반 학생 모두가 서로 한 번씩 악수한다고 하자.

• 학생 10명 → 약 100번 악수 (10 × 10)
• 학생 20명 → 약 400번 악수 (20 × 20)
• 학생 100명 → 약 10,000번 악수 (100 × 100)

학생이 2배 늘면 악수는 4배 늘어난다!

코드 예시:

// 예시 1: 이중 반복문 (가장 전형적)
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        System.out.println(i + ", " + j);
    }
}
// n개 × n개 = n² 번 실행

// 예시 2: 모든 쌍 비교
for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        if (arr[i] > arr[j]) {
            // 두 요소 비교
        }
    }
}
// 버블 정렬, 선택 정렬 등 → O(n²)

// 예시 3: 2차원 배열 순회
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        matrix[i][j] = 0;
    }
}

왜 위험한가?

• 데이터 100개: 10,000번 연산
• 데이터 1,000개: 1,000,000번 연산
• 데이터 10,000개: 100,000,000번 연산 (1억 번!)
• 데이터 100만개: 1조 번 연산 → ❌ 시간 초과 확정

⚠️ 주의: 코딩테스트에서 데이터가 1만개 이상이면 O(n²) 알고리즘은 거의 항상 시간 초과가 난다!

---

🎯 O(1) 자세히 알아보기

O(1)의 진짜 의미

많은 초보자들이 오해하는 부분이다. O(1)은 "정확히 1번만 실행한다"는 뜻이 아니다!

O(1) = 입력 데이터의 크기(n)에 상관없이 항상 일정한 시간이 걸린다

예를 들어, 다음 두 코드 모두 O(1)이다:

// 이것도 O(1)
int x = arr[0];

// 이것도 O(1) (연산이 5번이지만!)
int result = (a + b) * (c - d) + e;

왜? 둘 다 배열 크기나 다른 데이터와 무관하게 실행되기 때문이다.

O(1)의 다양한 예시

// 1. 배열 특정 인덱스 접근
int value = arr[5];  
// 배열이 10개든 100만개든, arr[5]에 접근하는 시간은 동일

// 2. 변수에 값 저장
int x = 10;  
// 다른 데이터와 무관하게 바로 실행

// 3. 여러 번 연산해도 O(1)
int sum = a + b + c;  
int result = sum * 2 + 10;  
// 연산이 여러 번이지만, 데이터 크기(n)와 무관하므로 O(1)

// 4. 조건문도 O(1)
if (x > 10) {
    y = x * 2;
} else {
    y = x / 2;
}
// 데이터 크기와 무관

// 5. 스택/큐의 기본 연산
stack.push(5);   // 맨 위에 추가 → O(1)
stack.pop();     // 맨 위에서 제거 → O(1)
queue.offer(5);  // 맨 뒤에 추가 → O(1)
queue.poll();    // 맨 앞에서 제거 → O(1)

// 6. 해시맵(HashMap)의 조회/추가
map.put("key", 100);    // O(1)
int value = map.get("key");  // O(1)

주의: 이것은 O(1)이 아니다!

// ❌ O(n)이다 - 배열 크기에 비례
for (int i = 0; i < n; i++) {
    sum += arr[i];
}

// ❌ O(n)이다 - 반복문 내부가 O(1)이어도 n번 반복
for (int i = 0; i < n; i++) {
    int x = arr[i];  // 이 자체는 O(1)
}
// 전체는 O(1) × n = O(n)

핵심 정리

O(1)인지 판단하는 방법:

1. 반복문이 없는가? ✅
2. 재귀 호출이 없는가? ✅
3. 실행 횟수가 입력 크기(n)와 무관한가? ✅

세 조건을 모두 만족하면 O(1)이다!

---

🌟 실생활 비유로 이해하기

사전에서 단어를 찾는 상황으로 각 시간복잡도를 비유해보자:

O(1) - 사전 첫 페이지 펴기

상황: 사전의 첫 페이지를 펼쳐서 첫 단어를 본다.

특징:

• 사전이 100페이지든 10,000페이지든 첫 페이지를 펴는 시간은 똑같다.
• 즉시 접근 가능하다.

O(log n) - 이진 탐색으로 단어 찾기

상황: 정렬된 사전에서 "컴퓨터"라는 단어를 찾는다.

방법:

1. 사전 중간을 펼침 → "아"로 시작하는 단어 발견
2. "컴"은 "아"보다 앞에 있으니 앞쪽 절반만 본다
3. 앞쪽 절반의 중간을 펼침 → "사"로 시작하는 단어 발견
4. "컴"은 "사"보다 앞에 있으니 또 앞쪽 절반만 본다
5. 반복하면 몇 번 안에 찾는다!

특징:

• 사전이 2배 두꺼워져도 한 번만 더 펼치면 된다.
• 10,000페이지 사전도 약 13~14번이면 찾는다.

O(n) - 사전을 처음부터 끝까지 훑어보기

상황: 정렬되지 않은 사전에서 "컴퓨터"를 찾는다.

방법:

• 첫 페이지부터 하나하나 확인한다.
• 운이 나쁘면 끝까지 봐야 한다.

특징:

• 사전이 100페이지 → 최악의 경우 100페이지 확인
• 사전이 10,000페이지 → 최악의 경우 10,000페이지 확인
• 페이지가 늘어나는 만큼 시간도 늘어난다.

O(n²) - 사전의 모든 단어를 서로 비교

상황: 사전의 모든 단어 쌍을 비교한다.

방법:

• 첫 번째 단어를 나머지 모든 단어와 비교
• 두 번째 단어를 나머지 모든 단어와 비교
• 반복...

특징:

• 단어 100개 → 약 10,000번 비교
• 단어 1,000개 → 약 1,000,000번 비교
• 실생활에서는 절대 이렇게 하지 않는다!

시간복잡도 비교표

시간복잡도	비유	데이터 2배 시	속도
O(1)	첫 페이지 펴기	시간 변화 없음	가장 빠름 ⚡
O(log n)	중간부터 반씩 줄이며 찾기	+1번 더	매우 빠름
O(n)	처음부터 끝까지 보기	2배	보통
O(n log n)	분할 정복으로 정렬	2배 조금 넘음	준수
O(n²)	모든 쌍 비교	4배	느림 🐌

---

💡 실전 문제: MinStack (O(1) 구현 도전!)

이제 실제 문제로 O(1)을 이해해보자.

문제 설명

정수를 저장하는 스택을 구현하되, 다음 명령을 모두 O(1) 시간복잡도로 처리해야 한다:

1. push X: 정수 X를 스택에 넣는다
2. pop: 스택에서 가장 위 정수를 빼고 출력
3. top: 스택의 가장 위 정수를 출력
4. min: 스택에 들어있는 정수 중 최솟값을 출력

핵심 포인트

보통 push, pop, top은 쉽게 O(1)로 구현할 수 있다. 스택의 맨 위만 보면 되기 때문이다.

하지만 min(최솟값 찾기)을 O(1)로 구현하는 것이 이 문제의 핵심이다.

❌ 잘못된 접근 - 왜 안 되는가?

첫 번째 시도: 매번 전체 스택을 확인

public int min() {
    int minValue = Integer.MAX_VALUE;

    // 스택의 모든 요소를 확인
    for (int i = 0; i < size; i++) {
        if (stack[i] < minValue) {
            minValue = stack[i];
        }
    }
    return minValue;
}

문제점:

• 스택에 데이터가 n개 있으면 n번 확인해야 한다 → O(n)
• 스택에 100만개가 있으면? 매번 100만번 확인! → 너무 느림
• 문제 조건: O(1)로 구현해야 함 → ❌ 실패

왜 이렇게 푸는 걸 생각하게 되나?

처음 생각하면 당연히 이렇게 풀게 된다. "최솟값을 찾으려면 전부 봐야 하지 않나?" 하고 생각하기 때문이다.

하지만 이 문제의 핵심은 "매번 찾지 말고, 미리 저장해두자"는 아이디어다.

✅ 올바른 접근 - 어떻게 O(1)로 만들까?

핵심 아이디어: "매번 계산하지 말고, 미리 저장해두자!"

최솟값을 별도의 스택에 함께 저장한다. 이렇게 하면:

• push할 때: 새로운 최솟값도 함께 저장 → O(1)
• min 호출할 때: 저장된 최솟값 바로 반환 → O(1)

전략:

1. 일반 스택(stack): 실제 데이터 저장
2. 최솟값 스택(minStack): 각 시점의 최솟값 저장

구체적인 방법

push(x)할 때:

1. stack에 x를 넣는다
2. minStack에는 "지금까지의 최솟값"을 넣는다
   • 만약 x가 더 작으면 x를 넣고
   • 아니면 이전 최솟값을 그대로 넣는다

min()을 호출할 때:

• minStack의 맨 위를 보면 현재 스택의 최솟값이다!
• 바로 반환 → O(1)

전체 코드

public class MinStack {
    private int[] stack;      // 일반 데이터 저장
    private int[] minStack;   // 각 시점의 최솟값 저장
    private int top;          // 스택의 맨 위 위치

    public MinStack(int capacity) {
        stack = new int[capacity];
        minStack = new int[capacity];
        top = -1;  // 빈 스택
    }

    // push: O(1)
    public void push(int x) {
        // 1. 일반 스택에 추가
        stack[++top] = x;

        // 2. 최솟값 스택에 현재 최솟값 추가
        if (top == 0) {
            // 첫 번째 원소면 x가 최솟값
            minStack[top] = x;
        } else {
            // 새로 들어온 x와 이전 최솟값 중 더 작은 값
            minStack[top] = Math.min(x, minStack[top - 1]);
        }
    }

    // pop: O(1)
    public int pop() {
        if (top < 0) return -1;  // 빈 스택
        return stack[top--];     // 맨 위 제거하고 반환
    }

    // top: O(1)
    public int top() {
        if (top < 0) return -1;
        return stack[top];  // 맨 위만 보기
    }

    // min: O(1) ← 핵심!
    public int min() {
        if (top < 0) return -1;
        return minStack[top];  // 미리 계산해둔 최솟값 바로 반환!
    }
}

왜 O(1)인가?

push:

• stack[++top] = x → 1번 연산
• Math.min(...) → 1번 연산
• 스택 크기와 무관하게 항상 일정 → O(1)

min:

• minStack[top] → 1번 연산
• 반복문 없음, 바로 반환 → O(1)

대가:

• 메모리 2배 사용 (minStack 추가)
• 하지만 시간은 O(n)에서 O(1)로 엄청나게 빨라짐!

이것이 바로 "시간과 공간의 트레이드오프"다.

작동 원리 - 단계별 시뮬레이션

실제로 어떻게 동작하는지 하나씩 따라가보자.

초기 상태:

stack:    []
minStack: []
(둘 다 비어있음)

---

1단계: push(5)

stack:    [5]
minStack: [5]  ← 지금까지 최솟값은 5

설명:
- 5를 stack에 추가
- 첫 번째 원소니까 5가 최솟값
- minStack에도 5 저장

---

2단계: push(3)

stack:    [5, 3]
minStack: [5, 3]  ← 지금까지 최솟값은 3

설명:
- 3을 stack에 추가
- 이전 최솟값(5)와 새 값(3) 비교 → 3이 더 작음
- minStack에 3 저장
- 이제 min()을 호출하면 3이 반환됨

---

3단계: push(7)

stack:    [5, 3, 7]
minStack: [5, 3, 3]  ← 지금까지 최솟값은 여전히 3

설명:
- 7을 stack에 추가
- 이전 최솟값(3)과 새 값(7) 비교 → 3이 더 작음
- minStack에 3 저장 (이전 최솟값 유지)
- 핵심: 7은 최솟값이 아니지만, minStack에는 "현재 최솟값"인 3을 저장

---

4단계: min() 호출

결과: 3

설명:
- minStack의 맨 위를 보면 3
- 반복문 없이 바로 반환 → O(1)
- "스택 전체를 확인"할 필요가 없다!

---

5단계: pop()

pop 결과: 7

stack:    [5, 3]
minStack: [5, 3]  ← 7을 제거했으니, 최솟값은 다시 3

설명:
- stack과 minStack 모두 맨 위 제거
- 자동으로 이전 시점의 최솟값으로 돌아감!

---

6단계: min() 호출

결과: 3

설명:
- minStack의 맨 위 = 3
- 여전히 O(1)로 즉시 반환

---

7단계: pop()

pop 결과: 3

stack:    [5]
minStack: [5]  ← 3을 제거했으니, 최솟값은 5

설명:
- 3이 제거되면 최솟값이 바뀐다
- 하지만 minStack에 이미 저장되어 있음!

---

8단계: min() 호출

결과: 5

설명:
- minStack의 맨 위 = 5
- 여전히 O(1)로 즉시 반환
- "전체를 다시 확인"할 필요가 없다!

핵심 아이디어 정리

1. 각 시점마다 최솟값을 미리 계산해서 저장한다
2. pop할 때 자동으로 이전 최솟값으로 돌아간다
3. min() 호출 시 저장된 값만 보면 되므로 O(1)

이것이 "시간을 메모리로 사는" 전략이다!

공간복잡도 vs 시간복잡도 트레이드오프

이 MinStack 문제는 "시간과 공간의 트레이드오프"를 보여주는 전형적인 예시다.

트레이드오프란?
하나를 얻기 위해 다른 하나를 포기하는 것을 말한다.

우리의 선택:

구분	원래 방법 (O(n))	개선된 방법 (O(1))
시간복잡도	O(n) - 느림	O(1) - 매우 빠름 ✅
공간복잡도	O(1) - 추가 메모리 없음	O(n) - 메모리 2배 사용
min() 호출 100만번	엄청 오래 걸림	즉시 완료

구체적인 비교:

스택에 데이터 10,000개가 있고, min()을 1,000번 호출한다면:

• O(n) 방법: 10,000 × 1,000 = 천만 번 연산
• O(1) 방법: 1,000번 연산 (메모리는 2배 사용)

결론:

• 메모리를 2배 더 쓰는 대신
• 시간을 만 배 빠르게 만들었다!

언제 이런 선택을 하는가?

1. 시간이 더 중요할 때 (대부분의 경우)

   • 코딩테스트는 보통 시간 제한이 빡빡하고 메모리는 넉넉함
   • 사용자 경험에서 느린 것은 치명적

2. 메모리가 충분할 때

   • 현대 컴퓨터는 메모리가 넉넉함
   • 몇 MB 더 쓰는 것은 큰 문제가 아님

3. 메모리가 부족할 때는?

   • 임베디드 시스템, IoT 기기 등
   • 이런 경우에만 메모리를 우선시

다른 트레이드오프 예시:

1. 해시맵 (HashMap):

   • 메모리 O(n) 사용
   • 검색 시간 O(n) → O(1)로 단축

2. 동적 프로그래밍 (DP):

   • 메모리에 중간 결과 저장
   • 중복 계산 제거로 시간 대폭 단축

3. 캐시 (Cache):

   • 자주 쓰는 데이터를 메모리에 저장
   • 디스크 접근 시간 절약

핵심 교훈:

"무료 점심은 없다 (No free lunch)"

속도를 얻으려면 메모리를 주고, 메모리를 아끼려면 속도를 포기해야 한다.

상황에 맞게 선택하는 것이 중요하다!

---

⏱️ 왜 시간복잡도가 중요한가?

코딩테스트의 현실

코딩테스트에서는 시간 제한이 있다. 보통 문제마다 1~2초의 제한 시간이 주어진다.

아무리 정답 코드를 작성해도 시간 제한을 초과하면 틀린 것으로 처리된다. 이를 "시간 초과(Time Limit Exceeded)"라고 한다.

컴퓨터가 1초에 할 수 있는 연산

현대 컴퓨터는 대략 1초에 1억~10억 번 정도의 단순 연산을 수행할 수 있다.

코딩테스트 채점 서버 기준으로는 보통 1초에 약 1억 번(10^8)의 연산을 할 수 있다고 가정한다.

데이터가 100만 개일 때

시간복잡도	연산 횟수	실제 시간	결과
O(1)	1번	즉시	✅ 즉시 통과
O(log n)	약 20번	즉시	✅ 통과
O(n)	100만 번	약 0.01초	✅ 통과
O(n log n)	약 2,000만 번	약 0.2초	✅ 통과
O(n²)	1조 번	약 10,000초 (3시간)	❌ 시간 초과!

O(n²)로 풀면:

• 1,000,000 × 1,000,000 = 1,000,000,000,000 (1조)
• 1억 번/초로 계산하면 10,000초 = 약 2시간 47분
• 제한 시간 1초인데 3시간 걸림 → 완전히 불가능

실전 가이드: 데이터 크기별 알고리즘 선택

문제를 보고 데이터 크기(n)를 확인한 후, 사용할 알고리즘을 결정한다.

💡 경험 법칙:

데이터 크기 (n)	허용되는 시간복잡도	예시 알고리즘
n ≤ 10	O(n!), O(2^n)	브루트포스, 순열
n ≤ 20	O(2^n)	비트마스킹, DFS
n ≤ 100	O(n³)	플로이드-워셜
n ≤ 1,000	O(n²)	이중 반복문, 버블정렬
n ≤ 10,000	O(n²) 위험, O(n log n) 안전	병합정렬, 힙
n ≤ 100,000	O(n log n)	정렬 필수
n ≤ 1,000,000	O(n), O(log n)	해시맵, 이진탐색
n ≤ 10,000,000	O(n)	단순 순회만 가능

실전 예시

문제: 배열에서 두 수의 합이 target이 되는 쌍을 찾아라. (n = 100,000)

잘못된 풀이 - O(n²):

// 모든 쌍을 확인
for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        if (arr[i] + arr[j] == target) {
            return new int[]{i, j};
        }
    }
}
// 100,000 × 100,000 = 100억 번 → 시간 초과!

올바른 풀이 - O(n):

// HashMap 사용
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < n; i++) {
    int complement = target - arr[i];
    if (map.containsKey(complement)) {
        return new int[]{map.get(complement), i};
    }
    map.put(arr[i], i);
}
// n번만 순회 → 통과!

핵심 교훈

1. 데이터 크기를 먼저 확인한다
2. 허용되는 시간복잡도를 계산한다
3. 그에 맞는 알고리즘을 선택한다
4. 모르겠으면 더 빠른 알고리즘을 찾아야 한다

"정답은 맞는데 시간 초과"는 사실상 틀린 것이다!

---

🎓 핵심 정리

1. 시간복잡도는 데이터 증가에 따른 실행 시간 증가율
2. O(1)은 "상수 시간" - 데이터 크기와 무관하게 일정
3. 빠른 순서: O(1) > O(log n) > O(n) > O(n log n) > O(n²)
4. 코딩테스트에서는 시간복잡도 분석이 필수
5. 때로는 메모리를 더 사용해서 시간을 단축하는 것이 정답!

---

📚 다음 글 예고

다음에는 공간복잡도와 실전 알고리즘별 시간복잡도를 다루겠다.

• 재귀 함수의 시간복잡도 계산법
• DP(동적 프로그래밍)의 시간/공간 트레이드오프
• 그래프 알고리즘의 시간복잡도 분석

---

💬 마치며

시간복잡도는 처음에는 어렵게 느껴지지만, 문제를 풀다 보면 자연스럽게 익숙해진다.

"이 코드가 최악의 경우 몇 번이나 반복되나?"를 생각하는 습관을 들이자.

궁금한 점이나 추가로 다뤘으면 하는 주제가 있다면 댓글 남겨주기 바란다.

---

#코딩테스트 #알고리즘 #시간복잡도 #BigO #자료구조 #스택 #MinStack #Java