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

들어가며

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

이 글을 읽으면

• Big-O·Ω·Θ 정의와 루프 합·상각·재귀식으로 복잡도를 설명·검증하는 법을 배웁니다
• 병목 지점을 찾고 최적화하는 기법을 익힙니다
• 공간-시간 트레이드오프를 코드 수준 사례와 함께 이해하고, 캐시 계층·블로킹·분기 예측 같은 하드웨어 관점을 짚습니다
• 자료구조 선택으로 성능을 개선하는 전략을 이해합니다
• 코딩테스트와 프로덕션(관측·한계·스큐·회로 차단기 등)의 최적화 접근 차이를 감을 잡습니다

---

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

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

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

---

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

---

7. 시간 복잡도 분석의 내부

코딩테스트에서 자주 쓰는 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) 이라고 말할 수 있습니다. 즉 “최악 한 번”이 아니라 연산 시퀀스 전체를 놓고 평균 내는 관점입니다.

코딩테스트에서 유니온-파인드 경로 압축, 힙의 일부 연산 등도 상각으로 이해하면 “왜 맞는 로직인데 로그가 하나 줄어드나”를 설명하기 쉽습니다.

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

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는 증가율만 맞춘 뒤, 실측·제약(메모리, 캐시) 로 한 번 더 걸러야 합니다.

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

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

---

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

시간을 줄이기 위해 메모리를 더 쓰는 대표 패턴이 앞선 사례들과 맞닿아 있습니다. 누적 합 배열은 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·캐시 압박을 유발할 수 있습니다. 반면 정렬 기반은 메모리는 덜 쓰지만 비교 횟수가 늘 수 있습니다.

설계 질문 체크리스트

1. 동일한 부분 문제를 몇 번이나 다시 계산하는가 → 메모이제이션·DP 후보.
2. 질의가 많고 배열은 고정인가 → 전처리 + O(1) 질의 후보.
3. 최근 k개만 필요한가 → 슬라이딩 윈도·덱으로 공간 상한을 줄일 수 있는지 확인.
4. 전처리를 해두면 이후 연산이 충분히 많은가 → 빌드 비용을 상각할 만한지 계산.

---

9. 캐시 인지 알고리즘 설계

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

블로킹(타일링) 직관

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

데이터 배치: AoS vs SoA

Array of Structs(AoS) 는 객체 단위로 필드를 붙여 두고, Struct of Arrays(SoA) 는 필드별 배열을 나눕니다. 한 필드만 순회·벡터화할 때 SoA는 불필요한 필드를 메모리에서 건너뛰지 않아 캐시 대역폭을 아낍니다. 반면 객체 단위 업데이트가 많으면 AoS가 단순합니다.

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

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

소프트웨어 프리패치(개념만)

컴파일러·CPU가 다음에 읽을 가능성이 높은 주소를 미리 당겨오기도 합니다. 과도한 수동 프리패치는 오히려 버스 대역을 잡아먹을 수 있어, 프로파일로 확인된 핫패스에서만 다루는 것이 안전합니다.

False sharing (거짓 공유)

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

알고리즘 설계로 돌아가기

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

---

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

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

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

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

예측기가 “잘” 하는 경우

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

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

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

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

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

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

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

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

SIMD·벡터화와의 관계

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

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

실행 시 분기 빈도를 프로파일에 기록해 컴파일러가 핫 경로 배치를 최적화하는 기법입니다. 서비스 바이너리에서 p99를 줄이는 도구 중 하나이나, 빌드·배포 파이프라인이 복잡해질 수 있습니다.

벤치마크 방법 주의

• 한 번만 측정: 콜드 캐시·JIT·OS 노이즈에 휘둘릴 수 있습니다.
• 반복 측정 + 분산 확인: 평균만 보지 말고 최악·상위 백분위를 봅니다.
• 최적화(-O2/-O3) 와 비최적화(-O0) 혼동: 대회/실무 릴리스는 보통 최적화 켜짐을 전제로 합니다.

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

---

