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

작성 0xmote · 2026년 5월 18일 · 42분 읽기 · 수정 2026년 10월 2일 중급 개념

이 글의 핵심

입력 크기와 제한 시간으로 허용 복잡도를 먼저 가늠한 뒤, 코드를 보며 병목을 좁혀 가는 순서로 구성했습니다. 마스터 정리와 점화식 풀이, 상각 분석의 계정·잠재 방법, 공간과 시간의 트레이드오프까지 다뤄 왜 이 최적화가 통하는지 설명할 수 있게 해 줍니다.

들어가며

시간 복잡도를 줄이는 작업은 더 빠른 알고리즘을 외우는 것보다, 제한 조건(N의 범위)과 현재 풀이의 복잡도를 맞춰 보는 습관에서 시작합니다. TLE(Time Limit Exceeded)의 대부분은 불필요한 이중·삼중 루프나 같은 구간을 반복 계산하는 코드에서 생깁니다. 이 글은 병목을 찾는 순서대로 단계를 나누고, 각 단계마다 느린 코드와 고친 코드를 나란히 놓았습니다. 뒤쪽에서는 점화식과 상각 분석으로 차수를 검증하는 방법, 그리고 같은 Big-O인데도 느린 이유(캐시, 분기, I/O)를 다룹니다. 표의 수치는 대략적인 상한이며 언어와 채점 환경에 따라 여유가 달라집니다.

개념 설명

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

N (대략)	여유 있음	위험
≤ 10	O(N!)	—
≤ 20	O(2^N · N)	O(N!)은 불가
≤ 200	O(N³)	O(N⁴)
≤ 2×10³	O(N²)	O(N² log N)은 빠듯함
≤ 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)+Θ(n) → a=2, b=2, n^(log₂2) = n, f(n)=Θ(n) 이므로 케이스 2 (k=0) → T(n)=Θ(n log n).
이진 탐색(재귀 한 번): T(n)=T(n/2)+Θ(1) → n^(log₂1) = 1, f(n)=Θ(1) → 케이스 2 → T(n)=Θ(log n).
스트라센 행렬 곱: 부분 곱을 8개에서 7개로 줄여 T(n)=7T(n/2)+Θ(n²) → n^(log₂7) ≈ n^2.81이 n²보다 크므로 케이스 1 → T(n)=Θ(n^(log₂7)). 상수가 아니라 a를 줄여 차수 자체가 내려간 예입니다.

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

점화식 풀이 기법

반복 전개(Iterating / Recursion tree)
몇 단계 전개해 레벨별 비용이 등비수열로 줄어드는지, 일정한지, 늘어나는지 본 뒤, 깊이 O(log n) 또는 O(n) 등을 곱해 총합을 추정합니다. 병합 정렬·퀵소트 평균 분석에 익숙해지면 속도가 빨라집니다.
치환법(Substitution)
T(n) ≤ 2T(n/2) + cn이라고 두며, T(n) ≤ dn·log n 꼴을 가정해 귀납적으로 상수 d를 맞춥니다. 상한·하한을 각각 증명할 때 유용합니다.
변수 치환
예: T(n) = 2T(√n) + Θ(log n)은 m = log n으로 두면 S(m) = 2S(m/2) + Θ(m) 형태로 바뀌어 마스터 정리에 넣을 수 있습니다(정의역·바닥 함수는 점근에 동일하게 취급하는 경우가 많음).
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)`	불균등 분할, 1/5+7/10<1이라 레벨 비용이 등비 감소	`Θ(n)` (median of medians)
`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). 행렬 거듭제곱을 쓰면 Θ(log n)번의 2×2 행렬 곱으로 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) + 쿼리 O(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]

고급 활용

세그먼트 트리 업데이트

질의와 함께 값 갱신도 자주 일어나면 누적합은 갱신마다 O(N)이 들어 맞지 않습니다. 세그먼트 트리는 질의와 갱신을 모두 O(log N)에 처리합니다. 아래는 구간 합 버전입니다.

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

비트 연산 최적화

부분집합을 모두 나열하는 작업은 출력 크기 자체가 2^N·N이므로 어떤 방식으로 써도 O(2^N·N)입니다. 비트마스크의 이점은 부분집합을 정수 하나로 표현할 수 있다는 점입니다. 리스트를 만들지 않고 정수 상태로 DP 키나 방문 표시에 쓰면 메모리와 상수 비용이 크게 줄어듭니다.

