코딩테스트, "자료구조"가 아니라 "연산"으로 반응하라 - 연산 Abstraction
자료구조를 기준으로 function을 찾을 때는 문제
"스택은 이럴 때, 큐는 저럴 때..."
무엇보다 공통점, 단조로움에 대해서 처음에 관통이 어려움문제는 연산을 요구한다.
"어떤 자료구조를 쓰지?" 가 아니라
"어떤 연산이 필요하지?" 로 먼저 반응하는 순간
패턴이 보이기 시작한다. - 연산으로부터 패턴의 정형화
연산들을 토대로 공통점 분류 작업 project
목차
- 탐색 (Search)
- 구간 (Range)
- 우선순위 (Priority)
- 빈도 / 해시 (Frequency / Hash)
- 연결 / 집합 (Graph / Union)
- 그래프 탐색 응용 (Graph Traversal)
- DP (Dynamic Programming)
- 복잡도 한계 기준
1. 탐색 (Search)
| 시그널 | 패턴 | 복잡도 | 전환 조건 |
|---|---|---|---|
| 정렬된 배열에서 값/위치/개수 | bisect | O(log N) | 정렬 안 됐으면 불가 |
| "최솟값의 최대화" / "최댓값의 최소화" | 파라메트릭 서치 | O(N log N) | check 함수가 O(N) 이하여야 의미 있음 |
| 연속 구간 + 조건 + 크기 가변 | 투 포인터 | O(N) | 음수 포함이면 prefix sum + hashmap |
| 연속 구간 + 조건 + 크기 고정 | 슬라이딩 윈도우 | O(N) | 최솟값/최댓값 필요하면 deque |
| 문자열에서 패턴 위치/횟수 | KMP | O(N+M) | N×M < 10⁷ 이면 브루트포스 가능 |
| 공통 접두사 / 자동완성 | 트라이 | O(L) | 문자열 수 × 길이가 메모리 초과 주의 |
반응 기준
"~이상/~이하 중 최적값" → 파라메트릭 서치
"합이 K인 연속 구간" → 양수면 투 포인터 / 음수 포함이면 prefix+hash
"길이 K인 구간의 최대/최소" → 슬라이딩 윈도우
"정렬된 배열에서 몇 번째 / 몇 개" → bisect
"문자열 안에서 패턴" → KMP핵심 원리
bisect
정렬된 배열에서 선형 탐색 O(N) 대신,
단조성을 이용해 절반씩 제거하며 O(log N)에 위치를 찾는다.
import bisect
arr = sorted([4, 1, 7, 2, 9]) # [1, 2, 4, 7, 9]
bisect.bisect_left(arr, 5) # 3 → 5 이상인 첫 번째 인덱스
bisect.bisect_right(arr, 5) # 3 → 5 초과인 첫 번째 인덱스
# 범위 [lo, hi] 안의 원소 개수
def count_range(arr, lo, hi):
return bisect.bisect_right(arr, hi) - bisect.bisect_left(arr, lo)투 포인터
right를 늘릴수록 조건에 가까워지고, left를 당길수록 조건이 완화되는
단조성을 이용해 O(N²) → O(N)으로 줄인다.
left = 0
total = 0
answer = float('inf')
for right in range(n):
total += arr[right]
while total >= s: # 조건 만족하는 동안 최단 탐색
answer = min(answer, right - left + 1)
total -= arr[left]
left += 1슬라이딩 윈도우
크기 K인 구간을 매번 처음부터 계산하지 않고,
이전 결과에서 1개 빼고 1개 더하는 재사용으로 O(N×K) → O(N).
window_sum = sum(arr[:k])
answer = window_sum
for i in range(k, n):
window_sum += arr[i] # 오른쪽 추가
window_sum -= arr[i - k] # 왼쪽 제거
answer = max(answer, window_sum)파라메트릭 서치
정답 후보 범위에 단조성이 있을 때,
"이 값이 답이 될 수 있는가"를 O(N) check 함수로 판별하며
범위를 절반씩 줄여 O(N log N)에 최적값을 찾는다.
def check(mid):
return sum(max(tree - mid, 0) for tree in trees) >= m
left, right = 0, max(trees)
answer = 0
while left <= right:
mid = (left + right) // 2
if check(mid):
answer = mid
left = mid + 1
else:
right = mid - 12. 구간 (Range)
| 시그널 | 패턴 | 복잡도 | 전환 조건 |
|---|---|---|---|
| 구간 합 쿼리 (배열 불변) | 누적합 / 2D 누적합 | O(1) / 쿼리 | 배열이 바뀌면 BIT로 |
| 구간 전체에 값 일괄 추가 | 차이 배열 | O(1) / 업데이트 | 점 업데이트는 불가 |
| 점 업데이트 + 구간 합 | BIT (Fenwick Tree) | O(log N) | 최솟값/최댓값은 세그트리로 |
| 점 업데이트 + 구간 최솟값·최댓값 | 세그먼트 트리 | O(log N) | 구현 복잡 — BIT로 안 될 때만 |
| 오른쪽/왼쪽으로 다음 크거나 작은 값 | 단조 스택 | O(N) | 구간 최솟값이 아니라 "다음 값" |
| 고정 구간 내 최솟값/최댓값 반복 쿼리 | 스파스 테이블 | O(1) / 쿼리 | 배열 불변일 때만 / 전처리 O(N log N) |
반응 기준
배열이 안 바뀜 + 구간 합 → 누적합
배열이 안 바뀜 + 구간 최솟값 → 스파스 테이블
배열이 바뀜 + 구간 합 → BIT
배열이 바뀜 + 구간 최솟값·최댓값 → 세그먼트 트리
"다음으로 큰 수" / 히스토그램 → 단조 스택
구간에 일괄 더하기만 → 차이 배열핵심 원리
누적합
prefix[i] = arr[0] + ... + arr[i-1] 을 전처리해두면
구간 [l, r] 합을 prefix[r+1] - prefix[l] 로 O(1)에 계산.
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] + arr[i]
# 구간 [l, r] 합
query = prefix[r + 1] - prefix[l]단조 스택
스택에 "아직 다음으로 큰 값을 못 찾은 인덱스"를 유지.
새 원소가 스택 top보다 크면 → top의 "다음으로 큰 값"이 확정.
stack = []
result = [-1] * n
for i in range(n):
while stack and arr[stack[-1]] < arr[i]:
result[stack.pop()] = arr[i] # 다음으로 큰 값 확정
stack.append(i)3. 우선순위 (Priority)
| 시그널 | 패턴 | 복잡도 | 전환 조건 |
|---|---|---|---|
| 최솟값 / 최댓값 반복 추출 | heapq | O(log N) | 정적 데이터면 정렬 한 번이 더 빠름 |
| 실시간 K번째 값 유지 | 크기 K 고정 힙 | O(N log K) | K가 고정일 때만 |
| 실시간 중앙값 유지 | 두 힙 조합 | O(log N) | 삽입/삭제 동시에 필요할 때 |
| 특정 원소 삭제 + 최솟값 | 지연 삭제 + heapq | O(log N) | 힙에서 직접 삭제는 O(N) |
반응 기준
"매 순간 가장 작은/큰 것" → heapq
"다익스트라" → heapq 필수
"최댓값이 필요" → -val 음수 트릭
"중앙값을 실시간으로" → 두 힙 조합
"K번째로 큰 값 유지" → 크기 K 최소힙핵심 원리
heapq (다익스트라)
매 단계마다 가장 비용이 작은 노드를 O(log V)에 꺼내서 처리.
힙 없이 매번 전체 스캔하면 O(V²).
import heapq
def dijkstra(graph, start, n):
dist = [float('inf')] * (n + 1)
dist[start] = 0
heap = [(0, start)]
while heap:
cost, u = heapq.heappop(heap)
if cost > dist[u]: # 이미 처리된 노드 스킵
continue
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(heap, (dist[v], v))
return dist두 힙으로 중앙값 유지
작은 절반 → 최대힙 / 큰 절반 → 최소힙으로 나누어
두 힙의 top에서 중앙값을 O(1)에 계산.
import heapq
lower = [] # 최대힙 (부호 반전)
upper = [] # 최소힙
def add(num):
heapq.heappush(lower, -num)
if upper and -lower[0] > upper[0]:
heapq.heappush(upper, -heapq.heappop(lower))
if len(lower) < len(upper):
heapq.heappush(lower, -heapq.heappop(upper))
elif len(lower) > len(upper) + 1:
heapq.heappush(upper, -heapq.heappop(lower))
def median():
if len(lower) > len(upper):
return -lower[0]
return (-lower[0] + upper[0]) / 24. 빈도 / 해시 (Frequency / Hash)
| 시그널 | 패턴 | 복잡도 | 전환 조건 |
|---|---|---|---|
| 값 등장 횟수 | Counter / defaultdict(int) | O(N) | - |
| 합이 K인 두 수 쌍 | 해시맵 + 보수 탐색 | O(N) | 정렬 배열이면 bisect도 가능 |
| 합이 K인 부분 배열 개수 | 누적합 + 해시맵 | O(N) | 양수만이면 투 포인터도 가능 |
| 아나그램 / 동일 구조 그룹핑 | 정규화 키 + 해시맵 | O(N) | - |
| 값 범위가 너무 클 때 인덱스 재매핑 | 좌표 압축 | O(N log N) | 값이 아닌 순서만 필요할 때 |
| 삽입·삭제 중 K번째 원소 | 좌표압축 + BIT | O(N log N) | - |
반응 기준
"몇 번 등장?" → Counter
"두 수 합이 K?" → dict에 보수 저장
"부분 배열 합이 K?" → prefix_sum + dict
"같은 패턴으로 묶어라" → sorted(word) or tuple 정규화 키
"값이 10⁹인데 배열 인덱스로 쓰고 싶다" → 좌표 압축핵심 원리
누적합 + 해시맵 (음수 포함 구간합)
prefix[j] - prefix[i] = k → prefix[j] - k = prefix[i]
"지금까지 본 prefix 합 중 (현재 합 - k)가 있었는가"를 dict로 O(1) 체크.
from collections import defaultdict
def count_subarrays(arr, k):
prefix_count = defaultdict(int)
prefix_count[0] = 1 # arr[0]부터 시작하는 구간 처리
total = 0
answer = 0
for x in arr:
total += x
answer += prefix_count[total - k]
prefix_count[total] += 1
return answer좌표 압축
값이 10⁹까지 있어도 실제로 사용하는 값이 N개뿐이면
0~N-1로 재매핑해서 배열 인덱스로 활용.
sorted_unique = sorted(set(arr))
compress = {v: i for i, v in enumerate(sorted_unique)}
compressed = [compress[x] for x in arr]5. 연결 / 집합 (Graph / Union)
| 시그널 | 패턴 | 복잡도 | 전환 조건 |
|---|---|---|---|
| 같은 그룹인지 / 사이클 감지 | Union-Find | O(α) | 간선 삭제가 필요하면 사용 불가 |
| 최소 비용으로 모든 노드 연결 | 크루스칼 (정렬 + Union-Find) | O(E log E) | 밀집 그래프면 프림이 유리 |
| 가중치 없는 최단 경로 | BFS | O(V+E) | 가중치 있으면 다익스트라로 |
| 양수 가중치 최단 경로 | 다익스트라 + heapq | O(E log V) | 음수 가중치 있으면 벨만-포드 |
| 음수 가중치 / 전체 쌍 최단 경로 | 플로이드-워셜 | O(V³) | V > 500 이면 시간 초과 |
| 선행 조건 / 의존성 순서 | 위상 정렬 | O(V+E) | 사이클 있으면 위상 정렬 불가 |
| 가중치가 0 또는 1 | 0-1 BFS (deque) | O(V+E) | 다익스트라보다 빠름 |
반응 기준
"연결되어 있냐?" → Union-Find or BFS/DFS
"최소 비용 연결" → 크루스칼
"최단 거리" → 무가중 BFS / 양수 다익스트라 / 음수 벨만포드
"순서가 있는 의존성" → 위상 정렬
"0 또는 1 가중치" → 0-1 BFS핵심 원리
Union-Find
두 노드가 같은 집합인지를 O(α) ≈ O(1)에 판별.
경로 압축 + 랭크 병합으로 트리가 납작하게 유지됨.
parent = list(range(n + 1))
rank = [0] * (n + 1)
def find(x):
if parent[x] != x:
parent[x] = find(parent[x]) # 경로 압축
return parent[x]
def union(x, y):
px, py = find(x), find(y)
if px == py:
return False # 이미 같은 집합 → 사이클
if rank[px] < rank[py]:
px, py = py, px
parent[py] = px
if rank[px] == rank[py]:
rank[px] += 1
return True위상 정렬
진입차수가 0인 노드부터 처리하며 의존성 순서를 결정.
처리된 노드 수가 전체보다 적으면 사이클 존재.
from collections import deque
indegree = [0] * (n + 1)
for u, v in edges:
indegree[v] += 1
q = deque([i for i in range(1, n+1) if indegree[i] == 0])
order = []
while q:
node = q.popleft()
order.append(node)
for next_node in graph[node]:
indegree[next_node] -= 1
if indegree[next_node] == 0:
q.append(next_node)
if len(order) != n:
print("사이클 존재")6. 그래프 탐색 응용 (Graph Traversal)
| 시그널 | 패턴 | 복잡도 | 전환 조건 |
|---|---|---|---|
| 영역 크기 / 연결 컴포넌트 | DFS / BFS | O(V+E) | - |
| 조건 붙은 상태 공간 탐색 | BFS + 상태 튜플 | O(상태 수) | 상태가 너무 많으면 DP로 |
| 사이클 탐지 / 무한루프 판별 | DFS + 색칠 (white/gray/black) | O(V+E) | - |
| 트리에서 두 노드 최단 거리 | LCA (최소 공통 조상) | O(log N) | 일반 BFS로 안 되는 쿼리가 많을 때 |
반응 기준
"섬의 개수" / "영역 넓이" → DFS/BFS 컴포넌트
"문 열쇠 / 조건부 이동" → BFS + (위치, 상태) 튜플
"이 노드에서 탈출 가능?" → DFS 색칠
"트리에서 두 노드 거리 쿼리" → LCA핵심 원리
BFS + 상태 튜플
단순 위치만으로는 방문 체크가 안 되는 경우,
(위치, 조건 상태)를 튜플로 묶어서 visited에 저장.
from collections import deque
visited = set()
q = deque([(start_r, start_c, initial_state)])
visited.add((start_r, start_c, initial_state))
while q:
r, c, state = q.popleft()
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
nr, nc = r + dr, c + dc
new_state = update(state, nr, nc)
if (nr, nc, new_state) not in visited:
visited.add((nr, nc, new_state))
q.append((nr, nc, new_state))7. DP (Dynamic Programming)
| 시그널 | 패턴 | 복잡도 | 전환 조건 |
|---|---|---|---|
| 순서대로 최적값 / 경우의 수 누적 | 1D / 2D DP | O(N), O(N²) | 그리디 교환 논증 안 되면 DP |
| 구간을 분할해 최적화 | 구간 DP | O(N³) | N > 500 이면 시간 초과 |
| 트리에서 자식 → 부모 집계 | 트리 DP | O(N) | - |
| 부분집합 선택 / 순열 상태 압축 | 비트마스크 DP | O(2^N × N) | N ≤ 20 이하일 때만 |
| DAG 위상 순서 기반 점화식 | 위상정렬 DP | O(V+E) | - |
반응 기준
"최대/최소/경우의 수" + 앞 결과가 뒤에 영향 → DP
구간 [i, j] 최적값 → 구간 DP
N ≤ 20이고 모든 선택 조합 → 비트마스크 DP
트리에서 서브트리 집계 → 트리 DP
그리디 교환 논증이 안 됨 → DP로 전환핵심 원리
DP의 본질은 "이미 계산한 부분 문제의 결과를 재사용해서 중복 계산을 없애는 것".
그리디와의 구분 기준은 교환 논증이다.
"지금 최적 선택이 나중에도 최적을 보장하는가" → YES면 그리디, NO면 DP.
# 배낭 문제 — 전형적인 2D DP
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
weight, value = items[i - 1]
for w in range(capacity + 1):
dp[i][w] = dp[i - 1][w] # 안 담는 경우
if w >= weight:
dp[i][w] = max(dp[i][w], dp[i-1][w-weight] + value)8. 복잡도 한계 기준
코딩테스트 현장에서 시간 초과를 피하는 기준표.
10⁸ 연산 / 초 기준으로 역산한다.
N = 10⁶ → O(N) or O(N log N) 까지
N = 10⁵ → O(N log N) or O(N log² N) 까지
N = 10⁴ → O(N²) 까지
N = 10³ → O(N² log N) 까지
N = 500 → O(N³) 까지 → 플로이드-워셜, 구간 DP
N = 20 → O(2^N × N) 까지 → 비트마스크 DP
N = 10 → O(N!) 까지 → 완전탐색 / 백트래킹마치며
패턴은 외우는 것이 아니라 원리로 이해하는 것이다.
"왜 이 연산이 이 복잡도인가"를 이해하면
처음 보는 문제에서도 패턴이 보인다.모든 패턴의 공통점은 하나다.
"어차피 볼 필요 없는 것을 건너뛰는 방법을 찾는 것"
edit하는 개발자! story 있는 삶