11. 프로덕션 최적화 패턴

온라인 저지는 보통 단일 프로세스·제한된 입력을 가정하지만, 서비스에서는 측정·운영·실패가 함께 따라옵니다. 알고리즘 최적화는 한 함수의 Big-O에서 끝나지 않고, 시스템 전체의 지연 분포와 장애 한계까지 포함합니다.

1) 측정 우선, 가정은 나중

프로덕션에서는 프로파일러·APM·분산 트레이스(OpenTelemetry 등) 로 병목을 확인한 뒤 수정합니다. “느리다”는 감으로 복잡한 알고리즘만 바꾸면 I/O·락·GC·DNS·TLS 같은 진짜 원인을 놓칠 수 있습니다. RED/USE 같은 방법론으로 어디가 병목인지 먼저 고정합니다.

2) 알고리즘과 시스템의 경계

• 배치·스트리밍: 한 번에 모두 메모리에 올리지 않고 청크·커서로 처리해 피크 메모리를 제어합니다.
• 인덱스: DB·검색엔진에서 B-Tree·해시·역인덱스로 조회를 O(log n) 또는 상수에 가깝게. 복합 인덱스 컬럼 순서가 쿼리 패턴과 맞지 않으면 풀스캔으로 퇴행합니다.
• 캐시 계층: Redis 등으로 읽기 반복을 줄이되, TTL·무효화·스탬피드 대비가 필수입니다.
• 사전 계산·머티리얼라이즈드 뷰: 읽기 많은 집계는 오프라인/주기적으로 미리 계산해 온라인 경로를 O(1)~O(log n) 로 유지합니다.

3) 동시성과 큐

• 스레드 풀·작업 큐: 요청 폭주 시 무제한 스레드 생성 대신 경계 있는 큐로 보호합니다.
• 백프레셔: 생산 속도가 소비를 압도하지 않게 큐 길이·차단·드롭 정책을 둡니다.
• 락 경합: 자료구조의 알고리즘이 좋아도 락 하나가 전부 막을 수 있습니다. 샤딩·락프리 구조는 별도 난제입니다.

4) 신뢰성과 한계

• 타임아웃·서킷 브레이커: 느린 의존성이 전파되지 않게 실패를 빨리 감지하고 대체 경로를 탑니다.
• 벌크헤드(Bulkhead): 스레드·커넥션 풀을 의존성별로 분리해 한 파트의 지연이 전체를 잠식하지 않게 합니다.
• 레이트 리밋: 토큰 버킷·누출 버킷 등으로 악성·버스트 트래픽을 제어합니다(알고리즘 문제의 “초당 제한”과 맞닿습니다).
• 아이템포턴시 키: 재시도 가능한 API는 중복 적용을 막는 키 설계가 필요합니다.

5) 데이터 스큐와 “평균이 아닌 꼬리”

코딩테스트는 보통 최악 복잡도를 맞추면 되지만, 서비스는 소수의 거대 사용자·핫 키가 p99를 지배합니다. 샤딩 키 선택, 핫스팟 완화, 캐시 파티셔닝이 필요해집니다.

6) 읽기 경로 vs 쓰기 경로

CQRS를 완전히 도입하지 않아도, 읽기는 캐시·복제, 쓰기는 검증·트랜잭션으로 분리하는 식의 현실적 절충이 흔합니다. 알고리즘적으로는 “같은 질의”라도 일관성 수준에 따라 구현이 달라집니다.

7) 코딩테스트와의 차이

테스트는 정확한 알고리즘 복잡도가 핵심인 경우가 많고, 실무는 p99 지연, 동시성, 데이터 스큐, 배포·롤백까지 봅니다. 이 글의 사례들은 사고 훈련으로 그대로 이어지되, 배포 환경에서는 관측 가능성과 함께 적용하는 것이 좋습니다.

8) 기능 플래그·점진 롤아웃

비용이 큰 코드 경로(새 추천 모델, 무거운 집계)는 플래그로 트래픽 일부만 켜 성능·정확도를 검증합니다. 알고리즘 교체가 운영 리스크를 동반할 때의 안전장치입니다.

