코딩 테스트에서 시간 복잡도 줄이는 체크리스트 | TLE 탈출

들어가며

코딩테스트 시간복잡도 줄이기는 “더 빠른 알고리즘을 외운다”기보다, 제한 조건(N의 범위)과 현재 복잡도를 맞춰 보는 습관에서 시작합니다. 대부분의 TLE(Time Limit Exceeded)는 불필요한 이중·삼중 루프 또는 같은 구간을 반복 계산해서 생깁니다. 이 글은 시험장에서 바로 쓸 수 있게 체크리스트 형태로 정리했습니다. 수치는 대략적인 상한이며, 상수·언어·채점기 환경에 따라 여유가 달라질 수 있습니다. 체크리스트는 외우는 것보다 문제 읽고 30초 안에 한 번 훑는 습관으로 쓰는 것이 가장 효과적입니다.

이 글을 읽으면

• N 규모별로 허용되는 복잡도 대역을 직관으로 잡습니다
• O(N²) 후보를 O(N log N)으로 내리는 전형적 패턴을 떠올립니다
• 해시맵·정렬·누적합·이진 탐색 중 무엇을 쓸지 빠르게 고릅니다
• 점화식·마스터 정리·치환법으로 재귀·분할 정복의 차수를 검증합니다
• 상각 분석·공간 최적화·프로덕션 프로파일링으로 “같은 Big-O인데 느린” 원인을 나눕니다

---

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

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

개념 설명

대략적인 가이드 (1초 제한, 단순 연산 가정)

N (대략)	여유 있음	위험
≤ 20	O(N!)도 간신히	—
≤ 200	O(N³)	O(N⁴)
≤ 2×10³	O(N²)	O(N² log N)은 보통 OK
≤ 10⁵	O(N log N)	O(N²)은 거의 불가
≤ 10⁶	O(N)	O(N log N)은 종종 가능
≥ 10⁷	O(N) 선형·단순	O(N log N)도 빡빡할 수 있음
먼저 할 일: 문제에서 N, Q(쿼리 수), 문자열 길이를 밑줄 긋고, 현재 풀이의 복잡도를 한 줄로 씁니다. 이게 코딩테스트 시간복잡도 줄이기의 첫 단계입니다.

복잡도 계산 체크리스트

# 예제 1: 이중 루프
for i in range(n):
    for j in range(n):
        # O(N²)
        pass
# 예제 2: 정렬 + 순회
arr.sort()  # O(N log N)
for x in arr:  # O(N)
    # 전체: O(N log N)
    pass
# 예제 3: 중첩 루프 + 해시맵
for i in range(n):  # O(N)
    for j in range(m):  # O(M)
        if key in hashmap:  # O(1)
            # 전체: O(N × M)
            pass
# 예제 4: 쿼리 + 세그먼트 트리
# 전처리: O(N log N)
# 쿼리 Q개: O(Q log N)
# 전체: O(N log N + Q log N)

복잡도 분석 예제 심화

아래는 한 줄로 차수를 확정하기 어려울 때 자주 쓰는 미시 분석입니다. 공통 원칙은 “바깥 루프가 도는 횟수 × 안쪽이 한 번 도는 데 드는 최악 비용”을 합산하는 것이고, 조기 종료·누적 포인터가 있으면 상한을 따로 잡습니다.

예제 A: i에 따라 안쪽 한계가 바뀌는 이중 루프

# i = 0..n-1, j = i+1..n-1  → 쌍 (i,j)의 개수는 C(n,2) = n(n-1)/2
# 시간: Θ(n²), 공간: O(1)
for i in range(n):
    for j in range(i + 1, n):
        pass

예제 B: 합이 n에 도달할 때까지 — while 두 개

# i, j가 각각 최대 n까지 증가하지만, i+j가 n을 넘지 않는 패턴 등은
# “단계 수”를 직접 세는 편이 안전합니다.
i, j = 0, 0
while i < n:
    while j < n and cond(i, j):
        j += 1  # j는 전체 실행에서 최대 n번만 증가
    i += 1
# j가 바깥 루프마다 리셋되지 않으면 투 포인터류로 전체 O(n)인 경우가 많음

j가 리셋되지 않고 한 방향으로만 움직이면, j의 증가 횟수 전체가 O(n)으로 묶이는 투 포인터 상각이 됩니다. 반대로 매 i마다 j를 0으로 돌리면 다시 O(n²)이 됩니다.

예제 C: 재귀 + 구간 합 — 트리 높이 × 분할 비용

# 배열을 반으로 쪼개며 호출: 높이 O(log n), 레벨당 합쳐지는 비용이 Θ(n)이면 전체 Θ(n log n)
def rec(lo, hi):
    if lo == hi:
        return base(a[lo])
    mid = (lo + hi) // 2
    return merge(rec(lo, mid), rec(mid + 1, hi))  # merge가 선형이면 레벨당 Θ(n)

예제 D: sqrt 블록 분할 (루트 분할)

n원소를 √n크기 블록으로 나누면, 블록 개수와 블록 내부가 각각 √n이라 질의당 O(√n)이 되는 구조가 자주 나옵니다. Mo’s algorithm 등 오프라인 쿼리에서도 같은 “제곱근 균형”이 등장합니다.

예제 E: 비트 연산 한 번이 Θ(1)가 아닐 때

언어·하드웨어에서는 큰 정수(예: 수백 자리) 연산을 한 스텝으로 두면 안 됩니다. 비트 길이 L에 대해 덧셈·곱셈 비용을 따로 두는 비트 복잡도 관점이 필요합니다.

예제 F: 정렬된 배열에서 lower_bound를 루프마다

# 매번 이진 탐색 O(log n) × 바깥 n번 → O(n log n)
for x in queries:
    bisect_left(a, x)

정렬을 한 번만 하고, 이후 패턴이 투 포인터로 바뀌면 O(n)까지 내려갈 수 있는지 확인합니다.

---

점화식·마스터 정리

코딩 테스트에서 루프 중첩으로 복잡도를 세는 것과 별개로, 분할 정복·재귀 DP는 점화식으로 정리하는 편이 빠릅니다. 여기서는 대표적인 점근 분석 도구인 마스터 정리(Master Theorem)와, 정리가 깨질 때 쓰는 대체 기법을 함께 정리합니다.

마스터 정리(균등 분할 가정)

크기 n인 문제를 a개의 부분 문제로 나누고, 각 부분 문제 크기가 n/b(상수 b>1)이며, 분할·결합 비용이 f(n)일 때:

T(n) = a·T(n/b) + f(n),   T(1) = Θ(1)

n은 b의 거듭제곱이라 가정해도 점근적으로 동일한 차수가 나옵니다. f(n)과 n^(log_b a) 의 관계로 세 경우로 나뉩니다(로그는 밑 b).

경우	조건	결론
1	어떤 ε>0에 대해 f(n) = O(n^(log_b a − ε))	T(n) = Θ(n^(log_b a))
2	f(n) = Θ(n^(log_b a) · log^k n), k ≥ 0	T(n) = Θ(n^(log_b a) · log^(k+1) n)
3	f(n) = Ω(n^(log_b a + ε)) 이고 규칙성 조건 a·f(n/b) ≤ c·f(n) (어떤 c<1)	T(n) = Θ(f(n))

