"배열이 대단한 건 많이 담아서가 아니야. 한 줄로 담았기 때문에 그중 아무거나 뒤지지 않고 계산으로 짚어낼 수 있다는 게 대단한 거지."
똑같은 상자가 한 줄로
메모리를 번지수가 끝없이 이어지는 길이라고 생각해 봐. 배열은 그 길 어느 주소에서 시작해 크기가 똑같은 상자를 빈틈없이 붙여 놓은 한 구간이야. 0번 상자가 시작 지점이고, 1번은 바로 그 옆, i번째는 시작 지점에서 상자 너비만큼 i칸 간 자리야.
이 배치가 핵심이야. 컴퓨터는 i번째 원소를 찾으려고 배열을 뒤지지 않아. address = base + i × box_size로 주소를 바로 계산해 버리지. 곱셈 한 번, 덧셈 한 번, 그리고 그 자리로 점프. 그래서 arr[5]와 arr[5_000_000]이 걸리는 시간이 똑같아. 둘 다 주소 계산 한 번이거든. 이걸 임의 접근(random access)이라고 부르고, 배열을 배열이게 하는 초능력이 바로 이거야.
배열의 성질은 전부 여기서 따라 나와
"똑같은 상자가 한 줄로"라는 그림만 붙잡고 있으면, 배열의 성질은 하나하나 외울 게 없어져.
- 인덱싱은 O(1). 주소만 계산하면 되니까.
- 상자 크기는 다 같아야 해. 크기가 들쭉날쭉하면 주소 공식이 바로 깨지거든. 배열이 한 가지 타입만 담는 이유가 이거고, 문자열처럼 길이가 제각각인 값을 여러 언어가 그 값을 가리키는 포인터 배열로 저장하는 이유도 이거야.
- 중간에 끼워 넣으면 O(n). 빈틈이 없으니 자리 하나 만들려면 뒤쪽 상자를 전부 밀어야 해.
- 저수준에서는 크기가 고정이야. 늘리려면 더 큰 블록을 새로 잡고 통째로 복사해야 해. 분할 상환 분석에서 두 배씩 키우는 모델로 봤던 그 동작이 여기 붙는 거지.
배열은 한 덩어리로 붙은 메모리에 같은 크기 칸이 늘어선 구조야. 이 사실 하나가 O(1) 임의 접근(address = base + i × size)을 만들고, 배열의 나머지 비용까지 전부 설명해.
조용한 보너스: 캐시 지역성
붙어 있다는 사실에는 선물이 하나 더 딸려 와. CPU는 배열 원소 하나를 읽을 때 그 주변 덩어리째로 초고속 캐시에 올려놔. 다음에 옆 원소를 찾을 거라고 미리 걸어두는 건데, 배열에서는 그 예상이 거의 맞아. 그래서 배열을 훑는 건 이론상 O(n)일 뿐 아니라 실제로도 빠른 O(n)이야. 달라고 하기도 전에 다음 원소가 이미 손에 들어와 있으니까. 이건 기억해 둬. 연결 리스트에 가면 노드가 흩어져 있어서 이 이점을 통째로 날리는데, 그 차이는 빅오만 봐서는 안 보이거든.
피파의 고백
arr[i]가 O(1)이라는 건 이유를 알기 한참 전부터 외우고 있었어. 그냥 컴퓨터가 "뭘 찾는 걸 잘하나 보다" 하고 넘겼지. 아빠가 상자 늘어선 길이랑 base + i × size 공식을 그려주고 나서야 그게 마법이 아니게 됐어. 컴퓨터는 i번째 원소를 찾는 게 아니라 어디 있을 수밖에 없는지 계산해서 곧장 가는 거였어. 이유를 알고 나니까 외운 사실이 언제든 다시 끌어낼 수 있는 것으로 바뀌더라.