---

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

입력 크기별 허용 복잡도

입력 크기 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)

---

13. 자료구조 선택 가이드

연산별 최적 자료구조

연산	자료구조	복잡도
중복 제거	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)

---

14. 마무리

결과와 교훈

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

1. 복잡도 분석: 제한 시간과 입력 크기로 허용되는 상한을 먼저 대략 계산하시기 바랍니다. Big-O는 증가율이며, 증명 스케치·상각으로 “왜 이 차수인가”를 말할 수 있으면 실수가 줄어듭니다. 상수·캐시·분기는 그 다음 층위에서 다룹니다.
2. 병목 찾기: 중첩 루프·숨은 정렬·반복 검사 등 한 단계를 줄일 수 있는지를 의심하시기 바랍니다.
3. 공간-시간: 전처리·해시·DP로 시간을 줄일 때 공간·캐시·worst-case를 함께 보시기 바랍니다. “공간을 늘렸는데 느려짐”은 흔한 함정입니다.
4. 자료구조 선택: “맞는 로직” 위에 연산당 비용이 맞는 구조(해시, 누적 합, 힙 등)를 올리시기 바랍니다. 연속 배열 vs 포인터 추적은 캐시까지 고려할 때 달라질 수 있습니다.
5. 알고리즘 개선: 누적 합, DP, 그리디, 투 포인터 등 문제 제한에 맞는 도구를 골라 쓰시기 바랍니다.
6. 실무로 이어질 때: 프로덕션에서는 프로파일링·관측·운영 한계·스큐가 추가되므로, 복잡도 개선과 동시에 측정을 기본으로 삼으시기 바랍니다.

정리: 구현이 맞아도 복잡도가 한계를 넘으면 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

심화 부록: 구현·운영 관점

이 부록은 앞선 본문에서 다룬 주제(「알고리즘 최적화 실전 사례 | 코딩테스트 시간 초과(TLE) 해결기」)를 구현·런타임·운영 관점에서 다시 압축합니다. 도메인별 세부 구현은 글마다 다르지만, 입력 검증 → 핵심 연산 → 부작용(I/O·네트워크·동시성) → 관측의 흐름으로 장애를 나누면 원인 추적이 빨라집니다.

내부 동작과 핵심 메커니즘

flowchart TD
  A[입력·요청·이벤트] --> B[파싱·검증·디코딩]
  B --> C[핵심 연산·상태 전이]
  C --> D[부작용: I/O·네트워크·동시성]
  D --> E[결과·관측·저장]

sequenceDiagram
  participant C as 클라이언트/호출자
  participant B as 경계(런타임·게이트웨이·프로세스)
  participant D as 의존성(API·DB·큐·파일)
  C->>B: 요청/이벤트
  B->>D: 조회·쓰기·RPC
  D-->>B: 지연·부분 실패·재시도 가능
  B-->>C: 응답 또는 오류(코드·상관 ID)

• 불변 조건(Invariant): 버퍼 경계, 프로토콜 상태, 트랜잭션 격리, FD 상한 등 단계별로 문장으로 적어 두면 디버깅 비용이 줄어듭니다.
• 결정성: 순수 층과 시간·네트워크·스케줄에 의존하는 층을 분리해야 테스트와 장애 분석이 쉬워집니다.
• 경계 비용: 직렬화, 인코딩, syscall 횟수, 락 경합, 할당·GC, 캐시 미스를 의심 목록에 둡니다.
• 백프레셔: 생산자가 소비자보다 빠를 때 버퍼·큐·스트림에서 속도를 줄이는 신호를 어디에 둘지 정의합니다.

프로덕션 운영 패턴

