배열

배열은 같은 종류의 값 여러 개를 한 줄로 담아 두고 번호로 곧바로 꺼내게 해 주는 자료구조입니다. 몇 번째 값이든 꺼내는 데 걸리는 시간이 같습니다. 대신 중간에 값을 끼워 넣거나 빼려면 뒤쪽 값을 전부 옮겨야 합니다.

상세

이 절은 배열이 번호로 값을 곧바로 꺼내는 원리와 그 원리 때문에 치르는 대가를 다룹니다. 메모리에 값이 놓이는 모양을 그림으로 먼저 보고, 연산마다 걸리는 시간은 표로 모읍니다.

배열은 아파트의 우편함 줄과 닮았습니다. 우편함은 같은 크기로 한 줄로 붙어 있습니다. 호수만 알면 그 칸을 바로 엽니다. 다만 줄 중간에 새 우편함을 끼우려면 뒤쪽 우편함을 전부 밀어야 합니다.

번호로 값을 찾는 원리

배열은 값들을 메모리에 빈틈 없이 이어 붙여 둡니다. 이렇게 한 덩어리로 붙은 메모리를 연속된 메모리라고 부릅니다. 같은 종류의 값만 담으므로 모든 칸의 크기도 같습니다.

칸마다 붙는 번호를 인덱스라고 부릅니다. 대부분의 언어는 인덱스를 0부터 셉니다. 첫 칸이 0번입니다. 두 번째 칸은 1번입니다. 인덱스가 「첫 칸에서 몇 칸 떨어져 있나」를 뜻하기 때문입니다.

메모리 주소는 메모리의 바이트마다 붙은 번호입니다. 아래 그림은 정수 하나에 4바이트를 쓰는 배열이 주소 1000번부터 놓인 모습입니다.

block-beta
columns 4
  a["0번 · 주소 1000"] b["1번 · 주소 1004"] c["2번 · 주소 1008"] d["3번 · 주소 1012"]

칸 크기가 4라서 주소가 4씩 늘어납니다. 3번 칸의 주소는 1000 + 3 × 4 = 1012 입니다. 시작 주소에 「인덱스 × 칸 크기」를 더하면 됩니다. 이 계산은 곱셈 한 번과 덧셈 한 번이 전부입니다.

배열에 값이 열 개든 백만 개든 이 계산은 똑같습니다. 그래서 몇 번째 값이든 같은 시간에 꺼냅니다. 번호로 아무 칸이나 바로 꺼내는 이 성질을 임의 접근이라고 부릅니다.

코드로 보는 배열

아래는 성적 세 개를 담은 자바 배열입니다. 줄마다 내는 값을 오른쪽 주석에 적었습니다.

int[] scores = {90, 75, 88};
scores[0]        // 90
scores[2]        // 88
scores.length    // 3
scores[3]        // 범위 밖이라 오류

마지막 줄은 3번 칸을 달라고 한 경우입니다. 칸이 셋뿐이라 인덱스는 0부터 2까지입니다. 3번 칸은 없습니다. 자바는 이때 실행을 멈추고 오류를 냅니다.

C 언어는 인덱스가 범위 안인지 검사하지 않습니다. 그래서 배열 밖의 메모리를 그대로 읽거나 덮어씁니다. 이 실수가 버퍼 오버플로 같은 보안 문제로 이어집니다.

칸 수가 처음에 정해지는 까닭

배열은 만들 때 칸 수를 정합니다. 연속된 메모리를 한 번에 잡아야 하기 때문입니다. 바로 뒤의 메모리는 다른 데이터가 이미 쓰고 있을 수 있습니다. 그래서 나중에 칸을 이어 붙일 수 없습니다.

더 많이 담아야 하면 더 큰 배열을 새로 잡고 값을 전부 옮겨 담습니다. 이 옮기기를 알아서 해 주는 배열을 동적 배열이라고 부릅니다.

중간에 넣기와 빼기

중간에 값을 넣으려면 그 뒤의 값을 한 칸씩 뒤로 밀어야 합니다. 빈틈 없이 붙어 있어야 앞의 주소 계산이 맞기 때문입니다. 아래 두 그림은 10 · 20 · 40 · 50 이 담긴 배열의 2번 칸에 30 을 넣기 전과 후입니다.

넣기 전입니다. 마지막 칸은 비어 있습니다.

block-beta
columns 5
  a["0번 · 10"] b["1번 · 20"] c["2번 · 40"] d["3번 · 50"] e["4번 · 빈 칸"]

넣은 뒤입니다. 40 과 50 이 한 칸씩 뒤로 밀렸습니다.

block-beta
columns 5
  a["0번 · 10"] b["1번 · 20"] c["2번 · 30"] d["3번 · 40"] e["4번 · 50"]

