배열

컴퓨터 과학에서 배열(array)은 요소(값 또는 변수)의 모음으로 구성된 자료 구조로, 각 요소는 동일한 메모리 크기를 가지며 최소한 하나의 배열 인덱스 또는 키로 식별된다. 이러한 인덱스의 모음은 인덱스 튜플이라고 알려진 튜플일 수 있다. 일반적으로 배열은 동일한 자료형을 가진 요소들의 가변적이고 선형적인 모음이다. 배열은 각 요소의 위치(메모리 주소)를 수학 공식을 통해 인덱스 튜플로부터 계산할 수 있도록 저장된다.[^4][^1][^2] 가장 단순한 형태의 자료 구조는 일차원 배열이라고도 불리는 선형 배열이다.

예를 들어, 인덱스가 0부터 9까지인 10개의 32비트(4바이트) 정수 변수 배열은 메모리 주소 2000, 2004, 2008, ..., 2036(16진수로: 0x7D0, 0x7D4, 0x7D8, ..., 0x7F4)에 10개의 워드로 저장될 수 있으며, 인덱스 i를 가진 요소의 주소는 2000 + (i × 4)이다.[^5] 배열의 첫 번째 요소의 메모리 주소를 첫 번째 주소, 기초 주소 또는 기저 주소라고 한다.

행렬의 수학적 개념은 2차원 격자로 표현할 수 있기 때문에, 2차원 배열은 때때로 "행렬"이라고도 불린다. 경우에 따라 컴퓨팅에서 배열을 지칭하기 위해 "벡터"라는 용어가 사용되기도 하지만, 수학적으로는 벡터보다 튜플이 더 정확한 대응 개념이다. 테이블은 특히 룩업 테이블의 형태로 배열을 사용하여 구현되는 경우가 많으며, "테이블"이라는 단어가 배열의 동의어로 사용되기도 한다.

배열은 가장 오래되고 가장 중요한 자료 구조 중 하나이며, 거의 모든 프로그램에서 사용된다. 또한 리스트나 문자열과 같은 다른 많은 자료 구조를 구현하는 데에도 사용된다. 배열은 컴퓨터의 주소 지정 논리를 효과적으로 활용한다. 대부분의 현대 컴퓨터와 많은 외부 저장 장치에서 메모리는 주소가 인덱스인 1차원 워드 배열이다. 프로세서, 특히 벡터 프로세서는 배열 연산에 최적화되어 있는 경우가 많다.

배열이 유용한 주된 이유는 요소 인덱스를 실행 시간에 계산할 수 있기 때문이다. 이 특성 덕분에 하나의 반복문으로 배열의 임의의 많은 요소를 처리할 수 있다. 이러한 이유로 배열 자료 구조의 요소들은 동일한 크기를 가지고 동일한 데이터 표현 방식을 사용해야 한다. 유효한 인덱스 튜플의 집합과 요소들의 주소(따라서 요소 주소 지정 공식)는 배열이 사용되는 동안 보통[^2][^3] 고정되어 있지만, 항상 그런 것은 아니다.[^1]

"배열"이라는 용어는 배열 자료형을 가리키기도 하는데, 이는 대부분의 고급 프로그래밍 언어에서 제공하는 자료형의 일종으로, 실행 시간에 계산되는 하나 이상의 인덱스로 선택할 수 있는 값이나 변수의 모음으로 구성된다. 배열 자료형은 흔히 배열 구조로 구현되지만, 일부 언어에서는 해시 테이블, 연결 리스트, 탐색 트리 또는 기타 자료 구조로 구현될 수도 있다.

이 용어는 특히 알고리즘 설명에서 연관 배열 또는 "추상 배열"을 의미하는 데에도 사용되며, 이는 배열의 본질적인 속성을 포착하기 위한 이론적 컴퓨터 과학 모델(추상 자료형 또는 ADT)이다.

역사

