Sorting & Searching

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

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

1. 한 줄 정의

정렬은 데이터를 비교 가능한 순서로 재배치해 이후 판단 비용을 줄이는 전처리이고, 탐색은 그 순서나 자료구조의 성질을 이용해 원하는 값을 찾는 방법이다.

이 문서의 핵심 질문은 하나다. “지금 매번 처음부터 찾을 것인가, 아니면 한 번 순서를 만들어 이후 탐색을 싸게 만들 것인가?“

---

2. 왜 중요한가

정렬과 탐색은 “알고리즘 문제”에만 머무르지 않는다. DB 인덱스, 로그 정렬, 캐시 교체, 자동완성, 리더보드, 배치 중복 제거는 모두 같은 질문을 다른 이름으로 푼다.

• 응답 시간 차이: 정렬되지 않은 100만 개에서 선형 탐색은 평균 50만 번 비교한다. 정렬된 배열의 Binary Search는 약 20번 비교한다.
• 전처리 비용 판단: 정렬은 보통 O(n log n) 비용을 먼저 낸다. 대신 이후 반복 탐색이 O(log n)으로 줄어든다.
• 자료구조와 연결: basic-data-structures.mdx에서 본 배열, 해시 테이블, 연결 리스트, 힙이 실제 알고리즘 선택 기준으로 다시 등장한다.
• 보안과 운영 리스크: 결정론적 Quick Sort나 해시 테이블은 적대적 입력에서 평균 복잡도가 무너져 DoS 벡터가 될 수 있다.
• 실무 API 설계: DB에 ORDER BY를 위임할지, 애플리케이션 메모리에서 정렬할지, Top-K만 유지할지에 따라 메모리와 지연이 크게 달라진다.

---

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

초기의 탐색은 “처음부터 끝까지 본다”에 가까웠다. 배열이 정렬되어 있지 않다면 목표 값이 어디 있는지 알 방법이 없으므로 O(n) 선형 탐색이 자연스럽다. 하지만 데이터가 커지고 같은 데이터에 여러 번 질의가 들어오면 매번 O(n)을 지불하는 방식은 SLA를 깨뜨린다.

정렬·탐색 알고리즘은 이 한계를 세 방향으로 풀어왔다.

1. 순서를 만들어 탐색을 줄인다: 한 번 정렬하면 Binary Search로 후보를 절반씩 버릴 수 있다. n = 1,000,000이면 약 log2 n ≈ 20번 비교다.
2. 입력 분포를 이용한다: TimSort는 이미 정렬된 구간(run)을 감지해 거의 정렬된 로그나 이벤트 배열에서 O(n)에 가까운 성능을 낸다.
3. 전체를 보지 않는다: Top-K는 전체 정렬 대신 힙으로 상위 k개만 유지하고, LRU 캐시는 전체 데이터를 보관하지 않고 최근 접근 순서만 유지한다.

한계가 만든 대표 알고리즘

아래 표의 알고리즘 이름은 먼저 지형을 보여주기 위한 지도다. IntroSort, LRU/LFU, KMP처럼 낯선 이름은 뒤 절에서 필요한 만큼 다시 풀어 설명한다.

기존 방식의 한계	등장한 방법	해결 메커니즘
매번 처음부터 찾으면 O(n)	Binary Search	정렬된 순서로 후보 절반을 버림
Quick Sort 평균은 빠르지만 최악 O(n²)	IntroSort, TimSort, randomized pivot	최악 케이스 폴백 또는 입력 run 활용
전체를 정렬하면 Top-K도 O(n log n)	Heap 기반 Top-K	k개만 유지해 삽입·교체를 O(log k)로 제한
캐시에 모든 키를 둘 수 없음	LRU/LFU eviction	접근 시점 또는 빈도 정보를 보존해 버릴 키를 선택
문자열을 매 위치에서 다시 비교	KMP, Rabin-Karp, Boyer-Moore	실패 정보, rolling hash, 건너뛰기 규칙으로 재비교를 줄임

이 문서가 사라지면 DB 인덱스의 O(log n) 의미, Array.sort()의 숫자 정렬 버그, Redis LRU의 근사 동작, 자동완성 Trie의 공간-속도 trade-off를 모두 단편 지식으로 외우게 된다. 여기서는 각 알고리즘을 정의 → 등장한 문제 → 철학 → 메커니즘 → 경계 → 실패 신호 순서로 본다.

---

3. 학습 전제: 정렬은 “순서”를 사는 비용이다

basic-data-structures.mdx에서 이미 Big-O, 배열, 해시 테이블, 연결 리스트의 기본 구조를 다뤘다. 여기서는 필요한 전제만 짧게 다시 잡는다.

• 배열(Array): 인덱스 접근은 O(1), 순차 스캔은 O(n)이다. 연속 메모리라 캐시 지역성이 좋아 정렬 알고리즘의 기본 무대가 된다.
• 해시 테이블(Hash Table): 평균 O(1) 점 조회가 강점이지만 순서가 없다. x >= 100 같은 범위 탐색에는 부적합하다.
• 힙(Heap): 부모가 자식보다 크거나 작은 완전 이진 트리 계열 구조다. 최댓값/최솟값을 반복해서 꺼낼 때 유리하다.
• Big-O: 입력이 커질 때 증가 속도를 보는 도구다. 단, 같은 O(n log n)이라도 캐시 지역성, 안정성, 추가 메모리 때문에 실제 선택은 달라진다.

정렬의 비용은 보통 O(n log n)이다. 한 번만 찾는다면 그냥 선형 탐색이 더 단순할 수 있다. 같은 데이터에서 여러 번 찾거나 범위 질의가 반복될 때 정렬 비용은 투자로 바뀐다.

3-1. 정렬·탐색의 기본 선택지

정렬과 탐색을 고르는 첫 질문

한 번만 찾는다

정렬 비용을 내지 않고 선형 탐색 O(n)을 쓰는 편이 단순할 수 있다.

작은 배열, 단발성 검사, 입력이 이미 메모리에 있을 때

여러 번 찾는다

정렬 O(n log n)을 먼저 지불하고 Binary Search O(log n)으로 반복 질의를 줄인다.

같은 배열을 여러 요청이나 여러 단계에서 재사용할 때

정확한 값만 찾는다

Hash Table은 평균 O(1)이지만 순서가 없어 범위 질의에는 약하다.

id, email, token처럼 동등 조건 lookup이 지배적일 때

범위와 순위가 필요하다

정렬된 배열, B-Tree, Heap, Tree 계열이 순서 정보를 유지한다.

pagination, leaderboard, BETWEEN, Top-K, 자동완성 같은 작업

3-2. 정렬이 가져야 하는 성질

정렬 알고리즘을 볼 때는 이름보다 성질을 먼저 본다.