# 리스트 누적 방식 — 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 × N), 대신 mask 정수만으로도 부분집합을 다룰 수 있음
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(N) (배열 크기 약 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배로 늘리면, 확장이 일어나는 삽입은 원소 k개를 복사하므로 O(k)입니다. 하지만 그 전에 약 k/2번의 저렴한 삽입이 있었고, 각 삽입에 상수 크레딧을 몇 개씩 적립해 두면 복사 비용을 모두 갚을 수 있어 상각 삽입은 O(1)이 됩니다.

기법 2: 잠재(potential) 방법

자료구조 상태에 잠재 함수 Φ를 두어, 실제 비용 c_i에 Φ의 변화를 더한 상각 비용 ĉ_i = c_i + Φ_{i} - Φ_{i-1}의 상한을 증명합니다. Φ가 항상 0 이상이고 시작값이 0이면 상각 비용의 합이 실제 비용의 합 이상이 되므로 상한으로 쓸 수 있습니다. 피보나치 힙의 decrease-key가 상각 O(1)이라는 분석이 이 방법을 쓰는 대표 예입니다.

대표 패턴

구조/연산	최악 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) 보장이 필요한 스레드·임베디드에서는 “드물게 큰 지연” 자체가 문제가 될 수 있습니다. 그때는 재해시를 여러 삽입에 나눠 수행하는 점진적 리사이즈처럼 최악 지연을 보장하는 기법을 검토합니다.

투 포인터와 “상각” 직관

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

공간 복잡도 최적화

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

입력과 출력을 구분

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

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

큰 레코드를 직접 정렬하는 대신 인덱스 배열을 정렬하면, O(N) 보조 공간을 더 쓰는 대신 레코드 이동 비용을 줄일 수 있습니다.
비트 패킹으로 여러 불리언을 한 워드에 넣으면 메모리가 1/8 이하로 줄고 캐시 라인도 덜 씁니다.

그래프에서의 공간

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

재귀 vs 명시적 스택

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

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

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

놓치기 쉬운 공간 비용

방문 표시는 값 범위가 작으면 bool 배열이나 비트맵이, 범위가 크고 희소하면 해시셋이 적은 메모리를 씁니다. 대용량 문자열을 다룰 때는 슬라이싱이 복사를 일으키는지도 확인합니다. Python의 s[i:j]는 새 문자열을 만들고, C++의 std::string_view는 복사하지 않습니다.

캐시 복잡도 모델

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 열 우선: C/C++ 2차원 배열은 행 우선으로 저장되므로 a[i][j]를 돌 때 안쪽 루프가 j(연속된 차원)를 돌아야 캐시 라인을 끝까지 활용합니다. 안쪽 루프가 i를 돌면 매 접근마다 다른 캐시 라인을 건드리게 됩니다.

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

분기 예측과 실행 시간

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

영향이 큰 경우

데이터에 따라 갈리는 분기: 배열을 순회하며 if (x >= 128)처럼 값으로 분기하면, 정렬된 데이터에서는 분기 결과가 한 번만 바뀌어 예측이 거의 맞고, 무작위 데이터에서는 절반 가까이 빗나갑니다. 반면 이진 탐색의 비교 분기는 정렬 여부와 관계없이 매번 50:50에 가까워 예측이 잘 맞지 않습니다.
랜덤한 키 비교: 해시 충돌 처리·가지치기가 불규칙하면 분기 비용이 부각될 수 있습니다.

실무에서의 완화 아이디어

분기 줄이기: 루프 안의 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개로 제한합니다. 만료된 타임스탬프는 앞에서만 제거되므로 요청당 상각 O(1)입니다.

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명 조회를 처리하는 단순한 버전입니다. 아래 코드는 갱신마다 전체 사용자(U명)를 다시 훑어 힙을 만들므로 갱신 한 번이 O(U log K)입니다. 갱신이 잦다면 점수별 정렬 컨테이너(C++ std::set, Python sortedcontainers.SortedList)를 써서 갱신을 O(log U)로 내리거나, 힙에 새 항목을 넣고 낡은 항목은 꺼낼 때 버리는 지연 삭제를 씁니다.

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):
        self.scores[user_id] = score
        
        # 힙 재구성: 갱신마다 O(U log K)
        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')]

프로덕션 프로파일링 패턴

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

샘플링 vs 계측

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

플레임 그래프·호출 경로

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

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

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

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

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

메모리·할당 프로파일링

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

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

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

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

지속 프로파일링(Continuous profiling)

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

언어별 진입점(예시)

Go: pprof HTTP 엔드포인트, CPU·힙 프로파일, trace로 고루틴·블로킹 분석.
C/C++: Linux perf(perf record/perf report), Intel CPU에서는 LBR로 분기 경로 추정(환경 의존).
JVM: async-profiler, JFR, VisualVM 등 프로덕션 안전한 도구 선택이 중요.
Node.js: --cpu-prof, Clinic.js, V8 힙 스냅샷 — 이벤트 루프 지연은 별도로 봅니다.

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

SLO·지표와 연결

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

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

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

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

트러블슈팅

문제 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: 재귀 깊이 제한