알고리즘 최적화 실전 사례 | 코딩테스트 시간 초과(TLE) 해결기

들어가며

“로직은 맞는데 시간 초과가 나요!” 코딩테스트에서 가장 답답한 순간입니다. 이 글에서는 실제 문제를 통해 시간 복잡도를 개선하여 TLE를 해결한 사례들을 공유합니다.

일상에 빗대면, 지도는 맞는데 매 교차로마다 전 수를 세는 길찾기와 비슷합니다. 방향은 맞지만 일을 중복으로 너무 많이 하면 제한 시간에 못 미칩니다.

이 글을 읽으면

• 시간 복잡도를 정확히 분석하는 방법을 배웁니다
• 병목 지점을 찾고 최적화하는 기법을 익힙니다
• 자료구조 선택으로 성능을 개선하는 전략을 이해합니다
• 실전 코딩테스트에서 바로 쓸 수 있는 패턴을 습득합니다

---

목차

1. 사례 1: 중복 제거 - O(n²) → O(n)
2. 사례 2: 구간 합 - O(n×q) → O(n+q)
3. 사례 3: 최단 경로 - O(V³) → O(E log V)
4. 사례 4: 부분 수열 - O(2ⁿ) → O(n²)
5. 사례 5: 문자열 매칭 - O(n×m) → O(n+m)
6. 복잡도 개선 패턴 정리
7. 마무리

---

1. 사례 1: 중복 제거 - O(n²) → O(n)

문제

문제 요지는 다음과 같습니다. 배열에서 중복을 제거하고 정렬하여 출력하세요.

• 입력: n ≤ 100,000
• 시간 제한: 1초

TLE 코드 (O(n²))

vector<int> arr(n);
vector<int> result;

for (int i = 0; i < n; i++) {
    bool isDuplicate = false;
    
    // 🚨 중복 검사: O(n)
    for (int j = 0; j < result.size(); j++) {
        if (arr[i] == result[j]) {
            isDuplicate = true;
            break;
        }
    }
    
    if (!isDuplicate) {
        result.push_back(arr[i]);
    }
}

sort(result.begin(), result.end()); // O(n log n)

// 전체: O(n²) + O(n log n) = O(n²)

시간 분석

• n = 100,000
• O(n²) = 10,000,000,000 = 100억 번 연산
• 1초에 약 1억 번 → 100초 소요 → TLE!

AC 코드 (O(n log n))

// 방법 1: set 사용
set<int> s(arr.begin(), arr.end()); // O(n log n)
vector<int> result(s.begin(), s.end()); // 이미 정렬됨

// 방법 2: 정렬 + unique
sort(arr.begin(), arr.end()); // O(n log n)
arr.erase(unique(arr.begin(), arr.end()), arr.end()); // O(n)

// 전체: O(n log n)

결과

• TLE 코드: 100초 (예상)
• AC 코드: 0.15초
• 개선율: 667배

---

2. 사례 2: 구간 합 - O(n×q) → O(n+q)

문제

배열의 구간 [L, R] 합을 q번 쿼리하세요.

• 입력: n, q ≤ 100,000
• 시간 제한: 1초

TLE 코드 (O(n×q))

int arr[100000];
int q;

for (int i = 0; i < q; i++) {
    int L, R;
    cin >> L >> R;
    
    int sum = 0;
    // 🚨 매번 구간을 순회: O(n)
    for (int j = L; j <= R; j++) {
        sum += arr[j];
    }
    
    cout << sum << '\n';
}

// 전체: O(n × q) = 100,000 × 100,000 = 100억

AC 코드 (O(n+q))

// 누적 합 (Prefix Sum) 전처리
int arr[100000];
long long prefix[100001]; // prefix[i] = arr[0] + ... + arr[i-1]

// 전처리: O(n)
prefix[0] = 0;
for (int i = 0; i < n; i++) {
    prefix[i+1] = prefix[i] + arr[i];
}

// 쿼리: O(1)
for (int i = 0; i < q; i++) {
    int L, R;
    cin >> L >> R;
    
    long long sum = prefix[R+1] - prefix[L]; // O(1)
    cout << sum << '\n';
}

// 전체: O(n + q) = 200,000

결과

• TLE 코드: 100초 (예상)
• AC 코드: 0.02초
• 개선율: 5000배

---

3. 사례 3: 최단 경로 - O(V³) → O(E log V)

문제

그래프에서 시작점 s에서 모든 정점까지의 최단 경로를 구하세요.

• 입력: V, E ≤ 100,000
• 시간 제한: 2초

TLE 코드 (O(V³))

// Floyd-Warshall: 모든 쌍 최단 경로
int dist[1000][1000];

// 초기화
for (int i = 0; i < V; i++) {
    for (int j = 0; j < V; j++) {
        dist[i][j] = (i == j) ? 0 : INF;
    }
}

// 간선 입력
for (int i = 0; i < E; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    dist[u][v] = w;
}

// Floyd-Warshall: O(V³)
for (int k = 0; k < V; k++) {
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
        }
    }
}

