Sorting & Searching

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

정렬과 탐색 알고리즘 (Sorting & Searching)

1. 한 줄 정의

정렬 알고리즘은 데이터를 일정한 순서로 재배치하는 방법이며, 탐색 알고리즘은 정렬된 데이터나 특정 자료구조에서 원하는 값을 효율적으로 찾는 방법이다.

2. 왜 중요한가

성능의 핵심: 대부분의 실무 문제에서 데이터를 정렬하고 찾는 작업이 전체 처리 시간의 상당 부분을 차지한다. 잘못된 알고리즘 선택은 수천 배의 성능 차이를 만든다.
면접의 단골 주제: 시스템 설계와 코딩 테스트에서 “왜 이 정렬을 선택했나?”, “이 탐색의 시간복잡도는?” 같은 질문이 자주 나온다.
실무 직결: JavaScript의 Array.sort()가 내부적으로 어떻게 동작하는지, Redis가 왜 LRU 캐시를 쓰는지, DB 인덱스가 왜 Binary Search를 활용하는지 — 모두 이 개념에서 출발한다.
자료구조와 알고리즘의 교차점: Trie, Doubly Linked List, HashMap 등의 자료구조가 실제로 어떻게 쓰이는지를 구체적으로 이해할 수 있다.

2.5. 선행 기술의 한계 → 이 토픽의 등장

정렬·탐색 알고리즘 군은 “데이터가 커질수록 단순한 방법이 SLA를 깨뜨린다”는 정량적 한계에서 진화해 왔다. 100만 행에서 평균 50만 번 비교(선형 탐색) vs 정렬된 데이터에서 약 20번 비교(Binary Search) — 약 25,000배 차이가 모든 DB 인덱스의 존재 이유다. 이 절은 frontmatter lineage_oneliner(“선형 탐색(O(n)) 비효율 → 정렬(O(n log n))+Binary Search(O(log n)) 달성”)를 한계의 정량적 증거와 해결 메커니즘으로 풀어놓은 것이다.

① 선형 탐색 → Binary Search: 정렬되지 않은 배열의 탐색은 O(n). 한 번 정렬(O(n log n)) 비용을 지불하면 이후 모든 탐색이 O(log n). 단, Binary Search는 약 9년간 Java JDK java.util.Arrays.binarySearch에 overflow 버그가 숨어 있었고, Bentley의 Programming Pearls 원본 코드도 약 20년간 같은 버그를 안고 있었다 — 2006년 Joshua Bloch가 보고 (Google Research — Nearly All Binary Searches and Mergesorts are Broken). 이 silent failure가 §3-2와 §6.5 Case 2의 진단·복구로 이어진다.

② Quick Sort(Hoare, 1961) → IntroSort/TimSort: 평균 O(n log n)이지만 최악 O(n²). McIlroy의 “antiqsort” 적대적 입력 생성기는 BSD qsort() 2^16 입력을 무작위 대비 약 1,000배 느리게 만든다 — 단순 성능 저하가 아니라 알고리즘 복잡도 공격(DoS) (matslina — Algorithmic complexity attacks and libc qsort()). 이 한계가 IntroSort(C++ std::sort: QuickSort + HeapSort 폴백)와 TimSort(Tim Peters, 2002 — Python list.sort; Python 3.11부터 더 견고한 머지 정책의 Powersort로 교체)의 등장 이유다 (Wikipedia — Timsort).

③ 메모리 한계 → LRU 캐시: 모든 데이터를 메모리에 올릴 수 없을 때 어떤 키를 버릴지 결정해야 한다. 단순 FIFO는 “여전히 자주 쓰이는 항목”을 함부로 버려 hit rate를 떨어뜨린다. LRU는 “마지막 접근 시점”을 기준으로 삼아 이 한계를 해소한다 — 단 정확한 LRU는 모든 키에 timestamp 추적이 필요해 메모리가 곱빼기로 든다. Redis는 maxmemory-samples 샘플링으로 근사하는데, 샘플 수와 정확도가 직접 trade-off다 (§6.5 Case 4).

이 토픽이 사라지면 무엇이 깨지는가: DB 인덱스(B-Tree = 다진 Binary Search), 검색엔진 자동완성(Trie + Aho-Corasick), CDN/브라우저 캐시(LRU), 추천 시스템 Top-K 랭킹(Heap 기반 정렬) — 응답시간 SLA가 있는 거의 모든 시스템이 무너진다.

3. 핵심 개념

3-1. 정렬 알고리즘 비교

Quick Sort (퀵 소트)

비유: 책상 위에 카드가 흩어져 있다. 임의로 카드 한 장(피벗)을 고른다. 그 카드보다 작은 건 왼쪽, 큰 건 오른쪽으로 나눈다. 이제 왼쪽 더미와 오른쪽 더미에서 다시 같은 작업을 반복한다. 더 이상 나눌 수 없을 때 모두 합치면 정렬 완료다.

원리:

피벗(Pivot) 을 선택한다 (첫 번째, 마지막, 중앙, 또는 랜덤 선택)
피벗보다 작은 요소는 왼쪽, 큰 요소는 오른쪽으로 파티션(Partition) 한다
각 파티션에 대해 재귀적으로 같은 과정을 반복한다 (분할 정복)
핵심: 피벗 선택이 성능을 좌우한다 — 항상 최솟값/최댓값을 피벗으로 고르면 O(n²)이 된다

왜 Quick Sort는 “평균적으로” 가장 빠른가:

Quick Sort가 이론적으로 Merge Sort와 같은 O(n log n)인데도 실전에서 더 빠른 이유는 캐시 지역성(cache locality) 때문이다. Quick Sort는 배열 요소를 제자리에서(in-place) 교환하므로 CPU 캐시에 올라간 데이터를 반복 사용한다. 반면 Merge Sort는 병합 시 새 배열을 만들어야 해서 캐시 미스가 빈번하다. 이 차이가 상수 계수를 2~3배 벌려서 실측 성능에서 Quick Sort가 우위를 차지한다.

시간/공간 복잡도:

평균: O(n log n) — 피벗이 중앙에 가까울 때
최악: O(n²) — 이미 정렬된 배열에서 첫 번째 요소를 피벗으로 고를 때
공간: O(log n) — 재귀 호출 스택 (in-place 정렬)

// Quick Sort 구현
function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left >= right) return arr;

  const pivotIndex = partition(arr, left, right);
  quickSort(arr, left, pivotIndex - 1);
  quickSort(arr, pivotIndex + 1, right);
  return arr;
}

function partition(arr, left, right) {
  // 마지막 요소를 피벗으로 선택
  const pivot = arr[right];
  let i = left - 1;

  for (let j = left; j < right; j++) {
    if (arr[j] <= pivot) {
      i++;
      // 교환 (swap)
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  // 피벗을 제자리에 위치
  [arr[i + 1], arr[right]] = [arr[right], arr[i + 1]];
  return i + 1;
}

const arr = [64, 34, 25, 12, 22, 11, 90];
console.log(quickSort([...arr]));
// 예상 출력: [11, 12, 22, 25, 34, 64, 90]

// 최악의 케이스 시연 (이미 정렬된 배열 + 마지막 피벗)
const sorted = [1, 2, 3, 4, 5];
// 피벗이 항상 최솟값 → O(n²) 동작
console.log(quickSort([...sorted]));
// 예상 출력: [1, 2, 3, 4, 5] (결과는 맞지만 n²번 비교)

언제 깨지는가 — Algorithmic Complexity Attack (보안 silent failure): Quick Sort의 O(n²)는 단순 성능 저하가 아니라 DoS 공격 벡터다. McIlroy의 “antiqsort” 적대적 입력은 결정론적 피벗을 쓰는 모든 qsort 구현을 quadratic으로 끌어내릴 수 있고, BSD qsort() 2^16 원소에서 무작위 입력 대비 약 1,000배 느려진다 (matslina — Algorithmic complexity attacks and libc qsort()). 같은 원리가 다른 자료구조에도 적용된다 — Hash collision DoS(Perl/PHP/Java가 모두 패치한 취약점)는 hash 함수가 결정론적이면 공격자가 동일 버킷에 몰리는 키를 만들어 O(1)을 O(n)으로 무너뜨리는 동일 패턴이다. 진단(Node.js 예시):

const t0 = process.hrtime.bigint();
arr.sort((a, b) => a - b);
const ms = Number(process.hrtime.bigint() - t0) / 1e6;
if (ms > expectedMs * 10) {
  // 10배 임계 — adversarial input 의심
  console.warn("sort latency spike", { n: arr.length, ms });
}
// 예상 출력 (정상): sort latency spike 미발생
// 공격 입력 시: sort latency spike { n: 65536, ms: 1200 }

회복 절차: ① 사용자 입력에 의존한 정렬 키는 randomized pivot이나 IntroSort 계열을 보장하는 표준 라이브러리(JS Array.sort() = TimSort, C++ std::sort = IntroSort, Rust slice::sort_unstable = pdqsort)를 사용하고 ② 자체 구현이 필요하다면 Math.floor((left + right) * Math.random()) 같은 무작위 피벗을 적용한다. ③ 모니터링은 §9 직접 확인해보기 패턴으로 정렬 latency 분포를 RUM 데이터에 누적해 outlier 알림을 건다.

Merge Sort (병합 정렬)

비유: 카드 더미를 반씩 계속 나눠서 1장짜리 더미들로 만든다. 1장짜리는 이미 정렬된 것이나 다름없다. 이제 두 더미를 비교하면서 순서대로 병합한다. 이 과정을 계속 반복하면 전체가 정렬된다.

원리:

배열을 반으로 나눈다 (분할)
각 절반을 재귀적으로 정렬한다
두 정렬된 절반을 병합(Merge) 한다 — 두 포인터를 사용해 작은 쪽부터 새 배열에 담는다
핵심: 항상 O(n log n)이 보장된다 — 피벗 선택이 없으므로 최악의 케이스가 없다

시간/공간 복잡도:

항상: O(n log n) — 최선/평균/최악 모두 동일
공간: O(n) — 병합 시 임시 배열이 필요하다 (단점)
안정 정렬(Stable): 같은 값의 원소들이 원래 순서를 유지한다

// Merge Sort 구현 (상세 구현은 algorithm-paradigms.md의 D&C 섹션 참조)
function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0,
    j = 0;

  // 두 배열을 비교하면서 작은 쪽을 result에 추가
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }

  // 남은 요소 추가
  return result.concat(left.slice(i)).concat(right.slice(j));
}

