Ch.12 유사 사례와 키워드 정리¶

앞에서 트리 순회, BFS/DFS, DAG와 위상 정렬을 확인했다. 이제 같은 원리가 적용되는 실무 사례들을 모아본다. Part 3 (Ch.10~12)의 마지막이다.

12-7. 유사 사례¶

사례 1: 조직도 트리 (self-referential 테이블)¶

사원 테이블에 manager_id가 있다. 사원 → 매니저 → 팀장 → 부서장 → CEO로 트리가 이어진다.

CREATE TABLE employees (
    id INT PRIMARY KEY,
    name VARCHAR(100),
    manager_id INT NULL  -- 상위 매니저
);

"이 매니저 아래 모든 사원" 같은 쿼리가 자주 필요하다. 카테고리 트리와 100% 같은 패턴이다. 재귀 CTE나 Materialized Path가 똑같이 적용된다. ERP, 인사 시스템, 권한 관리(매니저는 부하의 정보를 본다) 어디에서나 등장한다.

사례 2: 댓글 트리 (대댓글 구조)¶

Reddit이나 디스코드 스레드처럼 댓글에 대댓글이 달리는 구조다. parent_comment_id로 self-reference 한다. 깊이 제한이 없으면 사용자가 만든 트리가 1,000 단계가 될 수 있다. 재귀로 처리하면 Stack Overflow가 난다.

(Reddit은 일정 깊이 이상의 댓글은 UI에서 접어버린다. 그게 단순한 UX 결정 같지만, 사실은 트리 깊이 폭주를 막는 안전장치다.)

사례 3: 파일 시스템 용량 계산¶

디렉토리의 전체 용량을 계산하려면 하위 디렉토리를 재귀적으로 순회해야 한다. du -sh 명령이 하는 일이 트리의 DFS다. 깊은 디렉토리에서 Python의 os.walk()가 안전한 이유는, 내부적으로 재귀가 아니라 명시적 Stack으로 구현되어 있기 때문이다.

사례 4: 웹 크롤러와 BFS¶

특정 페이지에서 시작해서 링크를 따라가며 페이지를 수집한다. BFS로 구현하면 "가까운 페이지부터", DFS로 구현하면 "한 방향으로 끝까지" 크롤링한다. 검색 엔진은 보통 BFS를 쓴다. "유명한 사이트는 다른 사이트에서 많이 링크된다"는 가정 때문에, 가까운 거리부터 크롤링하면 중요한 페이지를 빨리 수집할 수 있다.

사례 5: 친구 추천 (그래프 + BFS)¶

"친구의 친구" 추천이 BFS다. 내 노드에서 거리 2인 사람들을 BFS로 찾는다.

def friends_of_friends(user, graph):
    visited = {user}
    queue = deque([(user, 0)])
    candidates = set()
    while queue:
        node, depth = queue.popleft()
        if depth == 2:
            candidates.add(node)
            continue
        for friend in graph[node]:
            if friend not in visited:
                visited.add(friend)
                queue.append((friend, depth + 1))
    return candidates

Facebook의 "People You May Know", LinkedIn의 "2nd degree connection"이 전부 이 패턴이다. 실제로는 거리뿐 아니라 공통 친구 수, 같은 회사/학교 같은 가중치도 같이 본다.

사례 6: 작업 스케줄링 (DAG + Topological Sort)¶

Airflow DAG가 대표적이다. ETL 파이프라인은 보통 이렇게 생겼다.

graph LR
    EXT["extract_users"] --> TRANS["transform_users"]
    EXT2["extract_orders"] --> TRANS2["transform_orders"]
    TRANS --> JOIN["join_users_orders"]
    TRANS2 --> JOIN
    JOIN --> AGG["aggregate_metrics"]
    AGG --> LOAD["load_to_warehouse"]

Airflow Scheduler는 매 분 이 DAG를 위상 정렬해서 "지금 실행 가능한 Task"를 찾는다. extract_users와 extract_orders는 의존 관계가 없으니까 병렬로 실행된다. join_users_orders는 양쪽이 다 끝나야 시작한다.

같은 원리가 Spark의 lineage, Kubernetes의 init container 순서, Helm Chart의 hook 순서, ArgoCD Sync Wave에 그대로 적용된다.

사례 7: Kubernetes의 Pod 의존성¶

Pod A가 DB에 의존하고, Pod B가 Pod A에 의존하면, 배포 순서는 DB → A → B다. 이게 DAG의 위상 정렬이다. Helm Chart의 hook이나 ArgoCD의 Sync Wave가 이 원리로 동작한다.

