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

들어가며

“로직은 맞는데 시간 초과가 나요!” 코딩테스트에서 가장 답답한 순간입니다. 이 글에서는 전형적인 TLE 코드 다섯 가지를 시간 복잡도 관점에서 고친 뒤, 복잡도를 따지는 방법과 같은 차수 안에서 상수를 줄이는 하드웨어 관점(캐시, 분기 예측)을 차례로 다룹니다.

---

사례 1: 중복 제거 - O(n²) → O(n log 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
• 중복이 없으면 result가 계속 커지므로 비교는 약 n²/2 = 50억 번
• 채점 환경이 1초에 약 1억 번 정도 처리한다고 보면 수십 초 → TLE!
• 같은 코드를 이 글을 쓴 맥(clang -O2)에서 재 보면 약 1.3~1.7초였습니다. 컴파일러가 안쪽 비교 루프를 SIMD로 묶어 주기 때문이고, 그래도 1초 제한은 넘깁니다. 채점 서버의 컴파일 옵션에 따라 이보다 훨씬 느릴 수 있습니다.

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 코드: 중복이 적을수록 result가 커지므로 최악의 경우 약 n²/2 = 50억 번 비교가 필요합니다. “1초에 약 1억 번”이라는 경험칙으로도 제한을 수십 배 넘습니다.
• AC 코드: 정렬 기준 n log n ≈ 100,000 × 17 = 약 170만 번 비교로, 제한 안에 여유 있게 들어옵니다.
• 실제 실행 시간은 채점 서버와 입력에 따라 달라지므로, 직접 확인하려면 최대 크기 입력을 만들어 time ./a.out < input.txt로 재 보면 됩니다.
• 직접 재 본 값(Ubuntu 24.04 aarch64 컨테이너(8코어)의 g++ 13.3, 무작위 정수 100,000개로 중복이 거의 없는 입력, -O2): TLE 코드는 약 1,300ms였고, 같은 코드를 -O0으로 빌드하면 약 12,300ms였습니다. set 방식은 약 14ms(-O0 38ms), 정렬 + unique는 약 5ms(-O0 17ms)였고 세 방식의 결과(99,996개)는 모두 같았습니다. 같은 코드가 최적화 옵션만으로 약 10배 차이가 나므로, 채점 서버의 컴파일 옵션을 모르면 1초 안에 들어오는지 장담할 수 없습니다.

---

사례 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 코드: 쿼리마다 구간 길이만큼 더하므로 최악(모든 쿼리가 전체 구간) n × q = 100억 번 덧셈입니다. 이 맥(clang -O2)에서는 합 루프가 벡터화되어 약 0.4초에 끝났습니다. 최적화 옵션이 약하거나 구간 합 대신 분기가 낀 연산이면 훨씬 느려지므로, 안전한 쪽은 누적 합입니다(같은 입력에서 0.1ms).
• AC 코드: 전처리 n번 + 쿼리 q번으로 약 20만 번 연산입니다. 이 정도면 병목은 계산이 아니라 입출력이 되므로, ios::sync_with_stdio(false); cin.tie(nullptr);를 함께 넣는 편이 좋습니다.
• TLE 코드는 int sum에 합을 담아 원소 값이 크면 오버플로도 납니다. 누적 합을 long long으로 둔 것은 속도와 별개로 정답을 위해 필요한 부분입니다.
• 직접 재 본 값(Ubuntu 24.04 aarch64 컨테이너(8코어)의 g++ 13.3, n = q = 100,000이고 모든 쿼리가 전체 구간): 반복 합 방식은 -O2에서 약 1,335ms, -O0에서 약 14,864ms였고, 누적 합 방식은 -O2에서 약 0.06ms, -O0에서 약 0.65ms였습니다. 두 방식이 구한 합은 같았습니다.

---

사례 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 코드: V = 100,000이면 V³ = 10¹⁵ 번 연산이고, dist 배열만 V² × 4바이트 = 40GB라 메모리부터 들어가지 않습니다(위 코드의 dist[1000][1000]은 V가 1,000 이하일 때만 성립합니다).
• AC 코드: 간선마다 우선순위 큐 연산이 한 번 정도 일어나 약 E log V ≈ 170만 번 수준입니다.
• 핵심은 상수 최적화가 아니라 문제에 맞는 알고리즘 선택입니다. Floyd-Warshall은 모든 쌍의 최단 경로를 구하는 알고리즘이라, 시작점이 하나인 문제에는 필요 이상의 일을 합니다. 가중치가 음수가 아닐 때만 Dijkstra를 쓸 수 있다는 전제도 확인해야 합니다.
• 직접 재 본 값(Ubuntu 24.04 aarch64 컨테이너(8코어)의 g++ 13.3, -O2): V = 1,000, E = 100,000의 무작위 그래프에서 Floyd-Warshall은 약 562ms(-O0 약 9,035ms), 같은 그래프에서 0번 정점 하나만 시작점으로 한 Dijkstra는 약 0.36ms였고, 0번 정점에서 모든 정점까지의 거리는 두 방식이 모두 같았습니다. 정점 50,000개, 간선 100,000개(모든 정점에 닿는 그래프)에서 Dijkstra는 -O2로 약 4.2ms(-O0 약 29.7ms)였고, 이 크기의 Floyd-Warshall은 dist 배열만 약 10GB(V = 100,000이면 40GB)라 실행 자체가 불가능합니다.

---

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

문제

배열에서 합이 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·K))