직관: 부분 문제 합의 “무게”가 n^{\log_b a}인데, f(n)이 그보다 작으면(케이스 1) 재귀 트리 잎 비용이 지배하고, 같은 차수(케이스 2)면 레벨마다 비슷한 비용이 쌓여 로그가 하나 더 붙으며, 훨씬 크면(케이스 3) 루트 근처의 f(n)이 지배합니다.

예시:

• 병합 정렬: T(n)=2T(n/2)+\Theta(n) → a=2,b=2, n^{\log_2 2}=n, f(n)=\Theta(n) 이므로 케이스 2 (k=0) → T(n)=\Theta(n \log n).
• 이진 탐색(재귀 한 번): T(n)=T(n/2)+\Theta(1) → n^{\log_2 1}=1, f(n)=\Theta(1) → 케이스 2 → T(n)=\Theta(\log n).
• 행렬 곱 스트라센 등 상수를 줄인 분할: 형태만 같으면 위 표로 차수를 먼저 확정한 뒤 상수는 별도로 봅니다.

한계: 서브문제 크기가 n/2, n/3처럼 불균등하거나, T(n)=T(n-1)+\Theta(1)처럼 크기가 1씩만 줄면 마스터 정리를 바로 적용하기 어렵습니다. 이때는 아래 기법을 씁니다.

점화식 풀이 기법

1. 반복 전개(Iterating / Recursion tree)
   몇 단계 전개해 단계별 합이 기하급수·조화급수 중 무엇에 가까운지 본 뒤, 깊이 O(log n) 또는 O(n) 등을 곱해 총합을 추정합니다. 병합 정렬·퀵소트 평균 분석에 익숙해지면 속도가 빨라집니다.

2. 치환법(Substitution)
   T(n) ≤ 2T(n/2) + cn이라고 두고, T(n) ≤ dn·log n 꼴을 가정해 귀납적으로 상수 d를 맞춥니다. 상한·하한을 각각 증명할 때 유용합니다.

3. 변수 치환
   예: T(n) = 2T(√n) + Θ(log n)은 m = log n으로 두면 S(m) = 2S(m/2) + Θ(m) 형태로 바뀌어 마스터 정리에 넣을 수 있습니다(정의역·바닥 함수는 점근에 동일하게 취급하는 경우가 많음).

4. Akra–Bazzi(발전형)
   부분 문제 크기가 a_i n처럼 여러 비율로 갈라질 때 쓰는 일반화입니다. 실무·이론 모두에서 “불균등 분할”을 엄밀히 다룰 때 참고합니다.

알고리즘 코드를 짤 때는 “이중 for가 몇 번 도나”만이 아니라, 재귀 호출 트리의 높이·너비·단계당 비용을 그려 보는 습관이 시간 복잡도 실수를 줄입니다.

마스터 정리가 안 맞을 때 자주 나오는 점화식

점화식	풀이 요령	점근
T(n)=T(n-1)+Θ(1)	한 줄씩 전개 → n번	Θ(n)
T(n)=T(n-1)+Θ(n)	n+(n-1)+…+1	Θ(n²)
T(n)=T(n/2)+Θ(1)	높이 Θ(log n)	Θ(log n)
T(n)=2T(n/2)+Θ(n)	마스터 케이스 2	Θ(n log n)
T(n)=T(n/5)+T(7n/10)+Θ(n)	불균등 분할	Akra–Bazzi 등(보통 선형 근사)
T(n)=T(√n)+Θ(1)	m=log n 치환 후 높이	Θ(log log n)

퀵소트 최악 T(n)=T(n-1)+Θ(n)은 한쪽으로만 갈라져 Θ(n²)입니다. 평균은 분할이 대체로 균형이라 Θ(n log n)으로 분석합니다(랜덤 피벗·이론적 기대).

재귀 트리로 합산하기 (병합 정렬 복습)

T(n)=2T(n/2)+cn을 생각할 때, 깊이 log₂ n 각 레벨에서 분할·결합에 쓰이는 총 작업이 cn이라면, 전체는 대략 cn·log n=Θ(n log n)입니다. 잎은 n개이고 각 잎에서 Θ(1)이라 잎 합은 Θ(n)이지만, 레벨 합이 지배합니다(마스터 정리 케이스 2와 같은 그림).

치환법 예: T(n)≤2T(n/2)+cn에 대해 T(n)=O(n log n) 스케치

가설: T(n) ≤ k·n log n (밑 2 로그든 자연로그든 점근 동치).

귀납: T(n) ≤ 2·k·(n/2)·log(n/2) + cn = kn log n - kn + cn.
k를 충분히 크게 잡아 cn ≤ kn이 되게 하면(상수만 조정), T(n) ≤ kn log n을 맞출 수 있습니다. 바닥·천장(⌊n/2⌋)이 있으면 “승리 조건을 약간 느슨히” 잡는 것이 일반적입니다.

변수 치환 예: T(n)=2T(√n)+Θ(log n)

m = log n으로 두면 √n = 2^{m/2}라서 T(2^m)=2T(2^{m/2})+Θ(m)입니다. S(m)=T(2^m)로 쓰면 S(m)=2S(m/2)+Θ(m) → 마스터 정리로 S(m)=Θ(m log m) → T(n)=Θ(log n · log log n) 꼴이 됩니다(상수·로그 밑은 점근에서 생략 가능).

선형 점화식(간단한 DP·피보나치)

F(n)=F(n-1)+F(n-2)의 호출 트리는 지수적으로 중복됩니다 — 시간 Θ(φ^n), 메모이제이션하면 시간·공간 Θ(n). 행렬 거듭제곱·쌍항 공식으로 더 줄일 수 있는지는 문제 제약을 봅니다.

---

실전 구현

✅ 1단계: 중첩 루프가 “모든 쌍”을 보고 있는가?

• 배열에서 모든 (i, j) 쌍 → 기본 O(N²).
• 정렬 후 한 방향 스캔, 두 포인터, 이진 탐색으로 한 축을 줄일 수 있는지 확인합니다.

패턴 1-1: Two Sum (해시맵)

# 나쁜 예: 모든 쌍 — O(N²)
def two_sum_naive(a, target):
    for i in range(len(a)):
        for j in range(i + 1, len(a)):
            if a[i] + a[j] == target:
                return [i, j]
    return []
# 좋은 예: 해시맵 — O(N)
def two_sum(a, target):
    seen = {}
    for i, num in enumerate(a):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []
# 사용 예
print(two_sum([2, 7, 11, 15], 9))  # [0, 1]
print(two_sum([3, 2, 4], 6))       # [1, 2]

패턴 1-2: 쌍의 합이 K보다 작은 개수 (투 포인터)

# 나쁜 예: 모든 쌍 — O(N²)
def count_pairs_naive(a, k):
    count = 0
    for i in range(len(a)):
        for j in range(i + 1, len(a)):
            if a[i] + a[j] < k:
                count += 1
    return count
