Tree & Graph

분류: Layer 10 - 자료구조 & 알고리즘

트리와 그래프 (Tree & Graph)

1. 한 줄 정의

트리는 계층 관계를, 그래프는 임의 관계망을 노드와 엣지로 표현하는 자료구조다.

앞선 L10 문서에서 배열, 큐, 해시 테이블, 정렬, 이진 탐색을 봤다면 이 문서의 질문은 하나로 압축된다. 데이터가 단순히 “나열된 값”이 아니라 부모-자식, 우선순위, 의존성, 연결 경로를 가진다면 어떤 구조로 모델링해야 하는가?

답은 보통 세 갈래다.

• BST/B-Tree 계열: 정렬 순서를 구조 안에 넣어 점 조회와 범위 조회를 같이 다룬다.
• Heap/Priority Queue: “항상 가장 먼저 처리할 것”을 O(1)에 확인하고, O(log n)에 꺼내도록 우선순위를 구조 안에 넣는다.
• Graph Traversal: 임의 연결 관계에서 도달 가능성, 최단 거리, 순환, 실행 순서를 계산한다.

이 문서는 세 구조를 외우는 것이 아니라, 어떤 문제가 생겨서 이 구조가 필요해졌는지 → 어떤 불변식으로 문제를 줄이는지 → 어디서 깨지는지를 따라간다.

---

2. L10 앞 문서에서 이어지는 확장 지도

정렬 배열, FIFO 큐, 해시 테이블만으로 모든 문제를 풀 수 있다면 트리와 그래프는 필요 없다. 하지만 세 구조는 관계를 1급 시민으로 다루지 못한다.

선행 자료구조의 한계와 확장 방향

정렬 배열

Binary Search로 조회는 O(log n)이지만 중간 삽입은 평균 n/2개 shift가 필요하다.

삽입·삭제와 정렬 조회가 모두 중요하면 BST 또는 B-Tree 계열로 확장한다.

FIFO Queue

먼저 들어온 순서만 보존하므로 긴급 작업을 먼저 처리한다는 요구를 표현하지 못한다.

도착 순서보다 우선순위가 중요하면 Heap 기반 Priority Queue로 확장한다.

Hash Table

키 하나의 동등성 조회는 빠르지만 범위, 순서, 의존성, 경로 질문에는 약하다.

순서가 필요하면 Tree, 임의 관계와 경로가 필요하면 Graph로 확장한다.

이 절은 지도만 제공한다. 정량 감각과 실패 신호는 다음 2.5에서 lineage로 풀고, 각 구조의 코드는 4~6장에서 다룬다.

그래프는 더 근본적인 한계를 푼다. “A가 B에 의존하고 B가 C에 의존하면 A는 언제 초기화해야 하는가?”, “A→B→C→A 순환이 있으면 정상인가 오류인가?”, “두 서비스 사이의 최단 호출 경로는 무엇인가?” 같은 질문은 값의 나열이 아니라 관계망 자체가 입력이다. 그래서 그래프는 노드와 엣지를 자료구조의 중심으로 올린다.

---

2.5. 선행 기술의 한계 — Tree & Graph 등장 이유

이 문서의 lineage_oneliner는 “배열과 큐로는 정렬·우선순위·의존성 처리 불가 → 트리와 그래프로 확장”이다. 여기서 “불가”는 구현할 수 없다는 뜻이 아니라, 입력이 커질수록 구조가 요구를 직접 표현하지 못해 비용과 실패 신호가 커진다는 뜻이다.

2.5.1 정렬 순서가 계속 바뀌는 문제

정렬된 배열은 조회가 빠르다. 앞선 sorting-searching.mdx에서 본 Binary Search는 정렬 전제만 있으면 100만 개도 약 20번 비교로 찾는다. 문제는 정렬 상태를 유지한 채 계속 삽입·삭제해야 할 때다.

예를 들어 실시간 랭킹 점수가 초당 수천 건 들어온다고 하자.

정렬 배열:
  새 점수 삽입 위치 찾기: O(log n)
  뒤 원소 밀기: O(n)
  전체 비용: O(n)

균형 BST:
  삽입 위치 찾기: O(log n)
  균형 복구: O(log n) 이내
  전체 비용: O(log n)

정렬 배열은 “순서”를 결과 배열에만 보존한다. BST는 “순서”를 노드의 왼쪽/오른쪽 관계로 보존한다. 이 차이가 삽입 비용을 바꾼다.

2.5.2 도착 순서와 처리 순서가 다른 문제

기본 자료구조 문서의 Queue는 FIFO(First In, First Out)다. BFS나 메시지 큐처럼 “먼저 온 것을 먼저 처리”해야 할 때는 맞다. 하지만 결제 재시도, 장애 알림, OS 스케줄러처럼 “더 급한 것을 먼저 처리”해야 하면 FIFO는 요구와 맞지 않는다.

단순 배열로 우선순위를 처리하는 방법은 두 가지인데 둘 다 한계가 있다.

방식	삽입	최우선 삭제	한계
매번 정렬	O(n log n)	O(1)	쓰기 빈도가 높으면 정렬 비용이 지배
정렬하지 않고 스캔	O(1)	O(n)	읽기 빈도가 높으면 매번 전체 탐색
Heap	O(log n)	O(log n), peek O(1)	임의 탐색은 약하지만 우선순위 처리에 맞음

Heap의 철학은 “전체 정렬은 과하다”이다. 우선순위 큐에서 필요한 것은 모든 원소의 완전한 순서가 아니라 최소값 또는 최대값이 루트에 있다는 보장이다.

2.5.3 의존성 순서와 순환을 묻는 문제

배열이나 해시 테이블은 “A가 B를 참조한다”는 사실을 저장할 수는 있다. 하지만 다음 질문에는 별도 알고리즘이 필요하다.

• AppModule → UserModule → AuthModule → UserModule 순환이 있는가?
• npm 패키지를 어떤 순서로 설치해야 하는가?
• Terraform 리소스 중 병렬 생성 가능한 것은 무엇인가?
• 친구의 친구처럼 2단계 이내 관계를 어떻게 찾는가?

이 질문의 공통점은 노드 하나가 아니라 노드 사이의 엣지 집합이 답을 결정한다는 점이다. 그래프는 이 관계를 직접 모델링하고, DFS/BFS/Topological Sort 같은 알고리즘으로 답을 계산한다.

---

3. 핵심 용어 먼저 잡기

트리와 그래프는 용어가 많다. 하지만 첫 회독에서 꼭 잡아야 하는 축은 많지 않다.

용어	뜻	왜 필요한가
Node(Vertex)	값 또는 대상을 담는 점	사용자, 작업, 모듈, 패키지, 트리 키처럼 관계의 주체
Edge	노드 사이의 연결	”의존한다”, “연결됐다”, “부모다”, “비용이 있다”를 표현
Root	트리의 시작 노드	부모가 없는 최상위 기준점
Leaf	자식이 없는 트리 노드	탐색이 끝나는 지점
Parent/Child	트리의 상하 관계	계층 구조의 방향을 만든다
Depth	루트에서 특정 노드까지 거리	노드가 얼마나 깊이 있는지
Height	노드에서 가장 먼 leaf까지 거리	탐색 비용 O(h)의 h
Degree	노드에 연결된 엣지 수	그래프 밀도와 탐색 비용에 영향
Path	엣지를 따라 이어진 노드열	도달 가능성과 최단 거리의 기본 단위
Cycle	출발 노드로 다시 돌아오는 경로	의존성 그래프에서는 오류, 소셜 그래프에서는 정상
DAG	Directed Acyclic Graph, 방향 비순환 그래프	위상 정렬이 가능한 의존성 그래프

트리는 그래프의 특수한 형태다. 보통 연결되어 있고, 사이클이 없으며, 부모-자식 방향이 명확한 그래프를 트리라고 부른다. 그래서 트리에서는 부모 방향으로 되돌아가지 않는 한 visited 집합 없이도 순회할 수 있지만, 일반 그래프에서는 visited가 없으면 사이클에서 무한 루프에 빠질 수 있다.

---

4. Tree: 정렬과 계층을 구조로 만든다

4-1. Binary Search Tree (BST)

BST(Binary Search Tree)는 각 노드가 다음 불변식을 지키는 이진 트리다.

