배열
배열의 100만 번째 값을 읽는 데는 한 단계면 되지만, 같은 배열 맨 앞에 값 하나를 넣으면 값 100만 개가 자리를 옮깁니다.
자료 구조란
이름 목록, 인쇄 대기 줄, 가격표를 다루는 프로그램은 그 데이터를 어딘가에 담아 두고 질문에 답해야 합니다. 세 번째 항목은 무엇인지, 이 이름이 목록에 있는지, 다음 차례는 어느 작업인지 같은 질문입니다. 자료 구조는 데이터를 담는 방식과 이런 질문에 답하는 방법을 함께 일컫는 말입니다. MIT의 6.006 강의는 여기서 두 가지를 나눕니다. 인터페이스는 「i번째 항목 가져오기」, 「끝에 항목 더하기」처럼 요청할 수 있는 연산의 목록입니다. 자료 구조는 그 연산을 메모리에서 실제로 처리하는 방법입니다. 인터페이스 하나 뒤에 여러 자료 구조가 있을 수 있고, 속도 차이는 아주 큽니다.
알고리즘 과정과 마찬가지로 이 과정도 단계 수를 셉니다. 그래야 초시계 없이 두 자료 구조를 비교할 수 있습니다. 이 단원에서 한 단계는 메모리 칸 하나를 읽거나 쓰는 일입니다. 아래 실험실이 그 수를 세어 줍니다.
나란히 붙은 칸 한 덩어리
배열은 값을 끊기지 않은 메모리 한 덩어리에 담습니다. 칸의 크기는 모두 같고, 번호는 0부터 매깁니다. 배열을 빨리 읽을 수 있는 까닭이 이 배치에 있습니다. 덩어리가 주소 s에서 시작하고 칸 하나가 c바이트라면, a[i]는 주소 s + i × c에 있습니다. 컴퓨터는 곱셈 한 번과 덧셈 한 번으로 그 주소를 구해 바로 찾아갑니다. i가 3이든 3,000,000이든 똑같습니다. MIT 강의 노트는 배열의 「get at(i)」와 「set at(i, x)」를 Θ(1)로 적습니다. 길이가 늘어도 비용이 늘지 않는다는 뜻입니다.
같은 배치 때문에 가운데를 바꾸는 일은 느립니다. 배열에 7, 3, 9, 4, 6이 들어 있고 맨 앞에 1을 넣고 싶다고 해 봅시다. 7 앞에는 빈칸이 없으므로 먼저 모든 값을 한 칸씩 오른쪽으로 옮겨야 합니다. 덮어쓰지 않으려면 맨 뒤 값부터 옮깁니다. 옮기기 5번과 쓰기 1번, 모두 6단계입니다. 맨 앞 값을 빼는 일은 반대입니다. 그 값을 읽고 나머지 4개를 한 칸씩 왼쪽으로 옮깁니다. 값이 n개인 배열의 i번 자리에 넣으려면 n − i번 옮기고 한 번 써야 하므로, 맨 앞이 가장 비싸고 맨 끝이 가장 쌉니다.
끌어서 돌리고, 휠이나 두 손가락으로 확대하세요.
블록이 가득 차면
메모리 블록은 크기가 정해져 있습니다. 칸이 다 찼는데 값을 더하면 어떻게 될까요? 배열은 더 큰 새 블록을 받아 모든 값을 옮겨 적은 뒤에야 새 값을 쓸 수 있습니다. 실험실에서 5칸이 다 찬 블록에 끝에 넣기를 하면 옮겨 적기 5번과 쓰기 1번이 듭니다. 매번 한 칸씩만 늘린다면 넣을 때마다 전부 옮겨 적어야 하고, n번 넣는 데 약 n²/2번을 옮겨 적게 됩니다.
MIT 강의 노트가 설명하는 해결책은 한 번에 크게, 예를 들어 두 배로 늘리는 것입니다. 용량 1에서 시작하면 값이 1, 2, 4, 8, 16개일 때 옮겨 적기가 일어나므로, 17번 넣는 동안 옮겨 적기는 모두 1 + 2 + 4 + 8 + 16 = 31번입니다. 한 번 넣을 때 2번이 안 됩니다. 넣기 한 번이 느릴 때도 있지만 길게 보면 넣기마다 일정한 비용으로 평균이 맞춰집니다. 이것을 분할 상환(amortized) Θ(1) 시간이라고 합니다. 자바스크립트 배열도 겉으로는 이렇게 움직입니다. MDN은 배열을 크기가 바뀌는 것으로 설명하고, push와 pop은 비용이 싼 끝쪽에서 일합니다.
| 값 n개에 대한 연산 | 실험실의 단계 수 | 증가 정도 |
|---|---|---|
| a[i] 읽기·쓰기 | 1 | Θ(1) |
| 맨 앞에 넣기 | 옮기기 n + 쓰기 1 | Θ(n) |
| 맨 앞 빼기 | 읽기 1 + 옮기기 (n − 1) | Θ(n) |
| 끝에 넣기(빈칸 있음) | 1 | Θ(1) |
| 끝에 넣기(가득 참) | 옮겨 적기 n + 쓰기 1 | 한 번은 Θ(n), 분할 상환 Θ(1) |
const a = [7, 3, 9, 4, 6];
console.log(a[3]); // 4, one step
a.push(8); // cheap: the end
a.unshift(1); // every value moves one cell right
console.log(a.join(" ")); // 1 7 3 9 4 6 8| 인터페이스 | get at(i), insert last(x)처럼 요청할 수 있는 연산 목록. |
| 자료 구조 | 그 연산을 메모리에서 실제로 처리하는 방법. |
| 배열 | 같은 크기 칸이 붙은 한 덩어리. a[i]는 시작 + i × 칸 크기에 있음. |
| 동적 배열 | 더 큰 블록(보통 두 배)으로 옮겨 적으며 늘어나는 배열. |
| 분할 상환 비용 | 몇몇 연산이 느려도 긴 연산 묶음에서 연산 하나당 평균 비용. |
- 이 단원의 단계 세기로, 값 1,000,000개짜리 배열에서 a[700000]을 읽는 데 몇 단계가 걸릴까요?
- 1
- 20
- 700,000
- 1,000,000
- 7, 3, 9, 4, 6이 든 배열에 빈칸이 넉넉합니다. 맨 앞에 값을 넣는 데 몇 단계가 걸릴까요(옮기기와 쓰기 합)?
- 같은 값 5개짜리 배열에서 맨 앞 값을 빼는 데 몇 단계가 걸릴까요(읽기 1번과 옮기기)?
- 빈칸이 있는 값 5개짜리 배열(자리 0~4)의 2번 자리에 넣으면 몇 단계일까요?
- 두 배씩 늘어나는 배열에 값 5개가 있고 용량도 5입니다. 값 하나를 끝에 넣으면 몇 단계일까요?
- 그 넣기가 끝난 뒤 용량은 얼마일까요?
- 용량 1에서 시작해 두 배씩 늘릴 때, 17번 넣는 동안 옮겨 적기는 모두 몇 번일까요?
- 두 배로 늘어나는 배열의 끝에 넣기를 왜 분할 상환 Θ(1)이라고 할까요?
- 넣기마다 정확히 한 단계가 걸려서
- 옮겨 적기가 드물어 n번 넣는 비용 합이 n의 상수배를 넘지 않아서
- 컴퓨터가 뒤에서 공짜로 옮겨 적어서
- 자바스크립트는 배열을 옮겨 적지 않아서
- MIT 6.006 용어로 「insert last(x)와 delete last()」는 무엇일까요?
- 자료 구조
- 인터페이스
- 메모리 주소
- 정렬 방법
- 길이가 n이고 0부터 세는 배열에서 마지막 값의 번호는?
- n
- n − 1
- n + 1
- 1
- 인터페이스는 연산 목록이고, 자료 구조는 그 연산을 처리하는 방법입니다.
- 배열은 값을 한 덩어리에 담으므로 a[i]는 한 단계입니다.
- 맨 앞 근처에서 넣거나 빼면 값 약 n개가 옮겨집니다.
- 두 배로 늘어나는 배열에서 끝에 넣기는 분할 상환 Θ(1)입니다. 용량 1에서 17번 넣으면 31번 옮겨 적습니다.
이 과정의 출처 (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