# 좋은 예: 정렬 + 투 포인터 — O(N log N)
def count_pairs(a, k):
    a.sort()
    count = 0
    left, right = 0, len(a) - 1
    while left < right:
        if a[left] + a[right] < k:
            count += right - left  # left와 [left+1..right] 모두 조건 만족
            left += 1
        else:
            right -= 1
    return count
# 사용 예
print(count_pairs([1, 2, 3, 4, 5], 7))  # 6쌍: (1,2),(1,3),(1,4),(1,5),(2,3),(2,4)

패턴 1-3: 각 원소보다 작은 원소 개수 (이진 탐색)

import bisect
# 나쁜 예: 각 원소마다 전체 순회 — O(N²)
def count_smaller_naive(a):
    result = []
    for i in range(len(a)):
        count = sum(1 for j in range(len(a)) if j != i and a[j] < a[i])
        result.append(count)
    return result
# 좋은 예: 정렬 + 이진 탐색 — O(N log N)
def count_smaller(a):
    sorted_a = sorted(a)
    result = []
    for num in a:
        idx = bisect.bisect_left(sorted_a, num)
        result.append(idx)
    return result
# 사용 예
print(count_smaller([5, 2, 6, 1]))  # [2, 1, 3, 0]

✅ 2단계: 같은 구간 합·최소를 매번 다시 계산하는가?

• 누적합(prefix sum)으로 구간 합을 O(1)로.
• 슬라이딩 윈도우로 고정 길이 구간 최소/최대를 O(N)으로.

패턴 2-1: 구간 합 쿼리 (누적합)

# 나쁜 예: 쿼리마다 구간 순회 — O(Q × N)
def range_sum_naive(a, queries):
    result = []
    for l, r in queries:
        result.append(sum(a[l:r+1]))
    return result
# 좋은 예: 누적합 — O(N + Q)
def range_sum(a, queries):
    # 전처리: 누적합 배열
    prefix = [0]
    for num in a:
        prefix.append(prefix[-1] + num)
    
    result = []
    for l, r in queries:
        result.append(prefix[r+1] - prefix[l])
    return result
# 사용 예
a = [1, 2, 3, 4, 5]
queries = [(0, 2), (1, 4), (2, 2)]
print(range_sum(a, queries))  # [6, 14, 3]

패턴 2-2: 고정 길이 K 윈도우 최대값 (슬라이딩 윈도우 + Deque)

from collections import deque
# 나쁜 예: 각 윈도우마다 max 계산 — O(N × K)
def max_sliding_window_naive(a, k):
    result = []
    for i in range(len(a) - k + 1):
        result.append(max(a[i:i+k]))
    return result
# 좋은 예: Deque 슬라이딩 윈도우 — O(N)
def max_sliding_window(a, k):
    dq = deque()  # 인덱스 저장, 값은 감소 순서 유지
    result = []
    
    for i, num in enumerate(a):
        # 윈도우 벗어난 인덱스 제거
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        
        # 현재 값보다 작은 값들 제거 (더 이상 최대값 후보 아님)
        while dq and a[dq[-1]] < num:
            dq.pop()
        
        dq.append(i)
        
        # 윈도우가 완성되면 결과 추가
        if i >= k - 1:
            result.append(a[dq[0]])
    
    return result
# 사용 예
print(max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3))  # [3, 3, 5, 5, 6, 7]

패턴 2-3: 2D 구간 합 (2D 누적합)

# 나쁜 예: 쿼리마다 2D 순회 — O(Q × M × N)
def range_sum_2d_naive(matrix, queries):
    result = []
    for r1, c1, r2, c2 in queries:
        total = 0
        for r in range(r1, r2 + 1):
            for c in range(c1, c2 + 1):
                total += matrix[r][c]
        result.append(total)
    return result
# 좋은 예: 2D 누적합 — O(M × N + Q)
def range_sum_2d(matrix, queries):
    if not matrix:
        return []
    
    m, n = len(matrix), len(matrix[0])
    # 전처리: 2D 누적합
    prefix = [[0] * (n + 1) for _ in range(m + 1)]
    for r in range(1, m + 1):
        for c in range(1, n + 1):
            prefix[r][c] = (matrix[r-1][c-1] + 
                            prefix[r-1][c] + 
                            prefix[r][c-1] - 
                            prefix[r-1][c-1])
    
    result = []
    for r1, c1, r2, c2 in queries:
        # 1-indexed로 변환
        r1, c1, r2, c2 = r1 + 1, c1 + 1, r2 + 1, c2 + 1
        total = (prefix[r2][c2] - 
                 prefix[r1-1][c2] - 
                 prefix[r2][c1-1] + 
                 prefix[r1-1][c1-1])
        result.append(total)
    return result
# 사용 예
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
queries = [(0, 0, 1, 1), (1, 1, 2, 2)]
print(range_sum_2d(matrix, queries))  # [12, 28]

✅ 3단계: “존재 여부·빈도”를 선형 탐색으로 찾는가?

• 해시맵(dict / unordered_map)으로 평균 O(1) 조회.
• 순서가 필요하면 TreeMap류는 O(log N) — 정렬 키가 필요할 때만.

패턴 3-1: 중복 찾기 (Set)

# 나쁜 예: 각 원소마다 전체 순회 — O(N²)
def find_duplicates_naive(a):
    duplicates = []
    for i in range(len(a)):
        for j in range(i + 1, len(a)):
            if a[i] == a[j] and a[i] not in duplicates:
                duplicates.append(a[i])
    return duplicates
# 좋은 예: Set — O(N)
def find_duplicates(a):
    seen = set()
    duplicates = set()
    for num in a:
        if num in seen:
            duplicates.add(num)
        seen.add(num)
    return list(duplicates)
# 사용 예
print(find_duplicates([1, 2, 3, 2, 4, 3, 5]))  # [2, 3]

패턴 3-2: 빈도 카운트 (해시맵)

from collections import Counter
# 나쁜 예: 각 원소마다 count 호출 — O(N²)
def most_frequent_naive(a):
    max_count = 0
    result = None
    for num in set(a):
        count = a.count(num)
        if count > max_count:
            max_count = count
            result = num
    return result
# 좋은 예: Counter — O(N)
def most_frequent(a):
    counter = Counter(a)
    return counter.most_common(1)[0][0]
# 사용 예
print(most_frequent([1, 2, 2, 3, 3, 3, 4]))  # 3

패턴 3-3: 두 배열 교집합 (Set)

# 나쁜 예: 각 원소마다 in 연산 — O(N × M)
def has_duplicate_naive(a, b):
    for num in a:
        if num in b:
            return True
    return False
# 좋은 예: Set 변환 — O(N + M)
def has_duplicate(a, b):
    set_b = set(b)
    for num in a:
        if num in set_b:
            return True
    return False
# 더 간결한 방법
def has_duplicate_v2(a, b):
    return bool(set(a) & set(b))