사례 8: 패키지 의존성 (pip, npm)¶

pip install fastapi를 하면 fastapi가 의존하는 starlette, pydantic, anyio, ... 가 줄줄이 설치된다. pip는 의존성 트리를 위상 정렬해서 "leaf부터" 설치한다. npm도 마찬가지다.

(npm의 악명 높은 node_modules는 의존성 그래프를 평탄화한 결과다. 같은 패키지의 다른 버전이 동시에 필요하면 중첩 설치도 한다. yarn, pnpm은 이 문제를 다르게 푼다.)

사례 9: 검색 엔진 자동완성 (Trie)¶

검색창에 "ap"를 치면 "apple", "application", "april"이 자동완성된다. 이게 Trie(트라이) 자료구조다.

graph TD
    ROOT["root"] --> A["a"]
    A --> P["p"]
    P --> P2["p"]
    P2 --> L["l"]
    L --> E["e (apple)"]
    P --> R["r"]
    R --> I["i"]
    I --> L2["l (april)"]
    P2 --> L3["l"]
    L3 --> I2["i"]
    I2 --> C["c"]
    C --> A2["a"]
    A2 --> T["t"]
    T --> I3["i"]
    I3 --> O["o"]
    O --> N["n (application)"]

각 노드가 한 글자를 담는다. "ap"까지 따라간 다음, 그 아래 모든 leaf를 BFS/DFS로 수집하면 자동완성 후보가 된다. 검색어 prefix 매칭, IP 라우팅 테이블(Longest Prefix Match), 사전 압축 저장(예: DAFSA)에 쓰인다.

Trie (트라이)

문자열을 효율적으로 저장하고 prefix 검색을 빠르게 수행하는 트리 자료구조다. 각 노드가 한 글자를 담고, 루트에서 노드까지의 경로가 문자열을 이룬다. 자동완성, 사전 검색, IP 라우팅 테이블에 쓰인다. 같은 prefix를 공유하는 문자열이 많을수록 메모리 효율이 좋다. Radix Tree나 DAFSA는 Trie를 압축한 변형이다.

사례 10: ML 모델의 계산 그래프¶

PyTorch나 TensorFlow의 forward pass도 DAG다. 입력 텐서에서 시작해 연산을 거쳐 출력 텐서까지의 경로가 그래프로 표현된다. backward pass(역전파)는 이 DAG를 역순으로 순회하면서 gradient를 계산한다. autograd가 위상 정렬을 내부에서 한다.

그래서 실무에서는 어떻게 하는가¶

"트리/그래프 문제"를 만났을 때의 체크리스트는 이렇다.

데이터 모양이 진짜 트리인가, 일반 그래프인가
트리: parent_id가 한 개, 사이클 없음 (카테고리, 조직도, 댓글)
그래프: 다대다 관계, 사이클 가능 (친구 관계, 페이지 링크)
DAG: 그래프인데 사이클 없음 (의존성, 파이프라인)
깊이가 사용자/데이터에 따라 변할 수 있는가
예: 반복문 + 명시적 Stack/Queue로 구현
아니오: 재귀로 간결하게 (단, 깊이 한계는 코드로 강제)
조회가 많은가, 변경이 많은가
조회 위주: Materialized Path, Closure Table
변경 위주: Adjacency List (parent_id) + 메모리 트리 구성
DB 엔진을 믿는다: 재귀 CTE
메모리에 다 들어가는가
들어감: 한 번 로드 후 메모리 BFS/DFS
안 들어감: DB 재귀 쿼리 또는 부분 로딩
사이클 가능성이 있는가
있음: 방문 노드 추적 필수 (visited set)
DAG여야 함: 사전에 위상 정렬로 검증

Part 3 마무리¶

Part 3 (Ch.10~12)에서 다룬 핵심:

자료구조 선택이 성능을 결정한다 (Ch.10: List vs Set, 4,000배 차이)
정렬과 검색은 DB 인덱스의 기초다 (Ch.11: B-Tree, EXPLAIN)
트리와 그래프는 계층 데이터와 의존성의 언어다 (Ch.12: BFS/DFS, DAG)

Part 4부터는 데이터베이스를 깊게 파고든다. Ch.10~12의 자료구조 지식이 DB 인덱스, 쿼리 최적화, 트랜잭션을 이해하는 기반이 된다.

12-8. 면접 Q&A (이 챕터로 답할 수 있는 단골 질문)¶

