Array(배열)
개념
배열(Array)은 가장 기본적인 자료구조로, 동일한 타입의 요소(Element)들을 연속적으로 나열한 형태로 저장한 자료구조입니다.
나열된 요소의 개수를 배열의 길이(또는 크기)라고 하며, 배열 선언 시에 길이를 지정합니다. 이후 해당 배열의 길이는 변경할 수 없습니다.
인덱스(Index)로 요소에 접근
배열의 각 요소에는 인덱스(Index)를 통해 접근할 수 있으며, 일반적으로 0부터 시작하는 정수 인덱스를 사용합니다.
배열은 동일한 타입의 요소들이 실제 메모리 상에서 연속적으로 할당됩니다. 따라서 0번째 요소의 위치에서 n칸 이동한 값으로 n번째 요소의 위치를 바로 알 수 있습니다. 예를 들어 타입의 크기가 4이고, 0번째(첫 번째) 요소의 위치가 10이라면, 2번째(두 번째가 아닌 세 번째가 됨) 요소의 위치를 10 + 2×4 = 18 로 한 번에 계산할 수 있습니다.
변경과 삽입, 삭제
할당된 공간 내에서 요소의 값은 변경할 수 있습니다.
그러나 배열은 고정된 크기로 선언되므로 새로운 공간에 값을 추가하거나 기존의 값을 삭제할 수 없습니다.
따라서 배열 사용 시에는 미리 충분한 길이를 할당해야 하며, 필요에 따라 길이 값을 나타내는 변수를 별도로 두어 실제 사용 중인 요소의 개수를 관리할 수 있습니다.
그 외에 배열에 할당된 길이보다 더 많은 요소를 저장하려고 하거나 실제 길이를 줄이려고 할 때에는 새로운 배열을 선언하고 기존 배열의 값을 복사해 넣는 방식을 사용할 수 있습니다.
동적 배열 vector 로 확장
필요에 동적(dynamic)으로 길이를 변경할 수 있는 벡터(vector) 자료구조가 있습니다.
내부적으로 고정 크기 배열을 사용하지만, 할당된 길이인 capacity와 실제 사용 중인 길이인 size를 분리하여 관리합니다. size가 capacity를 넘거나 너무 작아지면, 적당한 크기의 새 배열을 할당하여 기존 값을 복사해 사용합니다.
이를 통해 값의 추가 및 삭제가 유연해지면서도, 배열의 장점인 인덱스를 통한 빠른 접근 속도를 유지할 수 있어, 극단적인 최적화가 필요하거나, 명확히 고정된 크기의 배열만 필요한 경우 등을 제외하면 일반적인 배열의 역할을 벡터가 대체할 수 있습니다.
자세한 내용은 Vector 글에서 다룹니다.
시간 복잡도
배열은 생성 및 각 요소에 접근하여 값을 읽거나 변경하는 것이 가능하지만, 크기 변경이나 삽입, 삭제가 불가능합니다. 따라서 배열의 주요 연산들에 대한 시간 및 공간 복잡도는 다음과 같습니다:
| 연산 | 설명 | 시간 복잡도 |
|---|---|---|
| 생성 | 길이 n인 배열 생성 | O(n) |
| 접근 | 인덱스 i의 요소에 접근 | O(1) |
| 변경 | 인덱스 i의 요소 값 변경 | O(1) |
| 검색 | 특정 값의 요소 검색 (선형 탐색) | O(n) |
예시
int array[5];
array[0] = 10; // 0 번째이자 첫 번째 요소에 값 10 할당
array[1] = 20; // 1 번째이자 두 번째 요소에 값 20 할당
array[4] = 50; // 4 번째이자 다섯 번째(마지막) 요소에 값 50 할당
int first = array[0]; // 0 번째이자 첫 번째 요소: 값 10
int second = array[1]; // 1 번째이자 두 번째 요소: 값 20
int last = array[4]; // 4 번째이자 다섯 번째(마지막) 요소: 값 50
위의 예시의 첫 번째 줄에서 array라는 이름의 길이 5인 int 타입 배열을 선언했습니다.
int는 타입을, array는 배열의 이름이자 실질적으로 메모리상에서 배열의 시작 위치(0번째 요소의 위치)를 의미하며, [] 안에 길이 값 5를 지정하여 배열의 길이를 지정하면서 ;로 선언을 마무리합니다.
참고
배열은 대부분의 자료구조의 기본이 됩니다. 즉, 다른 대부분의 자료구조들은 실제 값들을 배열에 저장하되, 값들에 접근하거나 관리하는 추가적인 방식이나 구조를 더하여 구현한 것으로 볼 수 있습니다. 따라서 다른 자료구조의 구조에 기본적으로 배열이 포함되어 있다는 점을 항상 기억해야 합니다.
길이 n인 배열의 인덱스는 항상 0부터 n-1까지 값으로 각각 첫번째부터 마지막까지의 요소를 가리킵니다. 이때 배열의 길이는 n이며, 단지 마지막 요소의 인덱스가 n-1 이 되는 것임에 주의해야 합니다.
대부분의 경우와 같이 이 블로그에서도 첫 번째 요소는 0 번째 요소이자 인덱스 0, 두 번째 요소는 1 번째 요소이자 인덱스 1, … , n 번째 요소는 n-1번째 요소이자 인덱스 n-1로 표기합니다. 단, 가급적 혼동을 피하기 위해 가급적 숫자를 이용해 인덱스 값을 표기할 것입니다.