알고리즘 문제를 풀거나 실무에서 대용량 데이터를 다루다 보면, 기능은 완벽한데 "시간 초과"가 뜨거나 시스템이 버벅이는 경우를 마주합니다.
이때 우리가 가장 먼저 점검해야 할 것이 바로 시간 복잡도(Time Complexity)입니다. 오늘은 제가 공부한 내용을 바탕으로, O(n²)의 늪에서 빠져나와 O(n)으로 최적화하는 과정을 정리해보려 합니다.
1. 시간 복잡도란?
시간 복잡도는 알고리즘이 입력 크기(Input Size)에 따라 얼마나 많은 연산을 수행하는지를 나타내는 지표입니다.
단순히 "몇 초 걸린다"가 아니라, 수학적으로 실행 시간의 변화 추이를 표현하는 것이죠.
- 최악의 시간(Worst Case): 빅오(Big-O) 표기법의 기준이 되며, 가장 오래 걸릴 때를 가정합니다.
- 필요성: 효율적인 알고리즘 선택, 성능 개선 포인트 파악, 대규모 데이터 처리 가능 여부 판단
2. Big-O 표기법 총정리
Big-O 표기법은 데이터 입력 크기(n)가 무한대로 커질 때, 연산 횟수가 어떻게 증가하는지 상한선을 나타냅니다.
아래 표는 빠른 순서(위)에서 느린 순서(아래)로 정렬되어 있습니다.
| 표현 | 속도 / 이름 | 대표 예시 |
|---|---|---|
| O(1) | 상수 시간 (Fastest) | Stack의 Push/Pop, 배열 인덱스 접근 |
| O(log n) | 로그 시간 | 이진 탐색 (Binary Search) |
| O(n) | 선형 시간 | for문 1번 순회 |
| O(n log n) | 선형 로그 시간 | 퀵 정렬(Quick), 병합 정렬(Merge) |
| O(n^2) | 이차 시간 | 이중 for문, 삽입/거품 정렬 |
| O(2^n) | 지수 시간 (Exponential) | 피보나치 수열(재귀), 부분집합 구하기 |
| O(n!) | 팩토리얼 시간 (Slowest) | 외판원 순회 문제(TSP), 모든 순열 구하기 |
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n) < O(n!)
오른쪽으로 갈수록(아래로 갈수록) 실행 시간이 기하급수적으로 늘어나므로,
데이터가 많을 때는 O(n²) 이상의 알고리즘은 피하는 것이 좋습니다.
3. Case Study 01: 중복 없는 숫자 찾기
첫 번째 케이스는 "리스트에서 딱 한 번만 등장하는 숫자를 찾는 상황"입니다. 여기서 초보자들이 가장 많이 하는 실수가 발생합니다.
내가 작성한 문제의 코드 (O(n²))
for (int val : list) {
// 리스트 전체를 돌면서 val의 개수를 센다
if (Collections.frequency(list, val) == 1) {
System.out.println(val);
}
}
병목 분석
Collections.frequency(list, val) 메서드는 마법처럼 숫자를 세주는 게 아닙니다.
내부적으로 리스트 전체를 처음부터 끝까지 순회(O(n))합니다.
- 바깥쪽
for문: n회 반복 - 안쪽
frequency: n회 탐색 - 총 시간 복잡도: n × n = O(n²)
데이터가 10만 개라면, 100억 번의 연산을 하게 되어 프로그램이 멈출 수 있습니다.
최적화: HashMap 사용 (O(n))
이 문제를 해결하기 위해 HashMap을 사용하여 데이터를 미리 세어둡니다(Preprocessing).
// 1. O(n): 리스트를 한 번만 돌면서 개수를 맵에 저장
Map<Integer, Integer> countMap = new HashMap<>();
for (int val : list) {
countMap.put(val, countMap.getOrDefault(val, 0) + 1);
}
// 2. O(n): 맵을 확인하며 1번만 등장한 값 찾기
// (Map의 조회는 평균적으로 O(1)입니다)
이렇게 하면 루프가 중첩되지 않고 분리되어 O(n) + O(n) = O(2n), 즉 O(n)으로 획기적인 성능 향상이 일어납니다.
4. Case Study 02: 회문(Palindrome) 판별기
두 번째 케이스는 "문장을 단어별로 쪼개고, 회문이면 출력, 아니면 뒤집어서 출력"하는 로직입니다.
내가 작성한 코드 (O(n))
// 문장을 단어별로 쪼갬
for (int i = sens.length - 1; i >= 0; i--) {
// 각 단어(word)의 앞뒤를 비교 (회문 검사)
for (int e = 0; e < word.length() / 2; e++) {
if (word.charAt(e) != word.charAt(word.length() - 1 - e)) {
// ...
}
}
}복잡도 분석 (이건 병목이 아님)
얼핏 보면 for문 안에 for문이 있어 O(n²)처럼 보일 수 있습니다. 하지만 자세히 들여다보면 다릅니다.
- n: 단어의 개수
- k: 각 단어의 평균 길이
- N: 전체 문자열의 길이 (n × k)
우리는 모든 단어의 모든 글자를 한 번씩만 확인합니다. 즉, 전체 연산 횟수는 전체 글자 수(N)와 비례합니다.
입력 길이가 최대 10⁶이라도, O(N)은 충분히 효율적이므로 굳이 최적화할 필요가 없습니다.
5. 병목 현상 및 최적화 방안 요약
오늘 분석한 내용을 표로 정리해 보았습니다.
| 구분 | 병목 원인 | 기존 시간 복잡도 | 개선 후 |
|---|---|---|---|
| Case 01 (숫자 찾기) |
Collections.frequency에 의한 중복 순회 발생 |
O(n²) (매우 느림) |
O(n) (HashMap 사용) |
| Case 02 (회문 판별) |
없음 (구조적으로 효율적) | O(N) (전체 문자 수) |
변경 불필요 |
시간 복잡도 분석은 "내 코드가 왜 느린지"를 찾아내는 가장 중요한 핵심 이론입니다.
Case 01처럼 숨겨진 루프(frequency)를 찾아내 O(n)으로 만드는 것이 최적화의 핵심이고, Case 02처럼 구조적으로 이미 최적화된 코드를 구별해내는 안목 또한 중요한 것 같습니다.
'TEST > Testing' 카테고리의 다른 글
| Big-O, 왜 상수는 무시할까? (feat. Ω, Θ 표기법 정리)_Part 2 (0) | 2025.12.08 |
|---|