// 동적 계획법 (원소가 0 이상의 정수라고 가정)
// dp[j] = 지금까지 본 원소들로 합 j를 만드는 경우의 수
const long long MOD = 1'000'000'007; // 경우의 수가 2^n까지 커지므로 보통 나머지를 요구합니다
vector<long long> dp(K + 1, 0);
dp[0] = 1;
for (int i = 0; i < n; i++) {
    // j를 큰 쪽에서 작은 쪽으로 돌아야 같은 원소를 두 번 쓰지 않습니다
    for (int j = K; j >= arr[i]; j--) {
        dp[j] = (dp[j] + dp[j - arr[i]]) % MOD;
    }
}
cout << dp[K];
// 전체: O(n × K) = 1,000 × 100,000 = 1억

결과

• TLE 코드: 2¹⁰⁰⁰ 개의 부분집합을 모두 도는 것은 어떤 하드웨어로도 끝나지 않습니다.
• AC 코드: 약 1억 번의 단순 덧셈이라 1초 제한에 빠듯하게 들어갑니다. 반복이 단순하고 메모리 접근이 순차적이라 가능한 수준입니다.
• 2차원 dp[1001][100001]을 그대로 잡으면 int만으로도 약 400MB라 대부분의 메모리 제한(128~512MB)을 넘습니다. 각 행이 바로 이전 행만 참조하므로 위처럼 1차원 배열 하나로 줄이는 것이 이 문제의 실질적인 핵심입니다.
• 직접 재 본 값(Ubuntu 24.04 aarch64 컨테이너(8코어)의 g++ 13.3, -O2): 완전탐색은 원소 20개에서 약 4ms, 24개에서 약 71ms, 28개에서 약 1,142ms였습니다. 원소가 4개 늘 때마다 약 16배씩 늘어나 2ⁿ으로 증가하는 것이 그대로 보이고, 세 경우 모두 DP가 구한 경우의 수와 일치했습니다(원소 값은 09, 합은 3n). 1차원 DP는 n = 1,000, K = 100,000에서 반복이 99,951,760회였고 -O2로 약 50ms, -O0으로 약 437ms였습니다. 위 “1초 제한에 빠듯하게 들어간다”는 설명은 -O0에서도 이 입력에서는 0.5초 안이었으므로 여유가 있었습니다. 다만 이 측정의 원소는 099 난수여서 dp[K]는 0이었고(합의 최댓값이 K보다 작음), 반복 횟수와 시간만 확인한 것입니다.

---

사례 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 코드: 최악 입력(예: 텍스트가 aaaa…a, 패턴이 aa…ab)에서는 거의 모든 위치에서 패턴 끝까지 비교하므로 n × m = 100억 번에 가까워집니다. 무작위 문자열에서는 첫 글자에서 대부분 어긋나 빨리 끝나기 때문에, 예제 입력만으로는 이 문제가 드러나지 않습니다.
• AC 코드: KMP는 텍스트 포인터 i가 뒤로 가지 않으므로 전처리 포함 약 2(n + m)번 비교로 끝납니다.
• 직접 재 본 값(Ubuntu 24.04 aarch64 컨테이너(8코어)의 g++ 13.3, 텍스트 a 1,000,000개, 패턴 a 9,999개 + b): 단순 비교는 -O2로 약 2,642ms, KMP는 약 1.1ms였고, 두 방식이 찾은 위치는 같았습니다(일치 없음). 무작위 소문자 텍스트에서 같은 길이의 패턴을 찾는 단순 비교는 약 0.8ms로, 대부분 첫 글자에서 어긋나 거의 시간이 들지 않았습니다. 이 입력만 보면 TLE 코드가 문제없어 보이는 이유입니다.

---

복잡도 개선 패턴 정리

그림: 실제 실행 결과 — 사례 1·2의 TLE 코드와 개선 코드를 같은 입력에서 재 본 시간이다. 컴파일러(clang -O2)가 단순 루프를 벡터화해서 절대 시간은 글의 경험칙보다 훨씬 짧게 나오며, 기계·컴파일러마다 다르다. (환경: macOS 27.0.1 · Apple clang 21.0.0)