성질	의미	왜 중요한가
시간복잡도	최선/평균/최악 실행 시간이 어떻게 증가하는가	적대적 입력이나 대용량 입력에서 SLA를 지킬 수 있는가
공간복잡도	추가 메모리를 얼마나 쓰는가	Lambda, 컨테이너, DB work_mem 같은 제한과 직결
안정 정렬(Stable Sort)	같은 key끼리 원래 순서를 유지하는가	grade로 정렬해도 기존 createdAt 순서를 유지해야 할 때
제자리 정렬(In-place)	입력 배열 안에서 대부분 처리하는가	복사 비용과 메모리 피크를 줄일 수 있는가
입력 분포 적응성	이미 정렬된 구간을 활용하는가	로그, 타임스탬프, id처럼 현실 데이터가 부분 정렬된 경우
실패 모드	최악 입력에서 얼마나 나빠지는가	Quick Sort O(n²), hash collision DoS 같은 silent failure

오해 방지: “Quick Sort가 빠르다”, “Merge Sort가 안전하다”는 문장은 절반만 맞다. 빠르다는 말은 입력 분포와 구현의 피벗 전략을 포함해야 하고, 안전하다는 말은 메모리 여유가 있다는 조건을 포함해야 한다.

여기서 work_mem은 PostgreSQL이 정렬·해시 같은 작업 하나에 쓸 수 있는 작업 메모리 한도다. 알고리즘 자체는 O(n log n)이어도 이 한도를 넘으면 디스크를 쓰는 정렬로 바뀔 수 있다.

---

4. 정렬 알고리즘

4-1. Insertion Sort — 작은 입력과 거의 정렬된 입력의 기준점

Insertion Sort는 왼쪽에 이미 정렬된 구간을 만들고, 새 원소를 그 구간의 알맞은 위치에 끼워 넣는 방식이다.

등장한 문제: 매우 작은 배열에서는 복잡한 분할 정복보다 단순한 루프가 빠르다. 함수 호출, 재귀, 임시 배열 생성 같은 상수 비용이 더 크기 때문이다.

메커니즘

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const value = arr[i];
    let j = i - 1;

    while (j >= 0 && arr[j] > value) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = value;
  }
  return arr;
}

console.log(insertionSort([3, 1, 2, 5, 4]));
// 예상 출력: [1, 2, 3, 4, 5]

수치 감각

입력 상태	비교/이동 경향	해석
이미 정렬됨	각 원소당 거의 1번 확인, O(n)	거의 정렬된 데이터에서는 매우 좋다
역순	모든 원소가 앞쪽으로 이동, O(n²)	최악 케이스는 빠르게 무너진다
작은 partition	n이 작아 상수 비용이 지배	TimSort/IntroSort 내부에서 보조로 쓰인다

실패 신호: 입력 크기가 수천~수만을 넘어가고 무작위에 가까운데 직접 Insertion Sort를 쓰면 CPU 시간이 n²로 증가한다. 작은 입력 최적화용이지 범용 정렬의 주역은 아니다.

4-2. Quick Sort — 평균 속도와 최악 케이스 사이의 긴장

Quick Sort는 피벗(pivot)을 하나 고르고, 피벗보다 작은 값과 큰 값을 양쪽으로 나눈 뒤 각 구간을 재귀적으로 정렬한다.

등장한 문제: Merge Sort처럼 항상 O(n log n)을 보장하는 정렬은 좋지만, 임시 배열과 병합 비용이 있다. 인메모리 배열에서는 제자리 교환과 캐시 지역성이 강한 정렬이 더 빠를 수 있다.

철학: “전체를 한 번에 정렬하지 말고, 기준값으로 문제를 둘로 나누자.” 피벗이 균형 있게 나뉘면 깊이는 log n이 되고, 각 깊이에서 전체 n개를 한 번씩 본다. 그래서 평균 O(n log n)이 된다.

작은 worked example

입력 [4, 1, 3, 2]에서 마지막 원소 2를 피벗으로 잡아보자.

단계	상태	의미
시작	[4, 1, 3, 2]	pivot = 2
partition	[1, 2, 3, 4]	2보다 작은 1은 왼쪽, 큰 4/3은 오른쪽
왼쪽 재귀	[1]	크기 1이라 종료
오른쪽 재귀	[3, 4]	다시 partition

이 예시는 작지만 핵심을 보여준다. 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 boundary = left;

  for (let i = left; i < right; i++) {
    if (arr[i] <= pivot) {
      [arr[boundary], arr[i]] = [arr[i], arr[boundary]];
      boundary++;
    }
  }

  [arr[boundary], arr[right]] = [arr[right], arr[boundary]];
  return boundary;
}

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

Quick Sort worst case

이미 정렬된 [1, 2, 3, 4, 5]에서 마지막 원소를 피벗으로 고르면 매번 한쪽 partition이 비어 있다.

[1, 2, 3, 4, 5], pivot=5 -> 왼쪽 4개, 오른쪽 0개
[1, 2, 3, 4], pivot=4    -> 왼쪽 3개, 오른쪽 0개
[1, 2, 3], pivot=3       -> 왼쪽 2개, 오른쪽 0개

재귀 깊이가 log n이 아니라 n이 되므로 비교 횟수는 n + (n-1) + ... + 1 = O(n²)에 가까워진다. 결과는 맞지만 시간이 무너지는 silent failure다.

Algorithmic Complexity Attack

Quick Sort의 O(n²)는 단순한 면접 trivia가 아니다. 결정론적 피벗을 쓰는 qsort() 구현은 입력을 조작해 quadratic으로 끌어내릴 수 있다. McIlroy의 “antiqsort” 계열 적대 입력은 BSD qsort()에서 2^16 원소를 무작위 입력 대비 약 1,000배 느리게 만든 사례로 알려져 있다.

이 패턴은 해시 테이블의 Hash collision DoS와 같은 종류다. 평균 O(1) 또는 평균 O(n log n)에 기대는 구현이 공격자가 통제하는 입력에서 최악 복잡도로 떨어진다.

경계와 대응

• 표준 라이브러리가 IntroSort, TimSort, pdqsort처럼 최악 케이스 대응을 갖췄다면 직접 구현보다 낫다.
• 직접 구현해야 한다면 randomized pivot 또는 median-of-three를 고려한다.
• 사용자 입력을 정렬 키로 삼는 API는 p95/p99 정렬 시간과 입력 크기를 함께 본다.
• “정렬 결과는 맞는데 특정 입력만 느리다”가 대표 실패 신호다.

IntroSort는 Quick Sort로 시작하되 재귀 깊이가 위험해지면 Heap Sort로 전환하는 하이브리드다. pdqsort(pattern-defeating quicksort)는 이미 정렬된 패턴이나 반복 값처럼 Quick Sort를 망가뜨리는 입력을 감지해 분할 전략을 바꾸는 변형으로 이해하면 된다.

4-3. Merge Sort — 안정성과 최악 보장의 선택