# 사용 예
print(has_duplicate([1, 2, 3], [4, 5, 6]))  # False
print(has_duplicate([1, 2, 3], [3, 4, 5]))  # True

✅ 4단계: 쿼리마다 전체를 도는가?

• 오프라인이면 모스 알고리즘, 값이 고정 범위면 누적 빈도 배열, 구간 최소면 세그먼트 트리 등 쿼리당 비용을 줄이는 구조로 전환합니다.

패턴 4-1: 구간 최소 쿼리 (세그먼트 트리)

# 나쁜 예: 쿼리마다 구간 순회 — O(Q × N)
def range_min_naive(a, queries):
    result = []
    for l, r in queries:
        result.append(min(a[l:r+1]))
    return result
# 좋은 예: 세그먼트 트리 — O(N log N + Q log N)
class SegmentTree:
    def __init__(self, a):
        self.n = len(a)
        self.tree = [float('inf')] * (4 * self.n)
        self._build(a, 0, 0, self.n - 1)
    
    def _build(self, a, node, start, end):
        if start == end:
            self.tree[node] = a[start]
        else:
            mid = (start + end) // 2
            self._build(a, 2*node+1, start, mid)
            self._build(a, 2*node+2, mid+1, end)
            self.tree[node] = min(self.tree[2*node+1], self.tree[2*node+2])
    
    def query(self, l, r):
        return self._query(0, 0, self.n - 1, l, r)
    
    def _query(self, node, start, end, l, r):
        if r < start or l > end:
            return float('inf')
        if l <= start and end <= r:
            return self.tree[node]
        mid = (start + end) // 2
        left_min = self._query(2*node+1, start, mid, l, r)
        right_min = self._query(2*node+2, mid+1, end, l, r)
        return min(left_min, right_min)
def range_min(a, queries):
    st = SegmentTree(a)
    return [st.query(l, r) for l, r in queries]
# 사용 예
a = [3, 1, 4, 1, 5, 9, 2, 6]
queries = [(0, 3), (2, 5), (4, 7)]
print(range_min(a, queries))  # [1, 1, 2]

패턴 4-2: 구간 최소 쿼리 (Sparse Table - 정적 배열)

# Sparse Table: 전처리 O(N log N), 쿼리 O(1)
class SparseTable:
    def __init__(self, a):
        self.n = len(a)
        self.log = [0] * (self.n + 1)
        for i in range(2, self.n + 1):
            self.log[i] = self.log[i // 2] + 1
        
        max_log = self.log[self.n] + 1
        self.st = [[float('inf')] * max_log for _ in range(self.n)]
        
        # 길이 1 초기화
        for i in range(self.n):
            self.st[i][0] = a[i]
        
        # DP: st[i][j] = min(st[i][j-1], st[i + 2^(j-1)][j-1])
        for j in range(1, max_log):
            for i in range(self.n - (1 << j) + 1):
                self.st[i][j] = min(self.st[i][j-1], 
                                     self.st[i + (1 << (j-1))][j-1])
    
    def query(self, l, r):
        length = r - l + 1
        k = self.log[length]
        return min(self.st[l][k], self.st[r - (1 << k) + 1][k])
# 사용 예
a = [3, 1, 4, 1, 5, 9, 2, 6]
st = SparseTable(a)
print(st.query(2, 5))  # a[2..5] = [4,1,5,9] → 1
print(st.query(0, 7))  # a[0..7] 전체 → 1

✅ 5단계: 그래프는 BFS/DFS로 충분한가?

• 간선 가중치·최단 경로면 다익스트라 등으로 복잡도 클래스가 바뀝니다. BFS vs DFS와 연결해 봅니다.

패턴 5-1: 가중치 그래프 최단 경로 (다익스트라)

import heapq
# 나쁜 예: BFS (가중치 무시) — 틀린 결과
def shortest_path_bfs(graph, start, end):
    from collections import deque
    queue = deque([(start, 0)])
    visited = {start}
    
    while queue:
        node, dist = queue.popleft()
        if node == end:
            return dist
        for neighbor, weight in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))  # 가중치 무시!
    return -1
# 좋은 예: 다익스트라 — O((V + E) log V)
def dijkstra(graph, start, end):
    heap = [(0, start)]  # (거리, 노드)
    dist = {start: 0}
    
    while heap:
        d, node = heapq.heappop(heap)
        
        if node == end:
            return d
        
        if d > dist.get(node, float('inf')):
            continue
        
        for neighbor, weight in graph[node]:
            new_dist = d + weight
            if new_dist < dist.get(neighbor, float('inf')):
                dist[neighbor] = new_dist
                heapq.heappush(heap, (new_dist, neighbor))
    
    return -1
# 사용 예
graph = {
    0: [(1, 4), (2, 1)],
    1: [(3, 1)],
    2: [(1, 2), (3, 5)],
    3: []
}
print(dijkstra(graph, 0, 3))  # 0→2→1→3: 1+2+1=4

패턴 5-2: 음수 가중치 그래프 (벨만-포드)

# 다익스트라는 음수 가중치 처리 불가
# 벨만-포드: O(V × E)
def bellman_ford(edges, n, start):
    dist = [float('inf')] * n
    dist[start] = 0
    
    # n-1번 반복
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    
    # 음수 사이클 검사
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return None  # 음수 사이클 존재
    
    return dist
# 사용 예
edges = [
    (0, 1, 4),
    (0, 2, 1),
    (2, 1, -3),  # 음수 가중치
    (1, 3, 1),
    (2, 3, 5)
]
print(bellman_ford(edges, 4, 0))  # [0, -2, 1, -1]

---

고급 활용

세그먼트 트리 업데이트

구간 최소/최대 뿐만 아니라 업데이트도 빈번하면 세그먼트 트리가 필수입니다.

class SegmentTreeWithUpdate:
    def __init__(self, a):
        self.n = len(a)
        self.tree = [0] * (4 * self.n)
        self._build(a, 0, 0, self.n - 1)
    
    def _build(self, a, node, start, end):
        if start == end:
            self.tree[node] = a[start]
        else:
            mid = (start + end) // 2
            self._build(a, 2*node+1, start, mid)
            self._build(a, 2*node+2, mid+1, end)
            self.tree[node] = self.tree[2*node+1] + self.tree[2*node+2]
    
    def update(self, idx, val):
        self._update(0, 0, self.n - 1, idx, val)
    
    def _update(self, node, start, end, idx, val):
        if start == end:
            self.tree[node] = val
        else:
            mid = (start + end) // 2
            if idx <= mid:
                self._update(2*node+1, start, mid, idx, val)
            else:
                self._update(2*node+2, mid+1, end, idx, val)
            self.tree[node] = self.tree[2*node+1] + self.tree[2*node+2]
    
    def query(self, l, r):
        return self._query(0, 0, self.n - 1, l, r)
    
    def _query(self, node, start, end, l, r):
        if r < start or l > end:
            return 0
        if l <= start and end <= r:
            return self.tree[node]
        mid = (start + end) // 2
        return (self._query(2*node+1, start, mid, l, r) + 
                self._query(2*node+2, mid+1, end, l, r))
