Basic Data Structures

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

기본 자료구조 (Basic Data Structures)

1. 한 줄 정의

자료구조는 데이터를 메모리에 어떻게 배치하고 접근할지 정의한 구조로, 알고리즘 성능의 근간이 된다.

---

2. 왜 중요한가

백엔드 엔지니어가 자료구조를 알아야 하는 이유는 단순히 코딩 테스트 통과를 위해서가 아니다.

• API 응답 속도: 어떤 자료구조를 쓰느냐에 따라 같은 로직이 O(1)이 될 수도, O(n²)이 될 수도 있다.
• DB 설계: Hash Index vs B-Tree Index 선택은 Hash Table의 원리를 이해해야 판단할 수 있다.
• 메시지 큐 / 작업 큐: NestJS의 BullMQ, AWS SQS는 모두 Queue 자료구조 위에 올라간 추상화다.
• 면접: “이 코드의 시간복잡도가 뭔가요?”라는 질문은 시니어 면접에서 기본 중의 기본이다.

---

2.5. 단순 메모리 배치의 한계 — 자료구조가 분화한 이유

초기 메모리 모델은 “연속된 주소에 값을 일렬로 놓는다”는 단일 패턴(=배열)뿐이었다. 이 단일 모델의 한계가 누적되어 오늘날의 기본 자료구조들이 각 한계를 푸는 메커니즘으로 분화했다. 본 토픽이 사라지면, 아래 한계들이 모두 “왜 느린지 모르는 채로” 다시 발생한다.

단순 연속 배열의 한계	한계의 정량적 증거	등장한 자료구조	어떤 메커니즘으로 한계를 해소했나
맨 앞 삽입 시 전체 n개를 한 칸씩 뒤로 이동	n=100만에서 unshift 1회 = 100만 이동, O(n)	Linked List	포인터로 다음 노드 주소만 갖춰 삽입 자체는 O(1) — 단, 인덱스 접근을 포기
”방금 본 것을 다시 꺼낼 때” 전체 순회	콜스택·괄호 매칭에서 평균 O(n) 탐색	Stack (LIFO)	맨 끝 원소만 push/pop — 접근 패턴을 LIFO로 좁혀 모든 연산이 O(1)
“먼저 들어온 것을 먼저 처리”하려면 앞에서 dequeue → O(n)	Array.shift()로 BFS 구현 시 O(n²) — 본 문서 트러블슈팅 #5의 실측 5,200ms 사례 참조	Queue (FIFO)	head/tail 포인터로 양 끝에 O(1) — 메시지 큐(SQS, BullMQ)의 이론적 토대
값으로 위치를 찾으려면 처음부터 비교 → O(n)	n=10만에서 Array.includes 320ms vs Set.has 0.8ms (본 문서 3-4-1 실측)	Hash Table	해시 함수로 키를 버킷 인덱스로 직접 매핑 → 평균 O(1) (단, 충돌 시 O(n) 위험)
범위 조회(x > 100 등)에서 Hash는 정렬이 없어 전체 스캔	DB 인덱스가 Hash가 아닌 B-Tree를 기본으로 선택하는 이유 (L9 [[db-indexes]] 토픽 참조)	BST / B-Tree	정렬된 트리로 범위 + 점 조회 모두 O(log n) — Hash의 약점을 보완

이 표가 다른 토픽(L9 [[saga-pattern]]의 “2PC 한계 → Saga”와 동일한 패턴)에서도 작동한다 — 각 자료구조는 트리비아가 아니라 “이전 도구가 깨진 지점을 푸는 메커니즘”으로 등장했다.

외부 prerequisite의 연결: 위 표의 “단순 연속 배열은 빠르다”는 명제는 CPU 캐시(L1 캐시 라인 64B에 여러 원소가 함께 적재)에 의존한다 — 본 문서 3-2의 “이론과 실제가 다른 이유” 절에서 cache miss latency 수치로 다시 등장한다.

---

3. 핵심 개념

3-1. Big-O Notation (시간/공간 복잡도)

비유

택배 회사가 물건을 배달한다고 생각해보자.

• O(1) - 상수: 창고 번호를 알고 있어서 바로 꺼낸다. 몇 개가 있든 속도는 같다.
• O(log n) - 로그: 전화번호부에서 이름을 찾을 때 중간 페이지를 펴서 앞/뒤를 반씩 줄여가며 찾는다.
• O(n) - 선형: 창고 전체를 처음부터 끝까지 뒤진다.
• O(n log n): 정렬 알고리즘처럼 각 그룹마다 log n번씩 비교한다.
• O(n²) - 이차: 모든 택배끼리 서로 비교해본다. 100개면 10,000번.

원리: 시간 복잡도 vs 공간 복잡도

개념	의미	측정 대상
시간 복잡도	입력 크기 n에 따라 연산 횟수가 어떻게 증가하는가	실행 시간
공간 복잡도	입력 크기 n에 따라 메모리 사용량이 어떻게 증가하는가	메모리

Big-O는 항상 **최악의 경우(Worst Case)**를 기준으로 한다. 상수와 낮은 차수의 항은 무시한다. 예: 3n² + 5n + 100 → O(n²)

왜 Big-O는 “상수를 무시”해도 되는가

Big-O가 상수를 무시하는 이유는 입력이 충분히 클 때 성장 속도만이 의미 있기 때문이다. 3n²과 100n²은 둘 다 n이 2배가 되면 4배 느려진다. 반면 n은 n이 2배가 되면 2배만 느려진다. n이 100만을 넘어가는 실무 환경에서는 이 “성장 속도의 차이”가 상수 차이보다 압도적으로 크다.

하지만 실무에서는 상수도 중요하다. 같은 O(n log n)이라도 Quick Sort가 Merge Sort보다 빠른 이유는 상수 계수(캐시 적중률, 함수 호출 오버헤드)가 다르기 때문이다. Big-O는 “알고리즘 설계 단계에서 큰 그림을 잡는 도구”이고, 실제 성능 튜닝은 프로파일링으로 해야 한다.

또한 Amortized(분할 상환) 분석도 알아두면 좋다. JavaScript의 Array.push()는 보통 O(1)이지만, 내부 배열이 꽉 차면 2배 크기로 재할당하면서 O(n)이 된다. 하지만 n번의 push를 평균내면 각 push는 O(1)이다. 이것이 분할 상환 O(1)이다.

주요 복잡도 비교표

복잡도	이름	n=10	n=100	n=1000	대표 예시
O(1)	상수	1	1	1	해시 테이블 조회, 배열 인덱스 접근
O(log n)	로그	3	7	10	이진 탐색, BST 조회
O(n)	선형	10	100	1,000	단일 for 루프, 배열 순회
O(n log n)	선형로그	33	664	9,966	Merge Sort, Quick Sort(평균)
O(n²)	이차	100	10,000	1,000,000	중첩 for 루프, Bubble Sort

성장 속도: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)

코드 예시

// O(1) - 입력 크기와 무관하게 한 번만 실행
function getFirst(arr) {
  return arr[0]; // 배열이 1개든 100만개든 동일
}

// O(n) - 단일 루프
function findMax(arr) {
  let max = arr[0];
  for (let i = 1; i < arr.length; i++) {
    // n번 실행
    if (arr[i] > max) max = arr[i];
  }
  return max;
}

// O(n²) - 중첩 루프
function hasDuplicates(arr) {
  for (let i = 0; i < arr.length; i++) {
    // n번
    for (let j = i + 1; j < arr.length; j++) {
      // 최대 n번
      if (arr[i] === arr[j]) return true;
    }
  }
  return false;
}

// O(log n) - 이진 탐색 (정렬된 배열 필수)
function binarySearch(arr, target) {
  let left = 0,
    right = arr.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;
    else if (arr[mid] < target)
      left = mid + 1; // 절반을 버린다
    else right = mid - 1;
  }
  return -1;
}