Merge Sort는 배열을 반으로 나누고, 각 절반을 정렬한 뒤, 두 정렬된 배열을 병합한다.

등장한 문제: Quick Sort는 평균이 빠르지만 피벗이 나쁘면 O(n²)로 떨어진다. stable sort나 최악 O(n log n) 보장이 필요하면 다른 선택지가 필요하다.

철학: “정렬하기 어려운 큰 문제를, 이미 정렬된 작은 문제의 병합으로 바꾸자.” 병합 단계는 두 포인터로 왼쪽/오른쪽의 앞 원소만 비교하면 된다.

메커니즘

function mergeSort(arr, compare = (a, b) => a - b) {
  if (arr.length <= 1) return arr;

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

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

  while (i < left.length && j < right.length) {
    if (compare(left[i], right[j]) <= 0) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }

  return result.concat(left.slice(i), right.slice(j));
}

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

안정 정렬 worked example

const rows = [
  { name: "Alice", grade: "A", createdAt: 1 },
  { name: "Bob", grade: "A", createdAt: 2 },
  { name: "Charlie", grade: "B", createdAt: 3 },
];

const sorted = mergeSort(rows, (a, b) => a.grade.localeCompare(b.grade));
console.log(sorted.map((row) => row.name));
// 예상 출력: ["Alice", "Bob", "Charlie"]

Alice와 Bob의 grade가 같을 때 compare(left[i], right[j]) <= 0이면 왼쪽을 먼저 넣는다. 그래서 같은 key의 기존 순서가 유지된다. 이 성질이 stable sort다.

수치 감각과 경계

• 시간: 최선/평균/최악 모두 O(n log n)
• 공간: 일반적인 배열 구현은 O(n) 임시 공간 필요
• 장점: 안정 정렬, 외부 정렬(external sort)에 유리
• 단점: 인메모리 작은 배열에서는 복사 비용이 Quick Sort 계열보다 클 수 있음

DB나 대용량 파일 정렬에서 Merge Sort 계열이 자주 보이는 이유는 디스크 I/O가 랜덤 접근보다 순차 접근에 유리하기 때문이다. 메모리 안에서 모든 것을 해결할 수 없는 순간, “정렬된 run을 만들고 병합한다”는 철학이 강해진다.

4-4. Heap Sort — 최악 시간과 추가 공간을 동시에 통제

Heap Sort는 배열을 Max-Heap으로 만든 뒤, 루트의 최댓값을 배열 끝으로 보내고 heapify를 반복한다.

힙 리마인더: 힙은 “부모가 자식보다 항상 크다(Max-Heap)” 또는 “부모가 자식보다 항상 작다(Min-Heap)“는 부분 순서만 보장한다. 전체가 정렬된 것은 아니지만 최댓값/최솟값은 루트에서 O(1)에 볼 수 있다.

등장한 문제: Quick Sort의 최악 O(n²)을 피하고 싶고, Merge Sort의 O(n) 추가 공간도 부담될 때가 있다.

메커니즘

1. 배열 전체를 Max-Heap으로 만든다. 이 과정은 O(n)이다.
2. 루트의 최댓값을 배열 마지막으로 보낸다.
3. 힙 크기를 하나 줄이고 루트에서 heapify한다.
4. 반복하면 뒤쪽부터 정렬된 영역이 커진다.

function heapSort(arr) {
  const n = arr.length;

  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }

  for (let end = n - 1; end > 0; end--) {
    [arr[0], arr[end]] = [arr[end], arr[0]];
    heapify(arr, end, 0);
  }

  return arr;
}

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

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

  if (largest !== root) {
    [arr[root], arr[largest]] = [arr[largest], arr[root]];
    heapify(arr, heapSize, largest);
  }
}

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

경계

• 시간: 항상 O(n log n)
• 공간: O(1) 추가 공간
• 안정성: 보통 불안정 정렬
• 실측: 캐시 지역성이 Quick Sort보다 약해 평균 성능은 밀릴 수 있다

Heap Sort 자체보다 더 자주 쓰이는 형태는 Top-K다. 전체 정렬이 아니라 상위 k개만 필요하면 크기 k의 Min-Heap을 유지해 O(n log k)로 줄일 수 있다.

4-5. TimSort와 JavaScript Array.sort()

TimSort는 Merge Sort와 Insertion Sort를 섞은 안정 정렬이다. 핵심은 이미 정렬된 구간인 run을 감지해 재사용하는 것이다.

등장한 문제: 현실 데이터는 완전 무작위보다 “부분적으로 정렬된” 경우가 많다. 로그는 시간순에 가깝고, DB에서 가져온 row는 id나 createdAt 순서를 어느 정도 갖고 있다. 이런 데이터를 매번 무작위 배열처럼 다루면 이미 존재하는 질서를 버리는 셈이다.

worked example: natural run

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" },
];

logs.sort((a, b) => a.ts - b.ts);
console.log(logs.map((log) => log.ts));
// 예상 출력: [500, 501, 502, 1000, 1001, 1002]

TimSort는 [1000, 1001, 1002]와 [500, 501, 502] 같은 run을 감지하고 병합한다. 그래서 거의 정렬된 데이터에서 O(n)에 가까운 성능을 기대할 수 있다. V8 팀은 TimSort 도입 설명에서 자연 run이 많은 입력에서 기존 QuickSort 계열보다 비교/이동 횟수가 크게 줄어드는 사례를 보여줬고, 이런 입력에서는 수배 이상 차이가 날 수 있다.

JavaScript 숫자 정렬 반례

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]

비교 함수가 없으면 Array.sort()는 요소를 문자열로 바꿔 사전순으로 정렬한다. “10”은 “2”보다 앞이므로 숫자 정렬이 깨진다. 결과가 타입 에러 없이 조용히 틀리기 때문에 대표적인 failure signal로 기억해야 한다.

4-6. 정렬 알고리즘 선택 기준

정렬 알고리즘 선택 기준

Quick Sort 계열

평균 O(n log n), 공간 O(log n), 캐시 지역성이 좋다. 피벗 전략이 나쁘면 O(n²)로 무너진다.

표준 라이브러리가 최악 케이스 폴백을 갖췄거나 입력 분포를 통제할 수 있을 때

Merge Sort 계열

최선·평균·최악이 모두 O(n log n)이고 안정 정렬이 쉽다. 대신 O(n) 임시 공간이 필요하다.

stable sort, 외부 정렬, 최악 케이스 보장이 더 중요할 때

Heap Sort 계열

최악 O(n log n)과 추가 공간 O(1)을 보장한다. 캐시 지역성과 안정성은 약하다.

메모리 여유가 작고 최악 시간 보장이 필요한 제한 환경일 때

Insertion Sort

평균·최악은 O(n²)이지만 작은 배열과 거의 정렬된 입력에서는 매우 효율적이다.

