Tree & Graph

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

트리와 그래프 (Tree & Graph)

1. 한 줄 정의

트리는 계층적 관계를, 그래프는 임의적 관계망을 표현하는 자료구조이며, BST·Heap·Graph Traversal은 실무의 검색·스케줄링·의존성 분석에 직접 활용된다.

2. 왜 중요한가

검색 성능: 정렬된 배열에서 이진 탐색은 O(log n)이지만, 삽입/삭제도 O(log n)이 필요하다면 BST가 답이다.
우선순위 처리: 작업 스케줄러, 알림 시스템, Top-K 문제는 항상 Heap(Priority Queue)으로 구현된다.
관계 탐색: 서비스 의존성 그래프(npm, MSA), 네트워크 라우팅, 소셜 그래프는 Graph 탐색 알고리즘 없이는 분석 불가능하다.
코딩 인터뷰 빈출: LeetCode 기준 트리·그래프 문제가 전체의 30% 이상을 차지한다.

2.5. 선행 자료구조의 한계와 등장 배경

정렬 배열·FIFO 큐·해시 테이블만으로 충분했다면 트리·그래프는 필요 없었다. 세 자료구조는 각각 다음 한계를 해소하려는 동기로 등장했다.

정렬 배열의 삽입 비용: 정렬을 유지하면서 새 원소를 끼워 넣으려면 평균 n/2개 요소를 shift해야 하므로 O(n). n=10⁶에서 삽입 한 번에 평균 50만 회 메모리 이동 — 동일 워크로드를 자가 균형 BST로 옮기면 log₂(10⁶) ≈ 20단계만 거쳐 약 2.5만 배 차이로 줄어든다. 이것이 §3-1의 Linux 커널 CFS가 정렬 배열을 버리고 Red-Black Tree로 갈아탄 직접 동기다. CFS는 2007년 커널 2.6.23에서 기존 O(1) scheduler를 대체하며 도입됐고, “process가 끊임없이 생성·소멸하는” 환경에서 삽입·삭제 비용을 O(log N)으로 묶고 “leftmost cache로 다음 실행 대상 조회는 O(1)“을 보장하기 위해 Red-Black을 골랐다 (Wikipedia: Completely Fair Scheduler).
FIFO 큐의 우선순위 무관성: 순수 FIFO 큐는 도착 순서만 보존하므로 “긴급 작업을 먼저”라는 요구를 표현할 수 없다. 매 도착마다 다시 정렬하면 삽입이 O(n log n)이 되어 도착률이 높을수록 큐가 정렬에 매여 처리량을 잃는다. Heap은 부모≤자식 속성만 유지하므로 삽입·삭제 모두 O(log n), 최솟값 조회 O(1)로 묶는다. §3-2의 BullMQ priority 옵션이 이 한계를 푼 사례 — 내부의 Redis Sorted Set은 사실상 Min Heap이라 priority=1 알림이 priority=10 마케팅 배치보다 항상 먼저 dequeue된다.
인접 표현의 관계 분석 한계: 단순 테이블·리스트로는 “A→B→C→A 같은 순환이 존재하는가”, “이 모듈을 어느 순서로 초기화해야 하는가” 같은 질문에 직접 답할 수 없다. Graph는 노드+엣지 모델 위에 DFS 사이클 감지와 Kahn 위상 정렬을 얹어 두 질문을 각각 O(V+E)로 해결한다. §3-3의 NestJS DI 컨테이너가 시작 시 던지는 circular dependency 오류는 이 알고리즘의 직접 출력이며, 검사가 없다면 사이클을 가진 모듈은 런타임에 무한 재귀나 미초기화 프로바이더로만 드러난다 — 즉 silent failure 형태가 된다.

세 한계 모두 공통점이 있다: 노드 사이의 관계 또는 순서가 결과를 바꾸는데 선행 자료구조는 그 관계를 1급 시민으로 모델링하지 못한다. 트리·그래프가 사라지면 무엇이 깨지는가에 대한 답이기도 하다 — Linux 스케줄러는 다시 O(1) 큐 분할로 회귀하면서 동적 priority 응답성을 잃고, NestJS는 시작 시 사이클을 못 잡아 런타임 무한 루프를 허용하며, BullMQ는 priority 옵션 자체가 무효가 된다.

3. 핵심 개념

3-1. Binary Search Tree (BST)

비유

도서관의 “십진분류법 책장”을 상상해보세요. 왼쪽 칸에는 더 작은 번호, 오른쪽 칸에는 더 큰 번호가 있습니다. 책을 찾을 때 매번 전체를 뒤지는 게 아니라, 현재 위치에서 “왼쪽 or 오른쪽” 판단만 하면 됩니다. BST가 바로 이 원리입니다.

원리

BST의 핵심 속성은 다음 하나입니다:

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

이 속성 덕분에 탐색할 때 절반씩 범위를 줄여나갈 수 있습니다. 높이가 h인 트리에서 탐색은 O(h)입니다. 균형 트리라면 h = log n이므로 O(log n), 최악(한쪽으로만 편향된 트리)이면 h = n이므로 O(n)이 됩니다.

연산	평균 케이스	최악 케이스 (편향)
탐색	O(log n)	O(n)
삽입	O(log n)	O(n)
삭제	O(log n)	O(n)

자가 균형 트리(AVL Tree, Red-Black Tree)는 삽입/삭제 후 자동으로 균형을 맞춰 최악 케이스를 O(log n)으로 보장합니다. JavaScript의 Map, Java의 TreeMap은 내부적으로 Red-Black Tree를 사용합니다.

왜 BST가 “편향”되면 O(n)이 되는가 — 직관적 이해

BST의 성능은 **트리의 높이(h)**에 비례한다. 균형 잡힌 트리는 n개 노드에서 h = log n이지만, 정렬된 데이터를 순서대로 삽입하면 한쪽으로만 자라서 사실상 Linked List가 된다:

정렬된 데이터 [1, 2, 3, 4, 5] 삽입 시:

균형 BST:          편향 BST:
    3               1
   / \               \
  2   4               2
 /     \               \
1       5               3
                         \
                          4
                           \
                            5
높이 = 2 (log₂5)    높이 = 4 (= n-1)
탐색 = O(log n)      탐색 = O(n)

이것이 DB 인덱스가 단순 BST가 아닌 **B-Tree(자가 균형 + 다진 트리)**를 사용하는 이유다. B-Tree는 한 노드에 여러 키를 저장하여 트리 높이를 극단적으로 낮추고, 삽입/삭제 시 자동으로 재균형한다.

AVL Tree vs Red-Black Tree: 실무에서 어떤 것이 쓰이나

항목	AVL Tree	Red-Black Tree
균형 기준	엄격 (좌우 높이 차이 ≤ 1)	느슨 (최대 2배 높이 차이 허용)
탐색 속도	약간 빠름 (더 짧은 트리)	약간 느림
삽입/삭제	느림 (회전이 더 많음)	빠름 (최대 2~3회 회전 + 재색칠)
사용처	읽기 중심 시스템 (사전, 읽기 전용 DB)	쓰기 빈번한 시스템 (Java TreeMap, C++ std::map, Linux 커널)

실무 결론: 대부분의 범용 시스템은 Red-Black Tree를 사용한다. 정량 비교 — 벤치마크 연구에 따르면 삽입 시 AVL이 bottom-up Red-Black보다 약 1.2배 많은 회전을 수행하고, 삭제 시에는 Red-Black 변형들이 AVL의 개선된 삭제 알고리즘보다 약 26배 많은 회전을 수행한다 (arxiv 2406.05162 — Comparative Performance of AVL and Red-Black Tree). 다만 삭제 회전 자체가 비싼 연산은 아니므로 — 회전당 상수 시간이고 메모리 접근 패턴이 짧다 — “쓰기 합산이 워크로드의 절반을 넘으면 Red-Black, 탐색이 99%면 AVL”이 실용 기준이다. Linux 커널의 CFS(2007년 2.6.23에서 O(1) scheduler 대체)와 epoll, Java TreeMap, C++ std::map은 모두 전자에 해당해 Red-Black을 채택했다.

잘못 골랐을 때 어떻게 드러나는가: 탐색이 99% 이상인 워크로드(예: 정적 사전 자동완성, 라우팅 테이블)에 Red-Black을 그대로 쓰면 트리 높이가 AVL 대비 최대 2배까지 허용되어 p99 latency가 한 단계의 캐시 미스만큼 늘어난다 — 에러는 없고 SLO 미달로만 드러나는 silent 성격이다. 반대로 §2.5에서 본 알림 큐·스케줄러처럼 삽입·삭제가 끊임없는 워크로드에 AVL을 쓰면 매 작업당 회전이 더 많아 처리량이 점진적으로 떨어진다. 진단 절차 — (a) 평균 노드 깊이를 1줄 카운터로 노출(avgDepth = sumDepth / size), (b) 동일 워크로드 트레이스를 N=10⁵로 재현해 두 구현의 평균 응답 시간을 측정, (c) AVL의 깊이가 Red-Black 대비 일관되게 짧고(차이 ≥ 1.3배) 그래도 응답이 더 느리면 회전 비용이 지배적 — Red-Black 교체가 의미 있는 단계.