# 사용 예
a = [1, 3, 5, 7, 9, 11]
st = SegmentTreeWithUpdate(a)
print(st.query(1, 3))  # 3+5+7 = 15
st.update(2, 10)       # a[2] = 5 → 10
print(st.query(1, 3))  # 3+10+7 = 20

펜윅 트리 (Binary Indexed Tree)

세그먼트 트리보다 구현이 간단하고 메모리 효율적입니다. 구간 합 + 업데이트에 특화되어 있습니다.

class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)
    
    def update(self, idx, delta):
        idx += 1  # 1-indexed
        while idx <= self.n:
            self.tree[idx] += delta
            idx += idx & (-idx)
    
    def query(self, idx):
        # [0..idx] 합
        idx += 1  # 1-indexed
        result = 0
        while idx > 0:
            result += self.tree[idx]
            idx -= idx & (-idx)
        return result
    
    def range_query(self, l, r):
        # [l..r] 합
        if l == 0:
            return self.query(r)
        return self.query(r) - self.query(l - 1)
# 사용 예
ft = FenwickTree(6)
for i, val in enumerate([1, 3, 5, 7, 9, 11]):
    ft.update(i, val)
print(ft.range_query(1, 3))  # 3+5+7 = 15
ft.update(2, 5)              # a[2] += 5 (5 → 10)
print(ft.range_query(1, 3))  # 3+10+7 = 20

비트 연산 최적화

부분집합 문제에서 비트마스크를 사용하면 공간과 시간을 동시에 줄일 수 있습니다.

# 나쁜 예: 모든 부분집합 생성 — O(2^N × N)
def all_subsets_naive(a):
    result = [[]]
    for num in a:
        result += [subset + [num] for subset in result]
    return result
# 좋은 예: 비트마스크 — O(2^N)
def all_subsets(a):
    n = len(a)
    result = []
    for mask in range(1 << n):  # 0 ~ 2^n-1
        subset = []
        for i in range(n):
            if mask & (1 << i):
                subset.append(a[i])
        result.append(subset)
    return result
# 사용 예
print(all_subsets([1, 2, 3]))
# [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

---

성능과 비교

필요	선택	전형적 비용	메모리
키 존재/개수	해시맵	평균 O(1)	O(N)
정렬된 순서·다음 원소	Tree / 정렬+이분	O(log N)	O(N)
구간 합	누적합	전처리 O(N), 질의 O(1)	O(N)
구간 합 + 업데이트	펜윅 트리	질의·갱신 O(log N)	O(N)
구간 최소/갱신	세그먼트 트리	질의·갱신 O(log N)	O(4N)
구간 최소 (정적)	Sparse Table	전처리 O(N log N), 질의 O(1)	O(N log N)
우선순위	힙	push/pop O(log N)	O(N)

자료구조 선택 플로우차트

구간 쿼리가 필요한가?
├─ YES → 업데이트도 필요한가?
│   ├─ YES → 구간 합? → 펜윅 트리
│   │        구간 최소/최대? → 세그먼트 트리
│   └─ NO → 구간 합? → 누적합
│            구간 최소/최대? → Sparse Table
└─ NO → 존재/빈도 확인?
    ├─ YES → 순서 필요? → TreeMap (O(log N))
    │        순서 불필요? → 해시맵 (O(1))
    └─ NO → 우선순위? → 힙
             정렬? → sort + 이진 탐색

---

상각 분석

상각 분석(amortized analysis)은 “최악 한 번”이 아니라, 연산 시퀀스 전체를 놓고 한 번당 평균적으로 얼마나 비용이 드는지 보는 방법입니다. 코딩 테스트에서도 동적 배열 push, DSU(union-find), 해시 테이블 재해시처럼 “가끔 매우 비싼 연산”이 있을 때 진짜 한도를 잡는 데 쓰입니다.

누적 합(aggregate) 관점

n번의 연산에 총 비용이 O(n log n)이면, 상각으로 연산 1회당 O(log n)이라고 말할 수 있습니다. 최악 한 번이 O(n)이어도 전체 합이 O(n)이면 상각 O(1)일 수 있습니다.

기법 1: 계정(accounting) 방법

“비싼 연산”에 미리 저축해 둔 크레딧을 붙여 보는 방식입니다. 예: 동적 배열이 가득 차면 크기를 2배로 늘리면, 원소 하나당 재배치 비용을 생애에 걸쳐 나누면 상각 삽입 O(1)이 됩니다(말단 원소는 가끔 O(k)지만, 그 전에 k번의 저렴한 삽입이 쌓임).

기법 2: 잠재(potential) 방법

자료구조 상태에 잠재 함수 Φ를 두어, 실제 비용 c_i에 Φ의 변화를 더한 상각 비용 ĉ_i = c_i + Φ_{i} - Φ_{i-1}의 상한을 증명합니다. 이진 힙의 decrease-key가 구현마다 다르지만 상각 목표를 잡을 때 유용합니다.

대표 패턴

구조/연산	최악 1회	상각(시퀀스)	직관
동적 배열, 끝에 append, 가득 차면 2배 확장	O(n)	O(1) per append	희귀한 재할당을 전체로 나눔
이진 카운터 증가(비트 뒤집기)	O(log U) 비트	O(1) per increment	1이 끝에서 연속되는 횟수 상각
유니온 파인드(경로 압축·합치기 by rank)	—	거의 O(α(n)) per op	α는 역 아커만, 실질 상수
해시맵 재해시	O(n)	삽입 상각 O(1) 평균	테이블 크기 기하급수 증가

주의: 상각 O(1)이라도 실시간(latency) 보장이 필요한 스레드·임베디드에서는 “드물게 큰 지연” 자체가 문제가 될 수 있습니다. 그때는 worst-case 자료구조(예: B-트리, 다른 할당 전략)를 검토합니다.

투 포인터와 “상각” 직관

바깥 i가 증가할 때 안쪽 j가 되돌아가지 않고 끝까지 전진만 한다면, (i,j) 쌍 전체가 O(n)입니다. 이는 엄밀한 잠재 함수 증명이라기보다 루프 불변식에 가깝지만, 분석 습관은 상각과 같습니다.

---

공간 복잡도 최적화

시간을 줄이기 위해 공간을 쓰는 전략(메모이제이션, 누적합, 세그먼트 트리)과 반대로, MLE·캐시·GC 압박이 있으면 보조 공간(auxiliary space)을 먼저 줄입니다. 입력 배열 자체는 문제가 요구하는 저장이라 복잡도 표기에서 제외하는 경우가 많지만, 출력·복사는 포함합니다.

1. 입력과 출력을 구분

• 제자리(in-place) 알고리즘: O(1) 추가 공간(스택 재귀 깊이는 별도).
  예: 힙 정렬, 일부 퀵소트 파티션, 역순 뒤집기.
• DP 롤링: dp[i][*]가 dp[i-1][*]만 참조하면 2행 또는 1행으로 줄여 O(N) → O(min(N,M)) 등.

2. 자료구조 스왑으로 시간·공간 트레이드오프