작은 partition 처리, 거의 정렬된 입력, 정렬 원리 학습에 적합할 때

TimSort

natural run을 활용하는 안정 정렬이다. JavaScript 배열 정렬처럼 현실 데이터 분포에 강하다.

기본 라이브러리 정렬을 쓰고, 비교 함수만 정확히 제공하면 되는 대부분의 애플리케이션 코드

---

5. 탐색 알고리즘

5-1. Linear Search — 기준선으로 남겨야 하는 단순함

Linear Search는 처음부터 끝까지 하나씩 비교한다.

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}

복잡도는 O(n)이다. 하지만 항상 나쁜 것은 아니다.

• 입력이 작다.
• 한 번만 찾는다.
• 정렬 비용을 낼 만큼 반복 질의가 없다.
• 데이터가 stream이라 전체를 정렬할 수 없다.

실패 신호: 같은 배열을 요청마다 반복 스캔하거나, 중첩 루프 안에서 includes()를 반복하면 O(n²)로 커진다. 이때는 Set, Map, 정렬+Binary Search 중 하나를 다시 검토한다.

5-2. Binary Search — 전제 조건이 성능이다

Binary Search는 정렬된 배열에서 중간 값을 보고 왼쪽 또는 오른쪽 절반을 버리는 탐색이다.

등장한 문제: 선형 탐색은 n이 커질수록 비교 횟수가 그대로 늘어난다. 정렬된 순서를 알고 있다면 중간보다 작은지 큰지만으로 후보 절반을 버릴 수 있다.

핵심 불변식

• 탐색 범위 안에만 정답 후보가 있다.
• arr[mid] < target이면 mid 이하에는 정답이 없다.
• arr[mid] > target이면 mid 이상에는 정답이 없다.
• 반복할 때마다 범위가 반드시 줄어야 한다.

Binary Search 판단 흐름

flowchart TD
A["정렬된 배열과 target"] --> B["left/right 범위 설정"]
B --> C{"left <= right?"}
C -->|범위 종료| D["없음: -1 또는 insertion point"]
C -->|계속| E["mid = left + floor((right-left)/2)"]
E --> F{"arr[mid] == target?"}
F -->|같음| G["찾음: mid 반환"]
F -->|target이 더 큼| H["left = mid + 1"]
F -->|target이 더 작음| I["right = mid - 1"]
H --> C
I --> C

핵심은 정렬 전제, 범위 불변식, overflow-safe mid 계산이다.

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 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

5-3. Binary Search overflow — 유명한 silent failure

많은 의사코드는 mid = (left + right) / 2라고 쓴다. Java/C++ 같은 정수 언어에서 left + right가 Int.MAX_VALUE를 넘으면 overflow가 발생해 음수 인덱스나 잘못된 위치가 나온다.

이 버그는 Java JDK java.util.Arrays.binarySearch에 약 9년간 숨어 있었고, Bentley의 Programming Pearls 원본 코드도 약 20년간 같은 문제를 품고 있었다. 2006년 Joshua Bloch가 “Nearly All Binary Searches and Mergesorts are Broken”에서 설명한 사례다.

안전한 형태

const mid = left + Math.floor((right - left) / 2);

JavaScript Number는 안전 정수 범위가 넓어 일반 배열 크기에서 이 overflow가 잘 드러나지 않는다. 하지만 같은 사고방식으로 Java, C++, Rust의 정수 타입을 쓰거나, 인덱스가 큰 시스템 코드를 다룰 때는 안전한 형태가 기본값이어야 한다.

퀴즈

Binary Search가 가끔 틀릴 때 가장 먼저 확인할 두 가지는?

힌트: 전제 조건과 반복문의 불변식을 먼저 본다.

정답 보기

배열이 정렬되어 있는지와 범위 갱신이 매번 줄어드는지 확인한다. 정수 언어에서는 mid 계산이 overflow-safe한지도 함께 확인한다.

5-4. Lower Bound와 Upper Bound

Binary Search는 “값이 있는지”만 찾는 도구가 아니다. 정렬된 배열에서 어떤 값이 시작되는 위치와 끝나는 위치를 찾으면 범위 질의가 된다.

• Lower Bound: target 이상인 첫 번째 인덱스
• Upper Bound: target 초과인 첫 번째 인덱스

function lowerBound(arr, target) {
  let left = 0;
  let right = arr.length;

  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    if (arr[mid] < target) left = mid + 1;
    else right = mid;
  }

  return left;
}

function upperBound(arr, target) {
  let left = 0;
  let right = arr.length;

  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    if (arr[mid] <= target) left = mid + 1;
    else right = mid;
  }

  return left;
}

const nums = [1, 3, 5, 5, 5, 7, 9];
const count = upperBound(nums, 5) - lowerBound(nums, 5);

console.log(lowerBound(nums, 5));
console.log(upperBound(nums, 5));
console.log(count);
// 예상 출력:
// 2
// 5
// 3

DB 인덱스와의 연결: WHERE created_at BETWEEN A AND B는 B-Tree에서 시작 위치를 찾고, 끝 위치까지 순차적으로 읽는 패턴이다. Hash Table은 평균 O(1) 점 조회가 강하지만 순서를 모르기 때문에 이런 범위 탐색에는 맞지 않는다.

5-5. 정렬 비용은 언제 회수되는가

정렬은 O(n log n)이고 Binary Search는 O(log n)이다. 선형 탐색은 한 번에 O(n)이다. 같은 데이터에서 q번 찾는다고 하자.

전략	비용 모델
매번 선형 탐색	q * n
정렬 후 탐색	n log2 n + q * log2 n

n = 1,000,000이면 log2 n ≈ 20이다.

• q = 1이면 선형 탐색은 약 100만 비교, 정렬 후 탐색은 약 2천만 비교 규모라 손해일 수 있다.
• q = 100이면 선형 탐색은 약 1억 비교, 정렬 후 탐색은 약 2천만 + 2천 비교라 정렬이 유리해진다.

이 계산은 정확한 벤치마크가 아니라 판단의 출발점이다. 실제로는 메모리 복사, DB I/O, 네트워크 비용, 캐시 지역성이 더해진다.

5-6. Binary Search on Answer

Binary Search는 배열에서만 쓰지 않는다. 조건이 단조적이면 정답 후보 범위에도 적용할 수 있다. 예를 들어 “작업을 workers명에게 나눠줄 때 최대 작업 시간을 최소화하라”는 문제를 보자.

maxTime이 6일 때 가능하다면, 7, 8, 9도 가능하다. 반대로 5가 불가능하면 4, 3도 불가능하다. 이런 단조성이 있으면 답을 이진 탐색할 수 있다.

function canFinishInTime(
  tasks: number[],
  maxTime: number,
  workers: number,
): boolean {
  let needed = 1;
  let currentLoad = 0;

  for (const task of tasks) {
    if (task > maxTime) return false;
    if (currentLoad + task > maxTime) {
      needed++;
      currentLoad = task;
    } else {
      currentLoad += task;
    }
  }

  return needed <= workers;
}