📖 더 보기: Baeldung — Red-Black Tree vs. AVL Tree — 두 자가 균형 트리의 성능 차이를 수학적/실용적으로 비교 (중급)

코드 예시

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

class BST {
  constructor() {
    this.root = null;
  }

  // 삽입: 올바른 위치를 찾아 leaf에 추가
  insert(value) {
    const node = new TreeNode(value);
    if (!this.root) {
      this.root = node;
      return this;
    }

    let current = this.root;
    while (true) {
      if (value === current.value) return this; // 중복 무시
      if (value < current.value) {
        if (!current.left) {
          current.left = node;
          break;
        }
        current = current.left;
      } else {
        if (!current.right) {
          current.right = node;
          break;
        }
        current = current.right;
      }
    }
    return this;
  }

  // 탐색: 왼/오른쪽 방향으로 절반씩 제거
  search(value) {
    let current = this.root;
    while (current) {
      if (value === current.value) return current;
      current = value < current.value ? current.left : current.right;
    }
    return null;
  }

  // 중위 순회 (In-order): 정렬된 순서로 출력
  inorder(node = this.root, result = []) {
    if (!node) return result;
    this.inorder(node.left, result);
    result.push(node.value);
    this.inorder(node.right, result);
    return result;
  }

  // 삭제: 3가지 케이스 처리
  delete(value, node = this.root, parent = null) {
    if (!node) return this; // 값 없음

    if (value < node.value) {
      this.delete(value, node.left, node);
    } else if (value > node.value) {
      this.delete(value, node.right, node);
    } else {
      // 케이스 1: 자식이 없는 leaf 노드
      if (!node.left && !node.right) {
        if (!parent) this.root = null;
        else if (parent.left === node) parent.left = null;
        else parent.right = null;
      }
      // 케이스 2: 자식이 하나
      else if (!node.left || !node.right) {
        const child = node.left || node.right;
        if (!parent) this.root = child;
        else if (parent.left === node) parent.left = child;
        else parent.right = child;
      }
      // 케이스 3: 자식이 둘 — 오른쪽 서브트리의 최솟값(In-Order Successor)으로 교체
      else {
        let successor = node.right;
        let successorParent = node;
        while (successor.left) {
          successorParent = successor;
          successor = successor.left;
        }
        node.value = successor.value; // 값만 교체
        // 후계자 노드 삭제 (후계자는 왼쪽 자식이 없음 → 케이스 1 또는 2)
        if (successorParent === node) successorParent.right = successor.right;
        else successorParent.left = successor.right;
      }
    }
    return this;
  }
}

// 실행 예시
const bst = new BST();
[5, 3, 7, 1, 4, 6, 8].forEach((v) => bst.insert(v));

console.log(bst.search(4)); // TreeNode { value: 4, left: null, right: null }
console.log(bst.search(9)); // null
console.log(bst.inorder()); // [1, 3, 4, 5, 6, 7, 8] ← 항상 정렬된 순서!

// 삭제 예시
bst.delete(3); // 자식 2개 (1, 4) → 후계자 4로 교체
console.log(bst.inorder()); // [1, 4, 5, 6, 7, 8]
bst.delete(7); // 자식 2개 (6, 8) → 후계자 8로 교체
console.log(bst.inorder()); // [1, 4, 5, 6, 8]

예상 출력:

TreeNode { value: 4, left: null, right: null }
null
[1, 3, 4, 5, 6, 7, 8]
[1, 4, 5, 6, 7, 8]
[1, 4, 5, 6, 8]

BST 삭제 3케이스 요약:

케이스 1: 자식 없음 (leaf) → 그냥 제거
  삭제 전:   3        삭제 후:   3
            / \                 /
           1   4               1

케이스 2: 자식 하나 → 부모와 자식을 직접 연결
  삭제 전:   5        삭제 후:   5
            /                  /
           3                  1
          /
         1

케이스 3: 자식 둘 → 오른쪽 서브트리 최솟값(후계자)으로 교체
  삭제 전:   5        삭제 후:   5
            / \                 / \
           3   7               4   7
          / \                 /
         1   4               1
  3를 삭제 → 오른쪽 서브트리 최솟값 4가 3 자리로 이동

BST의 중위 순회(Left → Root → Right) 결과는 항상 오름차순 정렬입니다. 이 특성이 BST를 정렬 알고리즘으로도 활용하게 만듭니다.

Nest.js/AWS 실무 연결: BST가 어디서 쓰이나

DB 인덱스(B-Tree): MySQL, PostgreSQL의 기본 인덱스는 BST를 확장한 B-Tree다. WHERE created_at BETWEEN '2025-01-01' AND '2025-12-31' 같은 범위 쿼리가 O(log n)에 동작하는 이유가 B-Tree의 BST 속성 때문이다. B-Tree는 BST와 달리 한 노드에 여러 키를 저장할 수 있어 디스크 I/O를 최소화한다.

JavaScript Map 내부: 사실 JS의 Map은 해시 테이블 기반이지만, Java의 TreeMap은 Red-Black Tree(자가 균형 BST)로 구현된다. 정렬된 키 순회가 필요한 상황이라면 BST 기반 자료구조를 써야 한다.

Nest.js 미들웨어 라우트 매핑: Express/Fastify 기반 Nest.js는 URL 라우트를 내부적으로 Radix Tree(BST 변형)로 관리한다. /users/:id와 /users/profile 같은 패턴 충돌을 트리 구조로 효율적으로 해결한다.

// Nest.js에서 정렬된 데이터가 필요한 경우 직접 BST 활용 예시
// (실무에서는 DB ORDER BY + 인덱스로 해결하지만, 인메모리에서는 이 원리가 작동)
@Injectable()
export class RankingService {
  // MinHeap(BST 변형)으로 Top-K 실시간 랭킹 유지
  // 새 점수가 들어올 때마다 O(log k) 갱신
  async updateRanking(userId: string, score: number) {
    // heap.push(score) → O(log k)
    // heap.pop() → O(log k): k 크기 유지
  }
}

📖 더 보기: B-Tree Index 심층 가이드 — DEV Community — DB 인덱스가 B-Tree를 쓰는 이유와 BST와의 차이를 그림으로 설명 (입문)

3-2. Heap & Priority Queue

비유

응급실을 상상해보세요. 환자가 도착한 순서가 아니라 중증도 순서로 치료합니다. 새 환자가 들어오면 중증도에 따라 적절한 위치에 배치되고, 의사는 항상 가장 위급한 환자부터 처리합니다. 이것이 Priority Queue(우선순위 큐)이고, 그 내부 구현이 Heap입니다.

원리

Heap은 **완전 이진 트리(Complete Binary Tree)**로, 다음 두 가지 종류가 있습니다:

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

Max Heap 구조:
        10
       /  \
      9    8
     / \  / \
    7   6 5   4

배열 표현: [10, 9, 8, 7, 6, 5, 4]
인덱스 i의 자식: 왼쪽 = 2i+1, 오른쪽 = 2i+2
인덱스 i의 부모: Math.floor((i-1)/2)

삽입(Bubble Up / Heapify Up): 새 요소를 배열 끝에 추가한 뒤, 부모보다 크면(Max Heap 기준) 위로 교환. O(log n)

삭제(Bubble Down / Heapify Down): 루트를 제거하고 마지막 요소를 루트로 올린 뒤, 자식 중 큰 값과 교환하며 내려감. O(log n)

최대/최솟값 조회: 루트를 그냥 읽으면 됨. O(1)

연산	시간 복잡도
삽입	O(log n)
최솟값/최댓값 삭제	O(log n)
최솟값/최댓값 조회	O(1)

코드 예시

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

  // 부모/자식 인덱스 계산
  parent(i) {
    return Math.floor((i - 1) / 2);
  }
  leftChild(i) {
    return 2 * i + 1;
  }
  rightChild(i) {
    return 2 * i + 2;
  }

  // 두 인덱스 값 교환
  swap(i, j) {
    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
  }

  // 삽입: 끝에 추가 후 위로 올리기
  push(value) {
    this.heap.push(value);
    this._bubbleUp(this.heap.length - 1);
  }

  _bubbleUp(idx) {
    while (idx > 0) {
      const p = this.parent(idx);
      if (this.heap[p] > this.heap[idx]) {
        this.swap(p, idx);
        idx = p;
      } else break;
    }
  }

  // 최솟값 조회 (루트)
  peek() {
    return this.heap[0];
  }

  // 최솟값 제거 후 반환
  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(idx) {
    const n = this.heap.length;
    while (true) {
      let smallest = idx;
      const l = this.leftChild(idx);
      const r = this.rightChild(idx);
      if (l < n && this.heap[l] < this.heap[smallest]) smallest = l;
      if (r < n && this.heap[r] < this.heap[smallest]) smallest = r;
      if (smallest === idx) break;
      this.swap(idx, smallest);
      idx = smallest;
    }
  }

  size() {
    return this.heap.length;
  }
}

// 실행 예시: Top-3 최솟값 추출
const heap = new MinHeap();
[5, 1, 8, 3, 2, 7].forEach((v) => heap.push(v));

