자료 구조 고르기
키 1,023개 중에서 없는 키를 찾을 때 선형 탐색은 비교를 1,023번, 이진 탐색은 10번 하고, 칸 1,023개짜리 해시 테이블은 실험실에서 많아야 6번이었습니다.
던질 질문에서 출발하기
모든 일에 가장 좋은 자료 구조는 없습니다. 어떤 연산을 싸게 만들면 다른 연산이 비싸지므로, 고를 때는 프로그램이 가장 자주 할 일을 먼저 적어 봅니다. MIT 6.006은 가능한 경우를 두 인터페이스로 나눕니다. 순서열(sequence)은 내가 정한 순서(첫째, 둘째, 셋째)로 항목을 두고 자리로 항목을 찾습니다. 집합(set)은 키로 항목을 두고, 그 키가 있는지, 가장 작은 키는 무엇인지, 어떤 키 다음 키는 무엇인지 묻습니다. 순서 질문이 없는 집합을 사전(dictionary)이라고 합니다.
흔한 상황 몇 가지와 보통의 답입니다.
- 자리로 항목을 읽고 끝에 더하기: 동적 배열(자바스크립트 배열).
- 되돌리기 기록, 괄호 짝 맞추기, 깊이 우선 탐색: 스택. 배열을 끝에서만 쓰는 것입니다.
- 도착 순서대로 처리하는 작업, 너비 우선 탐색: 큐. 긴 배열에 shift를 쓰기보다 head 번호나 고리 버퍼를 씁니다.
- 이름이나 번호로 찾기: 해시 테이블. 자바스크립트에서는 Map이나 Set입니다.
- 넣고 지우면서도 키를 정렬된 상태로 두고, 다음 키를 묻기: 균형 잡힌 이진 탐색 트리.
- 이미 쥐고 있는 자리에서 자주 넣고 지우기: 연결 리스트.
다섯 자료 구조에서 같은 찾기
아래 실험실은 같은 키를 다섯 가지 방식으로 담고, 그중 하나를 찾는 데 필요한 비교 횟수를 셉니다. 키는 무작위 정수 15개, 127개, 1,023개 중에서 고릅니다. 정렬되지 않은 배열은 선형 탐색을 씁니다. 정렬된 배열은 이진 탐색을 씁니다. 균형 트리는 가운데 키부터 넣어서 가능한 한 낮게 만들었습니다. 다른 트리는 키를 정렬된 순서로 넣어 사슬이 되었습니다. 해시 테이블은 키 수만큼 칸을 두고, h(k) 계산을 1로 셉니다.
끌어서 돌리고, 휠이나 두 손가락으로 확대하세요.
키가 15개면 차이가 작습니다. 선형 탐색은 평균 8번, 이진 탐색은 약 3.3번입니다. 키가 1,023개면 다릅니다. 선형 탐색은 평균 512번이고 없는 키라면 1,023번이 필요하지만, 이진 탐색과 균형 트리는 10번을 넘지 않습니다. 사슬 트리는 선형 탐색만큼 나쁩니다. 해시 테이블은 사슬이 짧게 유지되어 어느 크기에서나 평균 2.3~2.5번이고, 이 실험실에서 키 1,023개일 때 가장 나쁜 경우도 6번이었습니다. 찾기에 Map을 기본으로 쓰는 까닭이 이것이고, 정렬된 구조는 순서까지 필요할 때만 들일 만한 값어치가 있습니다.
| 자리로 다루기 | i번 항목 가져오기 | 맨 앞 넣기·지우기 |
|---|---|---|
| 동적 배열 | 1 | n |
| 연결 리스트 | n | 1 |
| 정렬된 배열 | 1 | n |
| 키로 다루기 | 찾기 | 넣기 | 다음 키 |
|---|---|---|---|
| 배열·리스트 | n | n | n |
| 정렬된 배열 | log n | n | log n |
| 해시 테이블 | 평균 1 | 평균 1 | n |
| 균형 BST | log n | log n | log n |
두 표의 칸마다 항목 n개일 때 비용이 늘어나는 정도를 MIT 강의 노트 2, 4, 7강의 표를 따라 적었습니다. 해시 테이블과 탐색 트리는 자리가 아니라 키로 일하므로 두 번째 표에만 있습니다. 정렬되지 않은 배열이나 리스트에 키를 넣으려면 먼저 그 키가 이미 있는지 확인해야 해서 n이 듭니다. 정렬된 배열은 빨리 찾지만 새 키가 들어갈 자리를 만들려면 값을 옮겨야 합니다.
Map일까 객체일까
자바스크립트 프로그램은 일반 객체를 사전처럼 쓰는 일이 많아서 prices["apple"]처럼 씁니다. MDN은 키가 데이터에서 올 때 Map을 쓸 이유를 몇 가지 듭니다. 객체에는 프로토타입이 있어서 내 키와 겹칠 수 있는 기본 키가 들어 있습니다. Map은 문자열과 심볼뿐 아니라 어떤 값이든 키로 씁니다. 크기는 map.size 속성 하나로 알 수 있습니다. 넣은 순서대로 순회합니다. 이름이 정해진 칸 몇 개로 된 기록이라면 여전히 객체가 자연스럽습니다.
- 1953: H. P. 룬의 IBM 메모가 칸에 나눠 넣는 해싱과 체이닝을 제안합니다.
- 1956년 무렵: 뉴얼, 쇼, 사이먼의 IPL이 연결 리스트를 선보입니다.
- 1957: 바우어와 자멜존이 스택 방법으로 특허를 출원하고, 배열을 갖춘 포트란이 나옵니다.
- 1962: 아델손벨스키와 란디스가 처음 나온 균형 탐색 트리인 AVL 트리를 발표합니다.
- 2015: ECMAScript 2015가 자바스크립트에 Map과 Set을 더합니다.
- 키 1,023개 중에서 없는 키를 선형 탐색하면 비교가 몇 번일까요?
- 정렬된 키 1,023개에서 이진 탐색은 비교를 최대 몇 번 할까요?
- 키 15개를 선형 탐색할 때 15개 키 전부에 대한 평균 비교 횟수는?
- 키 127개를 정렬된 순서로 넣어 만든 BST에서 가장 큰 키를 찾으면 비교가 몇 번일까요?
- 글 편집기에 되돌리기가 필요합니다. 맞는 자료 구조는?
- 큐
- 스택
- 해시 테이블
- 정렬된 배열
- 인쇄 서버는 들어온 순서대로 작업을 처리해야 합니다. 맞는 자료 구조는?
- 큐
- 스택
- BST
- 스택처럼 쓴 연결 리스트
- 초마다 여러 번 id로 사용자 기록을 찾아야 합니다. 자바스크립트에서 보통 고르는 것은?
- 반복문으로 뒤지는 배열
- id를 키로 쓰는 Map
- 스택
- 연결 리스트
- 넣고 지우면서도 키를 정렬된 상태로 두고, 다음으로 큰 키를 자주 물어야 합니다. 가장 맞는 것은?
- 해시 테이블
- 균형 BST
- 큐
- 정렬 안 된 배열
- MIT 6.006 용어로 순서 연산이 없는 집합을 무엇이라고 할까요?
- 순서열
- 사전
- 스택
- 큐
- MDN에 따르면 데이터에서 온 키를 담는 사전으로 일반 객체를 쓰면 왜 위험할 수 있을까요?
- 객체는 문자열을 담지 못해서
- 프로토타입에서 온 기본 키가 내 키와 겹칠 수 있어서
- 객체가 늘 배열보다 느려서
- 객체가 1초 뒤 값을 잊어서
- 가장 자주 할 연산을 기준으로 고릅니다.
- 순서열: 배열, 연결 리스트, 스택, 큐. 집합: 해시 테이블, BST.
- 키 1,023개라면 선형 탐색은 최대 1,023번, 이진 탐색과 균형 트리는 최대 10번입니다.
- 자바스크립트의 기본 사전은 Map이고, 순서까지 필요하면 균형 트리를 씁니다.
이 과정의 출처 (5)
- MIT OpenCourseWare 6.006 Introduction to Algorithms, Spring 2020 (Demaine, Ku, Solomon), lecture notes 2 Data Structures (interface vs data structure, Sequence and Set interfaces, stack = insert_last/delete_last, queue = insert_last/delete_first, array, linked list, dynamic array, amortized Θ(1) append), 4 Hashing (chaining, pigeonhole collisions, chain length n/m), 6 Binary Trees Part 1 (height, traversal order, O(h) operations) and 7 Binary Trees Part 2: AVL (Adelson-Velsky and Landis, 1962) at ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/pages/lecture-notes
- MDN Web Docs, Array.prototype.shift (shifts all values left by 1), Array.prototype.unshift, Map (insertion order, Map vs Object, spec requires sublinear average access) and Set (developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects)
- ECMAScript 2025 Language Specification (tc39.es/ecma262), 24.1 Map Objects and 24.2 Set Objects ("must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements"), Array.prototype.shift steps (Repeat, while k < len: move element k to k - 1)
- D. E. Knuth, The Art of Computer Programming vol. 3 (2nd ed. 1998) section 6.4 History (H. P. Luhn, IBM internal memorandum January 1953, hashing with chaining; digit pairs added mod 10, 31415926 -> 4548) via gwern.net copy, and IEEE Spectrum, "Hans Peter Luhn and the Birth of the Hashing Algorithm" (2018)
- "A brief history of the stack", SIGCIS (sigcis.org/files/A brief history.pdf: Bauer and Samelson applied for the patent in 1957, US 3,047,228 granted July 31, 1962; IPL list processing by Newell, Simon and Shaw at RAND 1956) and Wikipedia, Information Processing Language (Newell, Shaw, Simon, RAND and Carnegie Institute of Technology, about 1956).
확인한 날: 2026-10-18