function minimizeMaxTime(tasks: number[], workers: number): number {
  let left = Math.max(...tasks);
  let right = tasks.reduce((sum, task) => sum + task, 0);

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

    if (canFinishInTime(tasks, mid, workers)) right = mid;
    else left = mid + 1;
  }

  return left;
}

console.log(minimizeMaxTime([3, 2, 3, 1, 2, 3, 6], 3));
// 예상 출력: 6

경계: 조건이 단조적이지 않으면 이 패턴은 깨진다. maxTime을 키웠는데도 가능/불가능이 뒤섞이면 Binary Search를 적용할 수 없다.

---

6. 문자열 검색과 접두사 탐색

문자열 검색은 긴 text 길이 n에서 pattern 길이 m을 찾는 문제다. 단순 비교는 n개의 시작 위치마다 m글자를 비교하므로 O(nm)이 될 수 있다.

6-1. 문자열 검색 알고리즘 비교

알고리즘	전처리	탐색	철학	실패/경계
Brute Force	O(1)	O(nm)	모든 위치에서 직접 비교	반복 패턴에서 재비교가 많음
KMP	O(m)	O(n + m)	실패한 비교 정보를 prefix로 재사용	실패 함수 이해가 어렵고 구현 실수
Rabin-Karp	O(m)	평균 O(n + m), 최악 O(nm)	rolling hash로 후보만 문자 비교	hash collision이면 검증 필요
Boyer-Moore	O(m + σ)	최선 O(n/m) 수준	오른쪽부터 비교해 크게 건너뜀	짧은 패턴/작은 알파벳에선 이점 감소
Trie	O(총 문자 수)	O(m)	접두사를 노드 경로로 공유	공간 사용량과 정규화 정책 필요

σ는 alphabet size, 즉 입력 문자 집합의 크기다. Boyer-Moore는 이 문서의 핵심 축은 아니므로 “오른쪽부터 비교해 건너뛰는 폭을 키운다” 정도만 잡고, 구현은 선택 심화로 남겨도 된다.

6-2. Brute Force — 단순하지만 반복을 버린다

text:    A A B A A C A A D A A B A A B A
pattern: A A B A

0번 위치에서는 네 글자가 모두 맞는다. 1번 위치에서는 두 번째 비교쯤 깨진다. Brute Force는 이 실패 정보를 다음 위치에서 거의 재사용하지 않는다.

실패 신호: text와 pattern에 반복 접두사가 많을수록 같은 문자를 계속 다시 비교한다. 예를 들어 text가 "AAAAAAAAAB"이고 pattern이 "AAAAB"라면 많은 위치에서 앞의 "AAAA"를 반복 비교한다.

6-3. KMP — 실패를 다음 시작점으로 바꾼다

KMP(Knuth-Morris-Pratt)는 pattern 안에서 “접두사이면서 접미사인 길이”를 미리 계산한다. 불일치가 나도 처음으로 돌아가지 않고, 이미 맞았던 접두사 정보를 이용해 pattern의 비교 위치를 옮긴다.

작은 예시

pattern이 "ABABAC"라고 하자.

prefix	가장 긴 prefix=suffix	의미
A	0	재사용할 접두사 없음
AB	0	없음
ABA	1	"A" 재사용 가능
ABAB	2	"AB" 재사용 가능
ABABA	3	"ABA" 재사용 가능
ABABAC	0	C에서 반복이 끊김

KMP의 철학은 “실패를 낭비하지 않는다”이다. 실패 함수는 다시 비교할 위치를 알려주는 압축된 기억이다.

경계: KMP는 구현이 까다롭고, 대부분의 애플리케이션 코드는 언어 내장 문자열 검색이 이미 충분히 최적화되어 있다. 직접 구현은 알고리즘 학습이나 제한된 환경에서 의미가 크다.

6-4. Rabin-Karp — 문자열을 숫자 fingerprint로 본다

Rabin-Karp는 pattern과 같은 길이의 window마다 hash를 계산한다. hash가 다르면 문자 비교를 생략하고, hash가 같을 때만 실제 문자를 비교한다.

왜 rolling hash가 필요한가

매 window마다 문자열 전체 hash를 다시 계산하면 O(m)이 든다. rolling hash는 맨 앞 문자를 빼고 새 문자를 더해 O(1)에 다음 hash를 만든다.

window "abcd" -> "bcde"
앞의 'a' 기여분 제거
나머지 "bcd"를 한 칸 이동
새 문자 'e' 추가

반례: hash가 같다고 문자열이 같은 것은 아니다. collision이 가능하므로 최종 후보는 실제 문자열 비교로 검증해야 한다. 이 검증을 빼면 “가끔 틀리는 검색”이 된다.

6-5. Trie — 접두사를 공유하는 탐색 구조

Trie는 문자열의 접두사를 노드 경로로 저장하는 트리다. "app", "apple", "application"은 "app" 경로를 공유한다.

등장한 문제: 자동완성처럼 “이 prefix로 시작하는 단어가 있는가”를 자주 묻는다면, 모든 문자열을 매번 순회하는 방식은 낭비다.

메커니즘

class TrieNode {
  constructor() {
    this.children = new Map();
    this.isEnd = false;
  }
}

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

  insert(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) node.children.set(char, new TrieNode());
      node = node.children.get(char);
    }
    node.isEnd = true;
  }

  search(word) {
    const node = this._find(word);
    return Boolean(node && node.isEnd);
  }

  startsWith(prefix) {
    return Boolean(this._find(prefix));
  }

  _find(text) {
    let node = this.root;
    for (const char of text) {
      if (!node.children.has(char)) return null;
      node = node.children.get(char);
    }
    return node;
  }
}

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

console.log(trie.search("app"));
console.log(trie.search("appl"));
console.log(trie.startsWith("appl"));
// 예상 출력:
// true
// false
// true

실패 신호

• startsWith("app")는 true인데 search("app")가 false라면 isEnd 설정을 의심한다.
• 대소문자, 공백, 한글 정규화 정책이 없으면 같은 단어가 서로 다른 경로로 저장된다.
• 알파벳 크기가 크고 단어 수가 많으면 공간 사용량이 커질 수 있다.

---

7. LRU Cache와 Top-K: 정렬·탐색의 실무 확장

LRU와 Top-K는 전통적인 “정렬 알고리즘”은 아니지만, 실무에서는 정렬·탐색의 판단 기준이 그대로 이어진다.

7-1. LRU Cache — 모든 것을 저장할 수 없을 때 무엇을 버릴까

LRU(Least Recently Used)는 가장 오래 사용하지 않은 항목을 먼저 제거하는 캐시 교체 정책이다.