최초의 디지털 컴퓨터는 데이터 테이블, 벡터 및 행렬 연산, 그리고 다른 많은 목적을 위해 배열 구조를 설정하고 접근하는 데 기계어 프로그래밍을 사용했다. 존 폰 노이만은 최초의 저장 프로그램 방식 컴퓨터를 제작하던 1945년에 최초의 배열 정렬 프로그램(병합 정렬)을 작성했다.[^6] 배열 인덱싱은 원래 자기 수정 코드를 통해 수행되었으며, 이후에는 인덱스 레지스터와 간접 주소 지정 방식이 사용되었다. 버로스 B5000과 그 후속 기종 등 1960년대에 설계된 일부 메인프레임은 메모리 세그먼테이션을 사용하여 하드웨어 수준에서 인덱스 범위 검사를 수행했다.[^7]

어셈블리 언어는 일반적으로 기계 자체가 제공하는 것 외에는 배열에 대한 특별한 지원이 없다. FORTRAN(1957), Lisp(1958), COBOL(1960), ALGOL 60(1960)을 포함한 최초의 고급 프로그래밍 언어들은 다차원 배열을 지원했으며, C(1972)도 마찬가지이다. C++(1983)에서는 런타임에 차원이 고정되는 다차원 배열[^2][^3]과 런타임에 유연하게 조정 가능한 배열[^1]을 위한 클래스 템플릿이 존재한다.

응용

배열은 수학적 벡터와 행렬, 그리고 기타 종류의 직사각형 테이블을 구현하는 데 사용된다. 크고 작은 많은 데이터베이스는 요소가 레코드인 1차원 배열로 구성되거나 이를 포함한다.

배열은 리스트, 힙, 해시 테이블, 덱, 큐, 스택, 문자열, VList 등 다른 자료 구조를 구현하는 데 사용된다. 다른 자료 구조의 배열 기반 구현은 대체로 단순하고 공간 효율적이며(암묵적 자료 구조), 오버헤드가 적지만, 트리 기반 자료 구조와 비교했을 때(정렬된 배열과 탐색 트리를 비교해 보라) 특히 수정 시 공간 복잡도가 좋지 않을 수 있다.

하나 이상의 대형 배열은 때때로 프로그램 내 동적 메모리 할당, 특히 메모리 풀 할당을 에뮬레이션하는 데 사용된다. 역사적으로 이것이 이식 가능한 방식으로 "동적 메모리"를 할당하는 유일한 방법이었던 경우도 있었다.

배열은 프로그램에서 부분적 또는 완전한 제어 흐름을 결정하는 데 사용될 수 있으며, (그렇지 않으면 반복적인) 다수의 IF 문에 대한 간결한 대안이 된다. 이러한 맥락에서 배열은 제어 테이블로 알려져 있으며, 배열에 포함된 값에 따라 제어 흐름이 변경되는 전용 인터프리터와 함께 사용된다. 배열은 프로그램 실행 경로를 지시하는 서브루틴 포인터(또는 SWITCH 문으로 처리할 수 있는 상대적 서브루틴 번호)를 포함할 수 있다.

요소 식별자와 주소 지정 공식

데이터 객체가 배열에 저장될 때, 개별 객체는 일반적으로 음이 아닌 스칼라 정수인 인덱스에 의해 선택된다. 인덱스는 첨자(subscript)라고도 불린다. 인덱스는 배열 값을 저장된 객체에 매핑한다.

배열의 요소를 인덱싱하는 방법에는 세 가지가 있다:

0 (0 기반 인덱싱): 배열의 첫 번째 요소는 첨자 0으로 인덱싱된다.[^8] 1 (1 기반 인덱싱): 배열의 첫 번째 요소는 첨자 1로 인덱싱된다. n (n 기반 인덱싱): 배열의 기본 인덱스를 자유롭게 선택할 수 있다. 일반적으로 n 기반 인덱싱을 허용하는 프로그래밍 언어는 음수 인덱스 값도 허용하며, 열거형이나 문자와 같은 다른 스칼라 데이터 타입도 배열 인덱스로 사용할 수 있다.