const arr = [64, 34, 25, 12, 22, 11, 90];
console.log(mergeSort(arr));
// 예상 출력: [11, 12, 22, 25, 34, 64, 90]

// 안정 정렬 확인 — 같은 값의 순서가 유지됨
const people = [
  { name: "Alice", age: 25 },
  { name: "Bob", age: 25 },
  { name: "Charlie", age: 20 },
];
const sorted = mergeSort(people).sort ? people : mergeSort(people);
// Alice와 Bob은 나이가 같지만 Alice가 먼저 유지됨 (stable)

Heap Sort (힙 정렬)

비유: 최대 힙(Max-Heap)은 “가장 큰 값이 항상 맨 위(루트)에 있는 완전 이진 트리”다. 루트에서 최댓값을 꺼내 배열 뒤에 놓고, 힙을 재정렬(heapify)한다. 이 과정을 반복하면 내림차순으로 정렬된다.

원리:

배열을 Max-Heap으로 변환한다 (heapify, O(n))
루트(최댓값)를 배열 마지막으로 보낸다
힙 크기를 1 줄이고, 루트부터 heapify를 다시 한다
모든 요소가 제자리를 찾을 때까지 반복한다

시간/공간 복잡도:

항상: O(n log n) — 최선/평균/최악 모두 동일
공간: O(1) — in-place 정렬 (추가 메모리 불필요)
불안정 정렬(Unstable): 같은 값의 원래 순서가 바뀔 수 있다

// Heap Sort 구현
function heapSort(arr) {
  const n = arr.length;

  // Max-Heap 구성 (뒤에서부터 heapify)
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }

  // 루트를 하나씩 꺼내서 배열 뒤로 보냄
  for (let i = n - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]]; // 루트(최댓값)를 맨 뒤로
    heapify(arr, i, 0); // 줄어든 힙에서 다시 heapify
  }

  return arr;
}

function heapify(arr, n, i) {
  let largest = i;
  const left = 2 * i + 1;
  const right = 2 * i + 2;

  if (left < n && arr[left] > arr[largest]) largest = left;
  if (right < n && arr[right] > arr[largest]) largest = right;

  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    heapify(arr, n, largest); // 변경된 하위 트리도 heapify
  }
}

const arr = [64, 34, 25, 12, 22, 11, 90];
console.log(heapSort([...arr]));
// 예상 출력: [11, 12, 22, 25, 34, 64, 90]

정렬 알고리즘 비교표

알고리즘	최선	평균	최악	공간	안정성	특징
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)	불안정	실전에서 가장 빠름
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	안정	최악 케이스 없음
Heap Sort	O(n log n)	O(n log n)	O(n log n)	O(1)	불안정	in-place + O(n log n) 보장
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	안정	교육용
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	안정	거의 정렬된 데이터에 유리

Nest.js/AWS 실무 연결: 정렬 알고리즘이 실제 코드에 어떻게 적용되나

DB ORDER BY vs 인메모리 정렬: Nest.js + TypeORM에서 정렬은 가능하면 DB에 위임해야 한다. DB는 인덱스가 있을 경우 정렬을 O(log n)으로 처리하지만, 인메모리로 가져와서 Array.sort()를 쓰면 O(n log n) + 네트워크 비용이 추가된다.

언제 깨지는가 — 정량 임계값: Node.js 단일 프로세스가 인메모리 정렬로 버틸 수 있는 한계는 대략 수십만 행 × 수 KB row 수준이다. 이 한계를 넘기면 GC 압박과 동시 요청 큐잉이 같이 무너진다. 구체적으로:

인메모리 정렬 위험 시그널: 단일 응답이 ~100,000행 × 200B (≈ 20MB)을 넘기면 V8 heap (기본 ~1.5GB)에서 정렬 사본 + JSON 직렬화 사본이 곱빼기로 소비된다. Lambda 1.5GB 메모리 환경이면 5~10 동시 요청부터 OOM 위험.
DB측 spill 임계값: PostgreSQL의 정렬은 work_mem (기본 4MB) 안에서만 인메모리, 초과 시 tempdir로 spill한다. row 1KB 가정 시 약 4,000행 이상 정렬은 디스크 I/O 발생. EXPLAIN (ANALYZE, BUFFERS)에서 Sort Method: external merge Disk: NkB 표시가 나오면 work_mem을 늘리거나 인덱스 정렬로 회피.
트래픽 RPS 관점: 공유 풀 환경에서 RDS work_mem을 무작정 올리면 모든 connection이 그만큼 쓸 수 있어 메모리 폭증. 100 connection × 64MB = 6.4GB. 인덱스 기반 ORDER BY로 spill 자체를 피하는 것이 안전.

출처: PostgreSQL work_mem 기본값 4MB는 PostgreSQL 공식 문서 — Resource Consumption. Sort spill 동작 일반 원리는 These Rows Are Made for Sorting (DuckDB ICDE 2023) 참조 — 대용량 정렬은 외부 정렬(external merge sort) 알고리즘이 내부적으로 사용된다.

// 나쁜 예: 전체를 가져와서 JS에서 정렬 → O(n log n) + 불필요한 데이터 전송
const users = await this.userRepo.find(); // 전체 조회
const sorted = users.sort((a, b) => b.createdAt - a.createdAt);

// 좋은 예: DB에서 정렬 → 인덱스 있으면 O(log n)
const users = await this.userRepo.find({
  order: { createdAt: "DESC" }, // DB의 B-Tree 인덱스 활용
  take: 20, // 페이지네이션까지 DB에서
});

AWS Lambda 배치 처리에서 정렬: Lambda로 SQS 메시지를 배치 처리할 때, 메시지 순서 보장이 필요하다면 수신한 메시지를 timestamp 기준으로 정렬 후 처리한다. 이때 Array.sort()(TimSort)는 이미 거의 정렬된 SQS FIFO 메시지에서 최선 O(n)으로 동작한다.

📖 더 보기: V8 블로그 — Getting things sorted in V8 — V8이 TimSort를 도입한 배경과 안정 정렬 보장 과정 (중급)

JavaScript `Array.sort()`는 TimSort를 사용한다

TimSort = Merge Sort + Insertion Sort 의 하이브리드 알고리즘이다. V8 v7.0(Chrome 70)부터 도입되었으며, Python에서 먼저 사용되어 검증된 알고리즘이다.

작은 배열(보통 32~64개 이하): Insertion Sort 사용 — 작은 배열에서는 캐시 효율이 높아 실전에서 더 빠름
큰 배열: Merge Sort 방식으로 정렬된 “런(run)“들을 병합
시간복잡도: 최선 O(n), 평균/최악 O(n log n)
안정 정렬: 같은 값의 원래 순서가 보장된다