등장한 문제: 캐시는 빠른 탐색을 위해 데이터를 메모리에 둔다. 하지만 메모리는 한정되어 있으므로 언젠가 버릴 키를 골라야 한다. FIFO는 들어온 순서만 보므로, 방금까지 자주 쓰이던 오래된 키를 버릴 수 있다.

철학: 최근에 접근한 데이터가 가까운 미래에도 다시 접근될 가능성이 높다는 locality 가정에 기대어 버릴 키를 고른다.

정확한 LRU의 메커니즘

• Map: key에서 노드로 O(1)에 접근한다.
• Doubly Linked List: 최근 사용 순서를 O(1)에 갱신한다.
• get(key): 노드를 찾고 MRU(head) 쪽으로 이동한다.
• put(key, value): 새 노드를 넣고, 용량 초과 시 LRU(tail) 쪽 노드를 제거한다.

용량 3
put(a), put(b), put(c)
상태: c(MRU) -> b -> a(LRU)

get(a)
상태: a(MRU) -> c -> b(LRU)

put(d)
상태: d(MRU) -> a -> c(LRU), b 제거

왜 이중 연결 리스트인가

단방향 연결 리스트에서 중간 노드를 삭제하려면 이전 노드를 찾아야 한다. 그러면 삭제가 O(n)이 된다. LRU는 get() 때마다 노드를 중간에서 빼서 앞으로 옮기므로 삭제와 삽입이 O(1)이어야 한다. 이중 연결 리스트의 prev 포인터가 그 비용을 줄인다.

간단한 JavaScript Map LRU

JavaScript Map은 삽입 순서를 유지하므로 작은 캐시에서는 Map만으로도 LRU 형태를 만들 수 있다.

class SimpleLRU {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map();
  }

  get(key) {
    if (!this.cache.has(key)) return -1;
    const value = this.cache.get(key);
    this.cache.delete(key);
    this.cache.set(key, value);
    return value;
  }

  put(key, value) {
    if (this.cache.has(key)) {
      this.cache.delete(key);
    } else if (this.cache.size >= this.capacity) {
      const oldestKey = this.cache.keys().next().value;
      this.cache.delete(oldestKey);
    }
    this.cache.set(key, value);
  }
}

const lru = new SimpleLRU(3);
lru.put("a", 1);
lru.put("b", 2);
lru.put("c", 3);
console.log(lru.get("a"));
lru.put("d", 4);
console.log(lru.get("b"));
// 예상 출력:
// 1
// -1

이 코드는 학습용으로 충분하지만, 고성능 캐시에서는 객체 할당, eviction hook, TTL, 동시성, 메모리 accounting까지 고려해야 한다.

7-2. Redis LRU는 정확한 LRU가 아니다

Redis는 모든 키의 정확한 접근 순서를 완벽히 추적하지 않는다. 메모리와 CPU 비용이 크기 때문이다. 대신 maxmemory-samples 개수만큼 키를 샘플링하고 그중 오래된 키를 제거하는 근사 LRU를 사용한다.

정량 감각

• 기본 샘플 수는 보통 5로 설명된다.
• 샘플 수를 늘리면 이론적 LRU에 가까워지지만 CPU 비용이 늘어난다.
• allkeys-lru는 TTL 여부와 무관하게 모든 키를 eviction 후보로 본다.
• volatile-lru는 TTL이 있는 키만 후보로 본다.

실패 신호

증상	의미	먼저 볼 것
최근에 쓴 것 같은 키가 사라짐	정확한 LRU가 아니라 샘플링 LRU일 수 있음	maxmemory-samples, hit/miss
maxmemory 도달 후 쓰기 실패	noeviction 또는 정책 부적합 가능	maxmemory-policy, evicted_keys
hit rate가 낮고 DB 부하가 같이 증가	캐시가 보호층이 아니라 증폭기가 됨	keyspace hits/misses, TTL 분포
평균은 정상인데 p99만 튐	hot key 또는 eviction storm 가능	percentile latency, hot key 분포

운영 절차의 핵심은 명령어가 아니라 관측 순서다. 정책 변경 전후로 hit rate, evicted key 수, p99 latency를 같이 비교해야 한다. hit rate는 hits / (hits + misses)로 계산한다. 예를 들어 hits=90,000, misses=10,000이면 90%이고, 정책 변경 뒤 75%로 떨어지면서 DB QPS가 같이 오른다면 eviction/TTL 정책이 캐시를 보호층이 아니라 부하 증폭기로 만들고 있다는 신호다.

7-3. Top-K — 전체 정렬하지 말고 필요한 순위만 유지한다

리더보드 상위 10명만 필요하다면 100만 명 전체를 매번 정렬할 필요가 없다.

나쁜 기준선

function getTopKBad(
  scores: Array<{ userId: string; score: number }>,
  k: number,
) {
  return [...scores].sort((a, b) => b.score - a.score).slice(0, k);
}

전체 정렬이라 O(n log n)이다.

Heap 방식의 철학

크기 k의 Min-Heap을 유지한다. heap의 루트는 현재 Top-K 중 가장 작은 점수다.

1. 새 점수가 루트보다 작거나 같으면 버린다.
2. 새 점수가 루트보다 크면 루트를 제거하고 새 점수를 넣는다.
3. heap 크기는 k를 넘지 않으므로 삽입/제거는 O(log k)다.

n	k	전체 정렬 대략 비용 n log2 n	Top-K heap 대략 비용 n log2 k
1,000,000	10	약 20,000,000 단위	약 3,300,000 단위
1,000,000	100	약 20,000,000 단위	약 6,600,000 단위

실패 신호: 요청마다 전체 배열을 정렬한 뒤 slice(0, k)를 한다면, k가 작아도 n 전체에 대한 정렬 비용을 내고 있다. batch나 stream에서는 heap, DB에서는 index order + limit, 검색엔진에서는 ranking collector 같은 구조를 검토한다.

---

8. 실무 판단 기준

8-1. DB ORDER BY vs 애플리케이션 정렬

가능하면 정렬과 페이지네이션은 DB에 위임한다. 이유는 DB가 인덱스, 통계, 메모리 제한, 외부 정렬 알고리즘을 함께 고려할 수 있기 때문이다.

// 위험: 전체 row를 애플리케이션으로 가져온 뒤 정렬
const users = await this.userRepo.find();
const sorted = users.sort(
  (a, b) => b.createdAt.getTime() - a.createdAt.getTime(),
);

// 일반적으로 더 나음: DB에서 정렬과 limit을 함께 수행
const users = await this.userRepo.find({
  order: { createdAt: "DESC" },
  take: 20,
});

정량 감각

• 응답 1건이 100,000행 × 200B ≈ 20MB를 넘으면 정렬 사본과 JSON 직렬화 사본 때문에 Node.js heap 압박이 커진다.
• PostgreSQL work_mem 기본값은 흔히 4MB로 설명된다. 정렬 working set이 이를 넘으면 external sort로 spill할 수 있다.
• 100 connection × 64MB work_mem = 6.4GB처럼 per-connection 메모리 설정은 총량으로 봐야 한다.