0 기반 인덱싱의 사용은 C, Java, Lisp를 포함한 많은 영향력 있는 프로그래밍 언어의 설계 선택이다. 이는 첨자가 배열의 시작 위치로부터의 오프셋을 나타내므로 첫 번째 요소의 오프셋이 0이 되어 구현이 더 간단해진다.

배열은 여러 차원을 가질 수 있으므로, 여러 인덱스를 사용하여 배열에 접근하는 것은 드문 일이 아니다. 예를 들어, 3개의 행과 4개의 열을 가진 2차원 배열 A는 0 기반 인덱싱 시스템의 경우 A[1][3] 표현식으로 2번째 행과 4번째 열의 요소에 접근할 수 있다. 따라서 2차원 배열에는 2개의 인덱스가, 3차원 배열에는 3개의 인덱스가, n차원 배열에는 n개의 인덱스가 사용된다.

요소를 지정하는 데 필요한 인덱스의 수를 배열의 차원, 차원수, 또는 랭크라고 한다.

표준 배열에서 각 인덱스는 연속된 정수(또는 열거형의 연속된 값)의 특정 범위로 제한되며, 요소의 주소는 인덱스에 대한 "선형" 공식으로 계산된다.

1차원 배열

1차원 배열(또는 단일 차원 배열)은 선형 배열의 한 유형이다. 요소에 접근할 때 행 또는 열 인덱스를 나타내는 단일 첨자가 사용된다.

예를 들어 C 선언 int a[10];은 10개의 정수로 이루어진 a라는 1차원 배열을 선언한다. 여기서 배열은 int 타입의 요소 10개를 저장할 수 있다. 이 배열의 인덱스는 0부터 9까지이다. 예를 들어, a[0]과 a[9] 표현식은 각각 첫 번째와 마지막 요소이다.

선형 주소 지정을 사용하는 벡터의 경우, 인덱스 i를 가진 요소는 주소 에 위치하며, 여기서 B는 고정된 기본 주소이고 c는 고정 상수로, 주소 증분 또는 *보폭(stride)*이라고도 한다.

유효한 요소 인덱스가 0에서 시작하면, 상수 B는 단순히 배열의 첫 번째 요소의 주소이다. 이러한 이유로 C 프로그래밍 언어는 배열 인덱스가 항상 0에서 시작하도록 지정하며, 많은 프로그래머들은 해당 요소를 "첫 번째"가 아닌 "0번째"라고 부른다.

그러나 기본 주소 B를 적절히 선택함으로써 첫 번째 요소의 인덱스를 변경할 수 있다. 예를 들어, 배열에 1부터 5까지 인덱싱된 5개의 요소가 있고, 기본 주소 B를 로 대체하면 동일한 요소의 인덱스는 31부터 35가 된다. 번호 매기기가 0에서 시작하지 않으면, 상수 B는 어떤 요소의 주소도 아닐 수 있다.

다차원 배열

다차원 배열의 경우, 인덱스 i,j를 가진 요소의 주소는 B + c · i + d · j이며, 여기서 계수 c와 d는 각각 행 및 열 주소 증분이다.

더 일반적으로, k차원 배열에서 인덱스 i1, i2, ..., ik를 가진 요소의 주소는 다음과 같다: B + c1 · i1 + c2 · i2 + … + ck · ik.

예를 들어: int a[2][3];

이것은 배열 a가 2개의 행과 3개의 열을 가지며, 배열이 정수 타입임을 의미한다. 여기서 6개의 요소를 저장할 수 있으며, 첫 번째 행부터 선형으로 저장된 후 두 번째 행으로 이어진다. 위의 배열은 a11, a12, a13, a21, a22, a23 순으로 저장된다.

이 공식은 메모리에 들어갈 수 있는 모든 배열에 대해 k번의 곱셈과 k번의 덧셈만 필요로 한다. 또한, 계수가 2의 고정 거듭제곱이면 곱셈을 비트 시프트로 대체할 수 있다.

계수 ck는 모든 유효한 인덱스 튜플이 서로 다른 요소의 주소에 매핑되도록 선택되어야 한다.

