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

들어가며

“로직은 맞는데 시간 초과가 나요!” 코딩테스트에서 가장 답답한 순간입니다. 이 글에서는 실제 문제를 통해 시간 복잡도를 개선하여 TLE를 해결한 사례들을 공유합니다. 일상에 빗대면, 지도는 맞는데 매 교차로마다 전 수를 세는 길찾기와 비슷합니다. 방향은 맞지만 일을 중복으로 너무 많이 하면 제한 시간에 못 미칩니다.

이 글을 읽으면

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

---

코딩 테스트 준비하며 깨달은 것

알고리즘 문제를 풀다 보면 “이게 실무에 무슨 도움이 될까?” 하는 의문이 들 때가 있습니다. 저도 그랬습니다. 하지만 실제 프로젝트에서 성능 문제에 부딪히면, 알고리즘 지식이 얼마나 중요한지 깨닫게 됩니다. 예를 들어, 사용자 검색 기능이 느려서 고민하다가 해시 테이블을 적용하니 응답 시간이 10초에서 0.1초로 줄어든 경험이 있습니다. 코딩 테스트는 단순히 취업을 위한 관문이 아니라, 문제 해결 능력을 키우는 훈련장입니다. 처음엔 브루트 포스로 풀다가, 시간 복잡도를 개선하는 과정에서 “아, 이렇게 생각하면 되는구나” 하는 깨달음을 얻을 때의 쾌감은 말로 표현하기 어렵습니다. 이 글에서는 단순히 정답 코드만 제시하는 게 아니라, 문제를 어떻게 접근하고 최적화하는지 사고 과정을 함께 공유하겠습니다.

목차

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²))

다음은 cpp를 활용한 상세한 구현 코드입니다. 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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))

아래 코드는 cpp를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

// 방법 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))

다음은 cpp를 활용한 상세한 구현 코드입니다. 반복문으로 데이터를 처리합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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))

다음은 cpp를 활용한 상세한 구현 코드입니다. 반복문으로 데이터를 처리합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

// 누적 합 (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³))

다음은 cpp를 활용한 상세한 구현 코드입니다. 반복문으로 데이터를 처리합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

// 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))

다음은 cpp를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

// 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ⁿ))

다음은 cpp를 활용한 상세한 구현 코드입니다. 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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²))

다음은 cpp를 활용한 상세한 구현 코드입니다. 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

// 동적 계획법
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))

다음은 cpp를 활용한 상세한 구현 코드입니다. 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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))

다음은 cpp를 활용한 상세한 구현 코드입니다. 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

// 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

아래 코드는 cpp를 사용한 구현 예제입니다. 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

// 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: 구간 쿼리 → 누적 합/세그먼트 트리

다음은 cpp를 활용한 상세한 구현 코드입니다. 반복문으로 데이터를 처리합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

// 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: 완전 탐색 → 동적 계획법

다음은 cpp를 활용한 상세한 구현 코드입니다. 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

// 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: 정렬 활용

다음은 cpp를 활용한 상세한 구현 코드입니다. 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

// 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--;
    }
}

---

일상 비유로 이해하기: 시간 복잡도는 책에서 원하는 페이지를 찾는 방법으로 비유할 수 있습니다. O(1)은 목차를 보고 바로 찾기, O(log n)은 이진 탐색처럼 중간을 펼쳐 앞뒤 판단하기, O(n)은 첫 페이지부터 하나씩 넘기기, O(n²)은 모든 페이지 조합을 확인하기입니다.

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)	이진 탐색

복잡도 계산 예시

다음은 cpp를 활용한 상세한 구현 코드입니다. 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

// 예제 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