맨 앞에 넣으면 모든 값을 밀어야 합니다. 값이 많을수록 밀어야 할 값도 늘어납니다. 빼기도 같습니다. 빠진 칸을 메우려고 뒤쪽 값을 한 칸씩 앞으로 당깁니다.

끝에 붙이거나 끝에서 빼는 것은 다릅니다. 밀거나 당길 값이 없어서 바로 끝납니다.

스택은 마지막에 넣은 값을 먼저 꺼내는 자료구조입니다. 넣고 꺼내는 쪽을 맨 위라고 합니다. 스택을 배열로 담을 때는 맨 위를 배열의 끝에 둡니다. 그러면 넣기와 빼기가 모두 끝에서만 일어납니다.

연산마다 걸리는 시간

걸리는 시간이 값의 개수 n 에 따라 어떻게 늘어나는지는 빅오 표기법으로 적습니다. O(1) 은 개수와 상관없이 시간이 일정하다는 뜻입니다. O(n) 은 개수에 비례해 시간이 늘어난다는 뜻입니다.

표의 마지막 줄은 이진 탐색입니다. 가운데 값과 견주어 찾는 값이 없는 쪽 절반을 버립니다. 이 일을 되풀이하면 값이 두 배로 늘어도 한 번만 더 견주면 됩니다. 그게 O(log n) 입니다.

메모리를 얼마나 쓰나

배열은 값 말고 따로 드는 메모리가 거의 없습니다. 값 n 개를 담으면 칸 n 개만 씁니다.

연결 리스트는 값을 메모리 여기저기에 흩어 둡니다. 대신 값마다 다음 값의 메모리 주소를 하나씩 더 담습니다. 그래서 같은 개수를 담아도 배열보다 메모리를 더 씁니다.

다음 값의 주소를 담은 이 값을 포인터라고 합니다. 포인터가 있어야 흩어진 값을 차례로 따라갈 수 있습니다.

이웃한 값을 읽는 데 시간이 덜 드는 까닭

이 절은 배열을 처음부터 끝까지 훑을 때 왜 시간이 덜 드는지 설명합니다. 답은 CPU(Central Processing Unit, 중앙 처리 장치)가 값을 읽는 방식에 있습니다.

CPU 는 메인 메모리에서 값을 바로 읽지 않습니다. 먼저 가까이 붙은 작은 메모리에 올려 둡니다. 이 작은 메모리가 CPU 캐시입니다. 캐시에서 읽으면 메인 메모리까지 다녀오는 것보다 시간이 훨씬 덜 듭니다.

CPU 는 캐시에 값 하나만 올리지 않습니다. 그 값 주변의 메모리를 일정한 크기로 묶어 함께 올립니다. 배열은 값이 붙어 있어서 한 값을 읽으면 다음 값들도 이미 캐시에 올라와 있을 때가 많습니다.

프로그램이 가까운 메모리를 이어서 읽는 경향을 참조 지역성이라고 부릅니다. 배열은 이 경향을 잘 탑니다. 그래서 배열을 처음부터 끝까지 훑으면 값을 흩어 둔 구조보다 대개 시간이 덜 듭니다. 연결 리스트는 값이 메모리 여기저기 흩어져 있어서 이 덕을 덜 봅니다.

배열을 고르는 때와 피하는 때

배열이 잘 맞는 경우는 셋입니다.

반대로 중간에 넣고 빼는 일이 잦으면 배열은 매번 값을 밀고 당깁니다. 그럴 때는 연결 리스트처럼 칸을 따로 두는 구조를 견줘 봅니다.

값을 번호가 아니라 이름 같은 키로 찾고 싶을 때도 배열만으로는 안 됩니다. 인덱스는 0부터 이어지는 정수여야 하기 때문입니다. 해시테이블은 키를 배열 번호로 바꿔서 이 문제를 풉니다. 안쪽에는 여전히 배열을 둡니다.

관련 항목

배열을 안쪽 그릇으로 쓰는 자료구조

스택 · 큐 · 이진 힙 · 원형 버퍼 · 해시테이블 · 문자열

배열의 하위 종류

동적 배열 · 정적 배열 · 다차원 배열 · 희소 배열 · 비트 배열

배열과 맞세워지는 자료구조

연결 리스트 · 레코드 · 튜플 · 스킵 리스트

배열 위에서 도는 알고리즘

이진 탐색 · 선형 탐색 · 정렬 알고리즘 · 투 포인터 · 슬라이딩 윈도우 · 알고리즘

배열의 속도를 설명하는 개념

메모리 주소 · 임의 접근 · 참조 지역성 · CPU 캐시 · 빅오 표기법 · 분할 상환 분석 · 포인터

배열에서 자주 나는 오류

버퍼 오버플로 · 인덱스 범위 초과 · off-by-one 오류

배열이 속하는 상위 분류

자료구조 · 컬렉션 · 시퀀스

배열과 이름이 겹치는 헷갈리는 이웃

연관 배열 · 리스트 · 벡터 · 인덱스