console.log("heap 내부:", heap.heap); // 힙 배열 구조
console.log("최솟값 조회:", heap.peek()); // 1 (O(1))
console.log("pop 순서:", heap.pop(), heap.pop(), heap.pop()); // 1, 2, 3

// Priority Queue 활용 예시: 작업 스케줄링
class TaskScheduler {
  constructor() {
    this.queue = new MinHeap();
  }
  addTask(priority) {
    this.queue.push(priority);
  }
  runNext() {
    return this.queue.pop();
  }
}

const scheduler = new TaskScheduler();
scheduler.addTask(5); // 낮은 우선순위
scheduler.addTask(1); // 긴급
scheduler.addTask(3); // 보통

console.log(
  "실행 순서:",
  scheduler.runNext(),
  scheduler.runNext(),
  scheduler.runNext(),
);

예상 출력:

heap 내부: [1, 2, 8, 5, 3, 7]   ← Min Heap 속성 유지
최솟값 조회: 1
pop 순서: 1 2 3
실행 순서: 1 3 5

Nest.js/AWS 실무 연결: Heap/Priority Queue가 어디서 쓰이나

BullMQ 우선순위 큐: BullMQ는 작업(Job)에 priority 속성을 부여할 수 있다. 내부적으로 Redis의 Sorted Set(점수 기반 정렬)을 사용하는데, 이것이 Min Heap과 동일한 역할이다. 긴급 알림(priority: 1)이 일반 배치 작업(priority: 10)보다 항상 먼저 실행된다.

AWS 서비스의 우선순위 처리: Amazon SQS의 FIFO 큐는 순수 FIFO지만, 실무에서는 긴급 작업용 High Priority 큐와 일반 작업용 Low Priority 큐를 분리하여 Heap과 동일한 효과를 낸다. CloudWatch Alarm의 심각도(CRITICAL > ERROR > WARN) 기반 처리도 Priority Queue 패턴이다.

// NestJS + BullMQ: 우선순위 큐 사용
@Injectable()
export class NotificationService {
  constructor(@InjectQueue("notifications") private queue: Queue) {}

  async sendCritical(userId: string) {
    await this.queue.add("push", { userId }, { priority: 1 }); // 최고 우선순위
  }

  async sendMarketing(userId: string) {
    await this.queue.add("push", { userId }, { priority: 10 }); // 낮은 우선순위
  }
}
// BullMQ는 내부적으로 Redis ZSet(Min Heap과 동일)으로 우선순위를 관리한다

📖 더 보기: BullMQ 우선순위 큐 문서 — priority 옵션으로 Heap 기반 우선순위 처리를 BullMQ에서 사용하는 방법 (입문)

3-3. Graph

비유

지하철 노선도를 생각해보세요. 역(노드)들이 선로(엣지)로 연결되어 있습니다. 강남역에서 홍대역까지 가는 최단 경로를 찾거나, 특정 노선의 모든 역을 순회하는 것이 Graph 탐색 알고리즘입니다.

원리: 표현 방법

인접 행렬 (Adjacency Matrix)

노드 수 = V, 간선 수 = E
행렬 크기: V × V

  0  1  2  3
0[0, 1, 0, 1]  → 0번 노드는 1번, 3번과 연결
1[1, 0, 1, 0]
2[0, 1, 0, 1]
3[1, 0, 1, 0]

장점: 두 노드의 연결 여부를 O(1)로 확인
단점: V² 공간. 간선이 적은 희소 그래프에서 낭비

인접 리스트 (Adjacency List)

{
  0: [1, 3],
  1: [0, 2],
  2: [1, 3],
  3: [0, 2]
}

장점: O(V + E) 공간. 실무에서 주로 사용
단점: 연결 여부 확인에 O(degree) 소요

항목	인접 행렬	인접 리스트
공간	O(V²)	O(V + E)
연결 확인	O(1)	O(degree)
이웃 탐색	O(V)	O(degree)
적합 상황	밀집 그래프	희소 그래프

선택 임계점: 밀도(실제 엣지 수 / V²)가 약 1/64 이상이면 인접 행렬이 공간 측면에서도 경쟁력을 갖기 시작한다 — 행렬 한 칸은 비트 하나로 표현 가능한 반면 리스트는 노드·엣지마다 포인터·길이 오버헤드가 붙기 때문이다. 그 아래면 인접 리스트가 명확히 유리하다. 예시 — 사용자 1,000명에 각자 친구 약 10명인 소셜 그래프는 엣지 약 5,000개, 최대 가능 엣지는 V²=10⁶, 밀도 약 0.005로 명확히 sparse → 리스트가 자연스러운 선택이다 (GeeksforGeeks — Adjacency List vs Matrix).

잘못 골랐을 때 어떻게 드러나는가: V=10,000인 sparse 그래프(E≈10⁵)에 인접 행렬을 boolean 배열로 쓰면 V²=10⁸ — JavaScript의 boolean은 V8 내부에서 객체 슬롯이 1바이트가 아니라 사실상 8바이트라 ~800MB가 점유돼 V=100짜리 단위 테스트는 통과하다가 production 규모에서 Node.js의 기본 heap limit(~2GB)을 깬다. 반대로 V=500, 밀도 0.7 같은 dense 케이스(예: 작은 fully-connected microservice mesh)에 인접 리스트를 쓰면 한 노드의 이웃 탐색이 평균 350개를 훑어야 해 BFS 1회 비용이 O(V·avg_degree) ≈ O(V²)로 부풀고, 모니터에서 latency ~ V² 형태의 2차 곡선이 보이면 이 케이스의 대표 신호다. 진단 1줄 — console.log("V=", V, "E=", E, "density=", E/(V*V))를 그래프 생성 직후 찍어 두면, 밀도가 0.015 이상인데 리스트를 쓰고 있거나 0.005 미만인데 행렬을 쓰고 있다면 표현 교체가 가장 빠른 최적화다.

위상 정렬 (Topological Sort) — DAG의 핵심 알고리즘

위상 정렬은 방향 비순환 그래프(DAG)에서 노드를 의존성 순서대로 나열하는 알고리즘이다. “A가 B에 의존한다”면 B가 A보다 먼저 와야 한다.

왜 중요한가: NestJS의 모듈 초기화 순서, npm/yarn의 패키지 설치 순서, Terraform의 인프라 리소스 생성 순서가 모두 위상 정렬로 결정된다. 위상 정렬이 불가능하면 곧 **순환 의존성(사이클)**이 존재한다는 뜻이다.

// Kahn's Algorithm (BFS 기반 위상 정렬)
function topologicalSort(graph) {
  const inDegree = {};
  const result = [];

  // 모든 노드의 진입 차수(in-degree) 계산
  for (const node of Object.keys(graph)) {
    if (!(node in inDegree)) inDegree[node] = 0;
    for (const neighbor of graph[node]) {
      inDegree[neighbor] = (inDegree[neighbor] || 0) + 1;
    }
  }

  // 진입 차수가 0인 노드를 큐에 넣음 (의존성 없는 노드)
  const queue = Object.keys(inDegree).filter((n) => inDegree[n] === 0);

  while (queue.length) {
    const node = queue.shift();
    result.push(node);
    for (const neighbor of graph[node] || []) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) queue.push(neighbor);
    }
  }

  // 모든 노드가 결과에 포함되지 않으면 사이클 존재
  if (result.length !== Object.keys(inDegree).length) {
    throw new Error("Cycle detected! Topological sort impossible.");
  }
  return result;
}

// 빌드 의존성 예시: C는 A,B에 의존, D는 C에 의존
const buildDeps = { A: ["C"], B: ["C"], C: ["D"], D: [] };
console.log(topologicalSort(buildDeps));

예상 출력:

['A', 'B', 'C', 'D']  또는 ['B', 'A', 'C', 'D']  ← A, B 순서는 상관없음

📖 더 보기: GeeksforGeeks — Detect cycle in Directed Graph using Topological Sort — 위상 정렬로 사이클을 감지하는 코드 설명 (중급)

원리: DFS (깊이 우선 탐색)

DFS는 한 방향으로 최대한 깊이 들어가다가 더 이상 갈 곳이 없으면 되돌아옵니다. 스택(재귀)으로 구현합니다.

그래프:   탐색 순서 (0 시작):
0-1-2     0 → 1 → 2 (막힘, 되돌아옴) → 3 → 4
0-3-4     (깊이 우선이므로 2에서 막히면 3으로)

원리: BFS (너비 우선 탐색)

BFS는 현재 노드의 모든 이웃을 먼저 방문한 뒤, 이웃의 이웃을 방문합니다. 큐로 구현합니다. 비가중치 그래프에서 최단 경로를 보장합니다.

왜 BFS가 최단 경로를 보장하는가: BFS는 “레이어 단위”로 탐색하기 때문이다. 시작 노드에서 거리 1인 노드를 모두 방문한 후에야 거리 2인 노드로 넘어간다. 따라서 특정 노드에 처음 도달한 시점이 곧 최단 거리다. DFS는 한 방향으로 깊이 파고들기 때문에 처음 도달한 경로가 최단이 아닐 수 있다.