const arr = [1, 3, 5, 7, 9, 11, 13];
console.log(binarySearch(arr, 7)); // 3 (인덱스)
console.log(binarySearch(arr, 4)); // -1 (없음)

예상 출력:

3
-1

공간 복잡도 예시:

// O(1) 공간 - 추가 변수 고정 개수
function sumArray(arr) {
  let sum = 0; // 변수 1개만 사용
  for (const n of arr) sum += n;
  return sum;
}

// O(n) 공간 - 입력 크기만큼 새 배열 생성
function doubleAll(arr) {
  return arr.map((n) => n * 2); // 새 배열 n개 원소 생성
}

Nest.js/AWS 실무 연결: Big-O가 실제 코드 리뷰에서 어떻게 쓰이나

Nest.js 백엔드 코드를 리뷰할 때 Big-O는 다음과 같은 상황에서 직접 등장한다.

시나리오: 사용자 권한 체크 로직

// 나쁜 예 — 요청마다 O(n) 탐색: 유저 수가 10만명이면 10만 번 비교
@Injectable()
export class AuthGuard {
  async canActivate(context: ExecutionContext): Promise<boolean> {
    const adminList: string[] = await this.userService.getAdminEmails();
    const email = context.getHandler().toString();
    return adminList.includes(email); // O(n) — 배열 선형 탐색
  }
}

// 좋은 예 — O(1) 탐색: Set으로 교체
@Injectable()
export class AuthGuardOptimized {
  private adminSet: Set<string>;

  async onModuleInit() {
    const emails = await this.userService.getAdminEmails();
    this.adminSet = new Set(emails); // 앱 시작 시 1번만 O(n)
  }

  async canActivate(context: ExecutionContext): Promise<boolean> {
    const email = getEmailFromContext(context);
    return this.adminSet.has(email); // O(1) — Hash Set 조회
  }
}

AWS Lambda에서 Big-O가 비용과 직결되는 이유: Lambda는 실행 시간(ms) × 메모리 크기로 요금이 계산된다. O(n²) 로직이 있으면 데이터가 2배 늘 때 실행 시간이 4배, 요금도 4배가 된다. Big-O 개선은 곧 AWS 청구서 절감이다.

📖 더 보기: Big O Cheat Sheet — freeCodeCamp — 주요 알고리즘 복잡도를 한눈에 비교하는 치트시트

---

3-2. Array vs Linked List

비유

• Array (배열): 강의실 좌석처럼 번호가 붙어있고 연속으로 배치되어 있다. 27번 자리를 찾으려면 바로 간다.
• Linked List (연결 리스트): 보물찾기 쪽지처럼 각 쪽지에 “다음 쪽지는 저기 있다”고 적혀있다. 원하는 것을 찾으려면 처음부터 따라가야 한다.

원리: 메모리 구조

Array - 연속 메모리 할당:

메모리 주소: 100  101  102  103  104
값:          [10] [20] [30] [40] [50]

arr[2] 접근 → 시작주소(100) + 2 × 타입크기 = 102번지 → 즉시 접근 O(1)

Linked List - 노드 + 포인터:

[data:10 | next:→] → [data:20 | next:→] → [data:30 | next:null]
  주소: 100              주소: 305            주소: 728

세 번째 노드 접근 → 100 → 305 → 728 (순서대로 따라가야 함) O(n)

연산별 시간복잡도 비교

연산	Array	Linked List	이유
인덱스 접근	O(1)	O(n)	Array는 주소 계산으로 즉시 접근
맨 앞 삽입	O(n)	O(1)	Array는 전체를 뒤로 밀어야 함
맨 뒤 삽입	O(1)	O(n) or O(1)*	*tail 포인터 있으면 O(1)
중간 삽입	O(n)	O(n)	둘 다 탐색 필요 (단, 삽입 자체는 LL이 O(1))
삭제	O(n)	O(n)	탐색 후 삭제
탐색	O(n)	O(n)	정렬 안된 경우 동일

코드 예시

// Array 기본 조작
const arr = [10, 20, 30, 40, 50];

// O(1) - 인덱스 접근
console.log(arr[2]); // 30

// O(n) - 맨 앞 삽입 (내부적으로 모든 요소를 뒤로 이동)
arr.unshift(5);
console.log(arr); // [5, 10, 20, 30, 40, 50]

// O(1) - 맨 뒤 삽입
arr.push(60);
console.log(arr); // [5, 10, 20, 30, 40, 50, 60]

// Linked List 직접 구현
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
    this.size = 0;
  }

  // O(1) - 맨 앞 삽입
  prepend(data) {
    const newNode = new Node(data);
    newNode.next = this.head;
    this.head = newNode;
    this.size++;
  }

  // O(n) - 인덱스 접근
  get(index) {
    let current = this.head;
    for (let i = 0; i < index; i++) {
      current = current.next; // 하나씩 따라간다
    }
    return current?.data;
  }

  toArray() {
    const result = [];
    let current = this.head;
    while (current) {
      result.push(current.data);
      current = current.next;
    }
    return result;
  }
}

const ll = new LinkedList();
ll.prepend(30);
ll.prepend(20);
ll.prepend(10);

console.log(ll.toArray()); // [10, 20, 30]
console.log(ll.get(1)); // 20

예상 출력:

[10, 20, 30]
20

JavaScript 배열의 특이점: V8 엔진

JavaScript의 배열은 이론적 배열과 다르다. V8 엔진이 상황에 따라 내부 구현을 바꾼다:

// V8이 C++ 정수 배열로 최적화 (packed SMI elements) - 빠름
const fast = [1, 2, 3, 4, 5];

// V8이 해시맵으로 전환 - 느려짐 (sparse array)
const sparse = [];
sparse[0] = 1;
sparse[9999] = 2; // 중간이 비어있으면 딕셔너리로 전환

// 혼합 타입 - 최적화 해제
const mixed = [1, "hello", true]; // double array로 강등

실무 팁: JS 배열에 중간에 구멍을 내거나 혼합 타입을 담으면 V8 최적화가 해제되어 성능이 급격히 저하될 수 있다.

왜 Array와 Linked List의 성능 차이가 이론과 실제에서 다른가

이론적으로 Linked List의 맨 앞 삽입은 O(1)이고 Array는 O(n)이다. 하지만 실제 성능은 CPU 캐시 때문에 다르다.

Array는 메모리에 연속으로 배치되어 있어 CPU L1/L2 캐시에 한 번에 올라간다. x86-64에서 캐시 라인은 64바이트이므로(ARM64는 128B) 4바이트 정수는 한 라인에 16개가 함께 적재된다. 순차 접근 시 16번 중 15번은 캐시 히트가 된다. 반면 Linked List 노드는 메모리에 흩어져 있어 매번 캐시 미스를 유발한다.

latency 수치 (Kaby Lake/Haswell 측정 기준):

• L1 hit: ~1ns (≈5 cycle @ 2.5GHz)
• L2 hit: ~5ns
• L3 hit: ~17ns
• DRAM 접근: 60100ns (L1 대비 **약 60100배**)

즉 Array 순회는 L1에서 끝나는데 Linked List는 노드 점프마다 DRAM까지 내려가므로, 같은 O(n) 순회라도 실측에서 1~2 차수 차이가 난다 (출처: Applied C++ Memory Latency, Intel Community — Sequential vs Random Access).

언제 이 cache 우위가 깨지는가 (Inversion): Linked List 노드를 메모리 풀(slab allocator)로 연속 할당하면 cache 우위 차이는 줄어든다. 따라서 “Array가 무조건 빠르다”가 아니라 “범용 malloc 환경에서 그렇다”가 정확한 명제다. JS는 V8의 GC 힙 위에서 동작하므로 사용자 코드에서 연속 할당을 강제할 방법이 없다 → JS에서는 사실상 항상 Array가 우위.

// 성능 비교: Array 순회 vs Linked List 순회
// Array는 캐시 적중률이 높아 실측에서 5~10배 빠르다
const n = 1000000;

