자료구조 선택이 성능을 바꾸는 방식
자료구조는 데이터를 어떻게 배치하고 접근할지 결정하고, Big-O는 그 결정이 입력 크기와 함께 어떤 비용으로 커지는지 보여준다. Array, Linked List, Stack, Queue, Hash Table의 원리와 실무 선택 기준, 그리고 JavaScript와 백엔드 환경에서 자주 만나는 실패 모드를 함께 정리한다.
Script Companion
오디오와 함께 스크립트 보기
- 01
자료구조를 배우는 이유는 코딩 테스트만이 아니다. 백엔드 코드에서 같은 기능이라도 어떤 구조를 쓰느냐에 따라 API 응답 속도가 O(1)에 가까워질 수도 있고, O(n²)로 무너질 수도 있다. DB 설계에서도 Hash Index와 B-Tree Index의 선택은 Hash Table의 원리를 알아야 판단할 수 있다. NestJS의 BullMQ나 AWS SQS처럼 익숙한 메시지 큐와 작업 큐도 결국 Queue 자료구조 위에 올라간 추상화다.
- 02
먼저 Big-O Notation은 입력 크기 n이 커질 때 연산 횟수나 메모리 사용량이 어떻게 증가하는지 표현하는 도구다. 창고 번호를 알고 바로 꺼내면 O(1), 전화번호부처럼 반씩 줄여 찾으면 O(log n), 처음부터 끝까지 뒤지면 O(n), 모든 항목끼리 서로 비교하면 O(n²)라고 볼 수 있다. Big-O는 보통 최악의 경우를 기준으로 보고, 3n² 더하기 5n 더하기 100 같은 식에서는 가장 큰 성장 항만 남겨 O(n²)로 본다.
- 03
Big-O가 상수를 무시하는 이유는 입력이 충분히 커질 때 성장 속도의 차이가 상수 차이보다 훨씬 중요해지기 때문이다. 3n²과 100n²은 둘 다 n이 두 배가 되면 네 배로 커지지만, n은 두 배만 커진다. 다만 실무에서는 상수도 중요하다. 같은 O(n log n)이라도 Quick Sort와 Merge Sort의 실제 속도는 캐시 적중률이나 함수 호출 오버헤드 때문에 달라질 수 있으므로, Big-O는 설계 단계의 큰 그림이고 실제 튜닝은 프로파일링으로 확인해야 한다.
- 04
분할 상환 분석도 함께 봐야 한다. JavaScript의 Array.push()는 보통 O(1)이지만, 내부 배열이 꽉 차면 더 큰 공간으로 재할당하면서 한 번은 O(n)이 될 수 있다. 그러나 n번의 push 전체를 평균내면 각 push는 O(1)로 볼 수 있고, 이것이 분할 상환 O(1)이다. AWS Lambda에서는 실행 시간과 메모리 크기가 비용으로 이어지므로, O(n²) 로직은 데이터가 두 배 늘 때 실행 시간과 요금이 네 배로 커질 수 있다.
- 05
Array와 Linked List는 메모리 배치 방식이 다르다. Array는 강의실 좌석처럼 번호가 붙은 연속 공간이라 인덱스 접근이 O(1)이다. 반면 Linked List는 보물찾기 쪽지처럼 각 노드가 다음 노드를 가리키므로 원하는 위치까지 처음부터 따라가야 한다. 맨 앞 삽입은 Linked List가 O(1)이고 Array는 O(n)이지만, 중간 삽입이나 삭제는 둘 다 대상을 찾는 탐색 비용이 필요하다. 맨 뒤 삽입은 Array가 보통 O(1)이고, Linked List는 tail 포인터가 있을 때 O(1)이 된다.
- 06
이론과 실제 성능이 갈리는 지점은 CPU 캐시다. Array는 메모리에 연속 배치되어 L1이나 L2 캐시에 한 번에 올라가기 쉽고, x86-64의 64바이트 캐시 라인에서는 4바이트 정수 16개가 함께 적재된다. 반면 Linked List 노드는 메모리에 흩어져 있어 노드 점프마다 캐시 미스를 만들기 쉽다. 문서는 L1 hit를 약 1ns, DRAM 접근을 60에서 100ns로 제시하며, 같은 O(n) 순회라도 실측 차이가 크게 날 수 있다고 설명한다.
- 07
이 캐시 우위가 항상 절대적인 것은 아니다. Linked List 노드를 메모리 풀이나 slab allocator로 연속 할당하면 차이가 줄어들 수 있으므로, 정확한 명제는 범용 malloc 환경에서는 Array가 보통 유리하다는 쪽에 가깝다. JavaScript에서는 V8의 GC 힙 위에서 동작하므로 사용자 코드가 연속 할당을 강제하기 어렵고, 실무에서는 대부분 Array나 동적 배열을 기본으로 선택하는 이유가 된다. 또한 JS 배열에 중간 구멍을 만들거나 혼합 타입을 담으면 V8 최적화가 해제되어 성능이 급격히 떨어질 수 있다.
- 08
Stack, Queue, Deque는 순서를 다루는 자료구조다. Stack은 접시 더미처럼 마지막에 넣은 것을 먼저 꺼내는 LIFO, Last In, First Out 구조다. Queue는 줄서기처럼 먼저 들어온 것이 먼저 나가는 FIFO, First In, First Out 구조다. Deque는 양쪽 끝에서 넣고 뺄 수 있는 Double-ended Queue다. NestJS의 Exception Filter와 stack trace는 함수 호출 스택의 관점으로 이해할 수 있고, BullMQ와 AWS SQS는 비동기 작업이나 메시지를 Queue 원리로 처리한다.
- 09
Hash Table은 해시 함수로 키를 버킷 인덱스에 매핑해 빠르게 찾는 구조다. 도서관에서 책 제목을 규칙으로 바꿔 서가 번호를 정하고, 나중에도 같은 규칙으로 바로 찾아가는 식으로 이해할 수 있다. JavaScript Object는 V8에서 고정 구조일 때 Fast Mode와 Hidden Class 기반으로 빠르게 접근하지만, 동적으로 프로퍼티가 추가되거나 delete obj.key가 쓰이면 Dictionary Mode, 즉 Hash Map 구조로 전환되어 느려질 수 있다. JavaScript Map은 항상 해시 테이블 기반이고, V8은 Open Addressing과 선형 탐사를 사용한다고 설명한다.
- 10
해시 충돌은 서로 다른 키가 같은 버킷 인덱스로 매핑되는 현상이다. Chaining은 같은 버킷에 연결 리스트로 묶고, Open Addressing은 테이블 안의 다른 빈 슬롯을 찾는다. Chaining은 추가 포인터가 필요하고 캐시 성능이 낮을 수 있지만 삭제가 단순하고, Open Addressing은 연속 메모리 덕분에 캐시 성능이 좋지만 부하율을 보통 80% 이하로 관리하고 삭제 표시가 필요하다. 최악에는 모든 키가 한 버킷으로 몰려 O(1) 평균 조회가 O(n)으로 떨어진다.
- 11
이 최악 성능은 실제 보안 문제인 Hash DoS로 이어질 수 있다. V8과 Node.js는 런타임 random seed를 hash 계산에 섞어 충돌 예측을 어렵게 만들고, startup snapshot으로 seed가 고정되는 문제는 deserialize 이후 rehash하는 방식으로 Node.js v8.3.0부터 재활성화했다고 문서는 설명한다. 2025년 V8이 비밀 시드를 가진 비암호 해시로 교체했다가 CVE-2025-27209로 다시 시드 기반으로 보강한 사례도 있다. Java 8 HashMap은 TREEIFY_THRESHOLD = 8과 MIN_TREEIFY_CAPACITY = 64 조건에서 버킷을 Red-Black Tree로 바꿔 O(log n) fallback을 제공한다.
- 12
Map과 Object의 선택 기준은 내부 동작을 기준으로 잡아야 한다. 키가 동적으로 추가되거나 삭제되면 Map이 유리하고, 특히 delete 연산이 빈번하면 Object의 최적화를 깨뜨릴 수 있으므로 Map을 선택하는 것이 낫다. 키가 고정된 설정 객체라면 Object가 적합하고 JSON 직렬화도 쉽다. 문자열이 아닌 숫자나 객체를 키로 써야 하면 반드시 Map을 써야 한다. 조회는 비슷하거나 Hidden Class 최적화가 살아 있는 Object가 약간 빠를 수 있지만, 삽입, 삭제, 순회에서는 Map이 유리한 경우가 많다.
- 13
인터뷰와 코딩 테스트에서는 자료구조 선택이 O(n²)을 O(n)으로 바꾸는 핵심이 된다. Two Sum은 지금 원소의 보수가 이미 나왔는지를 Hash Map으로 O(1)에 확인해 전체를 O(n)으로 낮춘다. Sliding Window는 고정 또는 가변 크기 구간을 움직이며 합, 최대, 최소를 구하고, Queue나 Deque를 사용해 중복 계산을 줄인다. Stack은 이전 상태를 되돌아봐야 하는 괄호 매칭이나 monotonic stack 문제에서 자주 쓰이며, 문서는 AWS CloudWatch의 다음 알림 임계값 초과 시점 찾기 같은 분석과도 연결한다.
- 14
실전 선택 기준은 질문으로 좁혀가면 된다. 중복 검사가 n > 1,000을 넘으면 Array.includes를 반복해 O(n²)을 만들기보다 Set.has를 고려한다. 최솟값을 반복 추출하고 n > 100이면 매번 Array.sort를 하는 대신 Min Heap이 맞다. 키-값 검색이 n > 100이면 Object와 for-in 탐색보다 Map.get이 적합하다. 앞쪽 삽입과 삭제가 빈번하면 Array.shift의 O(n)을 피하고 Linked List나 Deque를 고려한다. 정렬된 범위 쿼리에는 Hash Table보다 BST나 B-Tree 계열이 맞다.
- 15
메모리 제약이 있는 Lambda나 컨테이너에서는 공간 복잡도도 비용이다. 문서는 n > 100만 개 숫자라면 일반 Array의 약 40MB 대신 Float64Array의 약 8MB로 5배 메모리를 줄일 수 있다고 설명한다. 요소당 오버헤드도 다르다. Array 정수는 약 8바이트지만 Object는 Hidden Class와 프로퍼티 디스크립터 때문에 약 40에서 100바이트, Map은 항목당 약 50에서 80바이트, Linked List 노드는 값과 포인터와 객체 헤더 때문에 약 48바이트가 든다.
- 16
마지막으로 실패 모드를 기억해두면 실무에서 바로 도움이 된다. Array.unshift()와 Array.shift()는 앞쪽 요소를 다루며 전체 이동을 만들기 때문에, BFS나 작업 큐에서 반복하면 O(n²) 시간 초과로 이어질 수 있다. Hash Table이 O(1)인데 DB 쿼리가 왜 느린지 묻는다면, 자료구조 복잡도는 연산 횟수이고 실제 성능은 메모리 접근과 디스크 I/O 같은 연산 비용까지 곱해진 결과라고 설명해야 한다. NestJS에서 모듈 스코프 Map이나 Set에 요청별 임시 데이터를 계속 쌓으면 OOM으로 죽을 수 있으므로 제거 정책도 자료구조 선택의 일부다.
같은 레이어