모든 노드 N에 대해:
  N.left의 모든 값 < N.value < N.right의 모든 값

이 불변식 덕분에 탐색은 매 단계마다 왼쪽 또는 오른쪽 한쪽만 선택한다. 정렬 배열의 Binary Search가 “인덱스 범위를 절반씩 버리는” 방식이라면, BST는 “노드 관계를 따라 절반에 가까운 후보를 버리는” 방식이다.

손으로 따라가 보자.

삽입 순서: 5, 3, 7, 1, 4, 6, 8

        5
      /   \
     3     7
    / \   / \
   1   4 6   8

4 탐색:
  4 < 5 → 왼쪽
  4 > 3 → 오른쪽
  4 == 4 → 찾음

중위 순회(In-order Traversal)는 Left → Root → Right 순서다. BST 불변식 때문에 중위 순회 결과는 항상 오름차순이다.

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

function insert(root, value) {
  if (!root) return new Node(value);
  if (value < root.value) root.left = insert(root.left, value);
  else if (value > root.value) root.right = insert(root.right, value);
  return root;
}

function search(root, target) {
  let cur = root;
  while (cur) {
    if (target === cur.value) return cur;
    cur = target < cur.value ? cur.left : cur.right;
  }
  return null;
}

function inorder(root, out = []) {
  if (!root) return out;
  inorder(root.left, out);
  out.push(root.value);
  inorder(root.right, out);
  return out;
}

let root = null;
for (const v of [5, 3, 7, 1, 4, 6, 8]) root = insert(root, v);
console.log(search(root, 4)?.value); // 4
console.log(inorder(root)); // [1, 3, 4, 5, 6, 7, 8]

4-2. BST의 핵심 경계: 높이가 성능이다

BST의 탐색, 삽입, 삭제 비용은 O(h)다. 여기서 h는 트리 높이다. 균형이 잡힌 트리는 h ≈ log2(n)이지만, 한쪽으로 편향되면 h ≈ n이 된다.

정렬된 입력 [1, 2, 3, 4, 5]를 순서대로 삽입

균형에 가까운 모양:        편향 BST:
      3                    1
    /   \                   \
   2     4                   2
  /       \                   \
 1         5                   3
                                \
                                 4
                                  \
                                   5

높이 ≈ log n             높이 ≈ n
탐색 O(log n)            탐색 O(n)

이 반례는 중요하다. “BST라서 O(log n)“이 아니라 **균형이 잡힌 BST라서 O(log n)**이다. 단순 BST에 정렬된 입력이 들어오면 Linked List와 다를 바가 없다.

정량 예시로 보자.

n	균형 BST 높이 대략	편향 BST 높이 대략
1,000	10	999
1,000,000	20	999,999
1,000,000,000	30	999,999,999

실패 신호는 에러가 아니라 지연으로 나타난다. 기능 테스트는 통과하지만 입력이 거의 정렬된 날부터 p99 latency가 선형으로 늘어난다. 그래서 범용 라이브러리는 단순 BST보다 AVL Tree, Red-Black Tree, B-Tree처럼 균형을 유지하는 변형을 사용한다.

4-3. 삭제는 왜 어려운가

BST 삭제는 “노드를 지운 뒤에도 BST 불변식을 유지해야 한다”는 문제다. 삭제 대상의 자식 수에 따라 세 케이스로 나뉜다.

케이스	처리	학습 포인트
자식 없음	leaf만 제거	부모의 포인터를 null로 바꾼다
자식 하나	부모와 자식을 직접 연결	삭제 노드의 자식 서브트리는 그대로 BST다
자식 둘	오른쪽 서브트리의 최솟값 또는 왼쪽 서브트리의 최댓값으로 교체	교체값이 양쪽 범위를 모두 만족한다

자식 둘 케이스를 손으로 보면 이해가 쉽다.

3 삭제 전:
        5
      /   \
     3     7
    / \
   1   4

3의 오른쪽 서브트리 최솟값 = 4

3 삭제 후:
        5
      /   \
     4     7
    /
   1

여기서 4는 원래 3보다 크고, 5보다 작다. 그래서 3의 자리로 올라와도 왼쪽 서브트리와 오른쪽 부모 관계를 동시에 만족한다.

4-4. AVL Tree vs Red-Black Tree

자가 균형 트리는 삽입·삭제 후 회전(rotation)을 통해 높이를 다시 낮춘다. AVL Tree와 Red-Black Tree는 둘 다 최악 O(log n)을 보장하지만 철학이 다르다.

항목	AVL Tree	Red-Black Tree
균형 기준	엄격하다. 좌우 높이 차이를 작게 유지	느슨하다. 색 규칙으로 높이를 제한
탐색	평균적으로 조금 더 짧은 경로	AVL보다 높이가 더 클 수 있음
삽입/삭제	회전이 더 자주 발생	재색칠과 적은 회전으로 끝나는 경우가 많음
어울리는 워크로드	읽기 압도적, 정적 사전, 라우팅 테이블	삽입·삭제가 잦은 범용 Map/Set, 스케줄러

실무 판단은 “읽기와 변경 중 무엇이 지배적인가”다.

• 탐색이 99%이고 데이터가 거의 정적이면 AVL이 p99 탐색 경로를 줄이는 데 유리할 수 있다.
• 삽입·삭제가 계속 발생하면 Red-Black Tree가 균형 복구 비용과 구현 복잡도에서 안전한 선택이다.
• Linux 커널의 CFS(Completely Fair Scheduler)는 실행 가능한 태스크를 Red-Black Tree에 넣어 가상 실행 시간이 가장 작은 태스크를 빠르게 찾는다. 태스크가 계속 생성·소멸하므로 엄격한 균형보다 안정적인 갱신 비용이 중요하다.

잘못 고른 신호도 다르다.

• 읽기 중심 워크로드에서 트리 평균 깊이가 꾸준히 깊어지면 p99 lookup latency가 먼저 오른다.
• 쓰기 중심 워크로드에서 회전·재균형 카운터가 요청량보다 빠르게 증가하면 처리량이 떨어진다.
• 평균은 괜찮은데 특정 입력 분포에서만 느리면, “정렬된 입력이 단순 BST를 편향시키는가”를 먼저 의심한다.

4-5. 왜 데이터베이스 인덱스는 단순 BST가 아니라 B-Tree인가

DB 인덱스는 정렬 조회와 범위 조회를 위해 트리 성질을 사용한다. 하지만 디스크와 SSD는 메모리 포인터처럼 노드 하나씩 따라가는 비용이 싸지 않다. 그래서 DB는 보통 B-Tree 또는 B+Tree 계열을 쓴다.

단순 BST:
  한 노드에 키 1개
  n = 100,000,000이면 균형이어도 높이 약 27
  최악 27번 노드 접근

B-Tree/B+Tree:
  한 노드(페이지)에 수십~수백 개 키
  n = 100,000,000이어도 높이 약 3~4
  페이지 단위 I/O에 맞춤

핵심은 “트리면 다 같다”가 아니다. 메모리 안에서는 포인터 몇 번이 큰 문제가 아닐 수 있지만, 디스크나 SSD에서는 페이지 접근 횟수가 성능을 지배한다. B-Tree는 노드를 페이지 크기에 맞춰 넓게 만들어 높이를 낮춘다.

4-6. Tree 선택 기준 요약

질문	선택
단순 키 조회만 필요한가?	Hash Table이 보통 더 낫다
정렬 순회나 범위 조회가 필요한가?	BST/B-Tree 계열
데이터가 디스크 페이지 단위로 저장되는가?	B-Tree/B+Tree 계열
입력 순서가 정렬될 수 있고 단순 BST인가?	편향 O(n)을 의심하고 자가 균형 트리 사용
읽기 압도적이고 변경이 적은가?	AVL 또는 정렬 배열도 후보
삽입·삭제가 잦고 범용성이 중요한가?	Red-Black Tree 계열이 안전

4-7. Range Query worked example

BST와 Hash Table의 차이는 “값 하나 찾기”보다 “범위 찾기”에서 더 선명하다.

데이터:
  user scores = [10, 15, 21, 27, 33, 39, 41, 58]

질문:
  20 이상 40 이하 점수를 모두 찾기