왜 TimSort가 실전에서 가장 빠른가: TimSort의 핵심은 이미 부분적으로 정렬된 데이터(natural runs)를 감지하는 것이다. 실무 데이터는 완전히 무작위인 경우가 드물다. 타임스탬프 기반 로그, ID 순으로 삽입된 DB 레코드 등은 이미 거의 정렬되어 있다. TimSort는 이런 “런”을 찾아서 그대로 활용하므로, 거의 정렬된 데이터에서 O(n)에 가까운 성능을 보인다. V8 공식 벤치마크에서 “DownDown” 케이스(두 개의 역순 정렬 시퀀스로 이루어진 배열)에서 기존 QuickSort 대비 17배 속도 향상이 확인되었다 (V8 — Getting things sorted in V8). 단, 완전 무작위 PACKED_SMI_ELEMENTS 마이크로벤치에선 QuickSort가 더 빠른 케이스도 있다 — V8은 “거의 모든 실무 분포에서 우위”라는 trade-off로 TimSort를 선택했다. 이 결정은 입력 분포(단조 vs 무작위 vs 부분정렬)가 알고리즘 선택을 좌우한다는 일반 원리를 보여준다 — 같은 원리가 DB 옵티마이저의 정렬 연산자 선택, Spark의 sort vs sort-merge join 선택에도 적용된다.

📖 더 보기: V8 블로그 — Getting things sorted in V8 — V8 팀이 QuickSort에서 TimSort로 전환한 이유와 벤치마크 (중급)

// JavaScript sort의 동작 — 비교 함수 없이 쓰면 문자열 정렬!
const nums = [10, 9, 2, 1, 100];
console.log(nums.sort());
// 예상 출력: [1, 10, 100, 2, 9] ← 문자열 사전순 정렬 (주의!)

console.log(nums.sort((a, b) => a - b));
// 예상 출력: [1, 2, 9, 10, 100] ← 올바른 숫자 정렬

// 안정 정렬 확인
const students = [
  { name: "Alice", grade: "A" },
  { name: "Bob", grade: "A" },
  { name: "Charlie", grade: "B" },
];
students.sort((a, b) => a.grade.localeCompare(b.grade));
console.log(students.map((s) => s.name));
// 예상 출력: ['Alice', 'Bob', 'Charlie'] — A등급 내에서 Alice → Bob 순서 유지됨

3-2. Binary Search (이진 탐색)

비유: 두꺼운 영어 사전에서 “robot”이라는 단어를 찾는다. 처음부터 찾지 않고, 중간 페이지를 펼쳐 r보다 앞인지 뒤인지 확인한다. 뒤라면 앞 절반은 버리고 뒷절반의 중간을 다시 펼친다. 이 과정을 반복하면 절반씩 줄어들면서 빠르게 찾을 수 있다.

원리:

전제 조건: 배열이 정렬되어 있어야 한다
탐색 범위를 절반씩 줄여나가기 때문에 O(log n)이 된다
n = 1,000,000 이라도 최대 20번만 비교하면 된다 (log₂(1,000,000) ≈ 20)
탐색 범위: [left, right) — 왼쪽은 닫히고(포함), 오른쪽은 열린(미포함) 구간으로 관리하면 구현이 일관성 있다

왜 Binary Search가 O(log n)인지 직관적으로 이해하기: 1,000,000개의 정렬된 데이터에서 값을 찾을 때, 한 번 비교할 때마다 탐색 범위가 절반으로 줄어든다. 1,000,000 → 500,000 → 250,000 → … → 1. “몇 번 반으로 나누면 1이 되는가?”가 곧 log₂(n)이다. 이것이 DB 인덱스(B-Tree)가 수억 건의 데이터에서도 밀리초 단위로 검색할 수 있는 근본 원리다.

실무에서 Binary Search가 직접 쓰이는 곳: DB의 WHERE id = 123 쿼리는 B-Tree 인덱스에서 Binary Search 변형을 사용한다. BETWEEN, >=, <= 같은 범위 쿼리는 Lower Bound/Upper Bound로 시작/끝 위치를 찾은 뒤 그 사이를 순차 스캔한다.

언제 깨지는가 — 9년간 숨어 있던 overflow silent failure: 의사코드의 mid = (left + right) / 2는 left + right가 Int.MAX_VALUE(2³¹ − 1)를 넘으면 음수로 wrap-around 되어 잘못된 인덱스(또는 ArrayIndexOutOfBoundsException)를 만든다. 이 버그는 Java JDK의 java.util.Arrays.binarySearch에 약 9년간 숨어 있다가 2006년 Joshua Bloch가 Sun에 보고했고, Bentley의 Programming Pearls 책 원본 코드는 약 20년간 같은 버그를 안고 있었다. 발현 조건은 배열 크기 약 2³⁰(≈10억) 이상 — 1980년대엔 비현실적이었으나 현재 Google 규모에선 일상 (Google Research — Nearly All Binary Searches and Mergesorts are Broken). 수정 형태(언어 무관 권장): mid = left + Math.floor((right - left) / 2) 또는 unsigned shift (left + right) >>> 1 (Java). JavaScript Number는 안전 정수 범위(2⁵³)가 넓어 실무 데이터 크기에서는 overflow가 발현하지 않지만, 같은 코드를 Java/C++로 포팅하거나 BigInt 경계에 닿는 알고리즘 문제에서는 반드시 수정 형태를 쓴다. Merge Sort의 병합 인덱스 계산에도 동일 패턴이 있으니 함께 확인 (관련 트러블슈팅: §6.5 Case 2).

Lower Bound vs Upper Bound:

Lower Bound: target 이상인 첫 번째 인덱스 (target이 처음 등장하는 위치)
Upper Bound: target 초과인 첫 번째 인덱스 (target 다음 값이 시작되는 위치)

// === 기본 Binary Search ===
function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) return mid; // 찾음
    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, 6)); // 예상 출력: -1 (없음)

// === Lower Bound ===
// target 이상인 첫 번째 인덱스 반환
// [1, 3, 5, 5, 5, 7] 에서 target=5 → 인덱스 2
function lowerBound(arr, target) {
  let left = 0;
  let right = arr.length; // 주의: length (배열 범위 밖)

  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] < target) {
      left = mid + 1; // mid는 확실히 아님 → left를 mid+1로
    } else {
      right = mid; // mid가 후보일 수 있음 → right를 mid로
    }
  }

  return left; // target 이상인 첫 번째 인덱스
}

// === Upper Bound ===
// target 초과인 첫 번째 인덱스 반환
// [1, 3, 5, 5, 5, 7] 에서 target=5 → 인덱스 5
function upperBound(arr, target) {
  let left = 0;
  let right = arr.length;

  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] <= target) {
      left = mid + 1; // mid는 target 이하이므로 → 오른쪽으로
    } else {
      right = mid; // mid가 upper bound 후보
    }
  }

  return left; // target 초과인 첫 번째 인덱스
}

// 실전 활용: target의 등장 횟수 계산
const nums = [1, 3, 5, 5, 5, 7, 9];
const target = 5;
const count = upperBound(nums, target) - lowerBound(nums, target);
console.log(`${target}의 등장 횟수:`, count);
// 예상 출력: 5의 등장 횟수: 3

// Lower Bound와 Upper Bound 위치 확인
console.log("Lower Bound (첫 번째 5의 위치):", lowerBound(nums, 5)); // 예상 출력: 2
console.log("Upper Bound (5 다음 값의 위치):", upperBound(nums, 5)); // 예상 출력: 5

3-3. 심화: LRU Cache (Least Recently Used Cache)

비유: 냉장고 선반을 생각해 보자. 자주 꺼내 쓰는 음식은 손이 닿기 쉬운 앞쪽에 있다. 꺼내 쓸 때마다 앞쪽으로 옮긴다. 냉장고가 꽉 차면 가장 오래 손대지 않은 뒤쪽 음식을 버린다. 이것이 LRU 캐시의 동작 원리다.

원리: LRU 캐시는 두 가지 연산을 O(1)에 처리해야 한다:

get(key): 키로 값을 찾기
put(key, value): 새 항목 추가 (용량 초과 시 가장 오래된 것 제거)

이를 위해 HashMap + Doubly Linked List(이중 연결 리스트) 의 조합을 사용한다:

HashMap: key → 노드 참조 를 저장 → O(1) 접근
Doubly Linked List: 최근 사용 순서를 관리 → 앞쪽이 MRU(가장 최근), 뒤쪽이 LRU(가장 오래됨)
- 이중 연결이어야 하는 이유: 특정 노드를 삭제할 때 이전 노드를 알아야 포인터를 수정할 수 있다. 단방향 연결 리스트는 이전 노드를 O(n)으로 찾아야 한다.