패턴 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), 순서 없음

unordered_set은 평균 O(n)이지만 원소 순서를 보장하지 않으므로, 사례 1처럼 정렬된 출력이 필요하면 결국 다시 정렬해야 합니다.

패턴 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·K) (K: 목표 합)
void backtrack(int idx, int sum) {
    if (idx == n) { /* ... */ }
    backtrack(idx + 1, sum + arr[idx]);
    backtrack(idx + 1, sum);
}
// ↓
// DP (사례 4와 같은 1차원 롤링 배열)
vector<long long> dp(K + 1, 0);
dp[0] = 1;
for (int i = 0; i < n; i++) {
    for (int j = K; j >= arr[i]; j--) {
        dp[j] = (dp[j] + dp[j - arr[i]]) % MOD;
    }
}

패턴 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--;
    }
}

---

시간 복잡도 분석의 내부

코딩테스트에서 자주 쓰는 Big-O 표기는 “정확한 연산 횟수”가 아니라 입력 크기 n이 충분히 커질 때 증가율의 상한을 말합니다. 같은 O(n log n)이라도 상수 배·저차항이 다르면 실측 시간은 달라지지만, 차수(지수)가 한 단계만 올라가도 (예: O(n²) → O(n³)) 제한을 넘기 쉬우므로 먼저 점근적 차수를 맞추는 것이 우선입니다.

점근 표기: O, Ω, Θ

엄밀하게는 다음과 같이 정의합니다 (비음수 함수 T(n), f(n)에 대해).

• O(f(n)) (상한): 어떤 양의 상수 c, n₀가 존재하여 모든 n ≥ n₀에 대해 T(n) ≤ c·f(n) 이면 T(n) = O(f(n))입니다. “최악이 아니라 위로 감싸는 관계”입니다.
• Ω(f(n)) (하한): T(n) ≥ c·f(n) 인 경우. “적어도 이만큼 걸린다”는 하한 논증에 씁니다.
• Θ(f(n)) (동차): O(f)이면서 동시에 Ω(f)일 때. 즉 위·아래 모두 f에 묶이면 동일 점근 차수로 본다는 뜻입니다.

알고리즘 문제에서 “이 구현은 O(n²)이다”라고 말할 때는 보통 최악 경우의 상한을 O로 적는 관례에 가깝습니다. 평균·랜덤 입력 분석이 필요하면 별도로 기대값을 명시하는 것이 안전합니다.

“왜 곱하며, 왜 max로 묶는가”

• 순차 실행: 앞 단계가 T₁(n), 뒤가 T₂(n)이면 전체는 T₁(n) + T₂(n)이고, 점근적으로는 지배항이 큰 쪽이 남아 O(max(T₁, T₂)) 로 쓰는 경우가 많습니다.
• 중첩: 바깥이 n번, 안이 n번이면 합이 아니라 곱입니다. 반복 횟수의 곱집합이기 때문입니다. 한쪽이 O(log n)이면 O(n log n)처럼 곱으로 결합합니다.

증명 스케치 1: 이중 루프가 O(n²)인 이유

대표적인 형태로, i = 0..n-1, j = 0..n-1 이중 루프의 내부 본문 실행 횟수는 n×n = n²입니다. 내부가 O(1)이면 전체는 Θ(n²) 입니다.

조금 다른 형태로 j = 0..i 처럼 안쪽 상한이 i에 의존하면, 내부 실행 횟수는 ∑ᵢ₌₀ⁿ⁻¹ (i+1) = n(n+1)/2 = Θ(n²) 입니다. 등차수열 합 공식으로 정확한 계수까지 계산할 수 있어, “대략 절반”이지만 점근 차수는 여전히 n²입니다.

증명 스케치 2: 누적 합으로 구간 합 쿼리가 O(1)

전처리로 prefix[t] = arr[0] + … + arr[t-1] (길이 n+1)를 만든 뒤, 구간 [L, R]의 합은 prefix[R+1] − prefix[L] 입니다. 전처리는 O(n), 쿼리당 산술 두 번이므로 O(1)입니다. 따라서 q개 쿼리면 O(n + q) 가 됩니다. 여기서 “곱”이 아니라 “합”인 이유는 각 쿼리가 서로 독립적으로 O(1) 이기 때문입니다.

상각 분석(Amortized Analysis) — “가끔 비싼 연산”을 나누어 맞기

동적 배열의 push_back 을 예로 들면, 평균적으로는 O(1)에 가깝지만, 용량이 찰 때마다 재할당·복사로 한 번씩 O(n)이 듭니다. 이때 n번 삽입 전체를 보면 총 비용이 O(n) 수준이 되어, 삽입 1회당 상각 O(1) 이라고 말할 수 있습니다. 즉 “최악 한 번”이 아니라 연산 시퀀스 전체를 놓고 평균 내는 관점입니다.