Hash Table은 score -> user를 빠르게 찾을 수 있지만, “20 이상 40 이하”라는 범위 질문에는 정렬 정보가 없다. 결국 모든 score를 확인해야 한다. BST는 먼저 lower bound인 20 이상 첫 지점으로 내려간 뒤, 중위 순회 방향으로 40 이하 노드만 읽으면 된다.

BST range search:
  1. 20보다 작은 서브트리는 버린다.
  2. 20 이상 후보를 만나면 왼쪽 경계부터 읽는다.
  3. 40을 넘는 순간 오른쪽 탐색을 멈춘다.

비용:
  시작점 찾기 O(log n)
  결과 k개 읽기 O(k)
  총 O(log n + k)

이 구조가 DB 인덱스의 핵심이다. WHERE created_at BETWEEN a AND b는 단일 키 조회가 아니라 범위 조회다. Hash Index가 동등 조건에는 빠를 수 있어도 범위 조건에 약한 이유가 여기 있다.

작은 반례도 기억하자.

질문 A: user_id = 42
  Hash Table이 자연스럽다.

질문 B: created_at >= yesterday ORDER BY created_at LIMIT 100
  정렬 순서와 범위가 필요하므로 B-Tree 계열이 자연스럽다.

즉 “Hash는 O(1), Tree는 O(log n)이니 Hash가 항상 좋다”는 판단은 질문 B에서 깨진다. 자료구조 선택은 단일 연산 복잡도가 아니라 시스템이 반복해서 묻는 질문의 형태에 맞춰야 한다.

---

5. Heap & Priority Queue: 전체 정렬 없이 최우선만 보장한다

5-1. 정의와 철학

Priority Queue는 “들어온 순서”가 아니라 “우선순위”에 따라 꺼내는 추상 자료형이다. Heap은 Priority Queue를 구현하는 대표 자료구조다.

Heap은 완전 이진 트리(Complete Binary Tree)이며 다음 속성 중 하나를 지킨다.

• Min Heap: 부모 값 ≤ 자식 값. 루트가 항상 최솟값.
• Max Heap: 부모 값 ≥ 자식 값. 루트가 항상 최댓값.

중요한 오해가 있다. Heap은 전체가 정렬된 배열이 아니다.

Min Heap 예:
        1
      /   \
     3     2
    / \   /
   8   5 7

배열 표현: [1, 3, 2, 8, 5, 7]

부모 ≤ 자식은 맞지만
배열 전체가 [1, 2, 3, 5, 7, 8]처럼 정렬된 것은 아니다.

Heap의 철학은 “필요한 만큼만 정렬한다”이다. 우선순위 큐에서 필요한 것은 루트가 최우선이라는 보장이지, 2등과 3등의 전체 순서가 모든 순간 완벽히 정렬되어 있다는 보장이 아니다.

5-2. 배열로 Heap을 표현하는 이유

Heap은 포인터 노드로 만들 수도 있지만, 완전 이진 트리라서 배열 표현이 자연스럽다.

인덱스 i 기준:
  left child  = 2i + 1
  right child = 2i + 2
  parent      = Math.floor((i - 1) / 2)

완전 이진 트리라 중간에 빈 칸이 없다. 그래서 배열 인덱스 공식만으로 부모와 자식을 찾을 수 있고, 별도 포인터가 필요 없다. 이 점은 앞선 기본 자료구조 문서의 “연속 메모리와 캐시 지역성”과도 연결된다.

5-3. 삽입과 삭제 메커니즘

Min Heap 삽입은 새 값을 배열 끝에 넣고, 부모보다 작으면 위로 올린다. 이 과정을 Bubble Up 또는 Heapify Up이라고 부른다.

기존 Min Heap: [1, 3, 2, 8, 5, 7]
0 삽입:        [1, 3, 2, 8, 5, 7, 0]

0과 parent 2 비교 → 교환
              [1, 3, 0, 8, 5, 7, 2]

0과 parent 1 비교 → 교환
              [0, 3, 1, 8, 5, 7, 2]

삭제는 루트를 제거한 뒤 마지막 값을 루트로 올리고, 자식 중 더 작은 쪽과 내려가며 교환한다. 이 과정을 Bubble Down 또는 Heapify Down이라고 부른다.

class MinHeap {
  constructor() {
    this.heap = [];
  }

  push(value) {
    this.heap.push(value);
    let i = this.heap.length - 1;
    while (i > 0) {
      const p = Math.floor((i - 1) / 2);
      if (this.heap[p] <= this.heap[i]) break;
      [this.heap[p], this.heap[i]] = [this.heap[i], this.heap[p]];
      i = p;
    }
  }

  peek() {
    return this.heap[0] ?? null;
  }

  pop() {
    if (this.heap.length === 0) return null;
    const min = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this.bubbleDown(0);
    }
    return min;
  }

  bubbleDown(i) {
    while (true) {
      const left = i * 2 + 1;
      const right = i * 2 + 2;
      let smallest = i;

      if (left < this.heap.length && this.heap[left] < this.heap[smallest]) {
        smallest = left;
      }
      if (right < this.heap.length && this.heap[right] < this.heap[smallest]) {
        smallest = right;
      }
      if (smallest === i) break;

      [this.heap[i], this.heap[smallest]] = [this.heap[smallest], this.heap[i]];
      i = smallest;
    }
  }
}

const heap = new MinHeap();
for (const v of [5, 1, 8, 3, 2, 7]) heap.push(v);
console.log(heap.peek()); // 1
console.log(heap.pop(), heap.pop(), heap.pop()); // 1 2 3

5-4. Top-K worked example

“100만 개 숫자 중 가장 큰 10개”를 구한다고 하자. 전체를 Max Heap에 넣고 10번 꺼내도 답은 맞다. 하지만 메모리와 시간이 불필요하게 크다.

더 좋은 방법은 크기 k짜리 Min Heap을 유지하는 것이다.

목표: 가장 큰 3개
입력: [3, 1, 4, 1, 5, 9, 2, 6]

Min Heap k=3 유지:
  [3]              3 저장
  [1, 3]           1 저장
  [1, 3, 4]        4 저장
  1은 heap[0]보다 크지 않음 → 버림
  5 > 1 → 1 제거, 5 삽입 → [3, 4, 5]
  9 > 3 → 3 제거, 9 삽입 → [4, 5, 9]
  2는 heap[0]보다 크지 않음 → 버림
  6 > 4 → 4 제거, 6 삽입 → [5, 6, 9]

결과: 9, 6, 5

복잡도는 O(n log k), 공간은 O(k)다. n=1,000,000이고 k=10이면 Heap에는 항상 10개만 남는다. 전체 Max Heap 방식은 O(n) 공간, O(n log n)에 가깝게 커진다. 이 차이는 “정답 전체를 정렬해야 하는가, 상위 k개만 필요한다”는 요구 차이를 자료구조가 반영한 결과다.

5-5. Priority Queue가 실무에서 보이는 모습

우선순위 큐는 반드시 내부 구현이 Heap이라는 뜻은 아니다. Redis Sorted Set, 데이터베이스 인덱스, 브로커 내부 스케줄러 등은 서로 다른 구현을 쓸 수 있다. 학습 관점에서 중요한 것은 추상 동작이다.

사례	우선순위 의미	Heap으로 생각하면 보이는 것
OS 스케줄러	실행할 태스크의 가상 시간 또는 priority	가장 먼저 실행할 태스크를 반복적으로 꺼낸다
BullMQ priority job	낮은 숫자 priority가 더 먼저 실행	FIFO Queue로는 긴급 작업을 앞세울 수 없다
Top-K 랭킹	상위 k개 점수	전체 정렬 대신 k개 후보만 유지한다
Dijkstra	현재까지 거리가 가장 짧은 노드	다음 확정 후보를 Min Priority Queue에서 꺼낸다
CloudWatch 알림 처리	CRITICAL > ERROR > WARN	심각도가 높은 알림을 먼저 처리한다

실패 신호도 추상 동작에서 나온다.