왜 DFS는 스택이고 BFS는 큐인가: DFS는 “마지막에 발견한 노드를 먼저 탐색”해야 하므로 LIFO(스택)가 자연스럽다. BFS는 “먼저 발견한 노드를 먼저 탐색”해야 하므로 FIFO(큐)가 필요하다. 이것은 자료구조 선택이 알고리즘 동작을 결정하는 대표적 예시다.

그래프:   탐색 순서 (0 시작):
0-1-2     0 → (1, 3) → (2, 4)
0-3-4     (레이어 단위로 방문: 거리 0 → 거리 1 → 거리 2)

코드 예시

class Graph {
  constructor() {
    this.adjacencyList = {};
  }

  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) {
      this.adjacencyList[vertex] = [];
    }
  }

  addEdge(v1, v2) {
    this.adjacencyList[v1].push(v2);
    this.adjacencyList[v2].push(v1); // 무방향 그래프
  }

  // DFS: 재귀 방식
  dfs(start) {
    const visited = {};
    const result = [];

    const dfsHelper = (vertex) => {
      visited[vertex] = true;
      result.push(vertex);
      for (const neighbor of this.adjacencyList[vertex]) {
        if (!visited[neighbor]) dfsHelper(neighbor);
      }
    };

    dfsHelper(start);
    return result;
  }

  // BFS: 큐 방식
  bfs(start) {
    const queue = [start];
    const visited = { [start]: true };
    const result = [];

    while (queue.length > 0) {
      const vertex = queue.shift(); // 큐에서 앞 꺼내기
      result.push(vertex);

      for (const neighbor of this.adjacencyList[vertex]) {
        if (!visited[neighbor]) {
          visited[neighbor] = true;
          queue.push(neighbor);
        }
      }
    }
    return result;
  }

  // 사이클 감지 (DFS 활용)
  hasCycle() {
    const visited = {};
    const dfsCheck = (vertex, parent) => {
      visited[vertex] = true;
      for (const neighbor of this.adjacencyList[vertex]) {
        if (!visited[neighbor]) {
          if (dfsCheck(neighbor, vertex)) return true;
        } else if (neighbor !== parent) {
          return true; // 방문한 노드로 다시 돌아옴 = 사이클
        }
      }
      return false;
    };

    for (const vertex in this.adjacencyList) {
      if (!visited[vertex]) {
        if (dfsCheck(vertex, null)) return true;
      }
    }
    return false;
  }
}

// 실행 예시
const g = new Graph();
["A", "B", "C", "D", "E"].forEach((v) => g.addVertex(v));
[
  ["A", "B"],
  ["A", "C"],
  ["B", "D"],
  ["C", "D"],
  ["D", "E"],
].forEach(([v1, v2]) => g.addEdge(v1, v2));

console.log("DFS (A 시작):", g.dfs("A"));
console.log("BFS (A 시작):", g.bfs("A"));
console.log("사이클 존재:", g.hasCycle());

// 의존성 그래프 예시 (npm 패키지)
const deps = new Graph();
["express", "accepts", "depd", "mime", "ms"].forEach((p) => deps.addVertex(p));
[
  ["express", "accepts"],
  ["express", "depd"],
  ["accepts", "mime"],
  ["mime", "ms"],
].forEach(([p1, p2]) => deps.addEdge(p1, p2));

console.log("express 의존성 DFS:", deps.dfs("express"));
console.log("express 의존성 BFS:", deps.bfs("express"));

예상 출력:

DFS (A 시작): ['A', 'B', 'D', 'C', 'E']   ← 깊이 우선: A→B→D→C(역방향)→E
BFS (A 시작): ['A', 'B', 'C', 'D', 'E']   ← 너비 우선: A→(B,C)→(D)→E
사이클 존재: true

express 의존성 DFS: ['express', 'accepts', 'mime', 'ms', 'depd']
express 의존성 BFS: ['express', 'accepts', 'depd', 'mime', 'ms']

Nest.js/AWS 실무 연결: Graph가 어디서 직접 쓰이나

NestJS DI 컨테이너 = 의존성 그래프: NestJS 애플리케이션이 시작될 때 NestFactory.create(AppModule)은 내부적으로 모든 모듈과 프로바이더의 의존성 그래프(DAG)를 구성한다. 이 그래프를 DFS로 탐색하며 순환 의존성(사이클)을 감지한다. 사이클이 발견되면 다음 오류가 발생한다:

Error: A circular dependency has been detected (AppModule -> UserModule -> AuthModule -> UserModule).
Please, make sure that each side of a circular dependency arrow is marked with a @forwardRef() decorator.

이 오류는 Graph 사이클 감지 알고리즘의 직접적인 출력이다. forwardRef()는 그래프 에지 방향을 바꿔 사이클을 끊는 기법이다.

AWS Step Functions = DAG: AWS Step Functions의 상태 머신은 각 상태(State)가 노드이고, 전환(Transition)이 에지인 DAG다. 병렬 처리(Parallel 상태)는 그래프의 분기 구조이고, 전체 실행 순서는 위상 정렬(Topological Sort)로 결정된다.

Terraform 리소스 그래프: terraform plan 실행 시 Terraform은 인프라 리소스 간 의존성을 그래프로 파악하고, 의존성이 없는 리소스는 병렬로 생성한다. 이 그래프 탐색이 없으면 VPC가 생성되기 전에 EC2를 만들려다 오류가 발생한다.

📖 더 보기: NestJS 순환 의존성 공식 문서 — DI 그래프에서 순환 참조가 발생하는 원인과 forwardRef() 해결법 (입문)

📖 더 보기: DigitalOcean — Understanding Circular Dependency in NestJS — 실제 순환 의존성 사례와 해결 패턴 (중급)

3-4. 트리·그래프 실전 심화 패턴

비유로 이해하기

“도시 지도에서 길을 찾는 두 가지 방법”

DFS (깊이 우선): 한 골목을 끝까지 들어가다가 막히면 되돌아와서 다른 골목 탐색. 미로 탈출에 최적.
BFS (너비 우선): 현재 교차로에서 가장 가까운 모든 골목부터 탐색. 최단 경로 보장.

트리는 사이클이 없는 그래프다. 트리에서는 부모→자식 방향이 명확하므로 visited 체크 없이도 탐색 가능하다. 그래프에서는 반드시 visited를 체크해야 무한 루프를 막을 수 있다.

BST vs B-Tree: 왜 DB는 BST를 쓰지 않는가

BST (이진 탐색 트리):
- 한 노드에 1개의 키
- 높이 = O(log n) (균형 시)
- 디스크 I/O: 노드당 1번 → 높이만큼 I/O 발생
- n=1억이면 높이 ≈ 27 → 최대 27번 디스크 I/O

B-Tree (데이터베이스 인덱스):
- 한 노드에 수백~수천 개의 키 (보통 페이지 크기 4KB에 맞춤)
- 높이 = O(log_m n) (m = 분기 수, 보통 100~1000)
- n=1억이면 높이 ≈ 3~4 → 최대 4번 디스크 I/O
- 디스크 블록 단위로 노드를 설계해 I/O 효율 극대화

이것이 CREATE INDEX가 쿼리를 수천 배 빠르게 만드는 근본 원리다.

Dijkstra 알고리즘: 가중치 그래프 최단 경로 (심화)

BFS는 비가중치 그래프에서 최단 경로를 보장하지만, 가중치가 있는 그래프에서는 Dijkstra가 필요하다.

// Dijkstra: Priority Queue(Min Heap) + BFS 변형
// AWS 서비스 간 레이턴시 최적 경로 찾기 예시
interface Edge {
  to: string;
  weight: number;
}
type Graph = Record<string, Edge[]>;

function dijkstra(graph: Graph, start: string): Record<string, number> {
  const dist: Record<string, number> = {};
  const visited = new Set<string>();

  // 모든 노드 거리를 무한대로 초기화
  for (const node of Object.keys(graph)) dist[node] = Infinity;
  dist[start] = 0;

  // 간단한 Priority Queue (실제로는 Min Heap 구현 권장)
  const pq: Array<[number, string]> = [[0, start]];

  while (pq.length > 0) {
    // 최소 거리 노드 선택 (Min Heap이면 O(log n), 여기선 O(n))
    pq.sort((a, b) => a[0] - b[0]);
    const [d, node] = pq.shift()!;

    if (visited.has(node)) continue;
    visited.add(node);

    for (const { to, weight } of graph[node] || []) {
      const newDist = d + weight;
      if (newDist < dist[to]) {
        dist[to] = newDist;
        pq.push([newDist, to]);
      }
    }
  }

  return dist;
}

// AWS 리전 간 레이턴시 그래프 (ms)
const awsLatency: Graph = {
  "ap-northeast-2": [
    // 서울
    { to: "ap-southeast-1", weight: 80 }, // 싱가포르
    { to: "us-west-2", weight: 180 }, // 오레곤
  ],
  "ap-southeast-1": [
    // 싱가포르
    { to: "eu-west-1", weight: 170 }, // 아일랜드
    { to: "us-east-1", weight: 220 }, // 버지니아
  ],
  "us-west-2": [
    { to: "us-east-1", weight: 60 },
    { to: "eu-west-1", weight: 130 },
  ],
  "us-east-1": [{ to: "eu-west-1", weight: 80 }],
  "eu-west-1": [],
};