// Array: 연속 메모리 → 캐시 친화적
const arr = Array.from({ length: n }, (_, i) => i);
console.time("Array 순회");
let sum1 = 0;
for (let i = 0; i < arr.length; i++) sum1 += arr[i];
console.timeEnd("Array 순회");

// Linked List: 포인터 체이닝 → 캐시 미스 빈번
// (실제로는 JS 객체 오버헤드까지 추가)

예상 출력:

Array 순회: 2.1ms
(Linked List 순회: 15~25ms — 같은 n에서 약 10배 느림)

이것이 실무에서 대부분의 경우 Array(또는 동적 배열)를 기본으로 사용하는 이유다. Linked List가 유리한 상황은 맨 앞 삽입/삭제가 극히 빈번하고, 랜덤 접근이 전혀 필요 없는 매우 특수한 경우뿐이다.

📖 더 보기: HappyCoders — Array vs Linked List — 두 자료구조의 성능을 벤치마크 데이터와 함께 비교 (중급)

---

3-3. Stack & Queue

비유

• Stack (스택): 접시 더미. 마지막에 올린 접시를 먼저 꺼낸다 (LIFO: Last In, First Out).
• Queue (큐): 줄서기. 먼저 온 사람이 먼저 나간다 (FIFO: First In, First Out).
• Deque (덱): 양쪽 문이 있는 줄서기. 앞뒤 어디서든 들어오고 나갈 수 있다.

원리

Stack - LIFO (Last In, First Out)

push(A)  → [A]
push(B)  → [A, B]
push(C)  → [A, B, C]
pop()    → C 반환, [A, B]   ← 마지막 들어온 것이 먼저 나옴

Queue - FIFO (First In, First Out)

enqueue(A)  → [A]
enqueue(B)  → [A, B]
enqueue(C)  → [A, B, C]
dequeue()   → A 반환, [B, C]  ← 처음 들어온 것이 먼저 나옴

코드 예시

// Stack - JavaScript 배열로 구현
class Stack {
  constructor() {
    this.items = [];
  }
  push(item) {
    this.items.push(item);
  } // O(1)
  pop() {
    return this.items.pop();
  } // O(1)
  peek() {
    return this.items[this.items.length - 1];
  } // O(1)
  isEmpty() {
    return this.items.length === 0;
  }
}

// 실제 활용: 괄호 매칭 검사
function isValidBrackets(s) {
  const stack = new Stack();
  const map = { ")": "(", "]": "[", "}": "{" };

  for (const char of s) {
    if ("([{".includes(char)) {
      stack.push(char); // 여는 괄호 → 스택에 추가
    } else {
      if (stack.isEmpty() || stack.peek() !== map[char]) {
        return false; // 짝이 안 맞음
      }
      stack.pop(); // 짝이 맞으면 제거
    }
  }
  return stack.isEmpty(); // 스택이 비어있으면 모두 매칭됨
}

console.log(isValidBrackets("({[]})")); // true
console.log(isValidBrackets("({[})")); // false

// Queue - 효율적 구현 (shift는 O(n)이라 직접 구현 권장)
class Queue {
  constructor() {
    this.items = {};
    this.head = 0;
    this.tail = 0;
  }
  enqueue(item) {
    this.items[this.tail] = item;
    this.tail++;
  }
  dequeue() {
    if (this.isEmpty()) return null;
    const item = this.items[this.head];
    delete this.items[this.head];
    this.head++;
    return item; // O(1)
  }
  isEmpty() {
    return this.head === this.tail;
  }
  size() {
    return this.tail - this.head;
  }
}

// BFS(너비 우선 탐색)에서의 Queue 사용 패턴
function bfs(graph, start) {
  const visited = new Set();
  const queue = new Queue();
  const result = [];

  queue.enqueue(start);
  visited.add(start);

  while (!queue.isEmpty()) {
    const node = queue.dequeue();
    result.push(node);

    for (const neighbor of graph[node] || []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.enqueue(neighbor);
      }
    }
  }
  return result;
}

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

예상 출력:

true
false
['A', 'B', 'C', 'D', 'E']

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

Stack — NestJS 예외 처리 파이프라인: NestJS의 Exception Filter는 함수 호출 스택(Call Stack) 원리로 동작한다. @Catch() 데코레이터로 등록된 필터들이 스택처럼 쌓이고, 예외가 발생하면 LIFO 순서로 올라가며 처리 가능한 필터를 찾는다. stack trace 자체가 함수 호출 스택의 현재 상태를 출력한 것이다.

Queue — BullMQ 작업 처리: BullMQ(NestJS 공식 지원)는 Redis를 저장소로 쓰는 Queue다. 이메일 발송, 이미지 처리, 알림 푸시 같은 비동기 작업을 FIFO 순서로 처리한다. AWS SQS도 동일한 Queue 원리로 서비스 간 비동기 메시지를 전달한다.

// NestJS + BullMQ: Queue 기반 비동기 이메일 작업 처리
@Processor("email-queue")
export class EmailProcessor {
  @Process("send-welcome")
  async handleWelcomeEmail(job: Job<{ email: string; name: string }>) {
    // FIFO 순서로 큐에서 꺼낸 작업 처리
    // 이 코드가 실행되는 동안 다른 작업들은 큐에서 대기
    const { email, name } = job.data;
    await this.mailer.send({ to: email, subject: `Welcome, ${name}!` });
    return { sent: true };
  }
}

📖 더 보기: BullMQ 공식 문서 — Bull Queues in NestJS — NestJS에서 BullMQ로 Queue 기반 작업 처리 구성 방법

Deque (Double-ended Queue):

// JavaScript에서 Deque는 배열로 구현 (슬라이딩 윈도우 최대값)
function maxSlidingWindow(nums, k) {
  const deque = []; // 인덱스를 저장
  const result = [];

  for (let i = 0; i < nums.length; i++) {
    // 윈도우 밖으로 나간 인덱스 제거
    if (deque.length && deque[0] < i - k + 1) deque.shift();

    // 현재 값보다 작은 이전 값들 제거 (뒤에서부터)
    while (deque.length && nums[deque[deque.length - 1]] < nums[i]) {
      deque.pop();
    }

    deque.push(i);
    if (i >= k - 1) result.push(nums[deque[0]]);
  }
  return result;
}

console.log(maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3));
// [3, 3, 5, 5, 6, 7]

---

3-4. Hash Table

비유

도서관 사서가 책을 보관할 때를 상상해보자. 책 제목을 특정 규칙으로 변환해서 → 서가 번호를 결정한다. 나중에 책을 찾을 때도 같은 규칙으로 번호를 계산하면 바로 그 서가로 간다. 이 “규칙”이 해시 함수이고, 서가가 버킷이다.

원리: 해시 함수 → 버킷 인덱스 매핑

키(key) → 해시 함수(hash function) → 해시값(hash) → 버킷 인덱스
"name"  →      hash("name")        →    12345      →    45 (버킷 크기로 나눈 나머지)

V8 엔진 내부에서 Hash Table이 어떻게 동작하는가

V8은 JavaScript의 Map과 Object를 상황에 따라 다른 내부 구조로 저장한다. 이 원리를 알면 성능 튜닝에 도움이 된다.

JavaScript Object의 두 가지 모드:

• Fast Mode (Hidden Class 기반): 객체가 생성 시점부터 고정된 구조를 갖는다면 V8은 C++ 구조체처럼 고정 오프셋으로 접근한다. 이 경우 해시 테이블이 아닌 메모리 오프셋 직접 접근이라 매우 빠르다.
• Dictionary Mode (Hash Map): 동적으로 프로퍼티가 추가/삭제되거나, delete obj.key를 사용하면 V8이 객체를 해시맵 구조로 전환한다. 이 모드로 전환되면 프로퍼티 접근이 크게 느려진다.