왜 이 조합인가:

HashMap만 쓰면: 접근은 O(1)이지만, 어떤 키가 가장 오래됐는지 알 수 없다 (순서 정보 없음)
LinkedList만 쓰면: 순서는 관리되지만, 특정 키를 찾으려면 O(n)으로 순회해야 한다
조합하면: HashMap으로 노드를 O(1)에 찾고, LinkedList로 O(1)에 순서를 바꾼다

왜 “이중” 연결 리스트여야 하는가: 단방향 연결 리스트에서 특정 노드를 삭제하려면 “이전 노드”를 알아야 포인터를 연결할 수 있다. 단방향에서는 이전 노드를 찾으려면 head부터 순회해야 하므로 O(n)이다. 이중 연결 리스트는 node.prev로 바로 접근하므로 삭제가 O(1)이 된다. LRU에서 get() 연산 시 노드를 현재 위치에서 제거하고 head(MRU)로 옮기는 작업이 매번 발생하므로, 이 O(1) 삭제가 전체 성능의 핵심이다.

📖 더 보기: Redis 공식 블로그 — Cache Eviction Strategies — LRU/LFU/TTL 등 캐시 교체 전략을 실무 관점에서 비교 (중급)

// LRU Cache 구현 — HashMap + Doubly Linked List
class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map(); // key → node 참조

    // 더미 헤드(MRU 쪽)와 더미 테일(LRU 쪽)
    // 더미 노드를 쓰면 경계 처리가 간단해짐
    this.head = { key: null, val: null, prev: null, next: null };
    this.tail = { key: null, val: null, prev: null, next: null };
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  // 노드를 head 바로 뒤(MRU 위치)에 삽입
  _insertAtFront(node) {
    node.prev = this.head;
    node.next = this.head.next;
    this.head.next.prev = node;
    this.head.next = node;
  }

  // 노드를 리스트에서 제거
  _remove(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  // 접근: O(1)
  get(key) {
    if (!this.cache.has(key)) return -1;

    const node = this.cache.get(key);
    // 가장 최근 사용으로 이동
    this._remove(node);
    this._insertAtFront(node);

    return node.val;
  }

  // 삽입/갱신: O(1)
  put(key, value) {
    if (this.cache.has(key)) {
      // 기존 노드 갱신 후 MRU로 이동
      const node = this.cache.get(key);
      node.val = value;
      this._remove(node);
      this._insertAtFront(node);
    } else {
      if (this.cache.size >= this.capacity) {
        // 용량 초과 → LRU(tail 직전 노드) 제거
        const lruNode = this.tail.prev;
        this._remove(lruNode);
        this.cache.delete(lruNode.key);
      }

      // 새 노드 생성 후 MRU로 삽입
      const newNode = { key, val: value, prev: null, next: null };
      this.cache.set(key, newNode);
      this._insertAtFront(newNode);
    }
  }
}

// 사용 예시
const lru = new LRUCache(3); // 용량 3

lru.put("a", 1);
lru.put("b", 2);
lru.put("c", 3);
// 상태: c(MRU) → b → a(LRU)

console.log(lru.get("a")); // 예상 출력: 1  →  a가 MRU로 이동
// 상태: a(MRU) → c → b(LRU)

lru.put("d", 4); // 용량 초과 → b(LRU) 제거
// 상태: d(MRU) → a → c(LRU)

console.log(lru.get("b")); // 예상 출력: -1  →  b는 이미 삭제됨
console.log(lru.get("c")); // 예상 출력: 3

실무 연결:

Redis LRU: Redis는 메모리가 부족할 때 LRU 정책으로 오래된 키를 자동 삭제한다 (maxmemory-policy allkeys-lru)
브라우저 캐시: 디스크/메모리 캐시에서 오래된 리소스를 LRU로 제거한다
CDN 캐시: Cloudfront, Fastly 등도 엣지 서버의 캐시 교체에 LRU 변형을 사용한다
CPU 캐시: L1/L2/L3 캐시도 LRU 기반 교체 정책을 사용한다

Nest.js/AWS 실무 연결: LRU Cache를 직접 쓰는 상황

NestJS CacheModule + LRU: @nestjs/cache-manager는 기본적으로 인메모리 LRU 캐시를 사용한다. TTL(Time-to-Live)과 max 옵션으로 용량을 제한하면 내부적으로 LRU 정책으로 오래된 항목을 제거한다.

// app.module.ts — NestJS 내장 LRU 캐시 설정
import { CacheModule } from "@nestjs/cache-manager";

@Module({
  imports: [
    CacheModule.register({
      ttl: 60, // 60초 후 자동 만료
      max: 100, // 최대 100개 항목 — 초과 시 LRU로 오래된 것 제거
    }),
  ],
})
export class AppModule {}

// 사용처 — 자주 조회되는 설정값 캐싱
@Injectable()
export class ConfigService {
  constructor(@Inject(CACHE_MANAGER) private cacheManager: Cache) {}

  async getConfig(key: string): Promise<string> {
    const cached = await this.cacheManager.get<string>(key);
    if (cached) return cached; // LRU에서 O(1) 조회

    const value = await this.db.getConfig(key); // DB 조회
    await this.cacheManager.set(key, value, 60); // LRU에 저장 + TTL
    return value;
  }
}

Redis maxmemory-policy 실무 설정: AWS ElastiCache(Redis) 사용 시 메모리 한도를 반드시 설정해야 한다. allkeys-lru는 모든 키에 LRU 적용, volatile-lru는 TTL이 설정된 키에만 LRU를 적용한다. 설정하지 않으면 OOM(Out of Memory) 오류로 Redis가 쓰기를 거부한다.

# Redis 설정 (redis.conf 또는 AWS ElastiCache 파라미터 그룹)
maxmemory 1gb
maxmemory-policy allkeys-lru  # 가장 오래 사용 안 한 키부터 제거

📖 더 보기: NestJS Cache Module 공식 문서 — CacheInterceptor와 수동 캐시 관리로 LRU 캐시를 활용하는 방법 (입문)

3-4. 문자열 검색 알고리즘

문자열 검색은 긴 텍스트(text, 길이 n)에서 패턴(pattern, 길이 m)을 찾는 문제다.

알고리즘 비교표

알고리즘	전처리	탐색	핵심 아이디어
Brute Force	O(1)	O(n × m)	모든 위치에서 하나씩 비교
KMP	O(m)	O(n + m)	실패한 비교 정보를 재활용 (실패 함수)
Rabin-Karp	O(m)	O(n + m) 평균, O(nm) 최악	해시값 비교 → 일치 시만 문자 비교
Boyer-Moore	O(m + σ)	O(n/m) 최선	오른쪽에서 왼쪽으로 비교, 불일치 시 크게 건너뜀

Brute Force (브루트 포스)

가장 단순한 방법: text의 모든 위치에서 pattern과 문자 하나씩 비교한다.

text: "AABAACAADAABAABA"
pattern: "AABA"
→ 위치 0부터 시작해서 맞지 않으면 위치 1로 이동 반복

KMP (Knuth-Morris-Pratt)

핵심 아이디어: 불일치가 발생했을 때, 이미 비교한 정보를 버리지 않고 재활용한다. 실패 함수(Failure Function)를 미리 계산해서 패턴의 어느 위치부터 다시 비교할지 결정한다.

예: pattern=“AABAAB” 에서 5번째 문자에서 불일치 → 처음으로 돌아가지 않고 2번째부터 다시 시작

Rabin-Karp

핵심 아이디어: 문자열을 숫자(해시값)로 변환해서 비교한다. 해시값이 같을 때만 실제 문자 비교를 수행한다. 롤링 해시(Rolling Hash)로 해시 재계산을 O(1)에 처리한다.

Trie (트라이) 자료구조

비유: 전화번호부를 생각해 보자. “APPLE”, “APP”, “APPLICATION”을 저장할 때, 공통 접두사 “APP”는 한 번만 저장하고 분기한다. 이것이 Trie다.

원리:

각 노드는 문자를 나타내며, 루트에서 단말 노드까지의 경로가 하나의 단어다
검색/삽입: O(m) — m은 검색어의 길이 (트리 깊이에만 의존)
공간: O(알파벳 크기 × 단어 총 길이) — 공통 접두사 공유로 공간 절약

실무 활용:

검색창 자동완성 (Google 검색어 추천)
사전 검색, 맞춤법 검사
IP 라우팅 테이블 (최장 접두사 매칭)