• peek()이 최솟값 또는 최댓값이 아니면 Heapify Down/Up 불변식이 깨졌다.
• pop() 이후 순서가 틀리면 삭제 후 두 자식 중 더 작은/큰 쪽을 고르지 않았을 가능성이 높다.
• Top-K에서 k가 작은데 전체 n개를 저장하면 메모리 사용량이 n에 비례해 올라간다.
• FIFO Queue로 priority를 흉내 내면 긴급 작업이 일반 배치 뒤에 밀리는 starvation, 즉 처리되어야 할 작업이 계속 뒤로 밀려 실행 기회를 얻지 못하는 현상이 생긴다.

5-6. Heap vs 정렬 배열 vs Queue

요구	Queue	정렬 배열	Heap
도착 순서 보존	좋음	부적합	부적합
최솟값/최댓값 반복 추출	매번 O(n) 탐색	추출 O(1), 삽입 O(n)	추출 O(log n), 조회 O(1)
임의 값 이진 탐색	불가	O(log n)	O(n)
전체 정렬 순회	불가	좋음	pop을 반복해야 함
대표 문제	BFS, 메시지 FIFO	정적 랭킹, 정렬 출력	scheduler, Top-K, Dijkstra

5-7. 우선순위가 있으면 공정성도 같이 설계해야 한다

Priority Queue는 “급한 일을 먼저”라는 요구를 잘 표현하지만, 그 자체로 공정성을 보장하지는 않는다. 높은 우선순위 작업이 계속 들어오면 낮은 우선순위 작업은 영원히 실행되지 않을 수 있다. 이것을 starvation(기아)이라고 한다.

상황:
  매초 priority=1 장애 알림 100개 유입
  매초 priority=10 리포트 작업 10개 유입
  worker 처리량은 매초 100개

순수 priority queue:
  priority=1만 계속 처리
  priority=10은 backlog가 계속 증가

이 문제는 Heap이 틀렸다는 뜻이 아니다. Heap은 주어진 priority 규칙을 정확히 실행했을 뿐이다. 문제는 priority 함수가 “긴급도”만 담고 “대기 시간”을 담지 않았다는 점이다.

공정성을 넣는 대표 방법은 priority를 시간에 따라 조정하는 것이다.

방법	아이디어	비용
Aging	오래 기다린 작업의 priority를 점점 올린다	priority 재계산 필요
큐 분리	high/normal/low 큐를 따로 두고 비율로 소비	구현은 단순하지만 튜닝 필요
Deadline priority	마감 시간이 가까운 작업을 먼저 처리	deadline 정의가 필요
Weighted fair queue	큐별 가중치만큼 번갈아 처리	처리량 예측이 필요

학습 관점의 결론은 이렇다. Heap은 “최우선 원소를 빠르게 꺼내는 메커니즘”이고, 공정성은 “priority 값을 어떻게 정의하고 갱신할 것인가”의 문제다. 장애 알림 큐, 배치 큐, OS 스케줄러를 설계할 때 두 층을 섞으면 원인을 잘못 찾는다.

실패 신호는 다음과 같다.

• 전체 처리량은 충분한데 특정 낮은 priority 큐의 age가 계속 증가한다.
• 평균 latency는 낮지만 low priority p99가 무한히 커진다.
• priority 값이 고정이라 오래 기다린 작업이 순서를 뒤집을 기회가 없다.
• retry 작업이 높은 priority로 재삽입되어 신규 작업을 계속 밀어낸다.

---

6. Graph: 임의 관계망을 직접 모델링한다

6-1. Graph의 기본 모델

그래프는 노드(Vertex)와 엣지(Edge)의 집합이다.

V = {A, B, C, D}
E = {(A, B), (A, C), (B, D), (C, D)}

그림:
    A
   / \
  B   C
   \ /
    D

그래프를 읽을 때는 먼저 네 가지를 묻는다.

질문	예	알고리즘 영향
방향이 있는가?	A imports B는 방향 그래프	사이클 감지와 위상 정렬에 중요
가중치가 있는가?	서비스 간 latency 80ms	BFS 대신 Dijkstra 등이 필요
사이클이 허용되는가?	소셜 팔로우는 허용, DI 의존성은 오류	visited와 cycle detection 의미가 달라짐
밀집인가 희소인가?	모든 노드가 거의 연결 vs 일부만 연결	인접 행렬/리스트 선택

6-2. 인접 행렬 vs 인접 리스트

그래프 표현 방식은 성능을 크게 바꾼다.

그래프:
  A -- B
  |    |
  C -- D

인접 행렬:
    A B C D
  A 0 1 1 0
  B 1 0 0 1
  C 1 0 0 1
  D 0 1 1 0

인접 리스트:
  A: [B, C]
  B: [A, D]
  C: [A, D]
  D: [B, C]

항목	인접 행렬	인접 리스트
공간	O(V²)	O(V + E)
두 노드 연결 확인	O(1)	O(degree)
한 노드의 이웃 순회	O(V)	O(degree)
어울리는 그래프	밀집 그래프	희소 그래프

밀도 감각을 가져야 한다. 사용자 1,000명이 있고 각자 친구가 평균 10명이라면 무방향 엣지는 약 5,000개다. 가능한 연결은 대략 1,000² = 1,000,000개이므로 밀도는 0.5% 수준이다. 이런 sparse graph에 V² 행렬을 쓰면 대부분의 칸이 0이다.

반대로 노드 500개가 대부분 서로 연결된 작은 네트워크라면 인접 행렬의 O(1) 연결 확인이 더 나을 수 있다. 특히 행렬을 bitset으로 압축할 수 있으면 포인터 오버헤드가 큰 리스트보다 공간 경쟁력이 생긴다.

실패 신호는 명확하다.

• V가 10,000인데 인접 행렬을 JavaScript boolean 배열로 만들면 V² = 100,000,000칸이다. JS 런타임의 실제 메모리 오버헤드까지 고려하면 단위 테스트는 통과해도 production 규모에서 OOM이 날 수 있다.
• 밀집 그래프를 리스트로 두고 매번 연결 여부를 찾으면 degree가 커져 latency가 V²에 가까운 곡선을 그린다.
• 그래프 생성 직후 V, E, density = E / (V * V)를 로그로 남기면 표현 선택 실패를 일찍 잡을 수 있다.

6-3. DFS와 BFS의 차이

DFS(Depth-First Search)는 한 방향으로 깊게 들어갔다가 막히면 되돌아온다. 스택 또는 재귀가 자연스럽다.

BFS(Breadth-First Search)는 가까운 이웃을 먼저 모두 방문한 뒤 다음 거리로 넘어간다. 큐가 필요하다. 앞선 기본 자료구조 문서의 Queue가 여기서 직접 쓰인다.

그래프:
    A
   / \
  B   C
   \ /
    D
    |
    E

DFS(A 시작, B 먼저):
  A → B → D → C → E

BFS(A 시작):
  A → B, C → D → E

BFS가 비가중치 그래프에서 최단 거리를 보장하는 이유는 레이어 단위로 확장하기 때문이다. 거리 1 노드를 모두 큐에 넣은 뒤에야 거리 2 노드가 나온다. 따라서 어떤 노드에 처음 도달한 순간의 거리가 최단 거리다.

거리 자체가 필요하면 visited와 함께 dist를 저장한다.

function bfsDistance(graph, start) {
  const dist = { [start]: 0 };
  const queue = [start];
  let head = 0;

  while (head < queue.length) {
    const node = queue[head++];
    for (const next of graph[node] ?? []) {
      if (next in dist) continue;
      dist[next] = dist[node] + 1;
      queue.push(next);
    }
  }

  return dist;
}

DFS는 처음 도달한 경로가 최단이라는 보장이 없다.

A에서 E로 가는 두 경로:
  A → B → D → E       길이 3
  A → C → E           길이 2

DFS가 B를 먼저 고르면 길이 3 경로를 먼저 발견할 수 있다.
BFS는 거리 1의 B, C를 모두 본 뒤 거리 2의 E를 발견하므로 최단 거리 2를 보장한다.

6-4. Traversal 코드: visited 타이밍이 핵심이다

그래프 순회에서 visited 집합은 선택이 아니다. 사이클이 있는 그래프에서 visited가 없으면 무한 루프가 된다.

const graph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "D"],
  D: ["B", "C", "E"],
  E: ["D"],
};

function dfs(graph, start) {
  const visited = new Set();
  const result = [];

  function visit(node) {
    visited.add(node);
    result.push(node);
    for (const next of graph[node] ?? []) {
      if (!visited.has(next)) visit(next);
    }
  }

  visit(start);
  return result;
}