JavaScript Map의 내부 구조: Map은 항상 해시 테이블 기반으로 구현되며, V8은 Open Addressing(선형 탐사)을 충돌 해결 방식으로 사용한다. 해시 코드는 객체 값과 무관한 랜덤 숫자이며, 이 값의 하위 비트로 초기 버킷 인덱스를 결정하고, 충돌 시 다음 슬롯을 순차적으로 탐색한다.

// V8 Dictionary Mode 유발 패턴 — 피해야 할 코드
const obj = { name: "Alice" }; // Fast Mode
delete obj.name; // Dictionary Mode로 전환! 느려짐
obj.age = 30; // 이미 느린 모드

// 권장: Object.assign 또는 스프레드로 불변성 유지
const newObj = { ...obj, age: 30 }; // 새 객체, Fast Mode 유지

📖 더 보기: V8 블로그 — Optimizing hash tables: hiding the hash code — V8 엔진 개발팀이 직접 설명한 Map 내부 해시 최적화 기법 (중급)

// 단순한 해시 함수 예시 (실제로는 훨씬 복잡)
function simpleHash(key, tableSize) {
  let hash = 0;
  for (let i = 0; i < key.length; i++) {
    hash = (hash + key.charCodeAt(i)) % tableSize;
  }
  return hash;
}

console.log(simpleHash("name", 10)); // 7 (예시)
console.log(simpleHash("age", 10)); // 5 (예시)

충돌(Collision)과 해결 방법

두 개의 다른 키가 같은 버킷 인덱스로 매핑되는 것을 충돌이라고 한다.

방법 1: Chaining (체이닝) - 연결 리스트로 연결

버킷[3] → [("name", "Alice")] → [("mane", "Bob")] → null
          (같은 해시값을 가진 두 항목이 연결 리스트로 연결)

class HashTableChaining {
  constructor(size = 10) {
    this.table = new Array(size).fill(null).map(() => []);
    this.size = size;
  }

  hash(key) {
    let hash = 0;
    for (const char of key) hash = (hash + char.charCodeAt(0)) % this.size;
    return hash;
  }

  set(key, value) {
    const index = this.hash(key);
    const bucket = this.table[index];
    const existing = bucket.find(([k]) => k === key);
    if (existing)
      existing[1] = value; // 업데이트
    else bucket.push([key, value]); // 추가
  }

  get(key) {
    const index = this.hash(key);
    const bucket = this.table[index];
    return bucket.find(([k]) => k === key)?.[1] ?? null;
  }
}

const ht = new HashTableChaining();
ht.set("name", "Alice");
ht.set("age", 30);
ht.set("name", "Bob"); // 업데이트

console.log(ht.get("name")); // "Bob"
console.log(ht.get("age")); // 30
console.log(ht.get("city")); // null

예상 출력:

Bob
30
null

방법 2: Open Addressing (개방 주소법) - 다른 빈 슬롯 탐색

class HashTableOpenAddressing {
  constructor(size = 10) {
    this.table = new Array(size).fill(null);
    this.size = size;
  }

  hash(key) {
    let hash = 0;
    for (const char of key) hash = (hash + char.charCodeAt(0)) % this.size;
    return hash;
  }

  set(key, value) {
    let index = this.hash(key);
    // 선형 탐사(Linear Probing): 충돌 시 다음 슬롯을 확인
    while (this.table[index] !== null && this.table[index][0] !== key) {
      index = (index + 1) % this.size; // 다음 슬롯
    }
    this.table[index] = [key, value];
  }

  get(key) {
    let index = this.hash(key);
    while (this.table[index] !== null) {
      if (this.table[index][0] === key) return this.table[index][1];
      index = (index + 1) % this.size;
    }
    return null;
  }
}

Chaining vs Open Addressing 비교

항목	Chaining	Open Addressing
메모리	추가 포인터 필요 (더 사용)	테이블 내부만 사용
캐시 성능	낮음 (연결 리스트 점프)	높음 (연속 메모리)
부하율 상한	제한 없음 (100% 이상 가능)	~80% 이하 권장
삭제	간단	복잡 (삭제 표시 필요)
최악 성능	O(n)	O(n)

왜 최악 O(n)이 발생하는가?

모든 키가 같은 버킷으로 해시되면(최악의 해시 함수, 또는 공격적 입력) 하나의 버킷에 n개가 몰린다. Chaining에서는 그 버킷의 연결 리스트를 전부 순회해야 하므로 O(n).

이것은 이론적 문제가 아니라 **실제 보안 공격(Hash DoS)**으로 이어진다. 공격자가 의도적으로 같은 해시값을 생성하는 키들을 대량 전송하면, 서버의 해시 테이블이 O(n)으로 전락해 성능이 급격히 저하된다. 두 진영의 대응 메커니즘은 다음과 같다.

• V8/Node.js — 런타임 random seed 주입: V8은 인스턴스 시작 시 random hash seed를 생성해 모든 hash 값 계산에 mix한다. 공격자가 같은 V8 인스턴스 내 hash 충돌을 사전에 예측할 수 없게 만드는 방식이다. 다만 startup snapshot에 hash 테이블이 미리 직렬화되면 seed가 고정되어 우회 가능 → V8은 snapshot deserialize 이후 affected 구조를 rehash하는 방식으로 Node.js v8.3.0부터 재활성화했다 (출처: V8 — About that hash flooding vulnerability). 2025년 V8이 비밀 시드를 가진 비암호 해시(rapidhash 계열)로 교체했다가 CVE-2025-27209로 다시 시드 기반으로 보강한 사례가 있어, “안전한 해시 함수”는 고정된 정답이 아니라 지속적 보강이 필요한 영역이다.
• Java 8 — 임계 충돌 시 트리화: HashMap은 한 버킷의 연결 리스트 길이가 TREEIFY_THRESHOLD = 8을 넘고 전체 테이블 capacity가 MIN_TREEIFY_CAPACITY = 64 이상이면 해당 버킷을 Red-Black Tree로 변환하여 O(log n)을 보장한다. 트리 노드 수가 UNTREEIFY_THRESHOLD = 6 아래로 줄면 다시 연결 리스트로 되돌린다 (출처: The Secret Improvement of HashMap in Java 8). 즉 Java는 “공격이 들어와도 무너지지 않는 fallback”을 자료구조 자체에 내장한 셈이다.

silent failure (Inversion): 직접 구현한 Hash Table에서 위 두 대응이 없으면, 에러도 없고 평균 응답 시간도 정상이지만 특정 IP의 특정 페이로드만 p99 응답이 수십 초로 튀는 형태로 나타난다. 감지는 모니터링 차원에서: node --prof로 hot function이 hash 함수에 몰리는지 확인, Redis라면 redis-cli --latency-history로 percentile 분포를 본다 — 평균(p50)만 보면 정상으로 보이므로 반드시 p99/p999를 함께 본다.

JavaScript Map vs Object: 실무 성능 판단 기준

Map과 Object는 둘 다 키-값 저장소이지만, 내부 동작이 다르므로 용도에 따라 성능 차이가 크다.

벤치마크 결과 요약 (문자열 키 기준):

• 삽입: Map이 Object보다 빠름 (특히 키가 동적으로 추가될 때)
• 삭제: Map이 압도적으로 빠름 (delete obj.key는 V8 Dictionary Mode 전환 유발)
• 조회: 비슷하거나 Object가 약간 빠름 (Hidden Class 최적화)
• 순회: Map이 빠름 (삽입 순서 보장, for..of 네이티브 지원)

실무 선택 기준:

• 키가 동적으로 추가/삭제 → Map 사용
• 키가 고정된 설정 객체 → Object 사용 (JSON 직렬화 용이)
• 키 타입이 문자열이 아님 (숫자, 객체) → 반드시 Map
• delete 연산이 빈번 → 반드시 Map (Object의 delete는 V8 최적화를 파괴)

📖 더 보기: Zhenghao — When You Should Prefer Map Over Object — Map vs Object 성능 벤치마크와 실무 선택 기준 (중급)