• 인덱스 배열으로 정렬 대신 순서만 추적해 O(N) 공간으로 비교 횟수를 줄이는 경우.
• 비트 패킹으로 여러 불리언을 한 워드에 넣어 캐시 라인 수를 줄임(실무·임베디드).

3. 그래프에서의 공간

• 인접 행렬 O(V²) vs 인접 리스트 O(V+E) — 희소 그래프면 리스트가 유리합니다.
• 역방향 그래프를 따로 두는지, 한 번의 DFS로 처리할 수 있는지에 따라 2배 공간을 아낄 수 있습니다.

4. 재귀 vs 명시적 스택

• 깊이 D 재귀는 호출 스택 O(D) — D가 크면 메모리 한도와 스택 오버플로 위험.
• 명시적 스택으로 바꿔도 동일 O(D)이지만, 스택 프레임 오버헤드는 줄일 수 있습니다.

5. “공간 줄이고 시간 늘리기”가 맞는 경우

• 플로이드-워샬 O(V³) 시간·O(V²) 공간 vs 다익스트라를 V번 O(V·(E log V)) — 그래프 밀도·제약에 따라 선택이 갈립니다.
• 세그먼트 트리 없이 오프라인 쿼리(스위프, Mo)로 메모리 O(N)만 쓰는 경우.

체크리스트

1. DP: 이전 행/열만 필요한가? → 롤링.
2. 두 문자열 LCS 등: 복원이 필요 없으면 값만 O(min)으로.
3. 중복 방문: visited 비트맵 vs bool 배열 vs 해시셋 — 값 범위에 따라 공간 차이가 큼.
4. 대용량 문자열: 부분 문자열 슬라이싱이 복사를 일으키지 않는지(언어별) 확인.

---

캐시 복잡도 모델

Big-O는 RAM 모델(균일한 메모리 접근 비용)을 가정하는 경우가 많습니다. 실제 CPU는 레지스터 → 캐시(L1/L2/L3) → 메인 메모리로 이어지는 계층이라, 같은 O(N)이라도 상수가 크게 달라집니다.

외부 메모리(I/O) 모델 개요

디스크·SSD처럼 블록 단위로 읽는 계층에서는, 비교 횟수보다 블록 전송 횟수가 병목인 경우가 많습니다. 전형적으로 크기 N 데이터가 블록 크기 B의 디스크에 있을 때, 정렬·스캔 등의 I/O 복잡도를 따로 씁니다(예: O((N/B)\log_{M/B}(N/B)) 꼴의 최적 외부 정렬류). 코딩 테스트에서는 거의 RAM만 보면 되지만, 대용량 로그·온디스크 인덱스를 다루는 실무에서는 이 관점이 핵심입니다.

캐시 의식적(cache-aware) 패턴

• 공간 지역성: 연속된 메모리(배열 순차 접근)는 한 캐시 라인에 여러 원소가 담겨 미스가 줄어듭니다.
• 시간 지역성: 같은 변수·같은 구역을 짧은 시간에 재사용하면 상위 캐시에 남아 유리합니다.
• 행 우선 vs 열 우선: 2차원 배열을 잘못된 순서로 스캔하면(예: C에서 열을 바깥 루프에 두는 식) 캐시 친화가 떨어질 수 있습니다. 바깥 루프가 연속 인접 차원이 되도록 맞춥니다.

캐시 무지(cache-oblivious) 알고리즘은 B를 코드에 넣지 않아도 점근적으로 I/O를 최적에 가깝게 맞추는 설계를 말합니다. 실무에서는 “데이터를 어떻게 줄 세우느냐”가 알고리즘 차수만큼이나 중요할 때가 많습니다.

---

분기 예측과 실행 시간

현대 CPU는 파이프라인과 분기 예측기로 분기문(if, ?:, 루프 종료)의 다음 주소를 미리 추측합니다. 예측이 빗나가면(misprediction) 파이프라인이 비워지고 수십 사이클 손실이 날 수 있어, 같은 O(N)이라도 분기 패턴에 따라 체감 시간이 달라집니다.

영향이 큰 경우

• 데이터에 따라 갈리는 분기: 정렬된 배열에서 이진 탐색은 한쪽으로 치우쳐 예측이 잘 맞는 편이고, 무작위 데이터에서는 패턴이 흐려질 수 있습니다.
• 랜덤한 키 비교: 해시 충돌 처리·가지치기가 불규칙하면 분기 비용이 부각될 수 있습니다.

실무에서의 완화 아이디어

• 분기 줄이기: 루프 안의 if를 두 루프로 쪼개기·sentinel·SIMD 마스크 등으로 대체하는 경우가 있습니다(가독성·유지보수와 트레이드오프).
• 정렬·전처리: 조건이 단조해지도록 정렬해 분기를 예측 가능하게 만듭니다.
• CMOV·무조건 연산: 아주 핫한 루프에서 컴파일러가 조건부 이동을 쓰기도 하지만, 항상 빠른 것은 아니므로 측정이 우선입니다.

요약하면, 알고리즘 차수를 줄인 다음에도 서버가 느리면 “캐시 미스와 분기 미스가 핫스팟에 얼마나 기여하는지”를 프로파일러로 확인하는 것이 좋습니다.

---

실무 사례

사례 1: 로그 집계 시스템

문제: 수백만 개의 로그에서 날짜별 에러 개수 집계

# 나쁜 예: 매번 전체 스캔 — O(Q × N)
def count_errors_by_date_naive(logs, dates):
    result = {}
    for date in dates:
        count = sum(1 for log in logs if log['date'] == date and log['level'] == 'ERROR')
        result[date] = count
    return result
# 좋은 예: 날짜별 인덱스 맵 — O(N + Q)
def count_errors_by_date(logs, dates):
    # 전처리: 날짜별 에러 카운트
    error_count = {}
    for log in logs:
        if log['level'] == 'ERROR':
            date = log['date']
            error_count[date] = error_count.get(date, 0) + 1
    
    result = {}
    for date in dates:
        result[date] = error_count.get(date, 0)
    return result

사례 2: API 레이트 리밋

문제: 슬라이딩 윈도우 방식으로 최근 1분간 요청 100개 제한

from collections import deque
import time
class RateLimiter:
    def __init__(self, max_requests, window_seconds):
        self.max_requests = max_requests
        self.window = window_seconds
        self.requests = deque()
    
    def allow_request(self):
        now = time.time()
        
        # 윈도우 벗어난 요청 제거
        while self.requests and self.requests[0] < now - self.window:
            self.requests.popleft()
        
        # 제한 확인
        if len(self.requests) < self.max_requests:
            self.requests.append(now)
            return True
        return False
# 사용 예
limiter = RateLimiter(max_requests=100, window_seconds=60)
for _ in range(150):
    if limiter.allow_request():
        print("Request allowed")
    else:
        print("Rate limit exceeded")

사례 3: 실시간 순위 시스템

문제: 게임 점수 업데이트 + 상위 K명 조회

