정렬과 탐색, 실무 성능의 기본 선택지
정렬, 이진 탐색, LRU 캐시, 문자열 검색을 실무 성능과 실패 모드 중심으로 풀어낸다. 알고리즘 선택에서 지배 연산, 입력 분포, 자원 예산을 어떻게 봐야 하는지도 함께 정리한다.
Script Companion
오디오와 함께 스크립트 보기
- 01
정렬과 탐색은 자료구조와 알고리즘을 배울 때 자주 나오는 주제이지만, 실무에서는 훨씬 직접적인 성능 문제로 나타난다. 데이터를 정렬하고 찾는 작업은 전체 처리 시간의 상당 부분을 차지할 수 있고, 잘못된 알고리즘 선택은 수천 배의 성능 차이로 이어질 수 있다. JavaScript의 Array.sort가 왜 TimSort를 쓰는지, DB 인덱스가 왜 Binary Search 계열 원리를 활용하는지, Redis가 왜 LRU 캐시 정책을 쓰는지도 모두 이 축에서 연결된다.
- 02
Quick Sort는 피벗을 고르고, 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 나눈 뒤, 양쪽 파티션에 같은 과정을 재귀적으로 적용하는 분할 정복 정렬이다. 평균 시간복잡도는 O(n log n)이지만, 이미 정렬된 배열에서 첫 번째 요소를 계속 피벗으로 고르면 최악의 O(n²)이 된다. 그럼에도 실전에서 빠르게 보이는 이유는 배열 안에서 제자리 교환을 하며 캐시 지역성을 잘 활용하기 때문이다. Merge Sort와 같은 O(n log n)이라도, 새 배열을 만들며 병합하는 비용과 캐시 미스 차이가 상수 계수에서 2~3배 차이를 만들 수 있다.
- 03
Quick Sort의 최악 성능은 단순히 느린 알고리즘 문제가 아니라 보안 실패가 될 수 있다. McIlroy의 antiqsort 적대적 입력은 결정론적 피벗을 쓰는 qsort 구현을 quadratic으로 끌어내릴 수 있고, BSD qsort는 2^16 원소에서 무작위 입력 대비 약 1,000배 느려진 사례가 제시되어 있다. 같은 패턴은 Hash collision DoS에도 보인다. hash 함수가 결정론적이면 공격자가 같은 버킷에 몰리는 키를 만들어 O(1)을 O(n)으로 무너뜨릴 수 있다. 그래서 사용자 입력에 의존하는 정렬 키라면 randomized pivot, IntroSort 계열, 또는 표준 라이브러리 사용 여부를 확인해야 한다.
- 04
Merge Sort는 배열을 반으로 계속 나눈 뒤, 정렬된 절반들을 두 포인터로 병합한다. 피벗 선택이 없기 때문에 최선, 평균, 최악이 모두 O(n log n)으로 보장되고, 같은 값의 원래 순서를 유지하는 안정 정렬이라는 장점이 있다. 대신 병합 과정에서 O(n) 임시 배열이 필요하다. Heap Sort는 배열을 Max-Heap으로 만들고 루트의 최댓값을 배열 뒤로 보낸 뒤 heapify를 반복한다. 항상 O(n log n)을 보장하고 추가 메모리는 O(1)이지만, 같은 값의 원래 순서가 바뀔 수 있는 불안정 정렬이다.
- 05
실무에서 정렬은 가능하면 데이터베이스에 맡기는 것이 기본 방향이다. Nest.js와 TypeORM에서 정렬 결과가 필요할 때, DB 인덱스를 활용한 ORDER BY는 인메모리로 가져온 뒤 Array.sort를 하는 방식보다 네트워크 비용과 애플리케이션 메모리 부담을 줄일 수 있다. 단일 응답이 약 100,000행 곱하기 200바이트, 즉 약 20MB를 넘으면 V8 heap에서 정렬 사본과 JSON 직렬화 사본이 함께 커진다. Lambda 1.5GB 메모리 환경에서는 5~10 동시 요청부터 OOM 위험이 생길 수 있다. PostgreSQL 정렬은 work_mem 기본 4MB 안에서만 인메모리로 처리되고, 초과하면 tempdir로 spill한다.
- 06
JavaScript Array.sort는 V8 v7.0, Chrome 70부터 TimSort를 사용한다. TimSort는 Merge Sort와 Insertion Sort의 하이브리드이며, 작은 배열에서는 Insertion Sort를 쓰고 큰 배열에서는 정렬된 런을 병합한다. 핵심은 자연 런, 즉 이미 부분적으로 정렬된 구간을 감지한다는 점이다. 실무 데이터는 타임스탬프 기반 로그나 ID 순으로 삽입된 DB 레코드처럼 완전히 무작위가 아닌 경우가 많다. V8 공식 벤치마크의 DownDown 케이스에서는 기존 QuickSort 대비 17배 속도 향상이 확인되었지만, 완전 무작위 PACKED_SMI_ELEMENTS 마이크로벤치에서는 QuickSort가 더 빠른 경우도 있다.
- 07
Binary Search는 정렬된 데이터에서 탐색 범위를 절반씩 줄이는 방식이다. 1,000,000개의 데이터도 한 번 비교할 때마다 500,000, 250,000으로 줄어들기 때문에 최대 약 20번 비교로 도달할 수 있다. 여기서 전제 조건은 반드시 정렬되어 있어야 한다는 점이다. 구현에서는 left는 포함하고 right는 미포함하는 구간으로 관리하면 일관성이 좋아진다. 하지만 mid를 left와 right의 합으로 바로 계산하면 Java나 C++에서는 Int.MAX_VALUE를 넘을 때 오버플로우가 날 수 있다. 이 버그는 Java JDK의 java.util.Arrays.binarySearch에 약 9년간 숨어 있다가 2006년 Joshua Bloch가 보고했다.
- 08
Binary Search는 단일 값 탐색에서 끝나지 않는다. Lower Bound는 target 이상인 첫 번째 인덱스이고, Upper Bound는 target 초과인 첫 번째 인덱스다. DB의 BETWEEN, >=, <= 같은 범위 쿼리는 이런 시작과 끝 위치를 찾은 뒤 그 사이를 순차 스캔하는 방식으로 이해할 수 있다. 정렬은 탐색을 위한 전처리이기도 하다. 한 번 O(n log n)의 정렬 비용을 지불하면 이후 탐색은 O(log n)으로 줄어든다. 또 정렬된 배열이 아니더라도 조건이 단조 증가하거나 단조 감소한다면 정답에 Binary Search를 적용할 수 있다. 문서에서는 AWS Step Functions의 병렬 작업 배분과 Lambda 배치 크기 최적화에도 이 패턴을 연결한다.
- 09
LRU Cache는 가장 오래 사용하지 않은 항목을 제거하는 캐시 정책이다. get과 put을 모두 O(1)에 처리하려면 HashMap과 Doubly Linked List의 조합이 필요하다. HashMap은 key에서 노드 참조로 바로 접근하게 해 주지만, 어떤 키가 오래되었는지는 알려주지 않는다. LinkedList는 순서를 관리하지만 특정 키를 찾으려면 O(n) 순회가 필요하다. 둘을 합치면 HashMap으로 노드를 찾고, 이중 연결 리스트로 최근 사용 순서를 O(1)에 바꿀 수 있다. 특히 이중 연결이어야 하는 이유는 삭제할 때 이전 노드가 필요하기 때문이다. 단방향 리스트라면 이전 노드를 찾기 위해 head부터 다시 순회해야 한다.
- 10
LRU는 Redis, 브라우저 캐시, CDN 캐시, CPU 캐시 같은 곳에서 실무적으로 연결된다. NestJS의 @nestjs/cache-manager도 TTL과 max 옵션으로 용량을 제한하면 인메모리 LRU 정책으로 오래된 항목을 제거한다. Redis에서는 allkeys-lru는 모든 키에 LRU를 적용하고, volatile-lru는 TTL이 설정된 키에만 LRU를 적용한다. 다만 Redis는 정확한 LRU가 아니라 근사 LRU를 사용한다. 모든 키의 접근 시간을 추적하면 메모리가 커지기 때문에 maxmemory-samples 기본값 5개의 키를 샘플링하고 그중 오래된 것을 삭제한다. 샘플을 10으로 올리면 추가 CPU 비용을 내는 대신 이론적 LRU에 더 가까워진다.
- 11
문자열 검색은 길이 n의 텍스트에서 길이 m의 패턴을 찾는 문제다. Brute Force는 모든 위치에서 하나씩 비교하므로 O(n 곱하기 m)이 될 수 있다. KMP는 실패한 비교 정보를 버리지 않고 실패 함수를 이용해 어느 위치부터 다시 비교할지 정한다. Rabin-Karp는 문자열을 해시값으로 바꿔 비교하고, 해시가 같을 때만 실제 문자를 비교한다. 이때 Rolling Hash로 해시 재계산을 O(1)에 처리한다. Trie는 공통 접두사를 공유하는 트리 구조로, APP, APPLE, APPLICATION처럼 같은 접두사를 한 번만 저장하고 분기한다. 검색과 삽입은 검색어 길이 m에 의존하며, 자동완성, 사전 검색, IP 라우팅 테이블에 활용된다.
- 12
새 알고리즘을 만났을 때는 세 가지 질문으로 도입 여부를 점검할 수 있다. 첫째, 이 워크로드의 지배 연산이 무엇인지 봐야 한다. get인지, insert인지, range scan인지, prefix match인지에 따라 SLA를 좌우하는 복잡도가 달라진다. 둘째, 입력 분포가 무작위인지, 단조 증가인지, 부분 정렬인지, 스큐가 있는지 확인해야 한다. QuickSort가 정렬된 배열과 마지막 피벗 조합에서 O(n²)으로 무너지는 것처럼, 분포 가정이 깨지면 최악 케이스가 나타난다. 셋째, 빡빡한 자원이 시간인지, 메모리인지, 캐시 미스인지, 네트워크 라운드트립인지 구분해야 한다.
- 13
트러블슈팅 관점에서는 증상과 원인을 분리해 봐야 한다. Array.sort가 숫자를 이상하게 정렬한다면 비교 함수가 없어서 요소를 문자열로 변환하고 사전순으로 정렬했을 가능성이 높다. Binary Search가 무한 루프에 빠지거나 값을 놓친다면 mid 오버플로우, left와 right 경계 조건 불일치, 또는 정렬되지 않은 배열 적용을 의심해야 한다. LRU Cache에서 put이 느려진다면 배열로 순서를 관리해 특정 위치 삭제가 O(n)이 되었을 수 있고, get 호출 뒤 MRU 이동이 안 된다면 현재 노드 제거와 앞쪽 삽입 중 하나가 빠졌을 수 있다. 정리하면, 정렬은 입력 분포와 자원 예산에 따라 선택하고, 탐색은 정렬 또는 단조 조건을 이용하며, LRU는 HashMap과 Doubly Linked List의 조합으로 get과 put의 O(1)을 맞춘다.
같은 레이어