1 개요
Level 5는 대부분의 개발자에게 불필요한 내용을 포함한다. 자신의 트랙에 집중한다. DS 트랙은 SQL 재귀 CTE, Island & Gaps, PIVOT을 익히면 대부분의 분석 문제를 해결할 수 있다. AIE 트랙은 세그먼트 트리, 위상 정렬, Trie, 정수론을 중심으로 준비한다.
2 DS vs AIE 트랙 우선순위
| 도구/개념 | DS 우선순위 | AIE 우선순위 | 설명 |
|---|---|---|---|
| 세그먼트 트리 | ★☆☆ | ★★★ | 구간 쿼리 + 업데이트 \(O(\log N)\) |
| Binary Indexed Tree (BIT) | ★☆☆ | ★★★ | 누적합 업데이트 \(O(\log N)\) |
| 위상 정렬 | ★☆☆ | ★★★ | DAG 순서 결정 |
| 문자열 KMP/Trie | ★★☆ | ★★★ | 패턴 매칭, 자동완성 |
| 고급 DP (구간, 트리) | ★★☆ | ★★★ | 구간 DP, 트리 DP |
| SQL 재귀 CTE | ★★★ | ★★☆ | 계층형 쿼리 |
| SQL Island & Gaps | ★★★ | ★★☆ | 연속 구간 분석 |
| SQL PIVOT | ★★★ | ★☆☆ | 행→열 변환 |
| 정수론 (소수, 모듈러) | ★☆☆ | ★★★ | 암호화, 조합 계산 |
sortedcontainers.SortedList |
★★★ | ★★★ | 정렬 유지 삽입/삭제 |
3 세그먼트 트리 (AIE 핵심)
class SegmentTree:
"""구간 합 세그먼트 트리"""
def __init__(self, arr):
self.n = len(arr)
self.tree = [0] * (4 * self.n)
self._build(arr, 1, 0, self.n - 1)
def _build(self, arr, node, start, end):
if start == end:
self.tree[node] = arr[start]
else:
mid = (start + end) // 2
self._build(arr, 2*node, start, mid)
self._build(arr, 2*node+1, mid+1, end)
self.tree[node] = self.tree[2*node] + self.tree[2*node+1]
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, start, mid, idx, val)
else:
self.update(2*node+1, mid+1, end, idx, val)
self.tree[node] = self.tree[2*node] + self.tree[2*node+1]
def query(self, node, start, end, l, r):
if r < start or end < l:
return 0
if l <= start and end <= r:
return self.tree[node]
mid = (start + end) // 2
return (self.query(2*node, start, mid, l, r) +
self.query(2*node+1, mid+1, end, l, r))
arr = [1, 3, 5, 7, 9, 11]
st = SegmentTree(arr)
st.query(1, 0, 5, 1, 3) # → 15 (arr[1]+arr[2]+arr[3] = 3+5+7)
st.update(1, 0, 5, 2, 10) # arr[2] = 10으로 변경
st.query(1, 0, 5, 1, 3) # → 20 (3+10+7)4 위상 정렬 (AIE 핵심)
from collections import deque
def topological_sort(n, edges):
"""
n: 노드 수
edges: [(from, to), ...] — 방향 간선
반환: 위상 정렬 순서 (불가능하면 빈 리스트)
"""
indegree = [0] * (n + 1)
graph = [[] for _ in range(n + 1)]
for u, v in edges:
graph[u].append(v)
indegree[v] += 1
queue = deque([i for i in range(1, n+1) if indegree[i] == 0])
result = []
while queue:
node = queue.popleft()
result.append(node)
for next_node in graph[node]:
indegree[next_node] -= 1
if indegree[next_node] == 0:
queue.append(next_node)
return result if len(result) == n else [] # n개가 안 나오면 사이클 존재
edges = [(1,3), (1,4), (2,3), (2,4), (3,5), (4,5)]
topological_sort(5, edges)
# → [1, 2, 3, 4, 5] 또는 [2, 1, 3, 4, 5] 등 가능한 순서 중 하나5 Trie (접두사 트리) (AIE 핵심)
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True
def search(self, word):
node = self.root
for ch in word:
if ch not in node.children:
return False
node = node.children[ch]
return node.is_end # True이면 완전한 단어
def starts_with(self, prefix):
node = self.root
for ch in prefix:
if ch not in node.children:
return False
node = node.children[ch]
return True # prefix로 시작하는 단어가 존재한다
trie = Trie()
for word in ["apple", "app", "application"]:
trie.insert(word)
trie.search("app") # → True (완전한 단어)
trie.search("appl") # → False (중간 단계)
trie.starts_with("appl") # → True (apple, application의 접두사)6 구간 DP
# 행렬 연쇄 곱셈 — 구간 DP 대표 문제
def matrix_chain(dims):
"""
dims: 행렬 크기 리스트 [p0, p1, ..., pn]
A[i] = dims[i] x dims[i+1]
"""
n = len(dims) - 1
dp = [[0] * n for _ in range(n)]
for length in range(2, n + 1): # 구간 길이 2부터
for i in range(n - length + 1):
j = i + length - 1
dp[i][j] = float('inf')
for k in range(i, j):
cost = dp[i][k] + dp[k+1][j] + dims[i] * dims[k+1] * dims[j+1]
dp[i][j] = min(dp[i][j], cost)
return dp[0][n-1]
matrix_chain([10, 30, 5, 60])
# → 4500 (최적: (A0*A1)*A2 = 10*30*5 + 10*5*60 = 1500+3000 = 4500)7 SQL 재귀 CTE (DS 핵심)
-- 조직도 계층 구조 탐색
WITH RECURSIVE org_tree AS (
-- 기저 케이스: 최상위 관리자
SELECT id, name, manager_id, 1 AS level
FROM employees
WHERE manager_id IS NULL
UNION ALL
-- 재귀 케이스: 부하 직원
SELECT e.id, e.name, e.manager_id, t.level + 1
FROM employees e
JOIN org_tree t ON e.manager_id = t.id
)
SELECT id, name, level
FROM org_tree
ORDER BY level, name;
-- level=1이 최상위, level=2가 직속 부하, 이하 순서대로 증가한다
-- 연속 날짜 구간 생성 (날짜 시퀀스)
WITH RECURSIVE dates AS (
SELECT '2024-01-01' AS dt
UNION ALL
SELECT DATE_ADD(dt, INTERVAL 1 DAY)
FROM dates
WHERE dt < '2024-01-31'
)
SELECT dt FROM dates;
-- 2024-01-01부터 2024-01-31까지 날짜를 생성한다8 SQL Island & Gaps (DS 핵심)
-- Island: 연속 구간 찾기
-- 데이터가 있는 날짜의 연속 구간을 찾는다
WITH numbered AS (
SELECT
date,
ROW_NUMBER() OVER (ORDER BY date) AS rn,
DATE_SUB(date, INTERVAL ROW_NUMBER() OVER (ORDER BY date) DAY) AS grp
FROM active_dates
)
SELECT
MIN(date) AS start_date,
MAX(date) AS end_date,
COUNT(*) AS days
FROM numbered
GROUP BY grp
ORDER BY start_date;
-- 연속된 날짜들을 같은 grp으로 묶어 구간의 시작/끝을 반환한다
-- Gap: 빠진 구간 찾기
WITH dates AS (
SELECT date, LEAD(date) OVER (ORDER BY date) AS next_date
FROM active_dates
)
SELECT date AS gap_start, next_date AS gap_end
FROM dates
WHERE DATEDIFF(next_date, date) > 1;
-- 날짜가 건너뛰어진 구간(갭)을 반환한다9 SQL PIVOT (CASE 기반) (DS 핵심)
-- 행→열 변환 (Pivot)
-- 분기별 매출을 한 행으로 변환
SELECT
year,
SUM(CASE WHEN quarter = 'Q1' THEN revenue ELSE 0 END) AS Q1,
SUM(CASE WHEN quarter = 'Q2' THEN revenue ELSE 0 END) AS Q2,
SUM(CASE WHEN quarter = 'Q3' THEN revenue ELSE 0 END) AS Q3,
SUM(CASE WHEN quarter = 'Q4' THEN revenue ELSE 0 END) AS Q4
FROM quarterly_sales
GROUP BY year;
-- 연도별로 4개 분기 매출이 열로 펼쳐진다10 sortedcontainers.SortedList
from sortedcontainers import SortedList # pip install sortedcontainers
sl = SortedList([5, 1, 3, 2, 4])
# sl → SortedList([1, 2, 3, 4, 5]) (자동 정렬)
sl.add(3.5) # sl → SortedList([1, 2, 3, 3.5, 4, 5])
sl.remove(3) # sl → SortedList([1, 2, 3.5, 4, 5])
sl[0] # → 1 (최솟값)
sl[-1] # → 5 (최댓값)
sl.bisect_left(4) # → 3 (4가 삽입될 왼쪽 인덱스)
sl.count(3.5) # → 1
# 삽입/삭제 O(log n), 인덱스 접근 O(log n)
# 코딩 테스트에서 정렬 상태를 유지하며 동적으로 원소를 추가/삭제할 때 사용한다11 정수론 (AIE 핵심)
# 에라토스테네스의 체 — O(n log log n)
def sieve(n):
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, int(n**0.5) + 1):
if is_prime[i]:
for j in range(i*i, n+1, i):
is_prime[j] = False
return [i for i, v in enumerate(is_prime) if v]
sieve(20) # → [2, 3, 5, 7, 11, 13, 17, 19]
# 모듈러 산술 — 큰 수 계산 시 오버플로우 방지
MOD = 1_000_000_007
# 조합 C(n, k) mod MOD — 메모이제이션 활용
from functools import lru_cache
@lru_cache(maxsize=None)
def comb_mod(n, k):
if k == 0 or k == n:
return 1
return (comb_mod(n-1, k-1) + comb_mod(n-1, k)) % MOD
comb_mod(10, 3) # → 120
# 또는 math.comb (Python 3.8+)
import math
math.comb(10, 3) # → 120 (모듈러 없이)12 유형별 사용 도구 매핑 (Level 5)
| 문제 유형 | DS 도구 | AIE 도구 |
|---|---|---|
| 구간 합 + 업데이트 | - | 세그먼트 트리, BIT |
| 작업 순서 결정 | - | 위상 정렬 |
| 접두사 매칭 | - | Trie |
| 구간 최적화 | 구간 DP | 구간 DP |
| 계층 구조 탐색 | 재귀 CTE | - |
| 연속 구간 분석 | Island & Gaps | - |
| 행→열 변환 | PIVOT | - |
| 소수 판별 | - | 에라토스테네스 체 |
| 큰 수 조합 | - | 모듈러 산술 |
| 정렬 유지 동적 삽입 | SortedList | SortedList |
13 Level 5 학습 전략
DS 트랙 우선 학습 순서는 다음과 같다.
- SQL: 재귀 CTE → Island & Gaps → PIVOT
- Python: SortedList → 구간 DP → 문자열 처리
AIE 트랙 우선 학습 순서는 다음과 같다.
- Python: 세그먼트 트리 → 위상 정렬 → Trie
- Python: 정수론 → 고급 DP → 비트 마스킹 심화