function bfs(graph, start) {
  const visited = new Set([start]);
  const queue = [start];
  let head = 0;
  const result = [];

  while (head < queue.length) {
    const node = queue[head++];
    result.push(node);

    for (const next of graph[node] ?? []) {
      if (!visited.has(next)) {
        visited.add(next); // 큐에 넣는 순간 방문 처리
        queue.push(next);
      }
    }
  }

  return result;
}

console.log(dfs(graph, "A")); // 예: [A, B, D, C, E]
console.log(bfs(graph, "A")); // [A, B, C, D, E]

여기서 queue.shift()를 쓰지 않고 head 인덱스를 쓰는 이유도 중요하다. JavaScript 배열의 shift()는 앞 원소를 제거하며 뒤 원소를 한 칸씩 당기므로 O(n)이다. BFS 루프에서 반복하면 전체가 O(V²)에 가까워질 수 있다.

visited는 큐에 넣을 때 처리한다. 꺼낼 때 처리하면 같은 노드가 큐에 여러 번 들어갈 수 있다. 작은 그래프에서는 답이 같아 보여도 큰 그래프에서는 큐 크기가 |E|에 가까워져 OOM 또는 TLE이 난다.

6-5. Cycle Detection: 사이클이 오류인지 정상인지부터 정한다

사이클은 항상 나쁜 것이 아니다.

• 소셜 그래프에서 A follows B, B follows A는 정상이다.
• 도로망에서 순환 경로는 정상이다.
• NestJS DI 모듈에서 UserModule → AuthModule → UserModule은 보통 오류다.
• Terraform 리소스 의존성에서 A depends_on B, B depends_on A는 생성 순서를 정할 수 없어 오류다.

방향 그래프에서 DFS 사이클 감지는 보통 세 상태를 둔다.

상태	뜻
unvisited	아직 방문하지 않음
visiting	현재 DFS 경로 위에 있음
done	이 노드에서 시작한 탐색이 끝남

visiting 상태의 노드를 다시 만나면 현재 경로 안에서 되돌아온 것이므로 사이클이다.

function findDirectedCycle(graph) {
  const state = new Map();
  const path = [];

  function visit(node) {
    state.set(node, "visiting");
    path.push(node);

    for (const next of graph[node] ?? []) {
      if (state.get(next) === "visiting") {
        return [...path.slice(path.indexOf(next)), next];
      }
      if (!state.has(next)) {
        const cycle = visit(next);
        if (cycle) return cycle;
      }
    }

    path.pop();
    state.set(node, "done");
    return null;
  }

  for (const node of Object.keys(graph)) {
    if (!state.has(node)) {
      const cycle = visit(node);
      if (cycle) return cycle;
    }
  }
  return null;
}

const modules = {
  AppModule: ["UserModule"],
  UserModule: ["AuthModule"],
  AuthModule: ["UserModule"],
};

console.log(findDirectedCycle(modules));
// [UserModule, AuthModule, UserModule]

6-6. Topological Sort: 의존성 순서를 만든다

Topological Sort(위상 정렬)는 DAG에서 노드를 의존성 순서대로 나열한다. “A가 B에 의존한다”면 B가 A보다 먼저 와야 한다.

아래 코드는 edge 방향을 먼저 와야 하는 노드 -> 나중에 올 노드로 둔다. 즉 A: ["C"]는 “A를 끝낸 뒤 C를 처리할 수 있다”는 뜻이다. 만약 입력 데이터가 “A depends on B” 형태라면 코드를 넣기 전에 B -> A로 뒤집어야 한다.

Kahn 알고리즘은 in-degree(진입 차수)를 사용한다.

1. 모든 노드의 in-degree를 계산한다.
2. in-degree가 0인 노드를 큐에 넣는다.
3. 큐에서 노드를 꺼내 결과에 넣고, 그 노드가 가리키는 이웃의 in-degree를 1 줄인다.
4. 새로 0이 된 이웃을 큐에 넣는다.
5. 결과 길이가 전체 노드 수보다 작으면 사이클이 있다.

function topologicalSort(graph) {
  const inDegree = {};

  for (const node of Object.keys(graph)) {
    inDegree[node] ??= 0;
    for (const next of graph[node]) inDegree[next] = (inDegree[next] ?? 0) + 1;
  }

  const queue = Object.keys(inDegree)
    .filter((node) => inDegree[node] === 0)
    .sort(); // 결정적 결과를 위해 정렬

  const result = [];

  // 결정성 설명을 우선한 학습용 구현이다. 대규모 그래프에서는
  // 매번 sort/shift 대신 priority queue나 head index queue를 쓴다.
  while (queue.length) {
    const node = queue.shift();
    result.push(node);

    for (const next of [...(graph[node] ?? [])].sort()) {
      inDegree[next]--;
      if (inDegree[next] === 0) queue.push(next);
    }
    queue.sort();
  }

  if (result.length !== Object.keys(inDegree).length) {
    throw new Error("Cycle detected");
  }

  return result;
}

const build = {
  A: ["C"],
  B: ["C"],
  C: ["D"],
  D: [],
};

console.log(topologicalSort(build)); // [A, B, C, D]

주의할 점은 위상 정렬 결과가 유일하지 않을 수 있다는 것이다. 위 예시에서 A와 B는 서로 독립이므로 [A, B, C, D]와 [B, A, C, D]가 모두 유효하다. 실무 테스트가 특정 순서를 기대한다면, in-degree 0 후보를 정렬하거나 우선순위 큐로 관리해 결정성을 만들어야 한다.

6-7. BFS와 Dijkstra의 경계

BFS는 비가중치 그래프에서 최단 경로를 보장한다. 모든 엣지 비용이 1이라고 보는 셈이다. 엣지마다 비용이 다르면 BFS의 “몇 번 이동했는가”와 “총 비용이 얼마인가”가 달라진다.

A에서 C로 가는 경로:

A --1--> B --1--> C     총 비용 2, 엣지 2개
A --10--------------> C 총 비용 10, 엣지 1개

BFS는 엣지 수만 보면 A→C를 먼저 찾을 수 있다.
하지만 비용 최단은 A→B→C다.

가중치가 모두 0 이상이면 Dijkstra 알고리즘을 사용한다. Dijkstra는 “현재까지 거리가 가장 짧은 미확정 노드”를 반복해서 고르므로 Min Priority Queue가 필요하다.

function dijkstra(graph, start) {
  const dist = {};
  const pq = [[0, start]]; // 학습용: 실제 서비스에서는 Min Heap 사용

  for (const node of Object.keys(graph)) {
    dist[node] = Infinity;
    for (const { to } of graph[node]) dist[to] ??= Infinity;
  }
  dist[start] = 0;

  while (pq.length) {
    pq.sort((a, b) => a[0] - b[0]);
    const [cost, node] = pq.shift();
    if (cost > dist[node]) continue;

    for (const { to, weight } of graph[node] ?? []) {
      const nextCost = cost + weight;
      if (nextCost < dist[to]) {
        dist[to] = nextCost;
        pq.push([nextCost, to]);
      }
    }
  }

  return dist;
}

학습용 코드는 pq.sort() 때문에 느리다. 실제 구현은 Min Heap으로 push와 pop min을 O(log n)에 처리한다. 여기서 봐야 하는 핵심은 Graph + Priority Queue가 만나면 가중치 최단 경로 문제가 풀린다는 점이다.

경계도 기억해야 한다.

• 음수 가중치가 있으면 Dijkstra는 일반적으로 안전하지 않다.
• 모든 가중치가 1이면 Dijkstra보다 BFS가 단순하고 빠르다.
• 최단 경로가 아니라 “의존성 순서”가 목표면 Dijkstra가 아니라 Topological Sort다.

6-8. 그래프 모델링에서 가장 흔한 실수

그래프 문제의 절반은 알고리즘보다 모델링에서 틀린다. 특히 방향, 가중치, 사이클 의미를 잘못 잡으면 올바른 알고리즘을 써도 답이 틀린다.

방향을 지워버리는 실수

의존성:
  AuthModule imports UserModule

방향 그래프:
  AuthModule → UserModule

무방향 그래프로 잘못 모델링:
  AuthModule -- UserModule