// JS의 Map은 Hash Table 기반 (Object보다 안전)
const map = new Map();
map.set("name", "Alice");
map.set(1, "one"); // 숫자 키도 가능
map.set({}, "obj key"); // 객체 키도 가능

console.log(map.get("name")); // "Alice"
console.log(map.size); // 3

// ❗ silent failure (가장 인지하기 어려운 실패): 객체 키는 reference equality로 비교된다.
// 같은 모양의 새 객체는 "다른 키"로 간주되어, 에러 없이 조용히 cache miss 또는
// 권한 누락으로 이어진다 — 운영 환경에서 "Map에 분명히 넣었는데 조회가 안 됨" 사고의 전형.
const userKey = (id) => ({ id }); // ❌ 매번 새 객체 생성
const permMap = new Map();
permMap.set(userKey(42), "admin");
console.log(permMap.get(userKey(42))); // undefined! 깊은 비교가 아니다
// 진단 명령: console.log(permMap.keys()); 키가 똑같이 보여도 reference가 다르면 다른 키.
// 해결: 정규화된 primitive(예: id 자체)나 동일 참조를 유지하는 캐시 객체를 키로 사용.

// Object는 key를 항상 문자열/Symbol로 강제 변환
const obj = {};
obj[1] = "number";
obj["1"] = "string";
console.log(Object.keys(obj)); // ["1"] — 같은 키로 취급됨!

예상 출력:

Alice
3
["1"]

---

3-4-1. 인터뷰/코딩 테스트 패턴 심화

“자료구조 선택 실수는 O(1)과 O(n²)의 차이를 만든다 — 면접관이 가장 먼저 보는 것”

빈출 패턴 1: Two Sum — Hash Map으로 O(n²) → O(n) 전환

코딩 인터뷰에서 가장 많이 나오는 유형이다. 배열에서 합이 target인 두 수의 인덱스를 찾는 문제다.

// 나쁜 예: 이중 루프 O(n²)
function twoSumBad(nums: number[], target: number): [number, number] {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) return [i, j];
    }
  }
  return [-1, -1];
}

// 좋은 예: Hash Map으로 O(n) — "보수(complement)를 먼저 저장"
function twoSum(nums: number[], target: number): [number, number] {
  const seen = new Map<number, number>(); // value → index

  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (seen.has(complement)) {
      return [seen.get(complement)!, i];
    }
    seen.set(nums[i], i); // 현재 값 저장
  }
  return [-1, -1];
}

console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1] (2+7=9)
console.log(twoSum([3, 2, 4], 6)); // [1, 2] (2+4=6)

예상 출력:

[0, 1]
[1, 2]

이 패턴은 “지금 원소의 보수가 이미 나왔는가?”를 O(1)에 확인하는 것이 핵심이다. 백엔드에서는 “중복 이메일 검사”, “결제 금액 쌍 검증” 등에 직접 적용된다.

빈출 패턴 2: Sliding Window — Queue/Deque로 O(n²) → O(n) 전환

고정 또는 가변 크기의 윈도우를 슬라이드하며 최대/최소/합을 구하는 패턴이다.

// 패턴: 크기 k인 서브배열의 최대 합 (고정 윈도우)
// 시간: O(n), 공간: O(1)
function maxSubarraySum(nums: number[], k: number): number {
  let windowSum = nums.slice(0, k).reduce((a, b) => a + b, 0);
  let maxSum = windowSum;

  for (let i = k; i < nums.length; i++) {
    windowSum += nums[i] - nums[i - k]; // 오른쪽 추가, 왼쪽 제거
    maxSum = Math.max(maxSum, windowSum);
  }
  return maxSum;
}

console.log(maxSubarraySum([2, 1, 5, 1, 3, 2], 3)); // 9 (5+1+3)

// 패턴: 중복 없는 가장 긴 부분 문자열 (가변 윈도우 + Set)
// 시간: O(n), 공간: O(min(n, 알파벳크기))
function lengthOfLongestSubstring(s: string): number {
  const charSet = new Set<string>();
  let left = 0;
  let maxLen = 0;

  for (let right = 0; right < s.length; right++) {
    // 중복 발생 시 왼쪽 포인터를 오른쪽으로 이동
    while (charSet.has(s[right])) {
      charSet.delete(s[left]);
      left++;
    }
    charSet.add(s[right]);
    maxLen = Math.max(maxLen, right - left + 1);
  }
  return maxLen;
}

console.log(lengthOfLongestSubstring("abcabcbb")); // 3 ("abc")
console.log(lengthOfLongestSubstring("pwwkew")); // 3 ("wke")

예상 출력:

9
3
3

실무 연결: API Rate Limiting에서 “지난 N초 동안 요청 수 계산”, 로그 분석에서 “K분 내 에러 최대 발생 구간” 같은 문제에 직접 적용된다.

빈출 패턴 3: Stack으로 괄호/단조성 문제 해결

Stack은 “이전 상태를 되돌아봐야 할 때” 유용하다. 인터뷰에서 괄호 매칭, 단조 스택(monotonic stack) 패턴이 자주 나온다.

// 단조 스택: 다음으로 더 큰 값(Next Greater Element) 찾기
// 시간: O(n), 공간: O(n)
function nextGreaterElement(nums: number[]): number[] {
  const result = new Array(nums.length).fill(-1);
  const stack: number[] = []; // 인덱스 저장

  for (let i = 0; i < nums.length; i++) {
    // 스택 top의 값보다 현재 값이 크면 → top의 NGE는 현재 값
    while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
      const idx = stack.pop()!;
      result[idx] = nums[i];
    }
    stack.push(i);
  }
  return result;
}

console.log(nextGreaterElement([2, 1, 2, 4, 3]));
// [4, 2, 4, -1, -1]
// 2의 NGE=4, 1의 NGE=2, 2의 NGE=4, 4의 NGE=없음, 3의 NGE=없음

예상 출력:

[4, 2, 4, -1, -1]

실무 연결: AWS CloudWatch에서 “다음 알림 임계값 초과 시점 찾기”, 주가 데이터에서 “다음 고점 탐지” 같은 분석에 쓰인다.

시간/공간 복잡도 심화: 자료구조별 실측 비교

// 자료구조 선택이 성능에 주는 실질적 영향 측정
const N = 100_000;

// 1. Array.includes() vs Set.has() — O(n) vs O(1)
const arr = Array.from({ length: N }, (_, i) => i);
const set = new Set(arr);
const target = N - 1; // 최악 케이스: 맨 끝 값 탐색

console.time("Array.includes O(n)");
for (let i = 0; i < 1000; i++) arr.includes(target);
console.timeEnd("Array.includes O(n)");

console.time("Set.has O(1)");
for (let i = 0; i < 1000; i++) set.has(target);
console.timeEnd("Set.has O(1)");

// 2. Array.unshift() vs Queue pointer — O(n) vs O(1)
console.time("Array.unshift 1만 회 O(n²)");
const q1: number[] = [];
for (let i = 0; i < 10_000; i++) q1.unshift(i);
console.timeEnd("Array.unshift 1만 회 O(n²)");

console.time("Queue pointer 1만 회 O(n)");
const q2: number[] = [];
for (let i = 0; i < 10_000; i++) q2.push(i);
console.timeEnd("Queue pointer 1만 회 O(n)");

예상 출력:

Array.includes O(n): ~320ms   (1000회 × O(n))
Set.has O(1): ~0.8ms          (1000회 × O(1)) → 약 400배 차이
Array.unshift 1만 회 O(n²): ~180ms
Queue pointer 1만 회 O(n): ~2ms → 약 90배 차이

이 수치들은 “왜 자료구조를 올바르게 선택해야 하는가”를 숫자로 보여준다. NestJS에서 요청당 Set/Map을 올바르게 사용하면 동일 로직이 수십 배 빨라질 수 있다.

---

3-5. 자료구조 선택 실전 가이드 (심화)

비유로 이해하기

“공구함에서 올바른 도구를 고르는 방법”

