[코딩테스트] 시간복잡도와 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번만 증가한다.
생활 속 예시: 끝말잇기 사전에서 단어 찾기
정렬된 사전에서 "사과"라는 단어를 찾는다고 하자. 전체 페이지를 처음부터 보지 않고 다음처럼 찾는다:
- 사전 중간을 펼친다 → "자"로 시작하는 단어 발견 → "사"는 앞쪽에 있으니 앞쪽만 보면 된다
- 앞쪽 절반의 중간을 펼친다 → "마"로 시작 → "사"는 뒤쪽에 있으니 뒤쪽만 보면 된다
- 그 범위의 중간을 펼친다 → "사"로 시작하는 단어 발견!
이렇게 매번 절반씩 줄여나가는 방식이 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²)이 걸린다. 하지만 "분할 정복" 방식을 쓰면:
- 카드를 반으로 나눈다
- 각각을 정렬한다
- 정렬된 두 묶음을 합친다
이 과정을 반복하면 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)인지 판단하는 방법:
- 반복문이 없는가? ✅
- 재귀 호출이 없는가? ✅
- 실행 횟수가 입력 크기(n)와 무관한가? ✅
세 조건을 모두 만족하면 O(1)이다!
🌟 실생활 비유로 이해하기
사전에서 단어를 찾는 상황으로 각 시간복잡도를 비유해보자:
O(1) - 사전 첫 페이지 펴기
상황: 사전의 첫 페이지를 펼쳐서 첫 단어를 본다.
특징:
- 사전이 100페이지든 10,000페이지든 첫 페이지를 펴는 시간은 똑같다.
- 즉시 접근 가능하다.
O(log n) - 이진 탐색으로 단어 찾기
상황: 정렬된 사전에서 "컴퓨터"라는 단어를 찾는다.
방법:
- 사전 중간을 펼침 → "아"로 시작하는 단어 발견
- "컴"은 "아"보다 앞에 있으니 앞쪽 절반만 본다
- 앞쪽 절반의 중간을 펼침 → "사"로 시작하는 단어 발견
- "컴"은 "사"보다 앞에 있으니 또 앞쪽 절반만 본다
- 반복하면 몇 번 안에 찾는다!
특징:
- 사전이 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) 시간복잡도로 처리해야 한다:
push X: 정수 X를 스택에 넣는다pop: 스택에서 가장 위 정수를 빼고 출력top: 스택의 가장 위 정수를 출력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)
전략:
- 일반 스택(
stack): 실제 데이터 저장 - 최솟값 스택(
minStack): 각 시점의 최솟값 저장
구체적인 방법
push(x)할 때:
stack에 x를 넣는다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)로 즉시 반환
- "전체를 다시 확인"할 필요가 없다!핵심 아이디어 정리
- 각 시점마다 최솟값을 미리 계산해서 저장한다
- pop할 때 자동으로 이전 최솟값으로 돌아간다
- 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배 더 쓰는 대신
- 시간을 만 배 빠르게 만들었다!
언제 이런 선택을 하는가?
시간이 더 중요할 때 (대부분의 경우)
- 코딩테스트는 보통 시간 제한이 빡빡하고 메모리는 넉넉함
- 사용자 경험에서 느린 것은 치명적
메모리가 충분할 때
- 현대 컴퓨터는 메모리가 넉넉함
- 몇 MB 더 쓰는 것은 큰 문제가 아님
메모리가 부족할 때는?
- 임베디드 시스템, IoT 기기 등
- 이런 경우에만 메모리를 우선시
다른 트레이드오프 예시:
해시맵 (HashMap):
- 메모리 O(n) 사용
- 검색 시간 O(n) → O(1)로 단축
동적 프로그래밍 (DP):
- 메모리에 중간 결과 저장
- 중복 계산 제거로 시간 대폭 단축
캐시 (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번만 순회 → 통과!
핵심 교훈
- 데이터 크기를 먼저 확인한다
- 허용되는 시간복잡도를 계산한다
- 그에 맞는 알고리즘을 선택한다
- 모르겠으면 더 빠른 알고리즘을 찾아야 한다
"정답은 맞는데 시간 초과"는 사실상 틀린 것이다!
🎓 핵심 정리
- 시간복잡도는 데이터 증가에 따른 실행 시간 증가율
- O(1)은 "상수 시간" - 데이터 크기와 무관하게 일정
- 빠른 순서: O(1) > O(log n) > O(n) > O(n log n) > O(n²)
- 코딩테스트에서는 시간복잡도 분석이 필수
- 때로는 메모리를 더 사용해서 시간을 단축하는 것이 정답!
📚 다음 글 예고
다음에는 공간복잡도와 실전 알고리즘별 시간복잡도를 다루겠다.
- 재귀 함수의 시간복잡도 계산법
- DP(동적 프로그래밍)의 시간/공간 트레이드오프
- 그래프 알고리즘의 시간복잡도 분석
💬 마치며
시간복잡도는 처음에는 어렵게 느껴지지만, 문제를 풀다 보면 자연스럽게 익숙해진다.
"이 코드가 최악의 경우 몇 번이나 반복되나?"를 생각하는 습관을 들이자.
궁금한 점이나 추가로 다뤘으면 하는 주제가 있다면 댓글 남겨주기 바란다.
#코딩테스트 #알고리즘 #시간복잡도 #BigO #자료구조 #스택 #MinStack #Java
'Coding Test' 카테고리의 다른 글
| 코딩 테스트 명심해야할 사항 (0) | 2026.01.29 |
|---|---|
| 자료구조 - 원형 큐(Circular Queue) (0) | 2026.01.29 |
| 자료구조 - 큐(Queue) (0) | 2026.01.29 |
| 자료구조 - 스택(Stack) (0) | 2026.01.29 |
| 자료구조 - 배열(Array) vs 연결 리스트(Linked List) (0) | 2026.01.29 |