무방향으로 바꾸면 “누가 누구를 필요로 하는가”가 사라진다. 위상 정렬은 방향이 있어야 한다. 방향을 잃으면 초기화 순서, 삭제 순서, 배포 순서를 계산할 수 없다.

반대로 소셜 친구 관계처럼 상호 연결이 본질이면 무방향 그래프가 자연스럽다. 팔로우 관계는 방향 그래프, 친구 관계는 대체로 무방향 그래프다. 같은 “사용자 관계”라도 엣지의 의미가 다르면 그래프 종류가 달라진다.

가중치를 무시하는 실수

서비스 호출 비용:
  A → B: 10ms
  A → C: 1ms
  C → B: 1ms

엣지 수 기준 최단:
  A → B        1 hop

latency 기준 최단:
  A → C → B    2ms

가중치를 무시하고 BFS를 쓰면 hop 수는 줄어도 latency는 커질 수 있다. 네트워크, 비용, 위험도, 실패 확률처럼 엣지마다 값이 있으면 “최단”의 의미를 먼저 정의해야 한다.

DAG라고 가정하는 실수

빌드 시스템, 마이그레이션, Terraform plan은 DAG라는 가정 위에서 동작한다. 그런데 실제 입력에 사이클이 있으면 위상 정렬은 순서를 만들 수 없다.

정상 DAG:
  Database → UserService → ApiServer

사이클:
  UserService → AuthService → UserService

사이클이 발견됐을 때 “forwardRef로 우회” 같은 전술만 먼저 떠올리면 구조 문제가 남는다. 사이클이 오류인 도메인에서는 공통 의존성을 분리하거나 방향을 바꿔 DAG를 회복하는 것이 본질적인 해결이다.

6-9. Dijkstra 손계산 예시

Dijkstra는 Priority Queue가 왜 필요한지 보여주는 좋은 예시다.

그래프:
  A → B (4)
  A → C (1)
  C → B (2)
  B → D (1)
  C → D (7)

목표:
  A에서 각 노드까지 최소 비용

단계	확정 노드	현재 dist	다음 후보
시작	없음	A=0, B=∞, C=∞, D=∞	(0, A)
1	A	B=4, C=1	(1, C), (4, B)
2	C	B=min(4, 1+2)=3, D=8	(3, B), (4, B old), (8, D)
3	B	D=min(8, 3+1)=4	(4, B old), (4, D), (8, D old)
4	D	완료	old 후보는 dist보다 크면 무시

최종 결과는 A=0, C=1, B=3, D=4다. 여기서 (4, B old)처럼 오래된 후보가 남는 이유는 Priority Queue에서 기존 후보의 우선순위를 낮추는 decrease-key를 구현하지 않고 새 후보를 다시 넣는 방식을 택했기 때문이다. 꺼냈을 때 cost > dist[node]면 무시하면 된다. 예제 코드가 도착 노드만으로 등장하는 to도 dist에 넣는 이유는, 마지막 노드가 graph의 key로 따로 없어도 거리를 기록하기 위해서다.

이 예시는 세 가지 직관을 준다.

• BFS처럼 “먼저 발견한 경로”를 확정하면 B=4가 되어 틀린다.
• Priority Queue는 아직 확정되지 않은 후보 중 가장 싼 것을 고르는 장치다.
• old 후보를 허용하면 구현은 단순해지지만 큐에 중복이 생긴다. edge relaxation, 즉 간선을 따라 더 싼 거리로 갱신할지 비교하는 단계 자체는 O(1)에 가깝고, 새 후보를 Priority Queue에 넣는 비용이 중복 push 방식에서 O(log E)로 붙는다.

---

7. 실무 시스템에서 구조를 알아채는 방법

트리와 그래프는 라이브러리 이름으로 드러나지 않는 경우가 많다. 대신 시스템이 묻는 질문을 보면 구조가 보인다.

시스템	숨어 있는 구조	왜 그렇게 보는가
PostgreSQL/MySQL 인덱스	B-Tree/B+Tree	정렬된 키에서 점 조회와 범위 조회를 페이지 단위로 처리
Linux CFS	Red-Black Tree	실행 후보를 가상 실행 시간 순서로 유지
BullMQ priority job	Priority Queue 추상화	FIFO가 아니라 priority 값으로 처리 순서 결정
NestJS DI 컨테이너	Directed Graph	모듈과 provider 의존성 방향을 따라 초기화하고 사이클 감지
npm/yarn 의존성	DAG + Topological Sort	패키지를 의존성 순서대로 설치
Terraform plan	Resource Graph	리소스 생성 순서와 병렬 가능성을 계산
AWS Step Functions	State Graph	상태와 전환을 그래프로 표현
소셜 추천	Graph Traversal	2-hop, connected component, shortest path 같은 질문

새 기술을 만났을 때는 다음 네 질문을 먼저 던진다.

1. 요소 사이의 관계가 부모-자식 계층인가, 임의 연결인가?
2. 순서가 결과를 바꾸는가?
3. 사이클이 정상 상태인가 오류인가?
4. 조회가 많은가, 변경이 많은가, 최우선 항목만 필요한가?

예를 들어 NestJS 모듈 import를 보자. 관계는 부모-자식이 아니라 임의 방향이다. 순서는 초기화 결과를 바꾼다. 사이클은 대체로 오류다. 그러면 이 문제는 “방향 그래프 + 사이클 감지 + 위상 정렬”로 읽힌다. forwardRef()는 마법이 아니라, 그래프 의존성 해석을 지연시켜 사이클을 우회하는 장치다. 장기적으로는 공통 모듈을 분리해 그래프를 DAG로 만드는 편이 더 건강하다.

---

8. 선택 기준과 반례 모음

8-1. BST vs Hash Table

질문	Hash Table	BST/B-Tree
단일 키 조회	평균 O(1)	O(log n)
정렬 순회	별도 정렬 필요	중위 순회 또는 leaf 순회
범위 조회	부적합	O(log n + k)
최악 케이스	충돌이 나쁘면 O(n)	균형 트리면 O(log n)
대표 사례	캐시, 딕셔너리, 중복 검사	DB 인덱스, ordered map, range query

반례: userId → user 조회만 필요하면 BST는 과하다. 반대로 created_at BETWEEN ... 같은 범위 조회를 Hash Table로 풀면 결국 전체 스캔이 된다.

8-2. Heap vs 정렬 배열

정렬 배열은 전체 순서를 계속 보존한다. Heap은 최우선 원소만 보장한다.

요구	정렬 배열	Heap
전체 정렬 출력	좋음	pop 반복 필요
동적 삽입	O(n)	O(log n)
최우선 조회	O(1)	O(1)
임의 값 탐색	O(log n) 가능	O(n)

반례: “상위 10개만 유지” 문제에서 매번 전체 배열을 정렬하면 답은 맞지만 비용이 과하다. 반대로 “모든 값을 정렬된 상태로 페이지네이션”해야 한다면 Heap은 적합하지 않다.

8-3. DFS vs BFS

질문	DFS	BFS
경로 존재 여부	좋음	좋음
비가중치 최단 거리	보장 안 함	보장
메모리	깊이에 비례	너비에 비례
사이클 감지	directed/undirected 모두 자연스러움	가능하지만 상태 관리가 더 필요
구현	재귀 또는 스택	Queue
위험	깊은 그래프에서 call stack overflow	shift()나 늦은 visited 처리로 큐 폭주

반례: 미로에서 출구 하나라도 찾으면 되는 경우 DFS가 단순하다. 하지만 “가장 적은 이동 횟수”가 목표면 BFS가 맞다.

8-4. Topological Sort vs Shortest Path

의존성 순서와 최단 경로는 다르다.

• Topological Sort는 DAG에서 “무엇을 먼저 해야 하는가”를 묻는다.
• BFS/Dijkstra는 그래프에서 “어디로 가는 비용이 가장 작은가”를 묻는다.

Terraform 리소스 생성 순서는 최단 경로 문제가 아니다. VPC를 만들고 subnet을 만들고 EC2를 만들어야 하는 의존성 순서 문제다. 반대로 네트워크 latency가 가장 작은 리전을 찾는 것은 위상 정렬이 아니라 최단 경로 문제다.

8-5. 인접 리스트 vs 인접 행렬