const distances = dijkstra(awsLatency, "ap-northeast-2");
console.log("서울 → 각 리전 최소 레이턴시(ms):");
for (const [region, dist] of Object.entries(distances)) {
  console.log(`  ${region}: ${dist}ms`);
}

예상 출력:

서울 → 각 리전 최소 레이턴시(ms):
  ap-northeast-2: 0ms
  ap-southeast-1: 80ms
  us-west-2: 180ms
  eu-west-1: 250ms   ← ap-northeast-2→us-west-2→eu-west-1 = 180+130
  us-east-1: 240ms   ← ap-northeast-2→us-west-2→us-east-1 = 180+60

NestJS 모듈 의존성 그래프 직접 시각화

// NestJS 모듈 간 의존성을 추출해 그래프로 표현
// (실제 NestJS 내부 동작과 동일한 원리)

interface Module {
  name: string;
  imports: string[];
}

function buildDependencyGraph(modules: Module[]): Record<string, string[]> {
  const graph: Record<string, string[]> = {};
  for (const mod of modules) {
    graph[mod.name] = mod.imports;
  }
  return graph;
}

function detectCircularDependency(
  graph: Record<string, string[]>,
): string | null {
  const visited = new Set<string>();
  const inStack = new Set<string>(); // 현재 DFS 경로상에 있는 노드

  function dfs(node: string, path: string[]): string | null {
    if (inStack.has(node)) {
      // 현재 경로에서 이미 방문한 노드 = 사이클 발견
      const cycleStart = path.indexOf(node);
      return path.slice(cycleStart).join(" → ") + " → " + node;
    }
    if (visited.has(node)) return null;

    visited.add(node);
    inStack.add(node);

    for (const dep of graph[node] || []) {
      const cycle = dfs(dep, [...path, node]);
      if (cycle) return cycle;
    }

    inStack.delete(node);
    return null;
  }

  for (const node of Object.keys(graph)) {
    if (!visited.has(node)) {
      const cycle = dfs(node, []);
      if (cycle) return cycle;
    }
  }
  return null;
}

const modules: Module[] = [
  { name: "AppModule", imports: ["UserModule", "AuthModule"] },
  { name: "UserModule", imports: ["DatabaseModule"] },
  { name: "AuthModule", imports: ["UserModule"] }, // UserModule 참조
  { name: "DatabaseModule", imports: [] },
];

const graph = buildDependencyGraph(modules);
const cycle = detectCircularDependency(graph);
console.log(cycle ? `사이클 감지: ${cycle}` : "사이클 없음 (정상)");

// 사이클 주입 테스트
modules[1].imports.push("AuthModule"); // UserModule → AuthModule 추가
const graph2 = buildDependencyGraph(modules);
const cycle2 = detectCircularDependency(graph2);
console.log(cycle2 ? `사이클 감지: ${cycle2}` : "사이클 없음");

예상 출력:

사이클 없음 (정상)
사이클 감지: UserModule → AuthModule → UserModule

4. 실무에서 어떻게 쓰이나

BST 활용 사례

데이터베이스 인덱스: MySQL의 B-Tree 인덱스는 BST의 확장. WHERE id BETWEEN 100 AND 200 쿼리가 O(log n)에 동작하는 이유.
자동완성(Auto-complete): 사전 기반 검색에서 알파벳 순서로 정렬된 BST 탐색.
파일시스템: 디렉토리 구조 탐색.

Heap/Priority Queue 활용 사례

작업 스케줄링: Node.js 이벤트 루프의 타이머, OS 프로세스 스케줄러.
Top-K 문제: “가장 많이 검색된 키워드 10개”, “최고 매출 상품 5개” → Min Heap으로 K개 유지.
Dijkstra 최단 경로: Priority Queue로 최소 비용 엣지를 항상 먼저 처리.
미디어 스트리밍: 버퍼 우선순위 관리.

Graph 활용 사례

npm/yarn 의존성 해결: 패키지 설치 순서를 위상 정렬(DFS 기반)로 결정.
MSA 서비스 의존성: 서비스 간 호출 관계를 그래프로 표현, 순환 의존성 감지.
AWS 네트워크 토폴로지: VPC, 서브넷, 라우팅 테이블 관계 분석.
소셜 그래프: “팔로우 추천” (BFS로 2단계 이내 연결 탐색).
Terraform 리소스 그래프: 인프라 리소스 생성 순서 결정.

5. 내 업무와의 연결고리

BackOps 엔지니어로서 Nest.js / AWS 스택을 사용한다면 다음 상황에서 직접 마주칩니다:

Nest.js 모듈 의존성: Nest.js의 DI(Dependency Injection) 컨테이너는 내부적으로 모듈 의존성 그래프를 구성하고 순환 의존성을 감지합니다. Circular dependency detected 오류가 발생하면 DFS 사이클 감지와 동일한 원리.

API 응답 우선순위: 결제 처리, 알림 발송 등 긴급도가 다른 작업을 처리할 때 Priority Queue 패턴 적용 가능.

데이터 파이프라인 순서: AWS Step Functions의 상태 머신은 DAG(Directed Acyclic Graph). 각 단계의 실행 순서가 위상 정렬로 결정됨.

ElasticSearch 검색: 내부 역색인(Inverted Index)은 트리 기반 자료구조. 검색 쿼리 성능 최적화 시 이해가 필요.

CloudWatch 알림 우선순위: 여러 알림이 동시에 발생할 때 심각도(CRITICAL > ERROR > WARN) 기반 처리 순서는 Max Heap으로 구현 가능.

새 기술에서 트리·그래프 구조를 알아채는 4가지 질문

위 사례들이 모두 BST/Heap/Graph로 환원되는 이유는 각 시스템이 노드+관계 구조 위에서 같은 종류의 결정을 내리기 때문이다. 처음 보는 라이브러리·인프라·프레임워크를 만났을 때 다음 4가지를 자문하면, 그 시스템 안에 어떤 자료구조가 숨어 있는지 빠르게 식별할 수 있다.

요소 사이의 관계가 부모→자식 단방향인가, 임의 방향인가? 단방향이면 트리, 임의면 그래프다. 예: NestJS 모듈 import는 임의 방향(서로가 서로를 참조 가능) → Graph로 모델링되고 사이클 감지가 필요. 반면 파일시스템 디렉토리는 부모→자식 단방향 → 트리로 충분하고 사이클 검사가 불필요.
“순서”가 결과를 바꾸는가? 바꾸면 위상 정렬 또는 우선순위 큐가 등장. 예: Terraform이 VPC를 EC2보다 먼저 만드는 것은 위상 정렬 결과, BullMQ에서 priority 1 작업이 priority 10보다 먼저 실행되는 것은 Min Heap. 순서 무관(예: Kubernetes의 Pod 라벨 매칭)이면 해시 테이블이면 충분.
사이클이 valid 상태인가, 오류인가? 오류로 처리해야 하면 DFS 사이클 감지 또는 Kahn 위상 정렬이 필요. NestJS DI 그래프는 사이클을 오류로 본다 → 시작 시 DFS 검사. 반대로 소셜 팔로우 그래프는 사이클이 정상 상태(상호 팔로우) → BFS·DFS 모두 visited 집합으로 처리.
조회 빈도가 변경 빈도보다 압도적으로 높은가? 그러면 정렬 배열이나 인덱스 구조가 유리. 둘이 비슷하면 자가 균형 트리(Red-Black)가 안전. 예: §3-1의 Linux 커널 CFS 스케줄러는 변경이 잦아 Red-Black, 반면 정적 라우팅 테이블은 정렬 배열로 충분.

이 네 질문은 본문에서 이미 사용된 분석 도구다. §3-3의 NestJS·Step Functions·Terraform 사례는 (1)·(2)·(3)을 차례로 적용해 도출됐고, §3-1의 AVL vs Red-Black 결정은 (4)를 적용한 결과다. 새 기술에서 같은 4질문을 적용하면 — 예: GraphQL 스키마 의존성에 적용하면 (1) 임의 방향, (2) 순서 무관(병렬 해석 가능), (3) 사이클은 보통 오류 → DFS 사이클 감지가 필요한 그래프 문제로 즉시 분류된다.

6. 비슷한 개념과 비교

BST vs Hash Table

항목	BST	Hash Table
탐색	O(log n)	O(1) 평균
정렬된 순회	O(n) 지원	지원 안 함
범위 검색	O(log n + k)	불가
메모리	포인터 오버헤드	해시 충돌 공간
적합 상황	정렬/범위 필요	단순 키-값 조회

DFS vs BFS

항목	DFS	BFS
자료구조	스택 (재귀)	큐
메모리	O(h): 트리 높이	O(w): 트리 너비
최단 경로	보장 안 함	보장 (비가중치)
사이클 감지	자연스럽게 가능	가능하지만 복잡
연결 요소 탐색	적합	가능
위상 정렬	가능 (후위 순회)	Kahn’s algorithm
적합 상황	경로 존재 여부, 미로	최단 거리, 레벨 순회