유니온-파인드도 같은 관점으로 봅니다. 경로 압축과 랭크(또는 크기) 기준 합치기를 함께 쓰면 개별 find는 가끔 길어도 연산 m번 전체가 O(m·α(n))으로 묶이고, α는 역아커만 함수라 실용적인 n에서는 상수처럼 취급합니다.

마스터 정리로 재귀식 풀기 (스케치)

T(n) = a T(n/b) + f(n) (a ≥ 1, b > 1) 형태의 분할 정복이 자주 나옵니다. 직관적으로는 서브문제 a개, 각 크기 n/b, 분할·병합 비용 f(n) 입니다. 대표적으로 병합 정렬 T(n) = 2T(n/2) + O(n)은 O(n log n) 입니다. (세부는 케이스별로 f(n)과 n^(log_b a)를 비교하는 마스터 정리 표준 형태를 참고하시면 됩니다.)

다중 변수: O(n + m) vs O(n × m)

그래프에서 정점 n, 간선 m을 동시에 볼 때, 인접 리스트를 한 번 순회하는 비용은 모든 간선을 합하면 O(m), 정점 방문은 O(n)이라 합쳐 O(n + m) 인 경우가 많습니다. 반면 인접 행렬에서 모든 쌍을 도는 이중 루프는 O(n²) 입니다. “변수가 두 개일 때 곱인지 합인지”는 루프가 데카르트 곱을 도는지, 각 객체를 한 번씩만 보는지로 구분하는 습관이 중요합니다.

최선·평균·최악

동일한 알고리즘도 입력 분포에 따라 달라집니다. 예를 들어 퀵소트는 평균 O(n log n), 최악 O(n²)입니다. 문제 문구가 “랜덤 입력”인지 “이미 정렬된 입력”인지에 따라 어느 복잡도를 기준으로 설계할지가 달라집니다. 코딩테스트에서는 보통 최악을 기준으로 잡는 편이 안전합니다.

“상수 시간”이 항상 빠른가

해시 테이블의 평균 O(1)은 해시 계산·충돌 처리·메모리 접근 같은 상수가 큽니다. n이 작을 때는 O(n log n) 정렬이 캐시 친화적이라 더 빠른 경우도 있습니다. 즉 Big-O는 증가율만 맞춘 뒤, 실측·제약(메모리, 캐시) 로 한 번 더 걸러야 합니다.

반대로 차수 차이가 작아 보여도 무시할 수는 없습니다. n = 1,000,000이면 log₂ n ≈ 20이라 O(n log n)과 O(n)은 연산 횟수로 최대 20배 정도 벌어집니다. 실제 시간 차이는 상수와 메모리 접근 패턴에 따라 이보다 작거나 클 수 있습니다.

KMP가 O(n + m)인 직관 (증명 방향)

텍스트 길이 n, 패턴 길이 m에 대해, 선형 시간 전처리(LPS) 로 “불일치 시 되돌아갈 길이”를 미리 정해 두면, 텍스트 포인터 i는 감소하지 않고 끝까지 진행합니다. 패턴 포인터 j의 되감은 전체 합이 O(n + m) 으로 묶입니다(각 문자 비교가 “낭비 없이” 상한 횟수 안에서만 일어난다는 불변 조건으로 증명합니다). 세부 증명은 교과서를 참고하되, “i는 앞으로만 간다” 가 핵심입니다.

---

공간-시간 트레이드오프 패턴

시간을 줄이기 위해 메모리를 더 쓰는 대표 패턴이 앞선 사례들과 맞닿아 있습니다. 누적 합 배열은 O(n) 공간을 추가해 쿼리를 O(1)로 만들고, 해시맵은 추가 공간으로 탐색을 상수에 가깝게 만듭니다.

자주 쓰는 패턴

패턴	시간 이득	공간 비용	주의
전처리(누적 합, 스파스 테이블 등)	반복 쿼리 축소	보통 O(n)~O(n log n)	빌드 비용·메모리 한도
메모이제이션 / 해시 기반 중복 제거	재계산 제거	O(상태 수) 또는 O(n)	해시 worst, 캐시 미스
DP의 롤링 배열	이전 행만 필요한 경우	차원 축소로 O(n) 등	인덱스 실수 방지

예제 A: 빈도 세기 — 정렬 vs 해시

상황: 길이 n 배열에서 각 값의 등장 횟수를 여러 번 조회해야 한다고 합시다.