모든 인덱스의 최솟값이 0이면, B는 모든 인덱스가 0인 요소의 주소이다. 1차원의 경우와 마찬가지로, 기본 주소 B를 변경하여 요소 인덱스를 변경할 수 있다. 따라서 2차원 배열의 행과 열이 각각 1부터 10, 1부터 20으로 인덱싱되어 있을 때, B를 로 대체하면 각각 0부터 9, 4부터 23으로 다시 번호가 매겨진다. 이 기능을 활용하여, 일부 언어(예: FORTRAN 77)는 수학적 전통에 따라 배열 인덱스가 1에서 시작하도록 지정하는 반면, 다른 언어(예: Fortran 90, Pascal, Algol)는 사용자가 각 인덱스의 최솟값을 선택할 수 있게 한다.

도프 벡터

주소 지정 공식은 차원 d, 기본 주소 B, 그리고 증분 c1, c2, ..., ck에 의해 완전히 정의된다. 이러한 매개변수를 배열의 기술자(descriptor), 보폭 벡터(stride vector), 또는 도프 벡터(dope vector)라 불리는 레코드에 묶어 저장하는 것이 유용한 경우가 많다.[^1][^2] 각 요소의 크기와 각 인덱스에 허용되는 최솟값 및 최댓값도 도프 벡터에 포함될 수 있다. 도프 벡터는 배열에 대한 완전한 핸들이며, 배열을 프로시저에 인수로 전달하는 편리한 방법이다. 많은 유용한 배열 슬라이싱 연산(예: 부분 배열 선택, 인덱스 교환, 인덱스 방향 반전)은 도프 벡터를 조작하여 매우 효율적으로 수행할 수 있다.[^1]

밀집 배치

종종 계수는 요소들이 메모리의 연속된 영역을 차지하도록 선택된다. 그러나 이것이 반드시 필요한 것은 아니다. 배열이 항상 연속된 요소로 생성되더라도, 일부 배열 슬라이싱 연산은 비연속적인 부분 배열을 만들 수 있다.

2차원 배열에는 두 가지 체계적인 밀집 배치가 있다. 예를 들어, 다음 행렬을 고려하자: A = \begin{bmatrix} 1 & 2 & 3 \ 4 & 5 & 6 \ 7 & 8 & 9 \end{bmatrix}.

행 우선 순서 배치(C에서 정적으로 선언된 배열에 채택됨)에서는 각 행의 요소가 연속된 위치에 저장되며, 한 행의 모든 요소는 다음 행의 어떤 요소보다 낮은 주소를 가진다: {| class="wikitable" |- | 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 |}

열 우선 순서(전통적으로 Fortran에서 사용됨)에서는 각 열의 요소가 메모리에서 연속적이며, 한 열의 모든 요소는 다음 열의 어떤 요소보다 낮은 주소를 가진다: {| class="wikitable" |- | 1 || 4 || 7 || 2 || 5 || 8 || 3 || 6 || 9 |}

3개 이상의 인덱스를 가진 배열의 경우, "행 우선 순서"는 마지막 인덱스만 1 차이나는 인덱스 튜플을 가진 두 요소를 연속된 위치에 배치한다. "열 우선 순서"는 첫 번째 인덱스에 대해 유사하게 적용된다.

프로세서 캐시나 가상 메모리를 사용하는 시스템에서는, 연속된 요소가 메모리의 연속된 위치에 저장될 때 배열 스캔이 훨씬 빠르다. 이는 참조의 지역성의 한 유형인 공간적 지역성이라고 알려져 있다. 다차원 배열을 사용하는 많은 알고리즘은 예측 가능한 순서로 배열을 스캔한다. 프로그래머(또는 정교한 컴파일러)는 이 정보를 사용하여 각 배열에 대해 행 우선 또는 열 우선 배치를 선택할 수 있다. 예를 들어, 두 행렬의 곱 A·B를 계산할 때, A는 행 우선 순서로, B는 열 우선 순서로 저장하는 것이 가장 좋다.

크기 변경