Heap vs 정렬 배열

항목	Heap	정렬 배열
최솟값 조회	O(1)	O(1)
삽입	O(log n)	O(n) — 쉬프트
삭제	O(log n)	O(n) — 쉬프트
임의 탐색	O(n)	O(log n)
적합 상황	동적 우선순위	정적 정렬 데이터

6.5. 트러블슈팅

트러블슈팅 1: BST 탐색이 무한 루프에 빠지는 경우

증상: BST 탐색 함수가 종료되지 않고 계속 실행되거나, 스택 오버플로우 발생.

원인: 삽입 시 실수로 BST 속성을 깨뜨려서 순환 참조(circular reference)가 생긴 경우. 예를 들어 node.right = node 형태의 실수.

// 잘못된 예시 (실수 케이스)
function insertBad(root, value) {
  if (value < root.value) {
    root.left = insertBad(root, value); // root를 재귀에 넘김 → 무한루프
  }
  // ...
}

// 올바른 예시
function insertCorrect(root, value) {
  if (!root) return new TreeNode(value);
  if (value < root.value) {
    root.left = insertCorrect(root.left, value); // root.left를 넘겨야 함
  } else {
    root.right = insertCorrect(root.right, value);
  }
  return root;
}

해결 방법: 재귀 함수에 항상 종료 조건(if (!root) return)을 먼저 작성하고, 재귀 호출 시 현재 노드가 아닌 자식 노드를 넘기는지 확인. 또는 반복(iterative) 방식으로 전환하면 무한루프 위험이 사라짐.

트러블슈팅 2: Heap에서 삭제 후 Heap 속성이 깨지는 경우

증상: pop() 이후 peek()이 최솟값이 아닌 다른 값을 반환. Priority Queue가 잘못된 순서로 작업을 처리.

원인: 루트 삭제 후 Heapify Down을 빠뜨리거나, 두 자식 중 더 작은 값과 교환하지 않고 무조건 왼쪽 자식과 교환하는 실수.

// 잘못된 Heapify Down (버그 있음)
_bubbleDownBad(idx) {
  const l = this.leftChild(idx);
  // 왼쪽 자식만 확인하는 실수 → 오른쪽이 더 작을 수 있음
  if (l < this.heap.length && this.heap[l] < this.heap[idx]) {
    this.swap(idx, l);
    this._bubbleDownBad(l);
  }
}

// 올바른 Heapify Down
_bubbleDownCorrect(idx) {
  const n = this.heap.length;
  let smallest = idx;
  const l = this.leftChild(idx);
  const r = this.rightChild(idx);
  // 양쪽 모두 확인하여 가장 작은 값 선택
  if (l < n && this.heap[l] < this.heap[smallest]) smallest = l;
  if (r < n && this.heap[r] < this.heap[smallest]) smallest = r;
  if (smallest !== idx) {
    this.swap(idx, smallest);
    this._bubbleDownCorrect(smallest);
  }
}

해결 방법: Heapify Down에서 왼쪽/오른쪽 자식을 모두 확인하고, 현재 노드보다 작은(Min Heap) 값이 있는 자식 중 더 작은 쪽과 교환해야 함.

트러블슈팅 3: BFS에서 visited 체크 타이밍 실수로 중복 방문 발생 (silent failure 변종)

증상: 작은 그래프(노드 수십 개)에서는 정답이 나와 단위 테스트가 통과하지만, 대규모 그래프(수만 노드 이상)에서만 큐 크기가 폭주해 OOM 또는 TLE이 발생한다. 답 자체는 결국 같이 나오기 때문에 “정확성 버그”가 아닌 “성능 버그”로 인식되어 원인 추적이 늦어진다 — 이 점이 silent failure적 성격이다. 일리노이대 CS 225 자료는 “marking visited after dequeuing allows duplicate enqueues, and you should always mark before pushing neighbors”라고 명시한다 (CS 225 BFS & DFS).

감지 방법: 큐 최대 길이를 측정하는 계측을 1줄 넣으면 즉시 드러난다 — 정상 BFS는 큐 길이가 ≤ |V|를 넘지 않지만, 잘못된 구현은 |E|에 가까워진다. 예: let maxQ = 0; while (queue.length) { maxQ = Math.max(maxQ, queue.length); ... } console.log("queue peak:", maxQ);

원인: 노드를 큐에 넣을 때가 아니라 꺼낼 때 visited 처리하는 실수. 큐에 이미 들어간 노드가 다시 삽입될 수 있음.

// 잘못된 BFS (꺼낼 때 visited 처리)
function bfsBad(graph, start) {
  const queue = [start];
  const visited = {};
  const result = [];

  while (queue.length) {
    const node = queue.shift();
    if (visited[node]) continue; // 이미 처리됐으면 건너뜀
    visited[node] = true; // 꺼낼 때 처리 → 큐에 중복 삽입 허용
    result.push(node);
    for (const neighbor of graph[node] || []) {
      queue.push(neighbor); // visited 확인 없이 삽입!
    }
  }
  return result;
}

// 올바른 BFS (넣을 때 visited 처리)
function bfsCorrect(graph, start) {
  const visited = { [start]: true }; // 시작 노드부터 visited
  const queue = [start];
  const result = [];

  while (queue.length) {
    const node = queue.shift();
    result.push(node);
    for (const neighbor of graph[node] || []) {
      if (!visited[neighbor]) {
        visited[neighbor] = true; // 큐에 넣을 때 바로 visited 처리
        queue.push(neighbor);
      }
    }
  }
  return result;
}

해결 방법: BFS에서 visited 처리는 반드시 큐에 넣는 시점에 해야 함. 꺼내는 시점에 처리하면 성능 문제가 생기고 일부 케이스에서 오답이 발생할 수 있음.

트러블슈팅 4: NestJS 순환 의존성 오류 (Graph 사이클 감지의 실무 사례)

증상: NestJS 앱 시작 시 다음 오류 발생:

Error: A circular dependency has been detected (UserModule -> AuthModule -> UserModule).
Please, make sure that each side of a bidirectional dependency is decorated with "forwardRef()".

원인: NestJS DI 컨테이너는 모듈 간 의존성을 **방향 그래프(Directed Graph)**로 구성하고, 앱 시작 시 DFS로 사이클을 감지한다. UserModule이 AuthModule을 import하고, AuthModule이 다시 UserModule을 import하면 사이클이 발생한다. 이것은 위상 정렬이 불가능한 그래프와 동일한 상황이다.

해결 방법:

// 방법 1: forwardRef()로 사이클 끊기 (임시 해결)
@Module({
  imports: [forwardRef(() => AuthModule)], // 지연 참조
  providers: [UserService],
  exports: [UserService],
})
export class UserModule {}

// 방법 2: 공통 모듈 추출로 근본적 해결 (권장)
// SharedModule에 양쪽이 공유하는 서비스를 분리
@Module({
  providers: [SharedAuthService],
  exports: [SharedAuthService],
})
export class SharedModule {}
// → UserModule과 AuthModule 모두 SharedModule을 import
// → 사이클 제거됨 (DAG 유지)

핵심: forwardRef()는 그래프의 에지 방향을 “지연 평가”로 바꿔 사이클을 우회하는 기법이다. 근본적으로는 그래프 구조 자체를 DAG로 재설계하는 것이 바람직하다.

트러블슈팅 5: Heap에서 Top-K 문제를 Max Heap으로 풀다가 메모리 초과

증상: “n개 원소에서 가장 큰 k개를 구하라” 문제에서 Max Heap에 전체를 넣은 뒤 k번 pop하는 방식으로 구현했는데, 메모리나 시간이 초과된다.

원인: Max Heap에 n개를 전부 삽입(O(n log n))하고 k번 pop하는 방식은 정확하지만, n이 수백만이고 k가 10처럼 작으면 Min Heap으로 k개만 유지하는 방식이 훨씬 효율적이다.

해결 방법:

// 나쁜 예: Max Heap에 전부 넣기 — O(n log n) 시간, O(n) 공간
function topKBad(nums, k) {
  // 전체를 Max Heap에 삽입 후 k번 pop
  // n = 100만, k = 10 → 100만 개를 모두 힙에 저장
  const maxHeap = new MaxHeap();
  for (const n of nums) maxHeap.push(n);
  const result = [];
  for (let i = 0; i < k; i++) result.push(maxHeap.pop());
  return result;
}

// 좋은 예: Min Heap으로 k개만 유지 — O(n log k) 시간, O(k) 공간
function topKGood(nums, k) {
  // k개짜리 Min Heap 유지: 새 값이 최솟값보다 크면 교체
  // n = 100만, k = 10 → 항상 10개만 힙에 유지
  const minHeap = []; // 간단히 정렬 배열로 시뮬레이션

  for (const num of nums) {
    if (minHeap.length < k) {
      minHeap.push(num);
      minHeap.sort((a, b) => a - b); // Min Heap 유지
    } else if (num > minHeap[0]) {
      minHeap[0] = num; // 최솟값 교체
      minHeap.sort((a, b) => a - b);
    }
  }

  return minHeap.sort((a, b) => b - a); // 내림차순 반환
}