// Trie 구현
class TrieNode {
  constructor() {
    this.children = {}; // { 문자: TrieNode }
    this.isEnd = false; // 단어의 끝 여부
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  // 단어 삽입: O(m)
  insert(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children[char]) {
        node.children[char] = new TrieNode();
      }
      node = node.children[char];
    }
    node.isEnd = true;
  }

  // 단어 검색: O(m)
  search(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children[char]) return false;
      node = node.children[char];
    }
    return node.isEnd;
  }

  // 접두사 검색 (자동완성 기반): O(m)
  startsWith(prefix) {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children[char]) return false;
      node = node.children[char];
    }
    return true; // 이 노드 하위에 단어가 있음
  }
}

const trie = new Trie();
trie.insert("apple");
trie.insert("app");
trie.insert("application");

console.log(trie.search("app")); // 예상 출력: true
console.log(trie.search("appl")); // 예상 출력: false (단어로 등록되지 않음)
console.log(trie.startsWith("appl")); // 예상 출력: true (apple, application의 접두사)
console.log(trie.startsWith("xyz")); // 예상 출력: false

더 깊이 알고 싶다면:

Boyer-Moore: 현업에서 가장 빠른 문자열 검색 알고리즘으로 꼽힘. 오른쪽에서 왼쪽으로 비교, Good Suffix Rule + Bad Character Rule 활용
Aho-Corasick: 여러 패턴을 동시에 검색할 때 사용 (스팸 필터, 바이러스 스캐너). KMP의 실패 함수를 Trie에 적용한 것

3-5. 정렬·탐색 실전 심화 패턴

새 알고리즘을 만났을 때 던지는 3가지 질문 (메타 분석 도구)

특정 알고리즘(QuickSort, TimSort, B-Tree, Bloom filter, Skip list 등)을 처음 마주쳐도 다음 3가지 질문에 답하면 도입 여부를 90% 결정할 수 있다. 이 3질문은 위 §3-1 ~ §3-3에서 알고리즘 선택을 정당화한 근거를 일반화한 것이다.

지배 연산은 무엇인가 — 이 워크로드에서 호출 빈도가 가장 높은 연산(get? insert? range scan? prefix match?). 그 연산의 점근 복잡도가 곧 SLA를 좌우한다.
입력 분포는 어떤 형태인가 — 무작위? 단조증가? 부분정렬? 스큐? 분포 가정이 깨지면 알고리즘이 최악 케이스로 무너진다 (예: QuickSort + 정렬된 배열 + 마지막 피벗 → O(n²)).
자원 예산은 어디가 빡빡한가 — 시간 / 메모리 / 캐시 미스 / 네트워크 라운드트립. 같은 O(n log n)이라도 캐시 지역성 차이가 상수 계수 2~3배를 가른다.

§3-1 TimSort 선택에 적용해보면: ① 지배 연산은 sort 1회당 비교, ② 실무 입력은 거의 정렬된 로그·ID 시퀀스가 다수, ③ 메모리는 V8 heap에 여유, 시간이 빡빡 — 결론: 무작위 마이크로벤치에서 QuickSort가 빠르더라도 실무 분포 우위가 있는 TimSort가 합리적. §3-3 LRU 선택에 적용해보면: ① 지배 연산은 get/put 각각, ② 입력 분포는 hot key skew (소수 키가 압도적 호출), ③ 메모리는 캐시 크기 == 비용 — 결론: get/put 모두 O(1) 보장 + 순서 정보 필요 → HashMap + DLL 조합. HashMap만이면 ②에서 깨지고, LinkedList만이면 ①에서 깨진다.

이 3질문은 새 자료구조를 도입하기 전 PR 본문이나 RFC 첫 문단에 답을 쓸 수 있는지로 자가 검증할 수 있다 — 답이 추측이라면 벤치마크가 먼저 필요하다.

비유로 이해하기

“도서관 사서가 책을 찾는 두 가지 방법”

정렬된 서가(Binary Search): 책이 번호 순서로 꽂혀 있으면 중간을 펴서 절반씩 줄여가며 O(log n)에 찾는다. 정렬되지 않은 창고(Linear Search): 번호가 없으면 처음부터 끝까지 O(n)으로 뒤져야 한다.

정렬은 탐색을 위한 전처리다. 한 번 정렬 비용(O(n log n))을 지불하면 이후 모든 탐색이 O(log n)이 된다. 탐색이 k번 이상 발생한다면 정렬이 이득이다 (k × O(log n) < O(n) + k × O(1) 조건 확인).

이진 탐색 응용 패턴 — “정답에 Binary Search 적용하기”

Binary Search는 정렬된 배열뿐 아니라 **“단조 증가/감소하는 조건”**에도 적용할 수 있다. 이 패턴을 “정답에 이진 탐색”이라 한다.

// 패턴: "최소값을 최대화" 또는 "최대값을 최소화" 문제
// 예: AWS Lambda를 n개 병렬 실행할 때, 가장 오래 걸리는 시간을 최소화하는 배분

function canFinishInTime(
  tasks: number[],
  maxTime: number,
  workers: number,
): boolean {
  // workers명이 각자 maxTime 이하로 작업을 마칠 수 있는가?
  let needed = 1;
  let currentLoad = 0;

  for (const task of tasks) {
    if (task > maxTime) return false; // 단일 작업이 maxTime 초과
    if (currentLoad + task > maxTime) {
      needed++;
      currentLoad = task;
    } else {
      currentLoad += task;
    }
  }

  return needed <= workers;
}

function minimizeMaxTime(tasks: number[], workers: number): number {
  // Binary Search: 최소 가능한 maxTime을 탐색
  let left = Math.max(...tasks); // 최소 하한: 가장 큰 단일 작업
  let right = tasks.reduce((a, b) => a + b, 0); // 최대 상한: 전부 혼자 처리

  while (left < right) {
    const mid = Math.floor((left + right) / 2);

    if (canFinishInTime(tasks, mid, workers)) {
      right = mid; // 더 줄일 수 있다 → 오른쪽 절반 버림
    } else {
      left = mid + 1; // 너무 작다 → 왼쪽 절반 버림
    }
  }

  return left; // 최소 가능한 maxTime
}

const tasks = [3, 2, 3, 1, 2, 3, 6];
console.log(minimizeMaxTime(tasks, 3)); // 6 (3명이 각자 최대 6시간 이내)

예상 출력:

이 패턴은 AWS Step Functions에서 병렬 작업 배분, Lambda 배치 크기 최적화 등에 직접 적용된다.

TimSort 내부 동작 심화 — “런(Run)을 감지하는 방법”

JavaScript의 Array.sort()가 실무 데이터에서 빠른 이유는 TimSort가 **자연 런(natural run)**을 활용하기 때문이다.

// TimSort가 유리한 실무 데이터 패턴 시연
// 타임스탬프 기반 로그 = 이미 부분 정렬된 데이터
const logs = [
  { ts: 1000, msg: "req-1" },
  { ts: 1001, msg: "req-2" },
  { ts: 1002, msg: "req-3" },
  // 재시작으로 인해 다시 낮은 타임스탬프
  { ts: 500, msg: "req-4-from-replica" },
  { ts: 501, msg: "req-5-from-replica" },
  { ts: 502, msg: "req-6-from-replica" },
];

// TimSort는 [1000,1001,1002] 런과 [500,501,502] 런을 각각 감지하고
// 두 런을 병합만 하면 됨 → 사실상 O(n) 수준
console.time("TimSort on partially sorted");
logs.sort((a, b) => a.ts - b.ts);
console.timeEnd("TimSort on partially sorted");

console.log(logs.map((l) => `${l.ts}: ${l.msg}`));

예상 출력:

TimSort on partially sorted: 0.041ms
500: req-4-from-replica
501: req-5-from-replica
502: req-6-from-replica
1000: req-1
1001: req-2
1002: req-3

LRU 캐시 - WeakRef를 활용한 메모리 누수 방지 (Node.js 14+)

// 일반 LRU: 캐시된 객체가 GC되지 않음 (메모리 점유)
// WeakRef 기반: 메모리 압박 시 GC가 캐시 항목을 수거할 수 있음

class WeakLRUCache<K extends object, V> {
  private cache = new Map<K, WeakRef<V>>();

  get(key: K): V | undefined {
    const ref = this.cache.get(key);
    if (!ref) return undefined;

    const value = ref.deref(); // GC됐으면 undefined
    if (value === undefined) {
      this.cache.delete(key); // 수거된 항목 정리
      return undefined;
    }
    return value;
  }