external sort는 메모리 안에서 끝나지 않아 임시 파일을 써서 정렬하는 방식이고, spill은 중간 데이터가 메모리 한도를 넘어 디스크로 흘러나가는 현상이다.

경계: DB에 위임한다고 항상 공짜는 아니다. 인덱스가 없으면 DB도 정렬 비용을 낸다. ORDER BY created_at DESC LIMIT 20이 자주 쓰이면 (created_at) 또는 필터 조건을 포함한 복합 인덱스를 검토한다.

8-2. 정렬·탐색 선택 질문 5개

새 알고리즘이나 자료구조를 만났을 때 아래 질문에 답하면 선택이 흔들리지 않는다.

1. 지배 연산은 무엇인가: sort, point lookup, range scan, prefix match, Top-K 중 무엇이 가장 자주 호출되는가?
2. 입력 분포는 어떤가: 무작위, 이미 정렬됨, 거의 정렬됨, 스큐, 적대적 입력 중 무엇에 가까운가?
3. 전처리 비용을 회수할 만큼 반복되는가: 한 번 찾는가, 같은 데이터에 수백 번 질의하는가?
4. 자원 예산은 어디가 부족한가: CPU, 메모리, DB I/O, 네트워크, tail latency 중 무엇이 병목인가?
5. 실패 신호를 관측할 수 있는가: p99 latency, spill, eviction, recursion depth, collision 같은 지표가 있는가?

이 질문에 답하지 못하면 “빠르다”, “안전하다” 같은 평가는 아직 근거가 부족하다.

8-3. 같은 Big-O라도 실제 성능이 달라지는 이유

Quick Sort와 Merge Sort는 둘 다 O(n log n)으로 설명된다. 그러나 실제 성능은 다를 수 있다.

• Quick Sort는 제자리 교환이 많아 캐시 지역성이 좋다.
• Merge Sort는 병합용 임시 배열이 필요해 메모리 대역폭을 더 쓸 수 있다.
• TimSort는 자연 run을 감지해 거의 정렬된 입력에서 비교 횟수를 크게 줄인다.
• Heap Sort는 최악 시간을 보장하지만 포인터 이동 패턴이 캐시에 덜 친화적일 수 있다.

Big-O는 후보를 줄이는 도구이고, 입력 분포와 자원 예산은 최종 선택을 정하는 도구다.

---

9. 비슷한 개념과 비교

9-1. Quick Sort vs Merge Sort vs Heap Sort

기준	Quick Sort 계열	Merge Sort 계열	Heap Sort 계열
평균 시간	O(n log n)	O(n log n)	O(n log n)
최악 시간	O(n²) 가능, 폴백 있으면 완화	O(n log n)	O(n log n)
추가 공간	보통 O(log n)	보통 O(n)	O(1)
안정 정렬	보통 아님	구현하기 쉬움	보통 아님
강점	평균 속도, 캐시 지역성	안정성, 외부 정렬, 최악 보장	메모리 제한, 최악 보장
주요 실패 신호	특정 입력에서 latency 급등	메모리 피크, 복사 비용	평균 성능 기대보다 낮음

9-2. Binary Search vs Hash Table

기준	Binary Search	Hash Table
시간복잡도	O(log n)	평균 O(1), 최악 O(n)
전제	정렬된 순서 필요	좋은 해시 함수와 충돌 대응
범위 탐색	가능	부적합
순서 보존	가능	기본적으로 없음
대표 사용	B-Tree 인덱스, lower/upper bound	Map, Set, cache, dictionary
실패 신호	정렬 전제 깨짐, boundary bug	collision, p99만 튀는 지연

9-3. LRU vs LFU

기준	LRU	LFU
교체 기준	가장 오래 사용하지 않은 항목	사용 횟수가 가장 적은 항목
잘 맞는 패턴	최근성이 강한 traffic	장기 인기 item이 반복되는 traffic
약한 패턴	scan 한 번으로 hot item이 밀릴 수 있음	오래된 인기 item이 과도하게 남을 수 있음
구현 비용	HashMap + Doubly Linked List	빈도 bucket, heap, 여러 list 등 더 복잡
Redis 정책 예시	allkeys-lru, volatile-lru	allkeys-lfu, volatile-lfu

9-4. Trie vs Hash Table 자동완성

기준	Trie	Hash Table
exact search	O(m)	평균 O(1) 가능
prefix search	O(prefix 길이 + 결과 수)	별도 인덱스 없으면 전체 key scan
공간	접두사 공유로 절약 가능하지만 포인터 많음	key 전체 저장
정규화 민감도	매우 높음	높음
적합한 상황	자동완성, 사전, 라우팅 prefix	정확한 key lookup

---

10. 실패 신호와 진단 기준

긴 복구 런북보다 먼저 봐야 할 것은 “어떤 현상이 어떤 개념 실패를 뜻하는가”다.

실패 신호	먼저 의심할 개념	학습 포인트
[10, 2]가 [10, 2] 또는 [1, 10, 2]처럼 정렬됨	JS Array.sort() 기본 문자열 비교	숫자 정렬은 comparator가 필요하다
Binary Search가 있는 값을 못 찾음	정렬 전제, boundary 갱신, overflow	전제와 불변식을 먼저 확인한다
정렬 결과는 맞지만 특정 입력에서 p99가 폭증	Quick Sort worst case, complexity attack	평균 복잡도만 보면 안 된다
DB ORDER BY가 갑자기 느림	index 부재, external sort spill	정렬 working set과 인덱스 순서를 함께 본다
Top-K API가 k=10인데도 느림	전체 정렬 후 slice	heap 또는 index order + limit을 검토한다
Redis에서 최근 키가 사라짐	근사 LRU 샘플링	정확한 LRU가 아니라 샘플 기반 eviction이다
캐시 hit rate 하락과 DB 부하 증가가 같이 발생	캐시 eviction/TTL 정책 실패	캐시가 보호층이 아니라 부하 증폭기가 될 수 있다
Trie에서 startsWith는 true, search는 false	isEnd 누락 또는 정규화 불일치	prefix 존재와 단어 완성은 다른 조건이다
KMP/Rabin-Karp 직접 구현이 가끔 틀림	failure table 또는 hash collision 검증 누락	최적화 정보는 정답 검증을 대체하지 않는다
해시 기반 탐색 평균은 정상인데 p99만 튐	hash collision, hot key, skew	평균보다 tail latency를 봐야 한다

---

11. 선택 부록: 직접 확인해보기

아래 코드는 본문 이해를 돕는 선택 실습이다. 핵심은 명령어가 아니라 관찰 포인트다.

정렬 성능 비교 스케치

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");

관찰 포인트:

• JavaScript로 직접 구현한 정렬과 엔진 내장 정렬은 상수 계수가 다르다.
• 무작위 입력, 정렬된 입력, 거의 정렬된 입력을 나눠 봐야 한다.
• 결과 숫자 하나보다 입력 분포별 순위 변화가 중요하다.

Binary Search 단계 출력

function binarySearchVerbose(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  let step = 0;

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

    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }

  return -1;
}

binarySearchVerbose([1, 3, 5, 7, 9, 11, 13, 15, 17, 19], 13);

예상 흐름:

step=1, left=0, right=9, mid=4, value=9
step=2, left=5, right=9, mid=7, value=15
step=3, left=5, right=6, mid=5, value=11
step=4, left=6, right=6, mid=6, value=13

관찰 포인트:

• 매 단계 범위가 줄어드는지 확인한다.
• left, right, 반복 조건이 같은 구간 규칙을 따르는지 본다.

정확한 LRU 구현 골격

class Node {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map();
    this.head = new Node(null, null);
    this.tail = new Node(null, null);
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  get(key) {
    if (!this.cache.has(key)) return -1;
    const node = this.cache.get(key);
    this._remove(node);
    this._insertAfterHead(node);
    return node.value;
  }

  put(key, value) {
    if (this.cache.has(key)) {
      const node = this.cache.get(key);
      node.value = value;
      this._remove(node);
      this._insertAfterHead(node);
      return;
    }

    if (this.cache.size >= this.capacity) {
      const lru = this.tail.prev;
      this._remove(lru);
      this.cache.delete(lru.key);
    }

    const node = new Node(key, value);
    this.cache.set(key, node);
    this._insertAfterHead(node);
  }

  _remove(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  _insertAfterHead(node) {
    node.prev = this.head;
    node.next = this.head.next;
    this.head.next.prev = node;
    this.head.next = node;
  }
}

관찰 포인트:

• get()이 값을 반환하는 동시에 MRU 위치로 옮기는지 본다.
• Map이 같은 node 객체를 가리키는지 본다.
• 배열 splice()로 순서를 관리하면 삭제가 O(n)이 되어 LRU의 목적이 깨진다.

대표 실패는 get()에서 값을 읽기만 하고 node를 MRU 위치로 옮기지 않는 것이다. 그러면 방금 읽은 hot key도 여전히 LRU 쪽에 남아 다음 put()에서 삭제될 수 있다.

---

12. 체크리스트

정렬·탐색 복습 체크리스트

• 정렬이 탐색 비용을 줄이는 전처리라는 관점으로 설명할 수 있다.
• Quick Sort의 평균 O(n log n)과 최악 O(n²)이 피벗 균형에서 갈린다는 것을 설명할 수 있다.
• 알고리즘 복잡도 공격이 왜 단순 성능 문제가 아니라 보안 문제가 되는지 설명할 수 있다.
• Merge Sort가 stable sort와 외부 정렬에 유리한 이유를 설명할 수 있다.
• Heap Sort와 Top-K heap의 차이를 설명할 수 있다.
• JavaScript Array.sort()에서 숫자 comparator가 필요한 이유를 반례로 보여줄 수 있다.
• Binary Search의 정렬 전제, 범위 불변식, overflow-safe mid 계산을 코드로 설명할 수 있다.
• Lower Bound와 Upper Bound로 중복 값 개수와 범위 시작점을 구할 수 있다.
• KMP, Rabin-Karp, Trie가 각각 어떤 재비교 비용을 줄이는지 설명할 수 있다.
• LRU Cache가 HashMap + Doubly Linked List를 결합하는 이유를 O(1) 연산 관점에서 설명할 수 있다.
• Redis 근사 LRU에서 maxmemory-samples가 정확도와 CPU 비용의 trade-off라는 것을 안다.
• DB ORDER BY와 애플리케이션 정렬 중 무엇을 선택할지 입력 크기, 인덱스, 메모리 기준으로 판단할 수 있다.

---

13. 핵심 키워드

키워드	한 줄 설명
정렬	데이터를 비교 가능한 순서로 재배치하는 전처리
탐색	원하는 값이나 범위를 찾는 과정
Stable Sort	같은 key의 원래 순서를 보존하는 정렬
In-place Sort	추가 메모리를 거의 쓰지 않고 입력 내부에서 처리하는 정렬
Quick Sort	피벗 기반 분할 정복, 평균 O(n log n), 최악 O(n²)
Merge Sort	정렬된 절반들을 병합하는 stable sort 계열
Heap Sort	Max-Heap으로 최댓값을 반복 추출하는 정렬
TimSort	natural run을 활용하는 Merge+Insertion 하이브리드
Binary Search	정렬된 후보를 절반씩 버리는 O(log n) 탐색
Lower Bound	target 이상인 첫 번째 위치
Upper Bound	target 초과인 첫 번째 위치
Binary Search on Answer	단조 조건을 만족하는 정답 범위를 이진 탐색하는 패턴
KMP	실패 함수를 이용해 문자열 재비교를 줄이는 알고리즘
Rabin-Karp	rolling hash로 문자열 후보 비교를 줄이는 알고리즘
Trie	접두사를 공유하는 문자열 탐색 트리
LRU	가장 오래 사용하지 않은 항목을 제거하는 캐시 정책
Top-K	전체 정렬 없이 상위 k개만 유지하는 문제
Algorithmic Complexity Attack	평균 복잡도 가정을 최악 입력으로 무너뜨리는 공격

---

14. 추천 리소스

리소스	난이도	설명
Google Research — Nearly All Binary Searches and Mergesorts are Broken	중급	Binary Search overflow 버그의 대표 사례
V8 — Getting things sorted in V8	중급	V8의 TimSort 도입 배경과 stable sort 설명
cp-algorithms — Binary Search	중급	lower/upper bound와 다양한 binary search 패턴
Redis — Key eviction	중급	Redis eviction policy와 근사 LRU 설명
Redis Blog — Cache Eviction Strategies	입문~중급	LRU/LFU/TTL 정책을 비교하는 캐시 교체 개요
Tech Interview Handbook — Sorting & Searching	입문	면접 관점의 정렬·탐색 선택 기준 요약

---

15. 한 줄 요약

정렬은 순서를 만들어 반복 탐색을 싸게 만드는 투자이고, 탐색은 그 순서나 자료구조의 제약을 이용해 후보를 줄이는 과정이다. 좋은 선택은 알고리즘 이름이 아니라 입력 분포, 반복 횟수, 메모리 예산, 실패 신호를 함께 보고 결정한다.

---

출처

• Google Research — Nearly All Binary Searches and Mergesorts are Broken
• V8 — Getting things sorted in V8
• cp-algorithms — Binary Search
• Redis — Key eviction
• Redis Blog — Cache Eviction Strategies
• matslina — Algorithmic complexity attacks and libc qsort()