신호	선택
V가 크고 E가 V에 가까운 수준	인접 리스트
두 노드 연결 여부를 매우 자주 묻고 V가 작음	인접 행렬
밀도가 높고 bitset 압축 가능	인접 행렬 고려
이웃 순회가 대부분	인접 리스트

반례: “행렬은 O(1) 연결 확인이라 항상 빠르다”는 말은 공간을 무시한 주장이다. V=100,000이면 V²는 10¹⁰칸이다. 애초에 만들 수 없는 구조는 빠를 수 없다.

8-6. 문제 문장을 자료구조로 번역하는 연습

자료구조 선택은 보통 문제 문장 안에 이미 숨어 있다.

문제 문장	핵심 신호	후보
”가장 최근/가장 먼저 들어온 것”	한쪽 끝 접근	Stack 또는 Queue
”가장 작은/큰 것을 반복해서 꺼내라”	최우선 반복 추출	Heap
”정렬된 순서로 범위를 훑어라”	range query	BST/B-Tree
”A를 하기 전에 B와 C가 필요하다”	의존성 방향	DAG + Topological Sort
”몇 단계 안에 도달 가능한가”	비가중치 거리	BFS
”비용이 가장 작은 경로”	weighted shortest path	Dijkstra
”순환이 있으면 안 된다”	cycle invalid	DFS cycle detection
”상호 연결은 정상이다”	cycle valid	Graph traversal + visited

반대로 위험한 문장도 있다.

• “일단 배열로 하고 느리면 최적화”라고 말했는데 삽입·삭제가 핵심이면 처음부터 비용 모델이 틀릴 수 있다.
• “HashMap이면 O(1)“이라고 말했는데 범위 조회가 있으면 정렬 정보가 없다.
• “BFS/DFS 아무거나”라고 말했는데 최단 거리 요구가 있으면 DFS는 반례가 있다.
• “위상 정렬하면 되지”라고 말했는데 입력이 DAG라는 보장이 없으면 cycle error path가 필요하다.

좋은 설계 문서나 PR 설명은 “이 자료구조를 왜 골랐는가”를 한 문장으로 말할 수 있어야 한다. 예를 들어 “알림 큐는 최우선 작업만 반복 추출하므로 전체 정렬 배열 대신 Heap 기반 Priority Queue를 쓴다”처럼 요구와 구조가 연결되어야 한다.

---

9. 실패 신호: 긴 런북보다 먼저 볼 것

트리와 그래프 오류는 컴파일 에러보다 성능 곡선, 큐 크기, 순서 흔들림으로 드러나는 경우가 많다.

증상	의미	먼저 의심할 개념
BST lookup p99가 입력 크기에 선형으로 증가	트리가 편향되어 높이가 n에 가까움	자가 균형 트리 필요
inorder() 결과가 정렬되어 있지 않음	BST 불변식이 깨짐	삽입·삭제 포인터 연결
Heap peek()이 최솟값이 아님	Heapify Up/Down 실패	두 자식 비교 누락
Top-K에서 메모리 사용량이 n에 비례	k개만 유지하지 않고 전체 저장	Min Heap k개 유지
BFS 큐 크기가 |V|보다 훨씬 커짐	visited를 큐 삽입 시점에 찍지 않음	visited 타이밍
DFS가 큰 입력에서 Maximum call stack size exceeded	재귀 깊이가 런타임 한계 초과	반복 DFS
위상 정렬이 일부 환경에서 순서가 달라짐	유효한 순서가 여러 개인데 결정성 없음	후보 정렬 또는 priority
NestJS circular dependency 오류	방향 그래프에 사이클 존재	모듈 분리 또는 의존 방향 재설계
sparse graph에서 OOM	인접 행렬을 잘못 선택	인접 리스트

운영 대응의 첫 단계는 명령어가 아니라 불변식 확인이다.

• BST: 모든 노드가 left < node < right 범위를 만족하는가?
• Heap: 모든 부모-자식 쌍이 heap property를 만족하는가?
• Graph traversal: visited가 “발견 시점”에 기록되는가?
• Topological Sort: 결과 길이가 전체 노드 수와 같은가?
• Representation: 현재 V, E, density가 선택한 표현과 맞는가?

---

9.5. 선택 부록: 짧은 진단 스니펫

본문 이해에 필수는 아니지만, 직접 구현하다 막힐 때 유용한 최소 점검 코드만 남긴다.

A. BST 편향 측정

function height(node) {
  if (!node) return -1;
  return 1 + Math.max(height(node.left), height(node.right));
}

let skewed = null;
for (const v of [1, 2, 3, 4, 5]) skewed = insert(skewed, v);
console.log(height(skewed)); // 4

let balancedLike = null;
for (const v of [3, 2, 4, 1, 5]) balancedLike = insert(balancedLike, v);
console.log(height(balancedLike)); // 2

높이가 log2(n)보다 훨씬 크면 탐색 비용도 같이 커진다. production에서는 전체 높이 계산이 비쌀 수 있으므로 샘플 노드 깊이나 평균 비교 횟수를 계측한다.

B. Heap property 검사

function isMinHeap(arr) {
  for (let i = 0; i < arr.length; i++) {
    const left = i * 2 + 1;
    const right = i * 2 + 2;
    if (left < arr.length && arr[i] > arr[left]) return false;
    if (right < arr.length && arr[i] > arr[right]) return false;
  }
  return true;
}

console.log(isMinHeap([1, 3, 2, 8, 5, 7])); // true
console.log(isMinHeap([1, 3, 0, 8, 5, 7])); // false

pop() 직후 이 검사가 실패하면 Bubble Down에서 왼쪽 자식만 비교했거나, 교환 후 인덱스 갱신을 빠뜨렸을 가능성이 높다.

C. BFS 큐 폭주 계측

function bfsWithQueuePeak(graph, start) {
  const visited = new Set([start]);
  const queue = [start];
  let head = 0;
  let peak = queue.length;

  while (head < queue.length) {
    const node = queue[head++];
    for (const next of graph[node] ?? []) {
      if (!visited.has(next)) {
        visited.add(next);
        queue.push(next);
      }
    }
    peak = Math.max(peak, queue.length - head);
  }

  return { visited: visited.size, peak };
}

정상 BFS의 큐는 그래프의 frontier 크기에 비례한다. visited를 꺼낼 때 처리하는 구현은 같은 노드가 여러 번 큐에 들어가 peak가 비정상적으로 커진다.

D. 반복 DFS로 재귀 한계 피하기

function dfsIterative(graph, start) {
  const visited = new Set([start]);
  const stack = [start];
  const result = [];

  while (stack.length) {
    const node = stack.pop();
    result.push(node);

    for (const next of [...(graph[node] ?? [])].reverse()) {
      if (!visited.has(next)) {
        visited.add(next);
        stack.push(next);
      }
    }
  }

  return result;
}

Node.js 재귀 깊이는 환경마다 다르지만 수만 단계 그래프에서는 안전하지 않다. 깊이가 입력 크기에 비례할 수 있으면 반복 DFS를 기본으로 둔다.

E. 위상 정렬 결정성 테스트

function runMany(fn, graph, times = 20) {
  const outputs = new Set();
  for (let i = 0; i < times; i++) outputs.add(fn(graph).join(","));
  return outputs;
}

const graph = { A: ["C"], B: ["C"], C: ["D"], D: [] };
console.log(runMany(topologicalSort, graph));
// Set { "A,B,C,D" } 처럼 하나만 남아야 결정적이다.

결과가 여러 개라도 그래프 이론상 틀린 것은 아닐 수 있다. 하지만 빌드, 마이그레이션, 모듈 초기화처럼 순서가 로그와 테스트에 남는 시스템에서는 결정성이 운영 품질이다.

---

10. 직접 확인해보기

10-1. BST 편향 vs 균형 근사 탐색 시간

function build(values) {
  let root = null;
  for (const v of values) root = insert(root, v);
  return root;
}

function countComparisons(root, targets) {
  let comparisons = 0;
  for (const target of targets) {
    let cur = root;
    while (cur) {
      comparisons++;
      if (target === cur.value) break;
      cur = target < cur.value ? cur.left : cur.right;
    }
  }
  return comparisons / targets.length;
}