정적 배열은 생성 시 크기가 고정되므로 요소의 삽입이나 제거를 허용하지 않는다. 그러나 새 배열을 할당하고 기존 배열의 내용을 복사함으로써 배열의 동적 버전을 효과적으로 구현할 수 있다; 동적 배열을 참조하라. 이 연산이 드물게 수행되면, 배열 끝에 삽입하는 데 분할 상환 상수 시간만 필요하다.

일부 배열 데이터 구조는 저장 공간을 재할당하지 않지만, 사용 중인 배열 요소의 수를 카운트 또는 크기라 불리는 값으로 저장한다. 이는 사실상 배열을 고정된 최대 크기 또는 용량을 가진 동적 배열로 만든다; Pascal 문자열이 이에 해당하는 예이다.

비선형 공식

더 복잡한 (비선형) 공식이 가끔 사용된다. 예를 들어, 밀집된 2차원 삼각 배열의 경우 주소 지정 공식은 2차 다항식이다.

효율성

저장과 선택 모두 (결정론적 최악의 경우) 상수 시간이 소요된다. 배열은 보유하는 요소 수 n에 대해 선형(O(n)) 공간을 차지한다.

요소 크기가 k이고 캐시 라인 크기가 B 바이트인 머신에서, n개의 요소를 가진 배열을 순회하려면 최소 ceiling(nk/B)번의 캐시 미스가 필요한데, 이는 요소들이 연속된 메모리 위치를 점유하기 때문이다. 이는 임의의 메모리 위치에 있는 n개의 요소에 접근하는 데 필요한 캐시 미스 횟수보다 대략 B/k배 더 효율적이다. 결과적으로, 배열에 대한 순차적 순회는 실제로 다른 많은 자료 구조에 대한 순회보다 눈에 띄게 빠르며, 이 속성을 참조 지역성이라고 한다(그러나 이것이 동일한 (지역) 배열 내에서 완전 해시나 단순 해시를 사용하는 것이 더 빠르지 않다는 것을 의미하지는 않으며, 이는 상수 시간에 달성 가능하다). 라이브러리는 메모리 범위를 복사하는 저수준 최적화 기능(예: memcpy)을 제공하며, 이를 사용하면 개별 요소 접근보다 훨씬 빠르게 배열 요소의 연속 블록을 이동할 수 있다. 이러한 최적화된 루틴의 속도 향상은 배열 요소 크기, 아키텍처 및 구현에 따라 달라진다.

메모리 측면에서, 배열은 요소별 오버헤드가 없는 간결한 자료 구조이다. 배열별 오버헤드(예: 인덱스 범위 저장)가 있을 수 있지만 이는 언어에 따라 다르다. 또한 배열에 저장된 요소가 개별 변수에 저장된 동일한 요소보다 더 적은 메모리를 필요로 할 수 있는데, 여러 배열 요소가 하나의 워드에 저장될 수 있기 때문이다; 이러한 배열을 흔히 패킹된 배열이라고 한다. 극단적인(그러나 흔히 사용되는) 경우가 비트 배열로, 모든 비트가 하나의 요소를 나타낸다. 따라서 단일 옥텟은 가장 간결한 형태로 최대 8가지 서로 다른 조건의 최대 256가지 조합을 담을 수 있다.

정적으로 예측 가능한 접근 패턴을 가진 배열 접근은 데이터 병렬성의 주요 원천이다.

다른 자료 구조와의 비교

동적 배열 또는 가변 크기 배열은 배열과 유사하지만 요소의 삽입 및 삭제 기능이 추가된다; 특히 끝에서의 추가와 삭제가 효율적이다. 그러나 배열이 추가 저장 공간을 예약하지 않는 반면, 동적 배열은 선형(Θ(n))의 추가 저장 공간을 예약한다.

연관 배열은 인덱스 값이 희소할 때 거대한 저장 오버헤드 없이 배열과 유사한 기능을 제공하는 메커니즘이다. 예를 들어, 인덱스 1과 20억에만 값을 포함하는 배열은 이러한 구조를 사용하면 이점을 얻을 수 있다. 정수 키를 가진 특수한 연관 배열에는 패트리샤 트라이, 주디 배열, 반 엠데 보아스 트리가 포함된다.