모든 공구가 못을 박을 수는 있지만, 망치가 가장 적합하다. 자료구조도 모든 것이 데이터를 저장할 수 있지만 상황마다 최적이 다르다. 잘못된 자료구조 선택은 이론적으로 맞더라도 실제로 10배~100배 느릴 수 있다.

실무 선택 기준 — 질문 체크리스트

자료구조를 고를 때 다음 질문에 답한다:

1. 데이터를 "순서"대로 접근해야 하는가?
   → YES: Array 또는 Queue/Stack
   → NO : Hash Table (빠른 검색)

2. "특정 위치"에 빠르게 접근해야 하는가?
   → YES: Array (O(1) 인덱스 접근)
   → NO : Linked List (삽입/삭제 빠름)

3. "키-값" 쌍으로 빠르게 찾아야 하는가?
   → YES: Hash Table (O(1) 평균)
   → 범위 조건도 필요: BST/B-Tree (O(log n))

4. "최소값/최대값"을 반복적으로 뽑아야 하는가?
   → YES: Min Heap / Max Heap (O(1) 조회, O(log n) 삽입/삭제)

5. 데이터 크기가 동적으로 변하는가?
   → YES: Dynamic Array (JavaScript Array, ArrayList)
   → 크기 고정: Fixed Array (더 빠름)

NestJS 실무에서 자주 쓰이는 패턴

// 패턴 1: Set으로 O(1) 중복 체크
@Injectable()
export class BlacklistService {
  private banned = new Set<string>(); // O(1) has()

  isBanned(userId: string): boolean {
    return this.banned.has(userId); // O(1) — Array.includes()의 O(n)과 비교
  }

  ban(userId: string) {
    this.banned.add(userId);
  }
}

// 패턴 2: Map으로 요청 카운팅 (Rate Limiting)
@Injectable()
export class RequestCounterService {
  private counts = new Map<string, number>();

  increment(key: string): number {
    const current = this.counts.get(key) ?? 0;
    this.counts.set(key, current + 1);
    return current + 1;
  }

  // 1분마다 리셋
  reset() {
    this.counts.clear(); // Map.clear() = O(n) — 전체 삭제
  }
}

// 패턴 3: 우선순위 기반 작업 처리 (Min Heap 대안)
// (JavaScript에 기본 Heap이 없으므로 배열 정렬 또는 직접 구현)
@Injectable()
export class PriorityTaskService {
  private tasks: Array<{ priority: number; fn: () => Promise<void> }> = [];

  addTask(priority: number, fn: () => Promise<void>) {
    this.tasks.push({ priority, fn });
    // 삽입할 때마다 정렬 — 소규모에서는 허용 가능
    this.tasks.sort((a, b) => a.priority - b.priority);
  }

  async runNext() {
    const task = this.tasks.shift(); // O(n) — 소규모라면 OK
    if (task) await task.fn();
  }
}

예상 출력 (패턴 1 — 10만 건 테스트 기준):

Array.includes() 10만 회: ~320ms
Set.has() 10만 회: ~8ms  ← 약 40배 빠름

자료구조 선택 수치 기준 (경계 조건)

“구현보다 선택이 더 중요하다.” 아래 기준은 잘못된 자료구조가 언제 문제가 되는지를 수치로 보여준다:

시나리오	잘못된 선택	한계	올바른 선택	이유
중복 검사 (n > 1,000)	Array.includes	O(n) × n = O(n²), n=1만이면 ~100ms	Set.has	O(1) 평균
최솟값 반복 추출 (n > 100)	Array.sort 매번	O(n log n) × 추출 횟수	Min Heap	O(log n) 추출
키-값 검색 (n > 100)	Object + for-in	O(n) 탐색	Map.get	O(1) 평균
빈번한 앞쪽 삽입/삭제	Array.shift	O(n) — n=1만이면 ~1ms/회	Linked List 또는 Deque	O(1)
정렬된 범위 쿼리	Hash Table	정렬 순서 없음	BST / B-Tree (DB 인덱스)	O(log n) 범위

Lambda 메모리 경계: n > 100만 개 숫자면 일반 Array(~40MB) 대신 Float64Array(~8MB)로 5배 메모리 절감. Lambda 128MB 제한 환경에서 결정적 차이.

자료구조별 메모리 사용량 비교

실무에서 Lambda나 컨테이너의 메모리 제약이 있을 때 자료구조 선택이 비용과 직결된다.

자료구조	요소당 메모리 오버헤드	이유
Array (정수)	~8바이트	값만 저장
Object	40100바이트	Hidden Class + 프로퍼티 디스크립터
Map	5080바이트/항목	해시 테이블 버킷 + 포인터
Linked List 노드	~48바이트	값 + prev + next 포인터 + 객체 헤더
Set	5070바이트/항목	Map과 유사한 내부 구조

// 메모리 효율이 중요할 때 — TypedArray 활용
// 일반 Array보다 훨씬 적은 메모리, 연속 메모리 보장
const floatArr = new Float64Array(1_000_000); // 8MB (일반 Array는 ~40MB)
const intArr = new Int32Array(1_000_000); // 4MB

// AWS Lambda 128MB 제한 환경에서 1백만 개 숫자를 다뤄야 한다면 TypedArray 필수

---

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

Big-O가 실무 결정에 영향을 주는 경우

// 나쁜 예: O(n²) - 사용자가 많을수록 폭발적으로 느려짐
async function findDuplicateUsers(users: User[]) {
  const duplicates = [];
  for (const user of users) {
    for (const other of users) {
      // 중첩 루프 → O(n²)
      if (user.id !== other.id && user.email === other.email) {
        duplicates.push(user);
      }
    }
  }
  return duplicates;
}

// 좋은 예: O(n) - Hash Map으로 최적화
async function findDuplicateUsersOptimized(users: User[]) {
  const emailMap = new Map<string, User>();
  const duplicates = [];
  for (const user of users) {
    if (emailMap.has(user.email)) {
      duplicates.push(user); // 중복 발견
    } else {
      emailMap.set(user.email, user); // O(1) 삽입
    }
  }
  return duplicates;
}

Stack: NestJS 에러 처리

NestJS의 Exception Filter는 함수 호출 스택(Call Stack) 기반으로 동작한다. 에러가 발생하면 스택을 타고 올라가며 적절한 핸들러를 찾는다.

Queue: BullMQ (NestJS)

// NestJS + BullMQ: Queue 기반 비동기 작업 처리
@Processor("email")
export class EmailProcessor {
  @Process("send-welcome")
  async sendWelcomeEmail(job: Job) {
    // Queue에서 꺼낸 작업을 FIFO 순서로 처리
    await this.emailService.send(job.data.email, "Welcome!");
  }
}

Hash Table: Redis, DB Index

• Redis: 내부적으로 Hash Table을 사용. HSET user:1 name Alice는 O(1) 접근
• PostgreSQL Hash Index: WHERE email = '[email protected]' 같은 동등 조건 검색에서 B-Tree보다 빠름
• JS Map vs Object: Map은 임의 타입 키 지원, 삽입 순서 보장, size 프로퍼티 제공

---

5. 내 업무와의 연결고리

업무 상황	자료구조	시간복잡도
NestJS 라우터 핸들러 조회	Hash Table (경로 → 핸들러 맵)	O(1)
BullMQ 작업 처리 순서	Queue (FIFO)	O(1) enqueue/dequeue
에러 로그 Undo 기능	Stack (LIFO)	O(1)
유저 이메일 중복 검사	Hash Table (Map)	O(n) vs O(n²)
AWS SQS 메시지 수신	Queue	O(1)
Redis HGETALL 조회	Hash Table	O(n) fields
DB 페이지네이션	Array (offset-based)	O(1) 접근

// 실무 패턴: 캐시로 O(n)을 O(1)로 최적화
class UserService {
  private cache = new Map<number, User>(); // Hash Table