const nums = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];
console.log(topKGood(nums, 3)); // [9, 6, 5]

예상 출력:

[9, 6, 5]

메모리 비교: n=1,000,000, k=10일 때

Max Heap 전체: ~8MB (100만 개 저장)
Min Heap k개 유지: ~80바이트 (10개만 저장) → 10만 배 차이

트러블슈팅 6: 위상 정렬 결과가 매번 다르게 나온다 (silent failure)

증상: 같은 DAG에 대해 위상 정렬을 실행할 때마다 순서가 달라진다. 단위 테스트는 가끔 통과·가끔 실패한다. 모든 결과가 의존성 측면에서는 “정답”이라 에러도, 사이클 경고도, 잘못된 출력도 발생하지 않는다. 의존성을 직접 깨뜨릴 때까지 — 예: 모듈 초기화 부수효과(side effect) 순서가 바뀌어 어떤 환경에서만 환경변수가 늦게 로드되는 식 — 문제가 가시화되지 않는다.

왜 silent failure 분류인가: “에러 없이 잘못 동작”의 정의에 부합한다. 출력이 형식상 valid하기 때문에 assertion·linter·타입 검사 어디에서도 잡히지 않는다. CI에서 1/N 확률로만 깨지므로 “flaky test” 라벨로 묻히기 쉽다. 감지하려면 같은 입력으로 N회 반복 실행해 결과 집합을 비교하는 별도 테스트가 필요하다.

원인: Wikipedia: Topological sorting에 따르면 진입 차수가 0인 노드가 여러 개이면 어느 것을 먼저 꺼내도 유효한 위상 순서이며, “Reflecting the non-uniqueness of the resulting sort, the structure S can be simply a set or a queue or a stack. Depending on the order that nodes n are removed from set S, a different solution is created.” JavaScript Object.keys()의 키 순회 순서는 ES2015 이후 정수 키는 오름차순이지만 비정수 키는 삽입 순서를 따라 — 같은 코드라도 그래프 구성 방식이 다르면 출력이 달라진다.

해결 방법:

// 비결정적 위상 정렬 (큐 삽입 순서 보장 없음)
function topoNondeterministic(graph) {
  const inDegree = {};
  for (const node of Object.keys(graph)) inDegree[node] = 0;
  for (const node of Object.keys(graph))
    for (const dep of graph[node]) inDegree[dep] = (inDegree[dep] || 0) + 1;

  const queue = Object.keys(inDegree).filter((n) => inDegree[n] === 0);
  // ← 순서가 Object.keys() 순서에 의존 → 비결정적
  const result = [];
  while (queue.length) {
    const node = queue.shift();
    result.push(node);
    for (const dep of graph[node] || []) {
      if (--inDegree[dep] === 0) queue.push(dep);
    }
  }
  return result;
}

// 결정적 위상 정렬 (알파벳 순으로 큐 정렬)
function topoDeterministic(graph) {
  const inDegree = {};
  for (const node of Object.keys(graph)) inDegree[node] = 0;
  for (const node of Object.keys(graph))
    for (const dep of graph[node]) inDegree[dep] = (inDegree[dep] || 0) + 1;

  // 알파벳 순 정렬로 결정적 결과 보장
  const queue = Object.keys(inDegree)
    .filter((n) => inDegree[n] === 0)
    .sort(); // ← 정렬 추가

  const result = [];
  while (queue.length) {
    queue.sort(); // 매번 정렬하여 결정적 순서 유지
    const node = queue.shift();
    result.push(node);
    for (const dep of (graph[node] || []).sort()) {
      if (--inDegree[dep] === 0) queue.push(dep);
    }
  }
  return result;
}

const graph = { A: ["C"], B: ["C"], C: ["D"], D: [] };
console.log(topoDeterministic(graph)); // 항상 ['A', 'B', 'C', 'D']

예상 출력:

['A', 'B', 'C', 'D']

실무 적용: NestJS 모듈 초기화 순서를 테스트할 때 결정적 위상 정렬을 사용하면 테스트 결과가 안정적이다.

트러블슈팅 7: DFS 재귀로 대규모 그래프 탐색 시 스택 오버플로우

증상: 노드 수가 10,000개 이상인 그래프를 DFS로 탐색하면 Maximum call stack size exceeded 오류 발생.

메모리 상한 수치:

Node.js 재귀 깊이 한계: ~~10,000~~15,000 프레임
재귀 DFS 1 프레임 ≈ 200~500바이트 → 10,000 깊이 × 500바이트 = ~5MB 스택
BFS의 Queue 메모리: 노드당 ~64바이트 × 노드 수 → 10만 노드 = ~6MB (안전)
반복 DFS의 명시적 스택: 동일 ~6MB (힙 메모리, 상한 없음)

프로덕션 실패 사례: Kubernetes 의존성 그래프 분석 도구에서 대규모 클러스터(노드 50,000개+)의 Pod 의존성을 DFS로 탐색했다가 Maximum call stack size exceeded로 분석 실패. 반복 DFS로 전환 후 해결 (재귀 깊이 제한 없음, 메모리 일정).

원인: 재귀 DFS는 함수 호출 스택을 사용하는데, JavaScript/Node.js의 기본 콜 스택 크기는 약 10,000~15,000 프레임.

해결 방법: 재귀 대신 명시적 스택(배열)을 사용한 반복 DFS로 전환.

// 재귀 DFS (스택 오버플로우 위험)
function dfsRecursive(graph, start, visited = {}) {
  visited[start] = true;
  for (const neighbor of graph[start] || []) {
    if (!visited[neighbor]) dfsRecursive(graph, neighbor, visited);
  }
}

// 반복 DFS (스택 오버플로우 없음)
function dfsIterative(graph, start) {
  const stack = [start];
  const visited = { [start]: true };
  const result = [];

  while (stack.length) {
    const node = stack.pop(); // 스택의 끝에서 꺼냄
    result.push(node);
    for (const neighbor of (graph[node] || []).slice().reverse()) {
      // .reverse()는 원래 DFS 순서 유지를 위함 (선택 사항)
      if (!visited[neighbor]) {
        visited[neighbor] = true;
        stack.push(neighbor);
      }
    }
  }
  return result;
}

7. 체크리스트

BST

BST 속성(왼쪽 < 부모 < 오른쪽)을 말로 설명할 수 있다
삽입, 탐색, 중위 순회를 코드로 구현할 수 있다
편향 트리에서 O(n)이 되는 이유를 설명할 수 있다
AVL/Red-Black Tree가 O(log n)을 보장하는 원리를 개념적으로 안다
중위 순회 결과가 정렬 순서인 이유를 설명할 수 있다

Heap & Priority Queue

Max Heap과 Min Heap의 차이를 설명할 수 있다
배열로 Heap을 표현할 때 인덱스 공식(2i+1, 2i+2)을 안다
Heapify Up(삽입)과 Heapify Down(삭제)을 구현할 수 있다
Priority Queue가 어떤 문제를 해결하는지 3가지 예를 들 수 있다
Top-K 문제를 Min Heap으로 O(n log k)에 풀 수 있다

Graph

인접 행렬과 인접 리스트의 트레이드오프를 설명할 수 있다
DFS를 재귀와 반복 두 가지 방식으로 구현할 수 있다
BFS로 최단 경로를 구할 수 있다
DFS로 사이클을 감지하는 코드를 작성할 수 있다
BFS의 visited 처리를 “큐에 넣을 때” 해야 하는 이유를 안다
의존성 그래프에서 DFS를 활용한 위상 정렬 개념을 안다

8. 핵심 키워드

키워드	설명
Binary Search Tree (BST)	왼쪽 < 부모 < 오른쪽 속성의 이진 트리
편향 트리 (Skewed Tree)	한쪽으로만 치우쳐 O(n)이 되는 BST
자가 균형 트리	AVL, Red-Black Tree. 항상 O(log n) 보장
완전 이진 트리	Heap의 기반. 마지막 레벨 왼쪽부터 채움
Heapify Up/Down	삽입/삭제 후 Heap 속성 복원 연산
Priority Queue	Heap으로 구현된 우선순위 큐 추상 자료형
인접 행렬	V×V 행렬로 그래프 표현. 밀집 그래프용
인접 리스트	배열+리스트로 그래프 표현. 희소 그래프용
DFS	스택/재귀 기반 깊이 우선 탐색
BFS	큐 기반 너비 우선 탐색. 최단 경로 보장
위상 정렬	DAG에서 의존성 순서대로 정렬 (DFS 활용)
사이클 감지	DFS에서 이미 방문한 노드로 돌아오면 사이클

8.5. 추천 리소스