  set(key: K, value: V) {
    this.cache.set(key, new WeakRef(value));
  }
}

// 사용 시 주의: WeakRef는 GC 타이밍을 보장하지 않으므로
// 항상 get() 결과가 undefined일 수 있음을 처리해야 함

Nest.js/AWS 실무: 정렬·탐색이 성능 병목이 되는 상황

시나리오: 실시간 리더보드 (Top-K 문제)

@Injectable()
export class LeaderboardService {
  private scores: Array<{ userId: string; score: number }> = [];

  // 나쁜 예: 매번 전체 정렬 → O(n log n)
  getTopKBad(k: number) {
    return this.scores
      .sort((a, b) => b.score - a.score) // 매번 전체 정렬
      .slice(0, k);
  }

  // 더 나은 예: k-크기 배열로 Top-K 유지 → 삽입 O(k), 전체 스캔 O(n·k)
  // ※ JavaScript 기본 Min Heap이 없어 배열 선형 탐색으로 구현. 진정한 Min Heap(이진 힙)이면 O(log k)
  // k개짜리 배열 유지: 새 점수가 배열 최솟값보다 크면 교체
  private topK: Array<{ userId: string; score: number }> = [];
  private readonly K = 10;

  updateScore(userId: string, score: number) {
    const existing = this.topK.findIndex((e) => e.userId === userId);
    if (existing >= 0) {
      this.topK[existing].score = score;
    } else if (this.topK.length < this.K) {
      this.topK.push({ userId, score });
    } else if (score > Math.min(...this.topK.map((e) => e.score))) {
      // 최솟값 제거 후 새 항목 삽입
      const minIdx = this.topK.reduce(
        (mi, e, i) => (e.score < this.topK[mi].score ? i : mi),
        0,
      );
      this.topK[minIdx] = { userId, score };
    }
  }

  getTopK(): typeof this.topK {
    return [...this.topK].sort((a, b) => b.score - a.score);
  }
}

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

정렬

데이터베이스 ORDER BY: 내부적으로 Quick Sort 변형 또는 Merge Sort 사용. 인덱스가 없는 컬럼 정렬은 비용이 크다.
JavaScript Array.sort(): TimSort 사용. 실무에서 가장 자주 쓰이는 정렬.
Pagination 구현: 대용량 데이터를 정렬 후 커서(cursor)로 페이징할 때 정렬 알고리즘 선택이 성능에 영향.

탐색

DB 인덱스 (B-Tree): Binary Search의 확장판. 인덱스가 있는 컬럼 조회는 O(log n)이고, 없으면 Full Scan O(n).
범위 쿼리: BETWEEN, >=, <= 쿼리는 내부적으로 Lower Bound / Upper Bound를 활용.

LRU Cache

Redis 캐시 교체 정책: maxmemory-policy allkeys-lru 설정으로 메모리 부족 시 LRU로 자동 삭제.
HTTP 캐시: Cache-Control: max-age와 함께 오래된 캐시를 LRU로 교체.
NestJS 캐시 모듈: @nestjs/cache-manager 내부에서 LRU 정책 지원.

측정 후 결정한 실 사례 — noeviction → allkeys-lru 전환 효과: Redis 운영 컨설팅 사례 보고에 따르면, 캐시 용도 인스턴스에서 maxmemory-policy를 잘못된 값(예: noeviction)으로 두면 maxmemory 도달 시 쓰기가 모두 실패하면서 application latency가 폭증한다. 정책을 allkeys-lru로 바꾸고 maxmemory-samples를 5 → 10으로 올리는 튜닝을 함께 적용한 다수 엔게이지먼트에서 p99 명령 latency 30~~70% 감소, 메모리 효율 20~~50% 향상이 보고된다 (Nextbrick — Redis Performance Optimization). 핵심은 정책 자체보다 진단 → 변경 → 측정 사이클이다: redis-cli INFO stats로 evicted_keys, keyspace_hits, keyspace_misses를 변경 전후에 비교해야 hit rate 변화로 결정을 정당화할 수 있다.

Trie

검색 자동완성 API: 검색창에서 타이핑 중 추천어 제공. Elasticsearch, Elasticsearch의 prefix query도 내부적으로 Trie 기반.
라우팅 테이블: Express/Fastify의 URL 라우팅도 Trie(Radix Tree) 기반으로 구현됨.

5. 내 업무와의 연결고리

NestJS + BackOps 관점:

API 응답 캐싱: NestJS에서 CacheInterceptor를 쓸 때 내부 LRU 캐시 동작을 이해하면 TTL 설정과 캐시 무효화 전략을 더 잘 결정할 수 있다.
배치 처리 최적화: AWS Lambda로 대량 데이터를 처리할 때, 정렬 + Binary Search 조합으로 중복 제거나 매칭 성능을 크게 개선할 수 있다.
Redis maxmemory 설정: Redis OOM(Out of Memory) 이슈가 발생했을 때 LRU 정책의 동작 원리를 알면 maxmemory-policy를 올바르게 설정할 수 있다.
자동완성 기능 구현: 운영 도구의 검색창에 자동완성이 필요하다면, 소규모는 Trie로 직접 구현하거나, 대규모는 Elasticsearch의 completion suggester를 활용할 수 있다.

6. 비슷한 개념과 비교

Quick Sort vs Merge Sort — 언제 뭘 쓸까?

상황	추천 알고리즘	이유
일반적인 인메모리 정렬	Quick Sort	평균적으로 더 빠름, 캐시 효율 좋음
안정 정렬 필요 (같은 값의 순서 보장)	Merge Sort	stable 보장
외부 정렬 (파일/DB)	Merge Sort	디스크 I/O에 유리한 순차 접근 패턴
최악 케이스를 반드시 피해야 할 때	Merge Sort / Heap Sort	O(n log n) 항상 보장
추가 메모리를 쓸 수 없을 때	Heap Sort	O(1) 추가 공간
JavaScript 기본 정렬	Array.sort() (TimSort)	이미 최적화됨, 직접 구현 불필요

Binary Search vs Hash Table — 탐색의 두 방법

	Binary Search	Hash Table
시간복잡도	O(log n)	O(1) 평균
전제 조건	정렬된 배열 필요	없음
범위 탐색	가능 (lower/upper bound)	불가능
공간	O(1)	O(n)
활용	정렬된 DB 인덱스, 범위 쿼리	캐시, 딕셔너리

LRU vs LFU (Least Frequently Used)

	LRU	LFU
교체 기준	가장 오래 사용하지 않은 것	사용 횟수가 가장 적은 것
구현 복잡도	중간 (HashMap + DLL)	높음 (HashMap + MinHeap 또는 여러 DLL)
적합한 상황	최근 접근 패턴이 중요할 때	장기적 접근 빈도가 중요할 때
Redis 지원	`allkeys-lru`, `volatile-lru`	`allkeys-lfu`, `volatile-lfu`

6.5. 트러블슈팅

Case 1. JavaScript `Array.sort()` 가 숫자를 이상하게 정렬한다

증상: [10, 9, 2, 1, 100].sort() 결과가 [1, 10, 100, 2, 9]로 나온다.

원인: Array.sort()는 비교 함수가 없으면 요소를 문자열로 변환해서 사전순(lexicographic) 정렬한다. “10”은 “2”보다 사전순으로 앞이기 때문에 10이 2 앞에 온다.

해결 방법: 반드시 비교 함수를 제공한다.

// 오름차순
[10, 9, 2, 1, 100].sort((a, b) => a - b);
// 예상 출력: [1, 2, 9, 10, 100]

// 내림차순
[10, 9, 2, 1, 100].sort((a, b) => b - a);
// 예상 출력: [100, 10, 9, 2, 1]

Case 2. Binary Search 구현에서 무한 루프 또는 틀린 결과가 나온다

증상: 분명히 배열에 있는 값인데 -1을 반환하거나, 특정 입력에서 무한 루프에 빠진다.

원인 1: mid 계산 시 (left + right) / 2 에서 정수 오버플로우. Java/C++에서 9년간 숨어 있다가 2006년 Joshua Bloch가 JDK Arrays.binarySearch에서 발견한 그 버그다 (Google Research blog). JavaScript Number는 2⁵³까지 안전하지만, 같은 코드를 다른 언어로 포팅하면 배열 크기 ~2³⁰부터 발현 (§2.5 lineage ① 참조)

원인 2: Lower/Upper Bound 구현에서 right = arr.length 와 left < right 조건이 맞지 않음

원인 3: 배열이 정렬되어 있지 않은 상태에서 Binary Search를 적용

해결 방법:

// 안전한 mid 계산
const mid = left + Math.floor((right - left) / 2);

// 배열 정렬 여부 확인 후 적용
const arr = [5, 3, 1, 4, 2];
arr.sort((a, b) => a - b); // 반드시 정렬 먼저!
console.log(binarySearch(arr, 3)); // 그 다음 탐색

Case 3. LRU Cache에서 실제로 O(1)이 보장되지 않는 경우

증상: LRU 캐시를 구현했는데, 대용량 데이터에서 put 연산이 느려진다.

원인 1: HashMap 대신 일반 Object를 키로 사용할 때, 특정 키 이름이 프로토타입 메서드와 충돌하거나 V8 엔진이 히든 클래스 최적화를 포기해서 성능이 저하된다.

원인 2: Doubly Linked List 구현 없이 배열로 순서를 관리하면, 배열에서 특정 위치의 삭제가 O(n)이 되어 전체가 O(n)으로 저하된다.

해결 방법:

// Object 대신 Map 사용 (키 순서 보장, 프로토타입 충돌 없음)
this.cache = new Map(); // ✅ Object 대신 Map

// 순서 관리를 배열로 하면 안 됨
// ❌ this.order = []; → splice가 O(n)
// ✅ Doubly Linked List 사용 → remove/insert가 O(1)

참고: JavaScript의 Map은 삽입 순서를 유지하므로, 간단한 LRU는 Map만으로 구현 가능하다.

// Map 활용 간단 LRU (실전 단순 버전)
class SimpleLRU {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map();
  }

  get(key) {
    if (!this.cache.has(key)) return -1;
    const val = this.cache.get(key);
    this.cache.delete(key);
    this.cache.set(key, val); // 최근 사용으로 재삽입
    return val;
  }

  put(key, value) {
    if (this.cache.has(key)) this.cache.delete(key);
    else if (this.cache.size >= this.capacity) {
      // Map의 첫 번째 키 = 가장 오래된 것
      this.cache.delete(this.cache.keys().next().value);
    }
    this.cache.set(key, value);
  }
}

Case 4. Redis LRU 캐시에서 예상치 못한 키가 삭제된다

증상: Redis에 maxmemory-policy allkeys-lru를 설정했는데, 최근에 접근하지 않은 키가 아닌 비교적 최근 키가 삭제된다.

원인: Redis는 정확한 LRU가 아니라 **근사 LRU(approximated LRU)**를 사용한다. 모든 키의 접근 시간을 추적하면 메모리가 너무 많이 필요하므로, Redis는 무작위로 maxmemory-samples(기본값 5)개의 키를 샘플링하고 그 중 가장 오래된 것을 삭제한다. Redis 공식 문서 표현 그대로 인용하면: “Redis 3.0 + maxmemory-samples 5”는 이미 Redis 2.8보다 명확히 나아졌고, 샘플을 10으로 올리면 추가 CPU 비용을 지불하는 대신 이론적 LRU에 매우 가까운 근사를 얻는다 (Redis — Key eviction). 즉 “최근 키가 잘못 삭제되는” 빈도는 샘플 수에 직접 의존한다.

해결 방법:

# 1. 샘플 수를 늘려 정확도 향상 (CPU 약간 증가)
CONFIG SET maxmemory-samples 10

# 2. Redis INFO stats로 히트율과 제거 수 모니터링
redis-cli INFO stats | grep -E "keyspace_hits|keyspace_misses|evicted_keys"
# 예상 출력:
# keyspace_hits:1234567
# keyspace_misses:12345
# evicted_keys:890

# 3. 히트율 계산: hits / (hits + misses) = 캐시 효율
# 90% 이하라면 maxmemory를 늘리거나 TTL을 짧게 조정

📖 더 보기: Redis 공식 문서 — Key eviction — 근사 LRU 동작 원리와 maxmemory-samples 튜닝 가이드 (중급)

Case 6. Trie 삽입 후 startsWith는 true인데 search는 false가 나온다

증상: trie.insert("app") 후 trie.search("app")이 false를 반환한다.

원인: isEnd 플래그를 삽입 마지막 글자의 노드에 설정하지 않았거나, 삽입 함수가 글자를 순회한 후 node.isEnd = true 설정을 빠뜨렸다.

해결 방법:

// 잘못된 예: isEnd 설정 누락
insert(word) {
  let node = this.root;
  for (const char of word) {
    if (!node.children[char]) node.children[char] = new TrieNode();
    node = node.children[char];
  }
  // ← isEnd = true 누락! search는 항상 false 반환
}

// 올바른 예
insert(word) {
  let node = this.root;
  for (const char of word) {
    if (!node.children[char]) node.children[char] = new TrieNode();
    node = node.children[char];
  }
  node.isEnd = true; // ← 마지막 노드에 단어 완성 표시
}

체크리스트:

search()는 마지막 노드의 isEnd가 true일 때만 true 반환
startsWith()는 마지막 노드 존재 여부만 확인 (isEnd 무관)
대소문자를 구분하는 Trie라면 삽입 전 word.toLowerCase() 정규화 필요

Case 7. LRU Cache를 직접 구현했는데 get() 호출 후 MRU 이동이 안 된다

증상: get(key) 호출 후 해당 키가 MRU로 이동해야 하는데, 이후 캐시가 가득 찼을 때 방금 get한 키가 삭제된다.

원인: get() 내에서 _remove(node) + _insertAtFront(node) 두 단계를 모두 해야 하는데, 한 단계를 빠뜨렸다. 또는 Map 갱신과 연결 리스트 조작이 동기화되지 않았다.

해결 방법:

// 잘못된 get() — 연결 리스트만 갱신하고 Map 갱신 누락
get(key) {
  if (!this.cache.has(key)) return -1;
  const node = this.cache.get(key);
  this._remove(node);
  this._insertAtFront(node);
  return node.val; // OK, 하지만 아래처럼 Map의 참조는 자동 갱신됨 (같은 객체)
}

// 흔한 버그: _remove와 _insertAtFront 사이에 새 node 객체를 생성하는 실수
get(key) {
  if (!this.cache.has(key)) return -1;
  const node = this.cache.get(key);
  this._remove(node);
  // ❌ 새 노드를 만들면 Map이 구 노드를 가리키게 됨
  const newNode = { key, val: node.val, prev: null, next: null };
  this._insertAtFront(newNode);
  // this.cache.set(key, newNode); ← 이 줄을 빠뜨리면 버그!
  return newNode.val;
}

// 올바른 get() — 같은 노드 객체를 재사용
get(key) {
  if (!this.cache.has(key)) return -1;
  const node = this.cache.get(key);
  this._remove(node);       // 현재 위치에서 제거
  this._insertAtFront(node); // MRU 위치로 삽입
  // Map은 동일 객체 참조이므로 별도 갱신 불필요
  return node.val;
}

Case 5. Quick Sort에서 이미 정렬된 데이터가 매우 느리다

증상: 무작위 데이터에서는 빠르지만, 정렬된 대용량 배열에서 눈에 띄게 느려진다.

원인: 첫 번째 또는 마지막 요소를 피벗으로 선택하면, 이미 정렬된 배열에서 매번 최솟값/최댓값이 피벗이 되어 파티션이 불균형하게 나뉜다. 결과적으로 재귀 깊이가 n이 되어 O(n²)이 된다.

해결 방법:

랜덤 피벗: 무작위로 피벗을 선택해서 최악 케이스 확률을 줄인다
Median of Three: 첫 번째, 중간, 마지막 중 중앙값을 피벗으로 선택
실무에서는 Array.sort() 사용: V8이 이미 TimSort로 최적화했으므로 직접 QuickSort를 구현하지 않는다

7. 체크리스트

8. 핵심 키워드

키워드	한 줄 설명
Quick Sort	피벗 기반 분할 정복, 평균 O(n log n), 최악 O(n²)
Merge Sort	분할 후 병합, 항상 O(n log n), 안정 정렬, O(n) 공간
Heap Sort	Max-Heap 활용, 항상 O(n log n), in-place
TimSort	Merge + Insertion 하이브리드, JavaScript `Array.sort()` 엔진
Binary Search	정렬된 배열에서 O(log n) 탐색
Lower Bound	target 이상인 첫 번째 인덱스
Upper Bound	target 초과인 첫 번째 인덱스
LRU Cache	Least Recently Used, 가장 오래 쓰지 않은 것 제거
Doubly Linked List	이중 연결 리스트, 양방향 O(1) 삽입/삭제
Rolling Hash	Rabin-Karp에서 슬라이딩 윈도우 해시 재계산
Trie	접두사 트리, 자동완성/사전 검색에 활용
Stable Sort	같은 값의 원래 순서를 보장하는 정렬
In-place	추가 메모리 O(1)만 사용하는 알고리즘