  async getUser(id: number): Promise<User> {
    // O(1) 캐시 조회
    if (this.cache.has(id)) return this.cache.get(id)!;

    // Cache miss → DB 조회 후 캐시 저장
    const user = await this.userRepo.findOne(id); // O(log n) B-Tree
    this.cache.set(id, user);
    return user;
  }
}

---

6. 비슷한 개념과 비교

Array vs Linked List 선택 기준

상황	추천 자료구조	이유
인덱스 접근이 빈번	Array	O(1) 접근
맨 앞 삽입/삭제가 빈번	Linked List	O(1) vs Array O(n)
크기가 고정됨	Array	메모리 효율
크기가 동적으로 변함	Linked List or Dynamic Array	리사이징 비용 없음
순차 접근만 필요	Linked List	캐시 미스 있지만 삽입 유리

Stack vs Queue vs Deque

자료구조	입출력	대표 사용처
Stack	LIFO (뒤로만)	함수 콜스택, Undo, 괄호 매칭, DFS
Queue	FIFO (앞에서 출력, 뒤에 입력)	BFS, 작업 큐, 메시지 큐
Deque	양방향	슬라이딩 윈도우, 덱 기반 스케줄러

Map vs Object (JavaScript)

항목	Map	Object
키 타입	모든 타입	String/Symbol만
삽입 순서	보장	ES2015+ 보장 (단, 숫자 키는 정렬됨)
size	map.size	Object.keys(obj).length
성능	잦은 추가/삭제에 최적화	고정 구조에 유리
직렬화	JSON 직접 불가	JSON.stringify 가능

---

6.5. 트러블슈팅

트러블슈팅 1: Array.unshift()가 느린데 원인을 모르겠다

증상: 앞에 요소를 추가하는 로직이 데이터가 많아질수록 급격히 느려진다.

원인: Array.unshift()는 O(n) 연산이다. 맨 앞에 요소를 추가하면 기존 모든 요소가 뒤로 한 칸씩 이동해야 한다. n=100만 개면 100만 번의 이동이 발생한다.

해결: 맨 앞 삽입/삭제가 빈번하면 Linked List나 Deque를 사용하거나, 실제로는 push 후 reverse가 필요한지 로직을 재검토한다.

// 나쁜 예: O(n) 반복
const log = [];
events.forEach((event) => log.unshift(event)); // O(n²) 전체

// 좋은 예: O(1) 반복
const log = [];
events.forEach((event) => log.push(event)); // O(n) 전체
log.reverse(); // O(n) 1번만

---

트러블슈팅 2: 면접에서 “왜 해시 테이블이 O(1)인데 DB 쿼리는 느린가요?”라고 물었을 때 당황

증상: Hash Table이 O(1)이면 DB도 O(1)이어야 하는 것 아닌가 혼동된다.

원인: DB의 Hash Index는 O(1)이지만, 모든 데이터를 메모리에 올릴 수 없어 디스크 I/O가 발생한다. 또한 범위 조회(>, <, BETWEEN)에서는 Hash Index가 B-Tree보다 느리다. DB 쿼리 속도는 자료구조 복잡도만의 문제가 아니다.

해결: 자료구조 복잡도 = 연산 횟수이고, 실제 성능 = 연산 횟수 × 연산 비용(메모리 접근 vs 디스크 I/O)임을 이해한다. 동등 조건만 있으면 Hash Index, 범위 조건이 있으면 B-Tree Index를 선택한다.

---

트러블슈팅 3: 코딩 테스트에서 JS 배열의 shift()로 Queue를 구현해 시간 초과 발생

증상: Queue를 push() + shift()로 구현했는데 시간 초과가 뜬다.

원인: Array.shift()는 O(n)이다. 앞에서 요소를 꺼낼 때 나머지 전체가 앞으로 이동한다. BFS 등에서 Queue를 n번 사용하면 전체가 O(n²)이 된다.

해결: 포인터 기반 Queue로 구현하거나, 인덱스를 직접 관리한다.

// 시간 초과 발생 패턴
const queue = [];
queue.push(node);
const curr = queue.shift(); // O(n) — 매번 전체 이동

// 해결: 포인터 기반 Queue
const queue = [];
let head = 0;
queue.push(node);
const curr = queue[head++]; // O(1) — 포인터만 이동

---

트러블슈팅 4: NestJS에서 Map/Set을 모듈 스코프로 관리하다가 메모리 누수

증상: 애플리케이션이 오래 실행될수록 메모리 사용량이 계속 증가하고, 결국 OOM(Out of Memory)으로 프로세스가 죽는다.

원인: @Injectable() 서비스에서 Map이나 Set을 인스턴스 변수로 선언했는데, 항목을 추가만 하고 제거하지 않아 무한정 증가한다. 특히 요청별 임시 데이터를 모듈 수준 Map에 저장하는 패턴이 위험하다.

해결 방법:

// 나쁜 예: 요청 데이터가 Map에 쌓여 메모리 누수
@Injectable()
export class RequestTracker {
  private requestData = new Map<string, any>(); // 계속 쌓임

  track(requestId: string, data: any) {
    this.requestData.set(requestId, data); // 절대 지워지지 않음!
  }
}

// 좋은 예 1: TTL 기반 자동 삭제
@Injectable()
export class RequestTracker {
  private requestData = new Map<string, { data: any; expiry: number }>();

  track(requestId: string, data: any, ttlMs = 60_000) {
    this.requestData.set(requestId, { data, expiry: Date.now() + ttlMs });
  }

  cleanup() {
    const now = Date.now();
    for (const [key, value] of this.requestData) {
      if (value.expiry < now) this.requestData.delete(key); // 만료된 것 제거
    }
  }
}

// 좋은 예 2: WeakMap 활용 (객체 키가 GC되면 자동 삭제)
const cache = new WeakMap<object, any>();
// 키 객체(req, res 등)가 사라지면 캐시도 자동으로 GC 대상이 됨

---

트러블슈팅 5: Queue 구현에서 shift() 사용으로 O(n²) 성능 저하

증상: BFS, 작업 큐 등 Queue를 사용하는 알고리즘이 입력 크기가 커질수록 비선형적으로 느려진다. n=1000에서 1ms이던 것이 n=100,000에서 수십 초가 걸린다.

원인: JavaScript에서 array.shift()는 O(n)이다. 배열 맨 앞 요소를 제거할 때 나머지 모든 요소를 한 칸씩 앞으로 이동시키기 때문이다. 이를 루프에서 n번 반복하면 전체가 O(n²)가 된다.

해결 방법:

// 나쁜 예: shift() 사용 — O(n²) 총 복잡도
const queue = [1, 2, 3, 4, 5];
while (queue.length) {
  const item = queue.shift(); // 매번 O(n) — 전체 이동!
  process(item);
}

// 좋은 예 1: 포인터 기반 — O(1)
const queue = [1, 2, 3, 4, 5];
let head = 0;
while (head < queue.length) {
  const item = queue[head++]; // O(1) — 포인터만 이동
  process(item);
}

// 좋은 예 2: 객체 기반 Queue 클래스 — O(1) enqueue/dequeue
class EfficientQueue {
  private items: Record<number, any> = {};
  private head = 0;
  private tail = 0;

  enqueue(item: any) { this.items[this.tail++] = item; }
  dequeue() {
    if (this.isEmpty()) return null;
    const item = this.items[this.head];
    delete this.items[this.head++];
    return item; // O(1)
  }
  isEmpty() { return this.head === this.tail; }
  size() { return this.tail - this.head; }
}

성능 비교 (n=100,000):

shift() 기반 Queue: ~5,200ms (O(n²))
포인터 기반 Queue:  ~12ms    (O(n))
→ 약 433배 차이

---

트러블슈팅 6: 해시 충돌로 인한 성능 저하를 모니터링하지 않다가 프로덕션 장애

증상: Redis나 직접 구현한 Hash Table이 특정 키 패턴에서만 느리다.