BFS와 DFS는 언제 어떻게 골라 쓰나요?

"최단 경로"나 "레벨 단위 처리"는 BFS다. 가까운 노드부터 방문하니까 거리 기준으로 답을 찾을 수 있다. "모든 경로 탐색", "존재 여부 확인", "사이클 감지"는 DFS가 적합하다. 깊이가 매우 깊을 가능성이 있으면 BFS는 Queue에 형제 노드를 다 담아야 해서 메모리가 부담된다. 반대로 DFS는 재귀로 쓰면 Stack Overflow 위험이 있다. 둘 다 시간 복잡도는 O(V+E)로 동일하다.

Python에서 BFS Queue로 List 대신 deque를 쓰는 이유가 뭔가요?

list.pop(0)이 O(n)이기 때문이다. 리스트 앞에서 원소를 빼면 뒤의 모든 원소를 한 칸씩 당겨야 한다. collections.deque의 popleft()는 O(1)이다. deque는 이중 연결 리스트 기반이라 양쪽 끝에서 O(1) 삽입/제거가 가능하다. BFS처럼 앞에서 빼고 뒤에 넣는 패턴(FIFO)에서는 deque가 정답이다. Ch.10에서 본 자료구조 선택 기준이 그래프 순회에도 그대로 적용된다.

재귀 DFS와 반복문 DFS, 어느 쪽을 써야 하나요?

깊이가 얕고 예측 가능하면 재귀가 코드가 깔끔하다. 그런데 트리·그래프 깊이를 예측할 수 없으면 반복문 + 명시적 Stack이 안전하다. 재귀는 함수 호출마다 Stack Frame이 쌓여서, Python은 기본 재귀 제한 1,000에 걸리면 RecursionError가 난다. sys.setrecursionlimit()으로 늘릴 수도 있지만 OS Stack 한계가 따로 있어서 진짜 해결은 아니다. 반복문 버전은 Heap 메모리의 List를 Stack으로 쓰니까 그 제한을 받지 않는다.

카테고리 트리를 재귀로 조회했더니 DB 쿼리가 폭증했어요. 어떻게 해결하나요?

세 가지 방향이 있다. 첫째, 전체 카테고리를 한 번에 가져온 뒤 메모리에서 부모-자식 Dict를 구성해 BFS/DFS로 순회한다. DB 쿼리가 1번으로 줄어든다. 둘째, MySQL 8.0+/PostgreSQL/SQLite가 지원하는 재귀 CTE(WITH RECURSIVE)로 DB 엔진이 트리 순회를 처리하게 맡긴다. 셋째, Materialized Path로 경로를 문자열에 저장해 LIKE 한 방으로 조회한다. 트래픽이 읽기 위주면 Materialized Path가 가장 빠르다. 이건 N+1 Problem의 트리 버전인데, Ch.13에서 더 자세히 다룬다.

DAG가 뭐고 실무에서 어디에 쓰이나요?

방향이 있고 사이클이 없는 그래프다. "A를 먼저 해야 B를 할 수 있다" 같은 의존 관계를 표현하기에 적합하다. 빌드 시스템(Bazel, Gradle), CI/CD 파이프라인, Airflow 같은 데이터 파이프라인, 패키지 매니저(pip, npm), Terraform 리소스 그래프, Spark lineage, ML 모델의 계산 그래프가 전부 내부적으로 DAG를 쓴다. Kubernetes 배포 순서나 Helm Chart, ArgoCD Sync Wave도 같은 원리다.

위상 정렬은 뭘 하는 알고리즘인가요?