import heapq
class Leaderboard:
    def __init__(self, k):
        self.k = k
        self.scores = {}  # user_id → score
        self.top_k = []   # min heap
    
    def update_score(self, user_id, score):
        old_score = self.scores.get(user_id, 0)
        self.scores[user_id] = score
        
        # 힙 재구성 (실제로는 lazy deletion 사용)
        self.top_k = []
        for uid, s in self.scores.items():
            if len(self.top_k) < self.k:
                heapq.heappush(self.top_k, (s, uid))
            elif s > self.top_k[0][0]:
                heapq.heapreplace(self.top_k, (s, uid))
    
    def get_top_k(self):
        return sorted(self.top_k, reverse=True)
# 사용 예
lb = Leaderboard(k=3)
lb.update_score('user1', 100)
lb.update_score('user2', 150)
lb.update_score('user3', 120)
lb.update_score('user4', 90)
print(lb.get_top_k())  # [(150, 'user2'), (120, 'user3'), (100, 'user1')]

---

프로덕션 프로파일링 패턴

실서비스에서는 정확한 복잡도만큼이 아니라, 어디서 시간이 쓰이는지를 팀이 공유 가능한 형태로 남기는 것이 중요합니다. 아래는 자주 쓰는 패턴입니다.

1. 샘플링 vs 계측

• 샘플링 프로파일러(예: perf의 주기적 인터럽트, 언어별 CPU 샘플러): 오버헤드가 상대적으로 작고 프로덕션에도 부담을 줄여 쓸 수 있습니다. 핫 함수·스택을 빠르게 잡기에 좋습니다.
• 계측(instrumentation) 또는 트레이싱: 호출마다 타이머를 심는 방식은 세밀하지만 비용이 커서, 개발·스테이징이나 짧은 캡처 구간에 두는 경우가 많습니다.

2. 플레임 그래프·호출 경로

CPU 샘플을 스택 트레이스로 모아 플레임 그래프로 보면, “넓은 막대 = 그 경로에서 많은 시간”을 한눈에 볼 수 있습니다. 한 함수만 느린 게 아니라 어떤 호출 체인으로 들어왔을 때 느린지가 드러나, 잘못된 캐시 정책·N+1 쿼리·불필요한 직렬화 같은 시스템 이슈까지 추적하기 쉽습니다.

diff 플레임 그래프(배포 전후 비교)는 회귀를 잡는 데 특히 유용합니다. 같은 워크로드에서 “새로 넓어진 막대”를 보면 원인 함수가 빠르게 좁혀집니다.

3. 벽시계(wall time) vs CPU 시간 vs 대기

요청이 느릴 때 CPU 프로파일만 보면 놓치는 경우가 많습니다.

• I/O 대기, 락 대기, GC Stop-The-World, 네트워크 RTT는 CPU 샘플에 잘 안 잡히거나 다른 스택으로 보입니다.
• 언어 런타임 트레이스(예: Go trace, JVM JFR, 브라우저 Performance)로 스레드가 무엇을 기다렸는지를 같이 봅니다.
• 분산 트레이싱(OpenTelemetry 등)으로 서비스 경계에서 지연이 붙는지 확인합니다 — 한 함수의 Big-O와 무관하게 페이로드 크기·직렬화·라운드 트립이 지배할 수 있습니다.

4. 메모리·할당 프로파일링

GC 언어에서 “CPU 핫스팟이 할당·복사”인 경우가 흔합니다.

• 할당 프로파일(allocation profile): 어떤 타입·호출 경로에서 객체가 많이 생기는지 봅니다.
• 힙 덤프는 비용이 크므로 스테이징이나 제한된 샘플링에 가깝습니다.
• 상수 한도를 줄이려면 “알고리즘 차수”보다 불필요한 문자열·배열 복사를 줄이는 쪽이 빠를 때가 많습니다.

5. 커널·프로덕션 관측(eBPF 등)

Linux 환경에서는 eBPF 기반 도구로 시스케줄링 지연, 블록 I/O, TCP 재전송, 시스콜 빈도를 프로세스와 함께 보는 경우가 있습니다. 애플리케이션 코드는 O(N)인데 디스크·페이지 캐시가 병목이면 사용자 체감은 개선되지 않습니다.

6. 지속 프로파일링(Continuous profiling)

짧은 캡처가 아니라 항상 낮은 샘플링으로 프로파일을 쌓으면, 사고 시점뿐 아니라 일상적인 핫스팟 추세를 봅니다. 비용·개인정보·보관 정책을 팀 규칙으로 정하는 것이 좋습니다.

7. 언어별 진입점(예시)

• Go: pprof HTTP 엔드포인트, CPU·힙 프로파일, trace로 고루틴·블로킹 분석.
• C/C++: Linux perf, clang/gcc와 sanitizers 병행, LBR로 분기 비용 추정(환경 의존).
• JVM: async-profiler, JFR, VisualVM 등 프로덕션 안전한 도구 선택이 중요.
• Node.js: --cpu-prof, 클리닉 닥터류, V8 힙 스냅샷 — 이벤트 루프 지연은 별도로 봅니다.

환경마다 허용 도구가 다르므로, 운영 정책과 맞춰 고릅니다.

8. SLO·지표와 연결

프로파일은 “무엇이 느린가”를 보여 주고, 메트릭은 “언제 느린가”를 보여 줍니다. 지연 P99, 에러율, CPU 대비 처리량과 함께 보면, 배포 후에만 터지는 회귀나 특정 테넌트만 겪는 병목을 좁힐 수 있습니다. Before/After 비교는 동일 부하·동일 빌드 타입·가능하면 Canary에서 먼저 수집하는 것이 해석이 쉽습니다.

부하 테스트와 프로파일을 함께 쓸 때는 실제 쿼리 믹스·캐시 히트율이 프로덕션과 비슷한지 확인합니다. 인위적으로 너무 작은 페이로드만 던지면 O(n) 알고리즘이 맞아도 병목이 안 보일 수 있습니다.

9. 알고리즘 검증과의 역할 분담

• 코딩 테스트·설계 단계: 점근 복잡도·자료구조 선택으로 차수를 맞춥니다.
• 프로덕션: 프로파일러로 상수·락·I/O·캐시를 줄입니다. 둘은 대체재가 아니라 순서가 있습니다.

이 구간을 체크리스트에 넣어 두면, “복잡도는 O(N)인데 왜 느리지?”라는 질문에 측정 기반으로 답하기 쉬워집니다.

---

트러블슈팅

문제 1: “맞는 알고리즘인데도 TLE”

원인 1: 입출력 병목

Python:

# 나쁜 예: input() 대량 호출
n = int(input())
a = [int(input()) for _ in range(n)]
# 좋은 예: sys.stdin 사용
import sys
input = sys.stdin.readline
n = int(input())
a = [int(input()) for _ in range(n)]
# 더 빠른 방법: 한 번에 읽기
import sys
data = sys.stdin.read().split()
n = int(data[0])
a = list(map(int, data[1:n+1]))

C++:

// 나쁜 예: cin/cout 동기화
#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;  // 느림
}
// 좋은 예: 동기화 해제
#include <iostream>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;  // 빠름
}

원인 2: 재귀 깊이 제한

