코딩 테스트에서 시간 복잡도 줄이는 체크리스트 | TLE 탈출
이 글의 핵심
코딩테스트에서 시간복잡도 줄이기 위해 중첩 루프·맵·정렬·누적합·이진 탐색을 단계별로 점검하는 체크리스트입니다.
들어가며
코딩테스트 시간복잡도 줄이기는 “더 빠른 알고리즘을 외운다”기보다, 제한 조건(N의 범위)과 현재 복잡도를 맞춰 보는 습관에서 시작합니다. 대부분의 TLE(Time Limit Exceeded)는 불필요한 이중·삼중 루프 또는 같은 구간을 반복 계산해서 생깁니다.
이 글은 시험장에서 바로 쓸 수 있게 체크리스트 형태로 정리했습니다. 수치는 대략적인 상한이며, 상수·언어·채점기 환경에 따라 여유가 달라질 수 있습니다.
체크리스트는 외우는 것보다 문제 읽고 30초 안에 한 번 훑는 습관으로 쓰는 것이 가장 효과적입니다.
이 글을 읽으면
- N 규모별로 허용되는 복잡도 대역을 직관으로 잡습니다
- O(N²) 후보를 O(N log N)으로 내리는 전형적 패턴을 떠올립니다
- 해시맵·정렬·누적합·이진 탐색 중 무엇을 쓸지 빠르게 고릅니다
목차
개념 설명
대략적인 가이드 (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)실전 구현
✅ 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 + 이진 탐색실무 사례
사례 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: “맞는 알고리즘인데도 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의 범위와 현재 풀이의 차수를 한 줄로 적는 것에서 절반은 끝납니다. 나머지는 중복 계산 제거·맞는 자료구조 두 가지 축으로만 점검하면 됩니다.
핵심 체크리스트 요약
- N 범위 확인 → 허용 복잡도 추정
- 중첩 루프 → 정렬/투포인터/이진탐색으로 축소
- 반복 계산 → 누적합/슬라이딩윈도우로 전처리
- 존재/빈도 → 해시맵/Set으로 O(1) 조회
- 쿼리 반복 → 세그먼트트리/Sparse Table로 쿼리당 비용 감소
- 가중치 그래프 → 다익스트라/벨만-포드로 최단 경로
다음 단계
- 패턴 연습: 두 포인터·슬라이딩 윈도우
- 그래프 알고리즘: BFS vs DFS 비교
- 실전 최적화 사례: 알고리즘 최적화 사례 연구
코딩테스트에서 TLE를 만나면 당황하지 말고 이 체크리스트를 30초 안에 훑어보세요. 대부분의 경우 자료구조 하나만 바꿔도 복잡도 클래스가 바뀝니다.