DAG에서 간선의 방향을 거스르지 않으면서 모든 노드를 일렬로 나열하는 알고리즘이다. "선행 조건을 먼저 처리하는 순서"를 결정한다. 진입 차수(in-degree)가 0인 노드부터 꺼내고, 꺼낸 노드와 연결된 간선을 제거하면서 새로 진입 차수가 0이 된 노드를 큐에 넣는 방식(Kahn's Algorithm)이 대표적이다. 사이클이 있으면 위상 정렬이 불가능한데, 이걸 역으로 이용해 사이클 감지에도 쓴다.

인접 리스트와 인접 행렬, 언제 어느 걸 쓰나요?

실무 그래프는 대부분 희소(sparse)하기 때문에 인접 리스트가 기본이다. SNS 친구, 페이지 링크, 패키지 의존성 모두 노드 수 대비 간선이 훨씬 적다. 인접 행렬은 O(V²) 공간을 쓰니까 노드가 만 개만 돼도 1억 칸이 필요하다. 행렬을 쓰는 경우는 노드 수가 작거나(< 1000) 거의 모든 노드가 서로 연결된 밀집 그래프, 그리고 행렬 연산이 본업인 경우(그래프 알고리즘 중 일부)다.

사이클 탐지는 어떻게 하나요?

DFS에 세 가지 상태(WHITE, GRAY, BLACK)를 두는 방법이 표준이다. 노드를 방문 시작할 때 GRAY, 모든 자식을 다 처리한 뒤 BLACK으로 표시한다. DFS 도중에 GRAY 노드를 다시 만나면 그게 사이클이다. 또 다른 방법은 Kahn's Algorithm을 돌렸을 때 결과 노드 수가 전체 노드 수와 일치하는지 확인하는 거다. 일치하지 않으면 사이클 안의 노드들이 in-degree가 영원히 0이 되지 않아서 큐에 못 들어간 거다.

Trie는 언제 쓰나요?

문자열 prefix 검색이 자주 일어나는 곳이다. 검색창 자동완성, IP 라우팅 테이블(Longest Prefix Match), 사전/스펠 체커, IDE의 식별자 검색이 대표적이다. 같은 prefix를 공유하는 문자열이 많을수록 메모리 효율이 좋다. 메모리가 부담되면 Radix Tree나 DAFSA로 압축한다. Redis 7부터는 prefix 검색이 자주 필요한 케이스를 위해 내부에 Trie 구조를 도입했다.

오늘의 키워드 정리¶

새 키워드¶

BFS (Breadth-First Search)

같은 깊이의 노드를 먼저 방문하는 탐색 알고리즘이다. Queue(FIFO)를 사용한다. 최단 경로 찾기, 레벨 단위 처리에 적합하다. Python에서는 collections.deque로 Queue를 구현한다. 트리가 넓으면 메모리 사용이 크다.

DFS (Depth-First Search)

한 방향으로 끝까지 파고든 뒤 돌아오는 탐색 알고리즘이다. Stack(LIFO)이나 재귀를 사용한다. 재귀 구현은 깔끔하지만 깊이가 깊으면 Stack Overflow 위험이 있다. 반복문 + 명시적 Stack이 더 안전하다. 메모리 사용량은 트리의 깊이에 비례한다.

DAG (Directed Acyclic Graph)

간선에 방향이 있고 사이클이 없는 그래프다. 빌드 시스템, CI/CD, 데이터 파이프라인, 패키지 의존성, Terraform, Spark lineage, ML 계산 그래프 등 실무에서 의존 관계를 표현하는 데 핵심적으로 사용된다.

Topological Sort (위상 정렬)

DAG에서 의존 관계를 지키면서 노드를 일렬로 나열하는 알고리즘이다. "선행 조건을 먼저 처리"하는 순서를 결정한다. Kahn's Algorithm(BFS 기반)이 대표적이다. 사이클이 있으면 위상 정렬이 불가능하므로, 사이클 감지에도 쓰인다.

CTE (Common Table Expression)

SQL의 WITH 키워드로 정의하는 임시 결과 집합이다. WITH RECURSIVE는 재귀 CTE로, 트리/그래프 순회를 SQL 한 방으로 처리할 수 있다. 카테고리/조직도 트리 조회의 표준 해법이다. MySQL 8.0+, PostgreSQL, SQLite, SQL Server, Oracle이 지원한다.

Materialized Path (구체화된 경로)

트리의 각 노드에 루트부터 자기까지의 경로를 문자열로 저장하는 패턴이다. 조회는 LIKE 한 번으로 빠르지만, 트리 구조 변경 시 하위 경로를 전부 갱신해야 한다. 읽기 위주 트리에 적합하다.

Trie (트라이)

문자열을 효율적으로 저장하고 prefix 검색을 빠르게 수행하는 트리 자료구조다. 각 노드가 한 글자를 담는다. 자동완성, 사전 검색, IP 라우팅 테이블에 쓰인다.

Adjacency List / Adjacency Matrix

그래프를 표현하는 두 가지 방식이다. 인접 리스트는 각 노드마다 이웃 노드들의 리스트를 들고 있는 방식으로, O(V+E) 공간을 쓴다. 인접 행렬은 V x V 2차원 배열로 표현하며 O(V²) 공간을 쓴다. 실무 그래프는 대부분 희소하므로 인접 리스트가 기본 선택이다.

In-degree / Out-degree (진입 차수 / 진출 차수)

방향 그래프에서 한 노드로 들어오는 간선의 수가 in-degree, 나가는 간선의 수가 out-degree다. Kahn's Algorithm의 핵심 개념이다.

재등장 키워드¶

키워드	최초 등장	이번 챕터에서의 역할
Stack Frame	Ch.4	재귀 깊이와 Stack Overflow (RecursionError)
Stack Overflow	Ch.4	깊은 트리 재귀의 함정
Hash Map / Dict	Ch.10	인접 리스트, children_map, in-degree 저장
자료구조 선택 기준	Ch.10	list vs deque, 인접 리스트 vs 행렬
B-Tree	Ch.11	트리 자료구조의 DB 특화 버전
N+1 Problem	(Ch.13 예고)	트리의 재귀 쿼리 = N+1의 트리 버전

키워드 연관 관계¶

graph LR
    TREE["Tree"] --> BFS
    TREE --> DFS
    TREE --> TRIE["Trie<br/>(자동완성)"]
    TREE --> BT["B-Tree<br/>(Ch.11)"]

    BFS -->|"Queue"| DEQ["deque<br/>(Ch.10)"]
    DFS -->|"Stack"| STK["Stack<br/>(Ch.4)"]
    DFS -->|"재귀 → Stack Overflow"| SF["Stack Frame<br/>(Ch.4)"]

    GRAPH["Graph"] --> DAG
    GRAPH --> REP["표현 방식"]
    REP --> ADJL["Adjacency List"]
    REP --> ADJM["Adjacency Matrix"]
    ADJL --> HASH["Hash Map<br/>(Ch.10)"]

    DAG --> TS["Topological Sort"]
    TS --> KAHN["Kahn's Algorithm<br/>(in-degree)"]
    DAG --> CYCLE["Cycle Detection<br/>(DFS 3색)"]

    TREE --> STORE["트리 저장 패턴"]
    STORE --> ADJ["Adjacency List<br/>(parent_id)"]
    STORE --> MP["Materialized Path"]
    STORE --> CTE["재귀 CTE"]
    ADJ -.->|"재귀 호출<br/>= N+1 트리 버전"| NP["N+1 Problem<br/>(Ch.13)"]

    DAG --> USE["실무 활용"]
    USE --> AIRFLOW["Airflow"]
    USE --> BUILD["Bazel/Gradle"]
    USE --> PKG["pip/npm"]
    USE --> SPARK["Spark Lineage"]
    USE --> K8S["K8s/Helm"]

여기까지의 지도 (누적)¶

위의 "키워드 연관 관계"가 이번 챕터 안의 연결이라면, 아래는 Ch.1부터 지금까지 도메인별로 쌓인 키워드다. 빈 레인은 앞으로 그 챕터에서 채워진다 — 다 채워지는 과정이 곧 이 강의의 지도다. (이번 챕터에서 추가된 키워드는 굵게.)

도메인	누적 키워드 (등장 챕터)
OS·실행	System Call·Kernel·Mode Switch·Buffer·File Descriptor(2) → CPU/IO Bound·GIL·Event Loop·async/await·Thread/Process Pool·Context Switch·IPC(3) → Process·Thread·PCB/TCB·Memory Layout·Virtual Memory·Page·TLB·OOM(4)
동시성·트랜잭션	Race Condition·Critical Section·Mutex/Lock·Deadlock·Semaphore·Starvation(5)
자료구조·알고리즘	Hash Table·Time/Space Complexity·Linear Search·Load Factor(10) → Binary Search·B-Tree/B+Tree·Index·Full Table Scan·Tim Sort·EXPLAIN(11) → BFS·DFS·DAG·Topological Sort·Trie·Adjacency List(12)
DB·캐시·튜닝	— (Ch.13에서 시작)
네트워크·분산	TCP/IP·Socket·3/4-Way Handshake·Connection Pool·Keep-Alive·TIME_WAIT(6)
설계·AI·품질·보안	Computational Thinking·CS 키워드(1) → LLM·Token·Context Window·Hallucination·Prompt Engineering(7) → 키워드 사전·DNS·Load Balancing·Circuit Breaker·CQRS(8) → Code Review·YAGNI·Cache Stampede(9)

다음 챕터(Ch.13)부터 Part 4: 데이터베이스 깊게 보기다. "JPA를 써서 DB를 모른다고요?"라는 제목부터 찔리지 않는가? 이번 챕터에서 살짝 다룬 N+1 Problem과 재귀 CTE가 거기서 정식으로 등장한다.

< BFS, DFS, 그리고 DAG