// V = 100,000 → V³ = 10¹⁵ → 불가능!

AC 코드 (O(E log V))

// Dijkstra: 단일 시작점 최단 경로
#include <queue>
#include <vector>

vector<pair<int,int>> adj[100000]; // {정점, 가중치}
int dist[100000];

void dijkstra(int start) {
    fill(dist, dist + V, INF);
    dist[start] = 0;
    
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    pq.push({0, start}); // {거리, 정점}
    
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        
        if (d > dist[u]) continue;
        
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

// 전체: O(E log V) = 100,000 × 17 = 1,700,000

결과

• TLE 코드: 불가능 (10¹⁵ 연산)
• AC 코드: 0.3초
• 개선율: 무한대 (실행 불가 → 실행 가능)

---

4. 사례 4: 부분 수열 - O(2ⁿ) → O(n²)

문제

배열에서 합이 K인 부분 수열의 개수를 구하세요.

• 입력: n ≤ 1,000, K ≤ 100,000
• 시간 제한: 1초

TLE 코드 (O(2ⁿ))

int arr[1000];
int count = 0;

// 모든 부분집합 탐색
void backtrack(int idx, int sum) {
    if (idx == n) {
        if (sum == K) count++;
        return;
    }
    
    // 포함
    backtrack(idx + 1, sum + arr[idx]);
    // 불포함
    backtrack(idx + 1, sum);
}

backtrack(0, 0);

// n = 1000 → 2¹⁰⁰⁰ → 불가능!

AC 코드 (O(n²))

// 동적 계획법
int dp[1001][100001]; // dp[i][j] = 처음 i개로 합 j를 만드는 경우의 수

dp[0][0] = 1;

for (int i = 0; i < n; i++) {
    for (int j = 0; j <= K; j++) {
        // i번째 원소를 포함하지 않음
        dp[i+1][j] += dp[i][j];
        
        // i번째 원소를 포함
        if (j + arr[i] <= K) {
            dp[i+1][j + arr[i]] += dp[i][j];
        }
    }
}

cout << dp[n][K];

// 전체: O(n × K) = 1,000 × 100,000 = 1억

결과

• TLE 코드: 불가능 (2¹⁰⁰⁰)
• AC 코드: 0.8초
• 개선율: 무한대

---

5. 사례 5: 문자열 매칭 - O(n×m) → O(n+m)

문제

텍스트에서 패턴이 나타나는 모든 위치를 찾으세요.

• 입력: 텍스트 길이 n ≤ 1,000,000, 패턴 길이 m ≤ 10,000
• 시간 제한: 2초

TLE 코드 (O(n×m))

string text, pattern;
vector<int> positions;

// 모든 위치에서 비교
for (int i = 0; i <= n - m; i++) {
    bool match = true;
    
    // 🚨 매번 패턴 전체 비교: O(m)
    for (int j = 0; j < m; j++) {
        if (text[i+j] != pattern[j]) {
            match = false;
            break;
        }
    }
    
    if (match) {
        positions.push_back(i);
    }
}

// 최악: O(n × m) = 1,000,000 × 10,000 = 100억

AC 코드 (O(n+m))

// KMP 알고리즘
vector<int> computeLPS(const string& pattern) {
    int m = pattern.size();
    vector<int> lps(m, 0);
    int len = 0;
    
    for (int i = 1; i < m; i++) {
        while (len > 0 && pattern[i] != pattern[len]) {
            len = lps[len - 1];
        }
        if (pattern[i] == pattern[len]) {
            len++;
        }
        lps[i] = len;
    }
    
    return lps;
}

vector<int> kmpSearch(const string& text, const string& pattern) {
    vector<int> lps = computeLPS(pattern); // O(m)
    vector<int> positions;
    
    int i = 0, j = 0;
    while (i < text.size()) {
        if (text[i] == pattern[j]) {
            i++;
            j++;
        }
        
        if (j == pattern.size()) {
            positions.push_back(i - j);
            j = lps[j - 1];
        } else if (i < text.size() && text[i] != pattern[j]) {
            if (j > 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
    
    return positions;
}

// 전체: O(n + m) = 1,010,000

결과

• TLE 코드: 100초 (예상)
• AC 코드: 0.05초
• 개선율: 2000배

---

6. 복잡도 개선 패턴 정리

패턴 1: 중복 제거 → set/unordered_set

// O(n²) → O(n log n) 또는 O(n)
for (int i = 0; i < n; i++) {
    for (int j = 0; j < result.size(); j++) {
        if (arr[i] == result[j]) { /* ... */ }
    }
}

// ↓

set<int> s(arr.begin(), arr.end()); // O(n log n)
// 또는
unordered_set<int> s(arr.begin(), arr.end()); // O(n)

패턴 2: 구간 쿼리 → 누적 합/세그먼트 트리

// O(n × q) → O(n + q)
for (int i = 0; i < q; i++) {
    int sum = 0;
    for (int j = L; j <= R; j++) {
        sum += arr[j]; // 매번 순회
    }
}

// ↓

// 누적 합 전처리
prefix[0] = 0;
for (int i = 0; i < n; i++) {
    prefix[i+1] = prefix[i] + arr[i];
}

// 쿼리: O(1)
int sum = prefix[R+1] - prefix[L];

패턴 3: 완전 탐색 → 동적 계획법

// O(2ⁿ) → O(n²) 또는 O(n³)
void backtrack(int idx, int sum) {
    if (idx == n) { /* ... */ }
    backtrack(idx + 1, sum + arr[idx]);
    backtrack(idx + 1, sum);
}

// ↓

// DP
int dp[n+1][K+1];
for (int i = 0; i < n; i++) {
    for (int j = 0; j <= K; j++) {
        dp[i+1][j] = dp[i][j];
        if (j >= arr[i]) {
            dp[i+1][j] += dp[i][j - arr[i]];
        }
    }
}

패턴 4: 정렬 활용

// O(n²) → O(n log n)
// 두 수의 합이 K인 쌍 찾기

// 완전 탐색
for (int i = 0; i < n; i++) {
    for (int j = i+1; j < n; j++) {
        if (arr[i] + arr[j] == K) { /* ... */ }
    }
}

// ↓

// 정렬 + 투 포인터
sort(arr.begin(), arr.end());
int left = 0, right = n - 1;

while (left < right) {
    int sum = arr[left] + arr[right];
    if (sum == K) {
        // 찾음
        left++;
        right--;
    } else if (sum < K) {
        left++;
    } else {
        right--;
    }
}

---

7. 시간 복잡도 체크리스트

입력 크기별 허용 복잡도

입력 크기 n	허용 복잡도	알고리즘 예시
n ≤ 10	O(n!)	순열, 완전 탐색
n ≤ 20	O(2ⁿ)	비트마스크 DP
n ≤ 500	O(n³)	Floyd-Warshall
n ≤ 5,000	O(n²)	버블 정렬, DP
n ≤ 100,000	O(n log n)	정렬, 세그먼트 트리
n ≤ 1,000,000	O(n)	선형 탐색, 해시
n ≤ 10,000,000	O(log n)	이진 탐색

복잡도 계산 예시

// 예제 1
for (int i = 0; i < n; i++) {          // O(n)
    for (int j = 0; j < n; j++) {      // × O(n)
        cout << i + j;                  // O(1)
    }
}
// 전체: O(n²)

// 예제 2
for (int i = 0; i < n; i++) {          // O(n)
    sort(arr.begin(), arr.end());       // × O(n log n)
}
// 전체: O(n² log n)

// 예제 3
for (int i = 0; i < n; i++) {          // O(n)
    if (binary_search(...)) {           // × O(log n)
        // ...
    }
}
// 전체: O(n log n)

---

8. 자료구조 선택 가이드

연산별 최적 자료구조

연산	자료구조	복잡도
중복 제거	set	O(n log n)
빠른 검색	unordered_set	O(1) 평균
정렬된 순서	set, map	O(log n)
구간 합	누적 합 배열	O(1) 쿼리
구간 최솟값	세그먼트 트리	O(log n)
최댓값 추적	priority_queue	O(log n)
LRU 캐시	list + unordered_map	O(1)

---

마무리

결과와 교훈

위 사례들에서 공통적으로 드러난 점은 다음과 같습니다.

1. 복잡도 분석: 제한 시간과 입력 크기로 허용되는 상한을 먼저 대략 계산하시기 바랍니다.
2. 병목 찾기: 중첩 루프·숨은 정렬·반복 검사 등 한 단계를 줄일 수 있는지를 의심하시기 바랍니다.
3. 자료구조 선택: “맞는 로직” 위에 연산당 비용이 맞는 구조(해시, 누적 합, 힙 등)를 올리시기 바랍니다.
4. 알고리즘 개선: 누적 합, DP, 그리디, 투 포인터 등 문제 제한에 맞는 도구를 골라 쓰시기 바랍니다.

정리: 구현이 맞아도 복잡도가 한계를 넘으면 TLE가 납니다. 디버깅에 들어가기 전에 종이에 복잡도를 적어 보시는 습관을 권장드립니다.

---

FAQ

Q1. 복잡도 계산이 어려워요.

중첩 루프를 세고, 각 루프의 반복 횟수를 곱하세요. 함수 호출도 고려해야 합니다.

Q2. O(n log n)과 O(n)의 차이가 크나요?

n이 작으면 차이가 미미하지만, n = 1,000,000이면 log n = 20이므로 20배 차이입니다.

Q3. 상수 시간 최적화도 필요한가요?

복잡도 개선이 우선입니다. 복잡도가 같다면 상수 최적화 (fast I/O 등)를 고려하세요.

---

관련 글

• 알고리즘 시간 복잡도 분석
• C++ 코딩테스트 입출력 최적화
• 동적 계획법 완벽 가이드

---

키워드

알고리즘, 시간 복잡도, 최적화, 코딩테스트, TLE, 시간 초과, 백준, 프로그래머스, 자료구조, 실전 사례, DP, 누적 합, KMP, Dijkstra