균형 트리는 인덱스 접근에 O(log n) 시간이 필요하지만, O(log n) 시간에 요소의 삽입이나 삭제도 허용하는 반면,[^9] 가변 크기 배열은 임의의 위치에서 요소를 삽입하거나 삭제하는 데 선형(Θ(n)) 시간이 필요하다.

연결 리스트는 중간에서 상수 시간 제거와 삽입을 허용하지만 인덱스 접근에는 선형 시간이 소요된다. 메모리 사용량은 일반적으로 배열보다 나쁘지만, 여전히 선형이다.

일리프 벡터는 다차원 배열 구조의 대안이다. 이는 한 차원 낮은 배열에 대한 참조의 1차원 배열을 사용한다. 특히 2차원의 경우, 이 대안적 구조는 각 행마다 하나씩 벡터에 대한 포인터들의 벡터가 된다(C 또는 C++에서의 포인터). 따라서 배열 A의 i행 j열에 있는 요소는 이중 인덱싱으로 접근한다(일반적인 표기법으로 A[i][j]). 이 대안적 구조는 들쭉날쭉한 배열을 허용하는데, 각 행이 서로 다른 크기를 가질 수 있으며, 일반적으로 각 인덱스의 유효 범위가 앞선 모든 인덱스의 값에 의존한다. 또한 하나의 곱셈(열 주소 증분에 의한)을 절약하고 이를 비트 시프트(행 포인터 벡터의 인덱싱을 위한)와 하나의 추가 메모리 접근(행 주소 가져오기)으로 대체하며, 이는 일부 아키텍처에서는 가치 있을 수 있다.

차원

배열의 차원은 요소를 선택하는 데 필요한 인덱스의 수이다. 따라서 배열을 가능한 인덱스 조합의 집합에 대한 함수로 본다면, 이는 그 정의역이 이산 부분집합인 공간의 차원이 된다. 그러므로 1차원 배열은 데이터의 목록이고, 2차원 배열은 데이터의 직사각형이며,[^10] 3차원 배열은 데이터의 블록이다.

이것을 주어진 정의역을 가진 모든 행렬 집합의 차원, 즉 배열의 요소 수와 혼동해서는 안 된다. 예를 들어, 5개의 행과 4개의 열을 가진 배열은 2차원이지만, 그러한 행렬들은 20차원 공간을 형성한다. 마찬가지로, 3차원 벡터는 크기가 3인 1차원 배열로 표현할 수 있다.

같이 보기

• 동적 배열
• 병렬 배열
• 가변 길이 배열
• 비트 배열
• 배열 슬라이싱
• 오프셋 (컴퓨터 과학)
• 행 우선 및 열 우선 순서
• 배열의 스트라이드

외부 링크

---

참고 문헌

[^1]: C++98 및 C++0x를 위한 런타임 유연 다차원 배열과 뷰

[^2]: Garcia, Ronald. MultiArray: 배열을 이용한 제네릭 프로그래밍을 위한 C++ 라이브러리

[^3]: Veldhuizen, Todd L.. Blitz++에서의 배열. Springer. (1998년 12월)

[^4]: Black, Paul E.. 배열. [[미국 국립표준기술연구소]]. (2008년 11월 13일)

[^5]: David R. Richardson (2002), 데이터 구조에 관한 책. iUniverse, 1112쪽. ISBN 0-595-24039-9 , ISBN 978-0-595-24039-5 .

[^6]: TAOCP 제3권 159쪽

[^7]: Levy, Henry M.. 능력 기반 컴퓨터 시스템. Digital Press

[^8]: cite web access-date = 2011년 4월 8일 publisher = 컴퓨터 프로그래밍 웹 프로그래밍 팁 title = 배열 코드 예제 - PHP 배열 함수 - PHP 코드 quote = 대부분의 컴퓨터 언어에서 배

[^9]: 카운티드 B-트리

[^10]: 2차원 배열 \ Processing.org