영역	운영 관점 질문
관측성	요청 단위 상관 ID, 에러율·지연 p95/p99, 의존성 타임아웃·재시도가 대시보드에 보이는가
안전성	입력 검증·권한·비밀·감사 로그가 코드 경로마다 일관적인가
신뢰성	재시도는 멱등 연산에만 적용되는가, 서킷 브레이커·백오프·DLQ가 있는가
성능	캐시·배치 크기·커넥션 풀·인덱스·백프레셔가 데이터 규모에 맞는가
배포	롤백 룬북, 카나리/블루그린, 마이그레이션·피처 플래그가 문서화되어 있는가
용량	피크 트래픽·디스크·FD·스레드 풀 상한을 주기적으로 검증하는가

스테이징은 데이터 양·네트워크 RTT·동시성을 프로덕션에 가깝게 맞출수록 재현율이 올라갑니다.

확장 예시: 엔드투엔드 미니 시나리오

앞선 본문 주제(「알고리즘 최적화 실전 사례 | 코딩테스트 시간 초과(TLE) 해결기」)를 배포·운영 흐름에 맞춰 옮긴 체크리스트입니다. 도메인에 맞게 단계 이름만 바꿔 적용할 수 있습니다.

1. 입력 계약 고정: 스키마·버전·최대 페이로드·타임아웃·에러 코드를 경계에 둔다.
2. 핵심 경로 계측: 요청 ID, 단계별 지연, 외부 호출 결과 코드를 로그·메트릭·트레이스에서 한 흐름으로 본다.
3. 실패 주입: 의존성 타임아웃·5xx·부분 데이터·락 대기를 스테이징에서 재현한다.
4. 호환·롤백: 설정/마이그레이션/클라이언트 버전을 되돌릴 수 있는지 확인한다.
5. 부하 후 검증: 피크 대비 p95/p99, 에러율, 리소스 상한, 알림 임계값을 점검한다.

handle(request):
  ctx = newCorrelationId()
  validated = validateSchema(request)
  authorize(validated, ctx)
  result = domainCore(validated)
  persistOrEmit(result, idempotentKey)
  recordMetrics(ctx, latency, outcome)
  return result

문제 해결(Troubleshooting)

증상	가능 원인	조치
간헐적 실패	레이스, 타임아웃, 외부 의존성, DNS	최소 재현 스크립트, 분산 트레이스·로그 상관관계, 재시도·서킷 설정 점검
성능 저하	N+1, 동기 I/O, 락 경합, 과도한 직렬화, 캐시 미스	프로파일러·APM으로 핫스팟 확인 후 한 가지씩 제거
메모리 증가	캐시 무제한, 구독/리스너 누수, 대용량 버퍼, 커넥션 미반납	상한·TTL·힙/FD 스냅샷 비교
빌드·배포만 실패	환경 변수, 권한, 플랫폼 차이, lockfile	CI 로그와 로컬 diff, 런타임·이미지 버전 핀
설정 불일치	프로필·시크릿·기본값, 리전	스키마 검증된 설정 단일 소스와 배포 매트릭스 표준화
데이터 불일치	비멱등 재시도, 부분 쓰기, 캐시 무효화 누락	멱등 키·아웃박스·트랜잭션 경계 재검토

권장 순서: (1) 최소 재현 (2) 최근 변경 범위 축소 (3) 환경·의존성 차이 (4) 관측으로 가설 검증 (5) 수정 후 회귀·부하 테스트.

배포 전에는 git add → git commit → git push 후 npm run deploy 순서를 권장합니다.

---

같이 보면 좋은 글 (내부 링크)

이 주제와 연결되는 다른 글입니다.

• 코딩 테스트에서 시간 복잡도 줄이는 체크리스트 | TLE 탈출
• C++ 알고리즘 최적화 | 시간복잡도·공간복잡도·트레이드오프 [#54-10]
• 정렬 문제 풀이 | 코딩 테스트 정렬 패턴 완벽 정리

---

이 글에서 다루는 키워드 (관련 검색어)

알고리즘, Algorithm, 최적화, 시간 복잡도, 코딩테스트, TLE, 실전 사례, 백준, 프로그래머스 등으로 검색하시면 이 글이 도움이 됩니다.