리소스	유형	난이도	URL
GeeksforGeeks - BST Operations	공식 문서/튜토리얼	입문	링크
W3Schools - DSA Binary Search Trees	인터랙티브 튜토리얼	입문	링크
DigitalOcean - Binary Heaps & Priority Queues in JavaScript	영상/블로그	중급	링크
VisuAlgo - DFS/BFS 시각화	인터랙티브 시각화	입문~중급	링크
PuppyGraph - DFS vs BFS 심층 가이드	블로그	중급	링크
NestJS 공식 문서 - 순환 의존성 처리	공식 문서	입문	링크
Baeldung - Red-Black Tree vs. AVL Tree	블로그	중급	링크
GeeksforGeeks - 위상 정렬로 사이클 감지	튜토리얼	중급	링크
Codeintuition - Topological Sort Explained	블로그	입문~중급	링크

📚 추천 리소스 (추가)

📖 Mastering Tree and Graph for Coding Interviews — DesignGurus — 트리·그래프 면접 문제의 접근 패턴과 엣지 케이스 처리법을 실전 중심으로 정리 (중급)
📖 Graph Algorithms Cheat Sheet — Memgraph — BFS/DFS/Dijkstra/Topo Sort를 한눈에 비교하는 면접 치트시트 (입문)
🎬 BFS Interview Questions & Tips — interviewing.io — 시니어 면접 기준으로 BFS 문제 접근법과 visited 체크 타이밍 등 실전 팁 (중급)
📖 DFS Interview Questions & Tips — interviewing.io — DFS 재귀·반복 구현, 사이클 감지, 위상 정렬 면접 팁 (중급)
📖 Graph Cheatsheet — Tech Interview Handbook — 그래프 알고리즘 복잡도와 선택 기준을 한 페이지로 압축 (입문)

9. 직접 확인해보기

9-1. BST 삽입 후 중위 순회 확인

// Node.js에서 직접 실행 가능
class TreeNode {
  constructor(v) {
    this.value = v;
    this.left = null;
    this.right = null;
  }
}

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

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

let root = null;
[5, 3, 7, 1, 4, 6, 8].forEach((v) => (root = insert(root, v)));
console.log(inorder(root));

예상 출력:

[1, 3, 4, 5, 6, 7, 8]

변형 실험: 편향 트리에서 탐색 시간이 얼마나 늘어나는가

위 코드를 그대로 둔 채, 같은 1만 개 정수를 (a) 균형이 잘 잡히도록 셔플해서 삽입한 경우와 (b) 정렬된 순서대로 삽입해 편향시킨 경우의 탐색 시간을 직접 비교한다. 본문 §3-1의 “편향 시 O(n)” 주장이 실측에서 어떻게 드러나는지 확인하는 단계다.

function buildAndSearch(values, targets) {
  let r = null;
  for (const v of values) r = insert(r, v);
  let found = 0;
  const t0 = process.hrtime.bigint();
  for (const t of targets) {
    let cur = r;
    while (cur) {
      if (cur.value === t) {
        found++;
        break;
      }
      cur = t < cur.value ? cur.left : cur.right;
    }
  }
  const t1 = process.hrtime.bigint();
  return { ms: Number(t1 - t0) / 1e6, found };
}

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:", buildAndSearch(sorted, targets));
console.log("균형 근사 BST:", buildAndSearch(shuffled, targets));

예상 출력 (수치는 환경마다 다름, 비율이 핵심):

편향 BST: { ms: ~25-60, found: 1000 }
균형 근사 BST: { ms: ~1-3, found: 1000 }

비율이 약 10~30배 차이로 벌어지면 본문의 O(log n) vs O(n) 주장이 실측으로 확인된 것이다. 출력이 다르면 의심할 것: (1) Node.js JIT 워밍업 — 두 호출을 각각 100회 반복해 평균을 내면 안정화, (2) 셔플이 부족 — crypto.randomBytes 기반 셔플로 교체.

다음 단계 과제: 편향 입력에서 N을 10,000 → 100,000으로 키워라. 탐색 시간이 약 10배 늘면 O(n)이 확인된다. 같은 N으로 균형 입력도 측정하면 시간이 거의 변하지 않거나 log 비율(약 1.2배)로만 늘어 O(log n)이 확인된다.

9-2. Min Heap 동작 확인

// MinHeap 클래스 위의 코드와 동일하게 사용

const heap = new MinHeap();
[10, 4, 7, 2, 8, 1].forEach((v) => heap.push(v));
console.log("힙 배열:", heap.heap);

const sorted = [];
while (heap.size() > 0) sorted.push(heap.pop());
console.log("정렬 결과:", sorted); // 힙 정렬!

예상 출력:

힙 배열: [1, 4, 2, 10, 8, 7]   ← Min Heap 속성 유지
정렬 결과: [1, 2, 4, 7, 8, 10]  ← Heap Sort!

9-3. 그래프 BFS로 최단 거리 계산

function shortestPath(graph, start, end) {
  if (start === end) return 0;

  const visited = { [start]: true };
  const queue = [[start, 0]]; // [노드, 거리]

  while (queue.length) {
    const [node, dist] = queue.shift();
    for (const neighbor of graph[node] || []) {
      if (neighbor === end) return dist + 1;
      if (!visited[neighbor]) {
        visited[neighbor] = true;
        queue.push([neighbor, dist + 1]);
      }
    }
  }
  return -1; // 경로 없음
}

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

console.log("A → E 최단 거리:", shortestPath(graph, "A", "E")); // 3
console.log("A → D 최단 거리:", shortestPath(graph, "A", "D")); // 2
console.log("A → A 최단 거리:", shortestPath(graph, "A", "A")); // 0

예상 출력:

A → E 최단 거리: 3
A → D 최단 거리: 2
A → A 최단 거리: 0

변형 실험: 사이클 추가 후 BFS·위상 정렬 동작 비교

위 그래프는 사이클이 없는 단순 그래프다. 본문 §3-3의 “BFS는 visited 체크로 사이클을 견딘다”, “위상 정렬은 사이클이 있으면 실패한다”라는 두 주장을 같은 입력에서 직접 확인한다.

// 위 graph에 의도적으로 사이클을 주입: E → A
const cyclicGraph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "D"],
  D: ["B", "C", "E"],
  E: ["D", "A"], // ← 추가된 역방향 에지
};

console.log("사이클 그래프 BFS A→E:", shortestPath(cyclicGraph, "A", "E"));

// 같은 그래프를 방향 그래프로 보고 위상 정렬 시도 (트러블슈팅 6의 topoDeterministic 재사용)
const directedCyclic = {
  A: ["B", "C"],
  B: ["D"],
  C: ["D"],
  D: ["E"],
  E: ["A"], // A→...→E→A 사이클
};
try {
  // §3-3의 topologicalSort 또는 트러블슈팅 6의 topoDeterministic 함수 재사용
  const order = topologicalSort(directedCyclic);
  console.log("위상 정렬:", order);
} catch (e) {
  console.log("위상 정렬 실패:", e.message);
}

예상 출력:

사이클 그래프 BFS A→E: 3       ← BFS는 visited 덕에 사이클에도 정답을 낸다
위상 정렬 실패: Cycle detected! Topological sort impossible.

출력이 다르면 의심할 것: (1) BFS에서 visited 처리가 “꺼낼 때”로 잘못 작성됨 → 트러블슈팅 3의 silent failure로 큐가 부풀음, (2) 위상 정렬 함수가 §3-3 본문의 Kahn 알고리즘이 아니라 사이클 감지가 빠진 단순 DFS면 무한 루프 — 종료 조건 확인.

다음 단계 과제: BFS의 사이클 내성과 위상 정렬의 사이클 거부가 어디서 갈리는지 직접 추적해라. shortestPath에 console.log("visit:", node)를 1줄 넣고 실행하면 E를 지나간 뒤 A로 다시 돌아가지 않음을 볼 수 있다 — visited 집합이 사이클을 끊는 지점이다. 같은 계측을 topologicalSort의 큐 처리 루프에도 넣으면 in-degree 0 노드가 결국 0개로 줄지 않고 멈춤을 확인할 수 있다 (이때 result.length !== Object.keys(inDegree).length가 사이클의 시그니처).

10. 한 줄 요약

BST는 정렬된 탐색을, Heap은 우선순위 접근을, Graph는 관계 탐색을 효율적으로 처리하며 세 자료구조 모두 실무의 DB 인덱싱, 작업 스케줄링, 의존성 관리에 직접 연결된다.

Sources:

Binary search tree - Wikipedia
Complexity of different operations in Binary tree, BST and AVL tree - GeeksforGeeks
DSA Binary Search Trees - W3Schools
DFS vs BFS: A Guide for Deep Understanding - PuppyGraph
Difference between BFS and DFS - GeeksforGeeks
Graph Traversal (Depth/Breadth First Search) - VisuAlgo
Binary Heaps and Priority Queues via JavaScript - DigitalOcean
Priority Queue Data Structure and Heaps in JavaScript - Adrian Mejia Blog
Completely Fair Scheduler - Wikipedia — Linux CFS가 Red-Black Tree를 선택한 이유와 O(log N) 삽입 / O(1) leftmost 조회 보장
Comparative Performance of the AVL Tree and Three Variants of the Red-Black Tree - arxiv 2406.05162 — 삽입/삭제 회전 횟수 정량 비교
Comparison between Adjacency List and Adjacency Matrix - GeeksforGeeks — 밀도 임계점과 표현 선택 기준