• 시간 우선·분포가 넓을 때: unordered_map (또는 값 범위가 좁으면 카운트 배열)으로 O(n) 전처리 후 조회 O(1) 평균.
• 공간을 줄이고 n이 작을 때: 정렬 후 런 길이 인코딩처럼 인접 동일 구간을 세면 추가 자료구조 없이 O(n log n) 전처리로 처리 가능.

같은 “빈도” 문제라도 값 범위·조회 횟수·메모리 한도에 따라 최선이 갈립니다.

예제 B: 구간 최솟값(RMQ) — 전처리 공간 늘리기

질의가 많다면 스파스 테이블 등으로 O(n log n) 전처리·공간을 쓰고 질의를 O(1) 또는 O(log n) 로 줄이는 선택이 있습니다. 반면 질의가 적으면 세그먼트 트리 없이 매번 구간을 도는 O(n)이 더 싸게 끝날 수 있습니다. 질의 수 q에 따라 O(q·n) vs O(n log n + q) 를 대략 비교하는 습관이 필요합니다.

예제 C: DP에서 공간만 줄이기 (롤링)

2차원 DP가 dp[i][j]에서 i-1 행만 참조한다면, 배열을 두 줄만 유지해 공간을 O(열 수) 로 줄일 수 있습니다. 시간 복잡도는 동일하지만, 캐시 워킹셋이 줄어 실측이 좋아지는 경우가 있습니다. 대신 인덱스 회전 실수가 늘므로 경계 테스트를 꼼꼼히 합니다.

예제 D: “미리 다 구해두기” vs “필요할 때만”

플로이드-워샬은 전 쌍 O(V³)로 모든 쌍 거리를 한 번에 얻습니다. 반면 쿼리가 소스-목적 한 쌍에만 집중된다면 다익스트라 한 번이 더 낫습니다. 전처리 비용을 한 번 지불할지, 요청마다 계산할지는 쿼리 패턴에 달려 있습니다.

“공간을 더 썼는데 왜 느려지나”

메모리를 크게 잡으면 RAM 용량뿐 아니라 캐시 적중률이 떨어져 오히려 느려질 수 있습니다. 또 불필요한 복사(예: 매번 전체 벡터 복제)는 공간·시간을 동시에 낭비합니다. 공간을 늘릴 때는 접근 패턴이 순차적인지, 동시에 필요한 최소 크기인지 함께 검토합니다.

해시는 worst-case에서 선형으로 퇴행할 수 있으며, 큰 버킷 배열은 TLB·캐시 압박을 유발할 수 있습니다. 반면 정렬 기반은 메모리는 덜 쓰지만 비교 횟수가 늘 수 있습니다.

---

캐시 인지 알고리즘 설계

CPU는 메인 메모리보다 캐시(L1/L2/L3) 에 가까운 데이터를 훨씬 빠르게 읽습니다. 알고리즘 복잡도가 같아도 메모리 접근 순서에 따라 실제 시간이 크게 달라질 수 있습니다. Big-O는 연산 횟수의 점근에 가깝으며, 실제 기계에서는 메모리 계층이 별도의 비용 모델입니다.

메모리 계층의 직관 (수치는 기기마다 다름)

흔히 L1 ≪ L2 ≪ L3 ≪ DRAM 순으로 지연과 용량이 갈립니다. 한 번의 메인 메모리 접근이 수십~수백 사이클에 달할 수 있어, 같은 O(n)이라도 순차 스캔이 랜덤 접근보다 훨씬 유리한 경우가 많습니다. 코딩테스트에서도 제한이 빡빡한 선형 문제에서 체감됩니다.

지역성(Locality)

• 시간 지역성: 최근에 쓴 주소를 곧 다시 쓴다 (루프 내 누적 변수).
• 공간 지역성: 인접 주소를 연달아 읽는다 (배열 순차 순회).

캐시는 보통 캐시 라인(예: 64바이트) 단위로 가져옵니다. 따라서 연속된 배열 스캔은 한 번 가져온 라인을 여러 원소가 나눠 쓰지만, 한 원소만 촘촘히 띄엄띄엄 접근하면 라인 단위 이득이 줄어듭니다.

행렬 순회 방향과 레이아웃

행 우선 저장(a[i][j]에서 j가 연속)일 때 바깥 루프가 i, 안이 j이면 연속 주소를 읽습니다. 반대로 j를 바깥에 두고 i를 안쪽에 두면 열 방향으로 뛰어다니며 같은 열 스트라이드가 커져 캐시 미스가 늘 수 있습니다.

// 예: n×n 행렬 합 — 행 우선 저장 가정 시 i 바깥, j 안이 유리한 경우가 많음
long long sum = 0;
for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
        sum += a[i][j];
    }
}