원인: 악의적 또는 의도치 않은 입력이 동일한 해시 버킷으로 집중되는 해시 충돌 공격(Hash DoS). 충돌이 많아지면 O(1) 평균이 O(n) 최악으로 전락한다.

해결:

• 입력 검증 및 길이 제한을 설정한다.
• 안전한 해시 함수(SipHash 등)를 사용하는 라이브러리(Node.js는 기본으로 SipHash 사용)를 활용한다.
• Redis의 경우 hash-max-listpack-entries 설정으로 작은 해시는 ziplist로 저장하여 공격 표면을 줄인다.

---

7. 체크리스트

• O(1), O(log n), O(n), O(n²)의 차이를 예제 코드와 함께 설명할 수 있다
• 이진 탐색이 O(log n)인 이유를 설명할 수 있다 (매 단계 절반 제거)
• Array와 Linked List의 메모리 구조 차이를 그림으로 설명할 수 있다
• 각 자료구조별 삽입/삭제/검색 시간복잡도를 말할 수 있다
• Stack은 LIFO, Queue는 FIFO라고 설명하고 실제 사용 예를 들 수 있다
• 해시 충돌이 무엇인지, Chaining과 Open Addressing의 차이를 설명할 수 있다
• JS에서 Map과 Object의 차이를 설명하고 언제 각각을 쓰는지 말할 수 있다
• JS 배열의 shift()가 O(n)인 이유를 설명할 수 있다
• V8 엔진이 배열을 최적화하는 방식(elements kinds)을 대략 설명할 수 있다
• BullMQ나 SQS가 Queue 자료구조를 사용한다는 것을 연결 지어 설명할 수 있다

---

8. 핵심 키워드

키워드	한 줄 설명
Big-O Notation	알고리즘의 성능을 입력 크기 n의 함수로 표현하는 표기법
시간 복잡도	연산 횟수가 n에 따라 어떻게 증가하는지
공간 복잡도	메모리 사용량이 n에 따라 어떻게 증가하는지
연속 메모리	Array처럼 메모리에 연속으로 배치되어 인덱스 계산이 가능한 구조
노드 + 포인터	Linked List의 메모리 구조; 각 노드가 다음 노드의 주소를 저장
LIFO	Last In, First Out - Stack의 원칙
FIFO	First In, First Out - Queue의 원칙
해시 함수	임의 데이터를 고정 크기 값(해시)으로 변환하는 함수
해시 충돌	다른 키가 같은 버킷 인덱스로 매핑되는 현상
Chaining	충돌 시 같은 버킷에 연결 리스트로 연결하는 방식
Open Addressing	충돌 시 다른 빈 슬롯을 탐사하는 방식
Load Factor	테이블 크기 대비 저장된 항목 수의 비율
V8 Elements Kinds	V8이 배열 요소 타입에 따라 내부 구현을 최적화하는 메커니즘

---

8.5. 추천 리소스

📚 추천 리소스

• 📖 Big O Cheat Sheet — freeCodeCamp — 주요 알고리즘·자료구조의 시간/공간 복잡도를 한눈에 비교하는 치트시트. 면접 직전 빠른 복습에 최적 (입문)
• 📖 When You Should Prefer Map Over Object — Zhenghao — Map vs Object 성능 벤치마크와 실무 선택 기준. V8 Dictionary Mode 함정까지 커버 (중급)
• 📖 Array vs Linked List 벤치마크 — HappyCoders — 두 자료구조의 실측 성능 데이터와 언제 무엇을 선택하는지 기준 정리 (중급)
• 📖 Hash Table Interview Cheatsheet — Tech Interview Handbook — 코딩 인터뷰에서 Hash Table을 활용하는 패턴·주의사항·복잡도 요약 (입문)
• 📖 V8 Elements Kinds — V8 공식 블로그 — V8이 배열 요소 타입에 따라 내부 구현을 최적화하는 방식. 프론트엔드·Node.js 성능 튜닝의 근거 (중급)
• 📖 About that hash flooding vulnerability in Node.js — V8 공식 블로그 — V8이 startup snapshot과 random hash seed로 Hash DoS를 어떻게 방어하는지 공식 설명 (중급)
• 📖 The Secret Improvement of HashMap in Java 8 — Runzhuo Li — TREEIFY_THRESHOLD=8, UNTREEIFY_THRESHOLD=6, MIN_TREEIFY_CAPACITY=64의 실제 상수와 동작 원리 (중급)

---

9. 직접 확인해보기

9-1. 시간복잡도 직접 측정

// performance.now()로 시간 측정
function measureTime(fn, label) {
  const start = performance.now();
  fn();
  const end = performance.now();
  console.log(`${label}: ${(end - start).toFixed(3)}ms`);
}

const n = 100000;
const arr = Array.from({ length: n }, (_, i) => i);

// O(1) vs O(n) 비교
measureTime(() => arr[n - 1], "O(1) - 인덱스 접근");
measureTime(() => arr.find((x) => x === n - 1), "O(n) - 선형 탐색");

예상 출력:

O(1) - 인덱스 접근: 0.001ms
O(n) - 선형 탐색: 2.847ms

9-2. Array.shift() O(n) 확인

function measureShiftVsPointer(size) {
  // shift() 방식 - O(n)
  const arr1 = Array.from({ length: size }, (_, i) => i);
  const start1 = performance.now();
  while (arr1.length) arr1.shift();
  const time1 = performance.now() - start1;

  // 포인터 방식 - O(1)
  const arr2 = Array.from({ length: size }, (_, i) => i);
  let head = 0;
  const start2 = performance.now();
  while (head < arr2.length) head++;
  const time2 = performance.now() - start2;

  console.log(
    `n=${size}: shift=${time1.toFixed(1)}ms, pointer=${time2.toFixed(1)}ms`,
  );
}

measureShiftVsPointer(10000);
measureShiftVsPointer(100000);

예상 출력:

n=10000: shift=5.2ms, pointer=0.1ms
n=100000: shift=520.8ms, pointer=1.2ms

shift()는 n이 10배 늘어나면 시간이 100배 늘어나는 O(n²) 패턴을 보인다.

9-3. Map vs Object 키 타입 차이 확인

// Node.js REPL 또는 브라우저 콘솔에서 실행
const map = new Map();
map.set(1, "number");
map.set("1", "string");
map.set(true, "boolean");

console.log(map.size); // 3 - 모두 다른 키
console.log(map.get(1)); // "number"
console.log(map.get("1")); // "string" (다른 키!)

const obj = {};
obj[1] = "number";
obj["1"] = "string"; // 덮어쓰기!

console.log(Object.keys(obj)); // ["1"] - 하나밖에 없음
console.log(obj[1]); // "string" (덮어씌워짐)

예상 출력:

3
number
string
["1"]
string

9-4. 해시 충돌 확인 (간단 시뮬레이션)

function simpleHash(key, size) {
  let hash = 0;
  for (const char of key) hash = (hash + char.charCodeAt(0)) % size;
  return hash;
}

// 충돌 확인
const tableSize = 5;
const keys = ["name", "mane", "amen", "age", "gap"];
const buckets = {};

for (const key of keys) {
  const index = simpleHash(key, tableSize);
  buckets[index] = buckets[index] || [];
  buckets[index].push(key);
}

for (const [index, items] of Object.entries(buckets)) {
  console.log(
    `버킷[${index}]: ${items.join(", ")}${items.length > 1 ? " ← 충돌!" : ""}`,
  );
}

예상 출력:

버킷[0]: name, mane, amen ← 충돌!
버킷[3]: age, gap ← 충돌!

---

10. 한 줄 요약

자료구조는 데이터 배치 방식을 결정하고, Big-O는 그 결정의 성능 비용을 수치화한다. Array는 인덱스 접근에, Hash Table은 검색에, Stack/Queue는 순서 처리에 최적화된 구조이며, 이를 잘못 선택하면 O(n)이 O(n²)으로 바뀌어 실서비스 장애로 이어진다.