Python:

# 나쁜 예: 기본 재귀 제한 (약 1000)
def dfs(node, graph, visited):
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(neighbor, graph, visited)
# 좋은 예 1: 재귀 제한 증가
import sys
sys.setrecursionlimit(10**6)
# 좋은 예 2: 반복문으로 변환
def dfs_iterative(start, graph):
    stack = [start]
    visited = set()
    
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                stack.append(neighbor)
    
    return visited

문제 2: “O(N log N)인데 불안하다”

상수 최적화

# 나쁜 예: 불필요한 정렬 반복
def process_queries(a, queries):
    result = []
    for q in queries:
        a.sort()  # 매번 정렬!
        result.append(bisect.bisect_left(a, q))
    return result
# 좋은 예: 한 번만 정렬
def process_queries_optimized(a, queries):
    a.sort()  # 한 번만
    result = []
    for q in queries:
        result.append(bisect.bisect_left(a, q))
    return result

자료구조 선택

# 나쁜 예: dict 조회 (해시 계산 오버헤드)
def count_frequency_dict(a):
    freq = {}
    for num in a:
        freq[num] = freq.get(num, 0) + 1
    return freq
# 좋은 예: 범위가 작으면 배열 인덱싱
def count_frequency_array(a, max_val):
    freq = [0] * (max_val + 1)
    for num in a:
        freq[num] += 1
    return freq
# 사용 예 (a의 값이 0~1000 범위)
a = [1, 2, 2, 3, 3, 3, 1000]
print(count_frequency_array(a, 1000))

문제 3: “메모리 초과 (MLE)“

공간 복잡도 줄이기

# 나쁜 예: 2D DP 전체 저장 — O(N × M)
def lcs_2d(s1, s2):
    n, m = len(s1), len(s2)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    return dp[n][m]
# 좋은 예: 1D DP (이전 행만 저장) — O(M)
def lcs_1d(s1, s2):
    n, m = len(s1), len(s2)
    prev = [0] * (m + 1)
    
    for i in range(1, n + 1):
        curr = [0] * (m + 1)
        for j in range(1, m + 1):
            if s1[i-1] == s2[j-1]:
                curr[j] = prev[j-1] + 1
            else:
                curr[j] = max(prev[j], curr[j-1])
        prev = curr
    
    return prev[m]

문제 4: “정답은 맞는데 시간이 빡빡”

조기 종료 (Early Exit)

# 나쁜 예: 답을 찾아도 끝까지 순회
def find_target(a, target):
    found = False
    for num in a:
        if num == target:
            found = True
    return found
# 좋은 예: 찾으면 즉시 반환
def find_target_optimized(a, target):
    for num in a:
        if num == target:
            return True
    return False
# 더 좋은 예: in 연산자 (C로 구현되어 더 빠름)
def find_target_best(a, target):
    return target in a

불필요한 복사 제거

# 나쁜 예: 리스트 슬라이싱 (복사 발생)
def process_windows(a, k):
    result = []
    for i in range(len(a) - k + 1):
        window = a[i:i+k]  # O(K) 복사
        result.append(sum(window))
    return result
# 좋은 예: 인덱스만 사용
def process_windows_optimized(a, k):
    result = []
    window_sum = sum(a[:k])
    result.append(window_sum)
    
    for i in range(k, len(a)):
        window_sum += a[i] - a[i-k]
        result.append(window_sum)
    
    return result

---

마무리

코딩테스트 시간복잡도 줄이기는 N의 범위와 현재 풀이의 차수를 한 줄로 적는 것에서 절반은 끝납니다. 나머지는 중복 계산 제거·맞는 자료구조 두 가지 축으로만 점검하면 됩니다. 분할 정복·재귀는 점화식과 마스터 정리로 차수를 재확인하고, 실서비스에서는 캐시·분기·프로파일링으로 상수와 시스템 병목을 따로 봅니다.

핵심 체크리스트 요약

1. N 범위 확인 → 허용 복잡도 추정
2. 중첩 루프 → 정렬/투포인터/이진탐색으로 축소
3. 반복 계산 → 누적합/슬라이딩윈도우로 전처리
4. 존재/빈도 → 해시맵/Set으로 O(1) 조회
5. 쿼리 반복 → 세그먼트트리/Sparse Table로 쿼리당 비용 감소
6. 가중치 그래프 → 다익스트라/벨만-포드로 최단 경로
7. 재귀·분할 정복 → T(n)=aT(n/b)+f(n) 형태면 마스터 정리, 아니면 반복 전개·치환·Akra–Bazzi
8. 상각·시퀀스 → 동적 배열·유니온 파인드·재해시 등은 “한 번 최악”이 아니라 시퀀스 합으로 본다
9. MLE·메모리 → DP 롤링·제자리·인접 표현·명시적 스택으로 보조 공간부터 줄인다
10. 같은 차수인데 느림 → 캐시 미스·분기 예측 실패·I/O·락·할당 — CPU만이 아니라 벽시계·트레이스로 핫스팟 확인

다음 단계

• 패턴 연습: 두 포인터·슬라이딩 윈도우
• 그래프 알고리즘: BFS vs DFS 비교
• 실전 최적화 사례: 알고리즘 최적화 사례 연구 코딩테스트에서 TLE를 만나면 당황하지 말고 이 체크리스트를 30초 안에 훑어보세요. 대부분의 경우 자료구조 하나만 바꿔도 복잡도 클래스가 바뀝니다.

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

이 부록은 앞선 본문에서 다룬 주제(「코딩 테스트에서 시간 복잡도 줄이는 체크리스트 | 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 순서를 권장합니다.

---

자주 묻는 질문 (FAQ)

Q. 이 내용을 실무에서 언제 쓰나요?

A. 코딩테스트 시간복잡도 줄이기: O(N²)을 O(N log N)으로 바꾸는 패턴, 중복 계산 제거, 자료구조 선택 체크리스트를 실전 기준으로 정리합니다. 알고리즘·시간 복잡도·최적화 중심으로 설명합니다. Start n… 실무에서는 위 본문의 예제와 선택 가이드를 참고해 적용하면 됩니다.

Q. 선행으로 읽으면 좋은 글은?

A. 각 글 하단의 이전 글 또는 관련 글 링크를 따라가면 순서대로 배울 수 있습니다. C++ 시리즈 목차에서 전체 흐름을 확인할 수 있습니다.

Q. 더 깊이 공부하려면?

A. cppreference와 해당 라이브러리 공식 문서를 참고하세요. 글 말미의 참고 자료 링크도 활용하면 좋습니다.

---

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

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

• 알고리즘 최적화 실전 사례 | 코딩테스트 시간 초과(TLE) 해결기
• 정렬 문제 풀이 | 코딩 테스트 정렬 패턴 완벽 정리
• C++ 알고리즘 최적화 | 시간복잡도·공간복잡도·트레이드오프 [#54-10]

---

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

알고리즘, 시간 복잡도, 최적화, 코딩 테스트, TLE, 체크리스트 등으로 검색하시면 이 글이 도움이 됩니다.