직접 재 본 값(Ubuntu 24.04 aarch64 컨테이너(8코어)의 g++ 13.3 -O2, 4096×4096 int 합, 두 번 반복해 거의 같은 값): 행 우선 순회가 약 4.1ms, 열 우선 순회가 약 33.9ms로 8배 넘게 느렸습니다. 같은 합을 구하는 코드인데 접근 순서만 다릅니다.

블로킹(타일링) 직관

행렬 곱 C = A×B 는 기본 삼중 루프가 O(n³)입니다. 복잡도는 같아도 캐시(보통 L1/L2)에 들어갈 만한 작은 타일(블록) 단위로 나눠 곱하면 재사용이 좋아져 실측이 좋아질 수 있습니다. 즉 알고리즘 차수는 유지하면서 상수 승수를 줄이는 전형적인 캐시 차원 최적화입니다. (고성능 수치 라이브러리가 블록 크기를 튜닝하는 이유입니다.)

데이터 배치: AoS vs SoA

Array of Structs(AoS) 는 객체 단위로 필드를 붙여 두며, Struct of Arrays(SoA) 는 필드별 배열을 나눕니다. 한 필드만 순회·벡터화할 때 SoA는 그 필드만 연속으로 읽으므로, 쓰지 않는 필드까지 캐시 라인에 끌려오는 AoS보다 캐시 대역폭을 아낍니다. 반면 객체 단위 업데이트가 많으면 AoS가 단순합니다.

직접 재 본 값(Ubuntu 24.04 aarch64 컨테이너(8코어)의 g++ 13.3 -O2): int 8개(32바이트)짜리 구조체 1,000만 개에서 필드 하나만 5번 합하면 AoS가 약 30ms, 그 필드만 따로 둔 int 배열(SoA)이 약 13ms로 2배 넘게 빨랐습니다. 합산에 쓰지 않는 7개 필드가 캐시 라인을 함께 차지하기 때문으로 보이며, 객체 전체를 쓰는 연산이라면 이 차이는 줄거나 뒤집힙니다.

포인터 따라가기와 캐시 미스

연결 리스트·트리는 노드가 흩어져 있어 추가 포인터 역참조마다 미스 가능성이 커집니다. 같은 O(n) 순회라도 배열(예: 배열 기반 힙, vector)은 연속 메모리라 노드 기반 구조보다 캐시에 유리한 경우가 많습니다. 자료구조 선택이 복잡도와 별개로 실측에 영향을 줍니다.

직접 재 본 값(Ubuntu 24.04 aarch64 컨테이너(8코어)의 g++ 13.3 -O2): int 100만 개를 20번 순회해 합하면 std::vector가 약 5ms, 같은 값을 담은 std::list가 약 26~27ms로 약 5배 느렸습니다. 이 실험의 list 노드는 순서대로 할당되어 메모리에서 가까이 놓였는데도 이 차이가 났습니다. 노드마다 값 외에 앞뒤 포인터가 있어 캐시 라인당 담기는 원소가 적고, 다음 노드 주소를 읽어야 다음 원소를 알 수 있기 때문이라고 설명할 수 있지만, 이 실험이 각 요인의 기여를 나눠 측정한 것은 아닙니다. 노드가 메모리 여기저기에 흩어지면 차이는 더 커질 수 있습니다.

프리패치(개념만)

CPU의 하드웨어 프리페처는 순차·일정 간격 접근을 감지해 다음 캐시 라인을 미리 가져오고, 소프트웨어 프리패치(__builtin_prefetch 등)는 프로그래머나 컴파일러가 직접 힌트를 넣는 방식입니다. 과도한 수동 프리패치는 오히려 버스 대역을 잡아먹을 수 있어, 프로파일로 확인된 핫패스에서만 다루는 것이 안전합니다.

False sharing (거짓 공유)

서로 다른 코어가 같은 캐시 라인에 있는 다른 변수를 갱신하면 캐시 일관성 때문에 성능이 크게 떨어질 수 있습니다. 병렬 최적화 시 패딩으로 라인을 분리하는 등의 기법이 나오는 이유입니다. (코딩테스트 단일 스레드에서는 드물고, 실무 병렬화에서 중요합니다.)

직접 재 본 값(Ubuntu 24.04 aarch64 컨테이너(8코어)의 g++ 13.3 -O2, 스레드 2개): 각 스레드가 자기 atomic<long long>을 1억 번 fetch_add(relaxed)할 때, 두 변수가 같은 캐시 라인(바로 옆)에 있으면 약 660ms, 64바이트 경계로 떼어 놓으면 약 181ms로 3.6~3.7배 차이가 났습니다. 두 스레드는 서로 다른 변수만 건드리는데도 캐시 라인을 주고받느라 느려진 것입니다.

알고리즘 설계로 돌아가기