8.5. 추천 리소스

리소스	유형	난이도	설명
GeeksforGeeks - Quick Sort vs Merge Sort	공식 문서	입문	두 알고리즘의 차이를 비교표와 코드로 설명
Baeldung - Quicksort vs Mergesort	블로그	입문~중급	이론적 배경과 실용적 선택 기준 정리
GeeksforGeeks - LRU Cache Implementation	공식 문서	중급	HashMap + Doubly Linked List LRU 구현 상세 설명
Medium - How to Implement LRU Cache	블로그	중급	단계별 LRU 구현 설명, 시각화 포함
cp-algorithms - Binary Search	알고리즘 레퍼런스	중급	Lower/Upper Bound 패턴 공식 설명, 수학적 배경 포함
V8 블로그 — Getting things sorted in V8	공식 블로그	중급	V8의 TimSort 도입 배경, 벤치마크, 안정 정렬 보장 과정
Redis 공식 블로그 — Cache Eviction Strategies	공식 블로그	중급	LRU/LFU/TTL 캐시 교체 전략 실무 비교
Redis 공식 문서 — Key eviction	공식 문서	중급	근사 LRU 알고리즘 동작 원리와 maxmemory-samples 설정

📚 추천 리소스 (추가)

📖 Sorting & Searching Cheatsheet — Tech Interview Handbook — 코딩 인터뷰에서 정렬/탐색 알고리즘을 고를 때의 판단 기준과 복잡도 요약 (입문)
📖 Sorting Algorithms Interview Questions — Devinterview.io — 면접에서 자주 나오는 정렬 알고리즘 질문과 상세 해설 모음 (중급)
📖 Quicksort Algorithm — Interview Cake — Quick Sort의 동작 원리를 시각적으로 설명하고 최악 케이스 회피 방법 포함 (입문)
🎬 Sorting Interview Questions & Tips — interviewing.io — 시니어 엔지니어 면접 기준으로 정렬 관련 질문의 의도와 답변 전략 (중급)
📖 cp-algorithms — Binary Search — Lower/Upper Bound 패턴의 수학적 배경과 다양한 응용 문제 (중급)

9. 직접 확인해보기

정렬 성능 비교 (Node.js 환경)

// 각 알고리즘의 실행 시간을 직접 측정해보자
function measureTime(fn, label) {
  const start = performance.now();
  fn();
  const end = performance.now();
  console.log(`${label}: ${(end - start).toFixed(3)}ms`);
}

// 무작위 배열 생성
const randomArr = () =>
  Array.from({ length: 50000 }, () => (Math.random() * 100000) | 0);

// 각 정렬 실행
const arr1 = randomArr();
const arr2 = [...arr1];
const arr3 = [...arr1];

measureTime(() => quickSort([...arr1]), "Quick Sort");
measureTime(() => mergeSort([...arr2]), "Merge Sort");
measureTime(() => arr3.sort((a, b) => a - b), "Array.sort (TimSort)");

예상 출력 (환경마다 다름):

Quick Sort: 15.234ms
Merge Sort: 22.891ms
Array.sort (TimSort): 8.456ms

TimSort가 가장 빠른 이유: V8 엔진 레벨에서 네이티브로 최적화되어 있어 JavaScript로 구현한 것보다 훨씬 빠르다.

Binary Search 동작 확인

const arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];

// 탐색 과정 시각화
function binarySearchVerbose(arr, target) {
  let left = 0,
    right = arr.length - 1,
    step = 0;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    step++;
    console.log(
      `Step ${step}: left=${left}, right=${right}, mid=${mid}, arr[mid]=${arr[mid]}`,
    );

    if (arr[mid] === target) {
      console.log(`✓ Found at index ${mid}`);
      return mid;
    }
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  console.log("✗ Not found");
  return -1;
}

binarySearchVerbose(arr, 13);

예상 출력:

Step 1: left=0, right=9, mid=4, arr[mid]=9
Step 2: left=5, right=9, mid=7, arr[mid]=15
Step 3: left=5, right=6, mid=5, arr[mid]=11
Step 4: left=6, right=6, mid=6, arr[mid]=13
✓ Found at index 6

10개 배열에서 4번만에 찾았다 (log₂(10) ≈ 3.32).

LRU Cache 동작 확인

const lru = new LRUCache(3);

const operations = [
  { op: "put", key: "a", val: 1 },
  { op: "put", key: "b", val: 2 },
  { op: "put", key: "c", val: 3 },
  { op: "get", key: "a" }, // a를 MRU로
  { op: "put", key: "d", val: 4 }, // 용량 초과, LRU(b) 제거
  { op: "get", key: "b" }, // b는 삭제됨
  { op: "get", key: "c" },
  { op: "get", key: "d" },
];

for (const { op, key, val } of operations) {
  if (op === "put") {
    lru.put(key, val);
    console.log(`put(${key}, ${val})`);
  } else {
    const result = lru.get(key);
    console.log(`get(${key}) = ${result}`);
  }
}

예상 출력:

put(a, 1)
put(b, 2)
put(c, 3)
get(a) = 1
put(d, 4)
get(b) = -1     ← b가 LRU로 제거됨
get(c) = 3
get(d) = 4

10. 한 줄 요약

“정렬은 Quick/Merge/Heap 중 상황에 맞는 것을 선택하고, 탐색은 Binary Search로 O(log n)을 달성하며, LRU Cache는 HashMap + Doubly Linked List 조합으로 O(1) get/put을 구현한 실무 핵심 자료구조다.”

Sources:

Sorting & Searching

정렬과 탐색 알고리즘 (Sorting & Searching)

1. 한 줄 정의

2. 왜 중요한가

2.5. 선행 기술의 한계 → 이 토픽의 등장

3. 핵심 개념

3-1. 정렬 알고리즘 비교

Quick Sort (퀵 소트)

Merge Sort (병합 정렬)

Heap Sort (힙 정렬)

정렬 알고리즘 비교표

Nest.js/AWS 실무 연결: 정렬 알고리즘이 실제 코드에 어떻게 적용되나

JavaScript Array.sort()는 TimSort를 사용한다

3-2. Binary Search (이진 탐색)

3-3. 심화: LRU Cache (Least Recently Used Cache)

Nest.js/AWS 실무 연결: LRU Cache를 직접 쓰는 상황

3-4. 문자열 검색 알고리즘

알고리즘 비교표

Brute Force (브루트 포스)

KMP (Knuth-Morris-Pratt)

Rabin-Karp

Trie (트라이) 자료구조

3-5. 정렬·탐색 실전 심화 패턴

새 알고리즘을 만났을 때 던지는 3가지 질문 (메타 분석 도구)

비유로 이해하기

이진 탐색 응용 패턴 — “정답에 Binary Search 적용하기”

TimSort 내부 동작 심화 — “런(Run)을 감지하는 방법”

LRU 캐시 - WeakRef를 활용한 메모리 누수 방지 (Node.js 14+)

Nest.js/AWS 실무: 정렬·탐색이 성능 병목이 되는 상황

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

정렬

탐색

LRU Cache

Trie

5. 내 업무와의 연결고리

6. 비슷한 개념과 비교

Quick Sort vs Merge Sort — 언제 뭘 쓸까?

Binary Search vs Hash Table — 탐색의 두 방법

LRU vs LFU (Least Frequently Used)

6.5. 트러블슈팅

Case 1. JavaScript Array.sort() 가 숫자를 이상하게 정렬한다

Case 2. Binary Search 구현에서 무한 루프 또는 틀린 결과가 나온다

Case 3. LRU Cache에서 실제로 O(1)이 보장되지 않는 경우

Case 4. Redis LRU 캐시에서 예상치 못한 키가 삭제된다

Case 6. Trie 삽입 후 startsWith는 true인데 search는 false가 나온다

Case 7. LRU Cache를 직접 구현했는데 get() 호출 후 MRU 이동이 안 된다

Case 5. Quick Sort에서 이미 정렬된 데이터가 매우 느리다

7. 체크리스트

8. 핵심 키워드

8.5. 추천 리소스

📚 추천 리소스 (추가)

9. 직접 확인해보기

정렬 성능 비교 (Node.js 환경)

Binary Search 동작 확인

LRU Cache 동작 확인

10. 한 줄 요약

JavaScript `Array.sort()`는 TimSort를 사용한다

Case 1. JavaScript `Array.sort()` 가 숫자를 이상하게 정렬한다