const N = 10_000;
const sorted = Array.from({ length: N }, (_, i) => i);
const shuffled = sorted.slice().sort(() => Math.random() - 0.5);
const targets = Array.from({ length: 1000 }, () =>
  Math.floor(Math.random() * N),
);

console.log("편향 BST 평균 비교:", countComparisons(build(sorted), targets));
console.log("균형 근사 평균 비교:", countComparisons(build(shuffled), targets));

기대 관찰은 “편향 BST는 평균 비교 횟수가 n에 가까워지고, 셔플 입력은 log n에 가까워진다”이다. 절대 시간보다 비교 횟수를 보면 Node.js JIT 영향이 줄어든다.

10-2. Min Heap으로 Top-K 유지

앞 절의 MinHeap은 숫자 비교를 기준으로 한다. 다음 실험은 “가장 큰 k개를 찾는데 왜 Min Heap을 쓰는가”를 확인한다.

function topK(nums, k) {
  const heap = new MinHeap();

  for (const num of nums) {
    if (heap.heap.length < k) heap.push(num);
    else if (num > heap.peek()) {
      heap.pop();
      heap.push(num);
    }
  }

  return heap.heap.slice().sort((a, b) => b - a);
}

console.log(topK([3, 1, 4, 1, 5, 9, 2, 6], 3)); // [9, 6, 5]

Heap 크기가 k를 넘지 않는지 확인해 보자. k=10, n=1,000,000이어도 공간은 k에 묶인다.

10-3. BFS는 사이클을 견디고, 위상 정렬은 사이클을 거부한다

const cyclicUndirected = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "D"],
  D: ["B", "C", "E"],
  E: ["D", "A"],
};

console.log(bfs(cyclicUndirected, "A"));

const directedCycle = {
  A: ["B"],
  B: ["C"],
  C: ["A"],
};

try {
  console.log(topologicalSort(directedCycle));
} catch (error) {
  console.log(error.message); // Cycle detected
}

같은 “cycle”이라도 알고리즘의 의미가 다르다. BFS는 visited로 이미 본 노드를 건너뛰며 계속 답을 낸다. 위상 정렬은 DAG에서만 정의되므로 사이클을 오류로 드러낸다.

---

11. 체크리스트

Tree

Tree 체크

• BST 불변식(왼쪽 < 부모 < 오른쪽)을 말로 설명할 수 있다.
• BST 탐색 비용이 O(log n)이 아니라 O(h)이며, h가 편향되면 O(n)이 된다는 점을 설명할 수 있다.
• 중위 순회 결과가 정렬 순서가 되는 이유를 손으로 따라갈 수 있다.
• BST 삭제의 세 케이스(leaf, 자식 하나, 자식 둘)를 구분할 수 있다.
• AVL Tree와 Red-Black Tree의 선택 기준을 읽기/쓰기 비율로 설명할 수 있다.
• DB 인덱스가 단순 BST보다 B-Tree/B+Tree를 쓰는 이유를 페이지 I/O 관점에서 설명할 수 있다.

Heap & Priority Queue

Heap & Priority Queue 체크

• Heap이 전체 정렬을 보장하지 않고 루트의 최우선만 보장한다는 점을 설명할 수 있다.
• 배열 Heap의 부모/자식 인덱스 공식을 사용할 수 있다.
• Bubble Up과 Bubble Down이 각각 언제 필요한지 설명할 수 있다.
• Top-K 문제에서 크기 k Min Heap을 쓰는 이유를 O(n log k), O(k)로 설명할 수 있다.
• Queue, 정렬 배열, Heap 중 어떤 상황에 무엇을 써야 하는지 고를 수 있다.

Graph

Graph 체크

• Directed/Undirected, Weighted/Unweighted, DAG, Cycle의 차이를 설명할 수 있다.
• 인접 행렬과 인접 리스트의 시간·공간 trade-off를 V, E, density로 설명할 수 있다.
• DFS와 BFS의 동작 차이를 스택/큐와 연결해 설명할 수 있다.
• BFS가 비가중치 최단 경로를 보장하는 이유를 레이어 관점으로 설명할 수 있다.
• visited를 큐에 넣는 시점에 처리해야 하는 이유를 설명할 수 있다.
• DFS cycle detection과 Kahn topological sort가 사이클을 어떻게 드러내는지 설명할 수 있다.
• BFS, Dijkstra, Topological Sort를 문제 목적에 맞게 구분할 수 있다.

---

12. 핵심 키워드

키워드	설명
Binary Search Tree (BST)	왼쪽 서브트리 < 부모 < 오른쪽 서브트리 불변식을 지키는 이진 트리
Skewed Tree	한쪽으로 편향되어 높이가 n에 가까워진 트리
Self-Balancing Tree	삽입·삭제 후 회전으로 높이를 O(log n)에 묶는 트리 계열
AVL Tree	엄격한 높이 균형을 유지하는 자가 균형 BST
Red-Black Tree	색 규칙으로 느슨한 균형을 유지하는 범용 자가 균형 BST
B-Tree/B+Tree	디스크/페이지 I/O에 맞춰 노드 하나에 여러 키를 담는 다진 트리
Complete Binary Tree	마지막 레벨을 제외하고 모두 차고, 마지막 레벨은 왼쪽부터 채워진 이진 트리
Heap	부모-자식 우선순위 불변식을 지키는 완전 이진 트리
Priority Queue	우선순위가 가장 높은 원소를 먼저 꺼내는 추상 자료형
Heapify Up/Down	삽입 또는 삭제 후 Heap 불변식을 복구하는 과정
Vertex/Node	그래프의 점
Edge	그래프의 연결
Adjacency List	각 노드의 이웃 목록으로 그래프를 표현하는 방식
Adjacency Matrix	V×V 행렬로 연결 여부를 표현하는 방식
DFS	스택/재귀 기반 깊이 우선 탐색
BFS	큐 기반 너비 우선 탐색
DAG	방향이 있고 사이클이 없는 그래프
Topological Sort	DAG 노드를 의존성 순서대로 나열하는 알고리즘
In-degree	어떤 노드로 들어오는 엣지 수
Cycle Detection	경로가 자기 자신으로 되돌아오는지 검사하는 과정
Dijkstra	비음수 가중치 그래프의 최단 경로 알고리즘

---

13. 추천 리소스

리소스	유형	난이도	URL
VisuAlgo - Binary Search Tree	시각화	입문	링크
VisuAlgo - Binary Heap	시각화	입문	링크
VisuAlgo - DFS/BFS	시각화	입문	링크
GeeksforGeeks - Complexity of BST/AVL operations	튜토리얼	입문	링크
Baeldung - Red-Black Tree vs AVL Tree	비교 글	중급	링크
DigitalOcean - Binary Heaps and Priority Queues in JavaScript	튜토리얼	중급	링크
cp-algorithms - Breadth First Search	알고리즘 레퍼런스	중급	링크
cp-algorithms - Topological Sorting	알고리즘 레퍼런스	중급	링크
NestJS 공식 문서 - Circular dependency	공식 문서	입문	링크
PostgreSQL 공식 문서 - Indexes	공식 문서	중급	링크

---

14. 한 줄 요약

Tree는 계층과 정렬 순서를 구조 안에 넣어 조회·범위·우선순위 문제를 줄이고, Graph는 임의 관계를 노드와 엣지로 올려 도달 가능성·최단 경로·의존성 순서·사이클을 계산하게 해 준다. 핵심은 이름을 외우는 것이 아니라 불변식, 선택 기준, 깨졌을 때의 실패 신호를 같이 보는 것이다.

---

15. Sources

• Binary search tree - Wikipedia
• Complexity of different operations in Binary tree, BST and AVL tree - GeeksforGeeks
• Red-Black Tree vs. AVL Tree - Baeldung
• Completely Fair Scheduler - Wikipedia
• PostgreSQL Documentation - Indexes
• Binary Heaps and Priority Queues via JavaScript - DigitalOcean
• Priority Queue Data Structure and Heaps in JavaScript - Adrian Mejia Blog
• Graph Traversal (Depth/Breadth First Search) - VisuAlgo
• Breadth First Search - cp-algorithms
• Topological Sorting - cp-algorithms
• Dijkstra Algorithm - cp-algorithms
• NestJS Circular dependency