• 인접 리스트가 유리한 희소 그래프 vs 행렬이 단순한 조밀 그래프: 메모리·캐시와 함께 고릅니다.
• 정렬된 배열 + 이진 탐색은 해시보다 느릴 수 있으나 순차 국소성이 좋아 작은 n에서 이기는 경우가 있습니다.

---

분기 예측과 마이크로 최적화

현대 CPU는 파이프라인을 깊게 쌓아 처리량을 올립니다. 분기문의 결과를 기다리면 파이프라인이 비는데, 이를 줄이기 위해 분기 예측기(branch predictor) 가 다음에 어떤 경로가 실행될지를 추측합니다. 예측이 빗나가면(misprediction) 수십 사이클의 페널티가 생길 수 있어, 핫 루프에서 if의 패턴이 성능을 가릅니다.

파이프라인과 분기 페널티 직관

분기가 해결(resolve)되기 전까지는 잘못된 경로로 들어간 명령을 되돌려야 합니다. 예측이 틀리면 페치·디코드 단계에서 낭비가 커집니다. 따라서 복잡도는 O(n)인데 랜덤 데이터에만 느린 코드가 나올 수 있습니다.

예측기가 “잘” 하는 경우

• 한쪽 분기(예: true)가 압도적으로 많으면 예측기가 그쪽을 학습해 비용이 작습니다.
• 규칙적인 패턴(예: 거의 항상 짝수, 거의 항상 오름차순)이면 예측이 안정적입니다.
• 데이터가 이미 정렬·그룹화되어 있으면 같은 조건이 연속되어 분기 히스토리에 유리해질 수 있습니다.

예측기가 “힘들어” 하는 경우

• 50:50에 가까운 무작위 분기는 예측 실패율이 높아질 수 있습니다.
• 입력 순서가 매번 바뀌는 조건(예: 랜덤 스왑 후 비교)은 패턴이 약합니다.
• 간접 분기(함수 포인터·가상 함수 다형성)는 추가 비용이 붙을 수 있습니다.

직접 재 본 값(Ubuntu 24.04 aarch64 컨테이너(8코어)의 g++ 13.3 -O2): 값이 0~255인 32,768개 int에서 if (x >= 128) s += x를 20,000번 반복해 합하면, 무작위 순서 데이터는 약 575ms, 같은 값을 정렬한 데이터는 약 328ms였습니다. 정렬만 했는데 약 1.75배 차이가 났습니다. 앞의 clang 측정에서는 두 값이 거의 같았으므로, 이 효과는 컴파일러가 분기를 남겨 두었는지에 따라 달라집니다.

코드 레벨 아이디어 (과용 금지)

데이터 정렬·전처리로 불필요한 분기 자체를 줄이는 것이 가장 깨끗합니다. 예를 들어 중복 제거 후 한 번만 특수 케이스를 처리하면, 루프 안의 if가 사라질 수 있습니다.

컴파일러 확장(예: GCC __builtin_expect)이나 분기 없는 산술은 프로파일로 핫패스가 확인된 뒤에만 검토하는 것이 안전합니다. 힌트는 실제 분포와 일치할 때만 의미가 있습니다.

// 예: 분기 대신 (0/1)에 대한 산술 — 가독성과 유지보수와 트레이드오프
int penalty = (x < threshold) * cost_if_small;  // 패턴이 단순할 때만

CMOV 계열의 조건부 이동으로 분기를 없애는 방식도 있으나, 컴파일러가 이미 비슷한 일을 하기도 하며, 가독성이 떨어질 수 있습니다.

SIMD·벡터화와의 관계

짧은 루프가 자동 벡터화되면 분기가 마스크 연산으로 바뀌기도 합니다. 반대로 데이터 의존 분기가 많으면 벡터화가 막힐 수 있습니다. “분기 줄이기”가 곧 SIMD 친화로 이어지는 경우가 있습니다.

프로파일 유도 최적화(PGO)

실행 시 분기 빈도를 프로파일에 기록해 컴파일러가 핫 경로 배치를 최적화하는 기법입니다. GCC·Clang(-fprofile-generate/-fprofile-use) 모두 지원하며 큰 서비스 바이너리의 처리량을 올리는 데 쓰이지만, 빌드·배포 파이프라인이 복잡해질 수 있습니다.

벤치마크 방법 주의

• 분기 예측 효과는 코드 모양에 따라 사라지기도 합니다. 위 실행 화면의 if (x >= 128) s += x 합계는 무작위 데이터와 정렬 데이터가 6.0ms와 5.7ms로 거의 같았습니다. clang -O2가 분기 없는 연산(조건부 선택·벡터화)으로 바꿨기 때문입니다. 분기가 정말 남는 루프(안에서 함수 호출 등)에서만 정렬 효과가 보입니다.

• 행렬 순회 방향 차이는 뚜렷했습니다. 4096×4096 int 합이 행 우선 46ms, 열 우선 약 55ms(913배)였습니다.

• 한 번만 측정: 콜드 캐시·JIT·OS 노이즈에 휘둘릴 수 있습니다.

• 반복 측정 + 분산 확인: 평균만 보지 말고 최악·상위 백분위를 봅니다.

• 최적화(-O2/-O3) 와 비최적화(-O0) 혼동: 대회/실무 릴리스는 보통 최적화 켜짐을 전제로 합니다.

복잡도 개선이 끝난 뒤에도 여유가 없을 때 상수 승수를 줄이는 보조 수단으로 이해하면 됩니다.

---

프로덕션에서는 무엇이 달라지나

온라인 저지는 단일 프로세스와 정해진 입력 범위를 가정하지만, 서비스에서는 한 함수의 Big-O보다 시스템 전체의 지연 분포가 문제가 되는 경우가 많습니다.

먼저 측정합니다. 프로파일러, APM, 분산 트레이스(OpenTelemetry 등)로 병목을 확인하지 않고 “느리다”는 감만으로 알고리즘을 바꾸면, 실제 원인이 I/O·락 경합·GC·네트워크 왕복이었을 때 아무것도 나아지지 않습니다.

알고리즘 관점이 그대로 쓰이는 곳도 많습니다. DB 인덱스(B-Tree)는 풀스캔 O(n)을 O(log n) 조회로 바꾸는 것이고, 복합 인덱스의 컬럼 순서가 쿼리 조건과 맞지 않으면 다시 풀스캔으로 돌아갑니다. 읽기가 많은 집계를 주기적으로 미리 계산해 두는 것은 앞에서 본 누적 합 전처리와 같은 공간-시간 트레이드오프입니다. 큰 데이터를 한 번에 메모리에 올리지 않고 청크나 커서로 나눠 처리하는 것은 피크 메모리를 제어하는 방법입니다.

반면 코딩테스트에는 없는 문제도 있습니다. 서비스에서는 소수의 거대 사용자나 핫 키가 p99 지연을 지배하는 데이터 스큐가 흔하고, 평균 복잡도가 좋아도 락 하나가 모든 요청을 직렬화할 수 있습니다. 이런 문제는 복잡도 분석만으로는 보이지 않으므로 관측 데이터와 함께 판단해야 합니다.

---

입력 크기별 허용 복잡도

시간 제한 1초, “1초에 약 1억 번 단순 연산”이라는 경험칙을 기준으로 한 대략적인 상한입니다. 채점 환경과 상수에 따라 경계는 달라집니다.

입력 크기 n	허용 복잡도	알고리즘 예시
n ≤ 10	O(n!)	순열, 완전 탐색
n ≤ 20	O(2ⁿ)	비트마스크 DP
n ≤ 500	O(n³)	Floyd-Warshall
n ≤ 5,000	O(n²)	2차원 DP
n ≤ 100,000~1,000,000	O(n log n)	정렬, 세그먼트 트리
n ≤ 10,000,000	O(n)	선형 탐색, 투 포인터
n이 그 이상(예: 10¹⁸)	O(log n) 또는 O(1)	이진 탐색, 분할 거듭제곱, 수식

복잡도 계산 예시

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

예제 2처럼 루프 안에 숨은 정렬이나 함수 호출이 있으면 그 비용까지 곱해야 합니다. TLE가 났을 때 가장 먼저 찾을 것이 이런 숨은 곱셈입니다.

---

연산별 자료구조

연산	자료구조	복잡도
중복 제거(정렬 유지)	set 또는 정렬 + unique	O(n log n)
존재 여부 검색	unordered_set	평균 O(1), 최악 O(n)
정렬된 순서로 삽입·삭제	set, map	O(log n)
구간 합(배열 고정)	누적 합 배열	전처리 O(n), 쿼리 O(1)
구간 최솟값(갱신 있음)	세그먼트 트리	O(log n)
최댓값 추적	priority_queue	삽입·삭제 O(log n), 조회 O(1)
LRU 캐시	list + unordered_map	평균 O(1)

---

TLE가 나면 먼저 할 일

구현이 맞아도 복잡도가 한계를 넘으면 TLE가 납니다. 디버깅에 들어가기 전에 입력 크기와 제한 시간으로 허용 복잡도를 먼저 계산하고, 코드의 복잡도를 종이에 적어 비교해 보는 것이 가장 빠른 확인 방법입니다. 차수를 맞춘 뒤에도 여유가 없다면 그때 입출력, 메모리 접근 순서, 분기 패턴 같은 상수 요인을 봅니다.

---

---

같이 보면 좋은 글

• C++ REST API 성능 최적화 예제