배열
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
배열은 메모리 공간에 데이터를 연속적으로 저장하는 자료 구조이다. 1945년 존 폰 노이만이 최초의 배열 정렬 프로그램을 작성하면서 등장했으며, C, C++, 자바 등 다양한 프로그래밍 언어에서 지원된다. 배열은 인덱스를 통해 요소에 빠르게 접근할 수 있고 메모리 사용 효율이 높다는 장점이 있지만, 크기가 고정되어 있어 동적으로 크기를 조절하기 어렵고, 요소의 삽입/삭제 시 데이터 이동이 필요하다는 단점도 있다. 배열은 1차원, 2차원, 다차원 형태로 구성될 수 있으며, 수학의 좌표 벡터, 행렬 구현, 데이터베이스, 다양한 자료 구조의 기반으로 활용된다.
존 폰 노이만은 최초의 저장식 프로그램 컴퓨터를 제조하던 1945년 머지 소트라는 최초의 배열 정렬 프로그램을 작성하였다.[40] 초기에는 자체 수정 코드를 통해 배열 색인화를 구현하였으며, 나중에 색인 레지스터와 비간접 주소 참조를 사용하게 되었다. 1960년대에 설계된 버로프 B5000 및 이후 세대 등 일부 메인프레임들은 메모리 세그멘테이션을 사용하여 하드웨어에 인덱스 바운드 검사를 수행했다.[41]
배열은 메모리 상에서 연속적인 공간을 차지하므로, 공간 효율성이 높고 빠른 접근 속도를 제공한다. 인덱스를 통해 각 요소에 직접 접근할 수 있으며, 접근 시간은 O(1)이다.
2. 역사
포트란(1928년), 코볼(1860년), 알골 60(1960년)을 포함한 최초의 고급 프로그래밍 언어들은 다차원 배열을 지원하였으며, C도 이 기능을 지원한다. C++의 경우, 다차원 배열을 위한 클래스 템플릿들이 지원되며, 이 안에서 차원은 런타임[42][43] 및 런타임 유연 배열에 고정된다.[44]
한국에서는 1980년대부터 컴퓨터 과학 교육과 연구가 본격화되면서 배열에 대한 이해와 활용이 확산되었다. 특히, 정보처리산업기사 등의 자격증 시험과 대학 교육 과정에서 배열은 핵심적인 내용으로 다루어졌다.
2. 1. 주요 프로그래밍 언어와 배열
C/C++에서는 정적 배열과 동적 배열을 모두 지원하며, 다차원 배열은 "배열의 배열" 형태로 구현된다.[38] C99 표준부터는 실행 시간에 요소 수를 지정할 수 있는 가변 길이 배열(VLA)이 도입되었으나,[33][34] C11에서는 선택적 기능으로 변경되었다. 가변 길이 배열은 스택 오버플로우를 일으킬 수 있으므로 작은 크기에만 사용해야 한다. 일부 환경에서는 `alloca()` 함수를 통해 유사한 기능을 제공한다.[35]
자바는 "배열의 배열"을 지원하며, 내부 배열의 크기가 고정되지 않은 재그 배열(jagged array)을 만들 수 있다. 자바에서 배열은 객체로 취급된다.
C#은 "진정한 다차원 배열"과 함께 자바와 같은 재그 배열을 지원한다. 재그 배열은 차원마다 영역 확보를 반복해야 하지만, 직사각형 배열은 한 번에 영역을 확보할 수 있다. 그러나 희소 행렬과 같이 드문드문한 배열에는 재그 배열이 더 효율적이다.
C 언어에서는 포인터를 사용하여 재그 배열과 유사한 데이터 구조를 만들 수 있지만, "배열의 배열"과는 의미적으로 다르므로 주의해야 한다.
3. 특징
프로세서 캐시 또는 가상 메모리를 사용하는 시스템에서 배열을 스캔하는 것은 연속적인 요소가 메모리의 연속된 위치에 저장될 때 희소하게 흩어져 있는 것보다 훨씬 빠르다. 이것은 참조의 지역성의 한 유형인 공간적 지역성으로 알려져 있다. 다차원 배열을 사용하는 많은 알고리즘은 예측 가능한 순서로 이를 스캔한다.
배열의 크기는 일반적으로 고정되어 있으며, 크기를 변경하려면 새로운 배열을 생성하고 데이터를 복사해야 한다. 정적 배열은 생성 시 크기가 고정되어 있어 요소를 삽입하거나 제거할 수 없다. 그러나 새 배열을 할당하고 이전 배열의 내용을 복사하면 배열의 ''동적'' 버전을 효과적으로 구현할 수 있다. 동적 배열을 참조.
C++(C++) 등 후발 언어에서는, 동적 메모리 확보를 위해 통상 new 연산자가 마련되어 있는 경우가 많으며, 배열의 동적 확보에는 형식과 요소 수를 지정하는 new[] 연산자를 사용한다.
Java(자바) 등 후발 언어에서는 가비지 컬렉션에 의한 자동 해제를 도입하는 경우가 많으며, 배열의 확보에 관해서 정적 확보·동적 확보와 같은 구분을 하지 않는 경우가 많다.
3. 1. 장점
배열은 다음과 같은 장점을 가진다.3. 2. 단점
4. 종류
1차원 배열(또는 단일 차원 배열)은 선형 배열의 한 유형이다. 요소에 접근하려면 행 또는 열 인덱스를 나타낼 수 있는 단일 첨자가 필요하다.[12]
C 언어 선언 `int anArrayName[10];`은 10개의 정수로 이루어진 1차원 배열을 선언하며, 0부터 9까지의 인덱스를 갖는다. `anArrayName[0]`과 `anArrayName[9]`는 각각 첫 번째 요소와 마지막 요소를 나타낸다.
선형 주소 지정을 사용하는 벡터의 경우, 인덱스 ''i''인 요소는 주소 ''B'' + ''c'' · ''i''에 위치한다. 여기서 ''B''는 고정된 ''기준 주소''이고 ''c''는 고정된 상수이며, ''주소 증가'' 또는 ''스트라이드''라고도 한다. 유효한 요소 인덱스가 0부터 시작하는 경우, 상수 ''B''는 배열의 첫 번째 요소의 주소이다. C 프로그래밍 언어는 배열 인덱스가 항상 0부터 시작하도록 지정하며, 많은 프로그래머들은 해당 요소를 "영 번째"라고 부른다. 그러나 기준 주소 ''B''를 변경하여 첫 번째 요소의 인덱스를 선택할 수 있다.
다차원 배열의 경우, 인덱스 ''i'', ''j''를 가진 요소의 주소는 ''B'' + ''c'' · ''i'' + ''d'' · ''j''가 되는데, 여기서 계수 ''c''와 ''d''는 각각 ''행'' 및 ''열 주소 증가량''이다.
더 일반적으로, ''k''차원 배열에서 인덱스 ''i''1, ''i''2, ..., ''i''''k''를 가진 요소의 주소는 ''B'' + ''c''1 · ''i''1 + ''c''2 · ''i''2 + … + ''c''''k'' · ''i''''k''이다.
예를 들어, `int a[2][3];`는 2개의 행과 3개의 열을 가진 정수형 배열을 선언하며, 6개의 요소(a11, a12, a13, a21, a22, a23)를 선형적으로 저장한다.
이 공식은 메모리에 들어갈 수 있는 모든 배열에 대해 ''k''번의 곱셈과 ''k''번의 덧셈만 필요로 한다. 만약 어떤 계수가 2의 고정된 거듭제곱이라면, 곱셈은 비트 연산으로 대체될 수 있다. 계수 ''c''''k''는 모든 유효한 인덱스 튜플이 별개의 요소의 주소에 매핑되도록 선택되어야 한다.
모든 인덱스에 대한 최소 법적 값이 0인 경우, ''B''는 모든 인덱스가 0인 요소의 주소이다. 요소 인덱스는 기본 주소 ''B''를 변경하여 변경될 수 있다.
정적 배열은 생성 시 크기가 고정되어 요소를 삽입하거나 제거할 수 없다. 그러나 새 배열을 할당하고 이전 배열의 내용을 복사하여 배열의 ''동적'' 버전을 효과적으로 구현할 수 있다. 동적 배열
일부 배열 자료 구조는 스토리지를 재할당하지 않고 사용 중인 배열 요소 수를 저장하는데, 이를 개수 또는 크기라고 한다. 이는 배열을 고정된 최대 크기 또는 용량을 가진 동적 배열로 효과적으로 만든다. 파스칼 문자열이 그 예이다.
배열의 ''차원''은 요소를 선택하는 데 필요한 인덱스의 수이다. 1차원 배열은 데이터 목록, 2차원 배열은 데이터 사각형,[12] 3차원 배열은 데이터 블록 등이다.
프로그램 실행 시에 배열의 크기를 지정하여 배열을 생성하는 것을 동적 확보라고 한다. C 언어에서는 malloc 함수나 `calloc` 함수를, C++(C++)에서는 new 연산자를 사용한다. 확보된 메모리는 명시적으로 해제해야 하며, 해제를 잊으면 메모리 누수의 원인이 된다. Java(자바) 등에서는 가비지 컬렉션에 의한 자동 해제를 도입하는 경우가 많다.
일반적인 배열의 첨자(인덱스)는 정수형이며, 유효한 값은 0 또는 1부터 시작하는 비음수 정수 값이다. 음수 또는 부동 소수점 수를 포함한 임의의 숫자형이나, 문자열 등을 첨자처럼 사용할 수 있는 배열을 연관 배열이라고 한다.
결정된 요소 수만 저장할 수 있는 배열을 정적 배열(static array) 또는 고정 길이 배열(fixed-length array)이라고 부른다[18]。
길이가 고정되어 있지 않고 실행 시 필요에 따라 요소를 추가하거나 삭제할 수 있는 배열을 동적 배열(dynamic array) 또는 가변 길이 배열(variable-length array)이라고 한다。 표준 라이브러리에서 제공되는 것(C++의 `std::vector`, Java의 , .NET의 System.Collections.Generic.List[21] 등)과, 언어에 내장된 것(Perl, D, JavaScript, Python의 list 등)이 있다.
Visual Basic, Visual Basic for Applications (VBA), Visual Basic .NET (VB.NET)에서는 배열을 문을 사용하여 나중에 크기를 조정할 수 있다[25]。
일반적으로 동적 배열은 내부적으로는 정적 배열로 구현되며, 부족해졌을 경우 새로운 영역을 확보하여 데이터를 옮겨서 실현된다.
1차원뿐만 아니라 2차원, 3차원 등의 다차원 배열(multidimensional array)을 갖춘 언어도 있다. 행렬이나 그리드와 같은 직사각형 구조를 가진 데이터 구조이므로, 직사각형 배열(rectangular array)이라고 불리기도 한다.[37]
C#이나 FORTRAN 등 일부 언어에는 "진정한" 다차원 배열이 있으며, `a[i, j]` 등과 같은 구문으로 접근한다.
"배열의 배열"의 경우, 내부 배열의 요소 수가 동일할 필요가 없는 데이터 구조일 수 있다. 재그 배열(jagged array), 불규칙 배열이라고도 한다. 자바(Java)에서의 배열의 배열은 재그 배열이다. C#에는 "진정한 다차원 배열"과 배열의 배열이 있으며, 배열의 배열은 자바와 마찬가지로 재그 배열이다.
요소의 주소를 지정하기 위한 참조 전개는 재그 배열에서는 차원의 수만큼 필요하지만, 직사각형 배열에서는 한 번으로 끝난다. 또한 배열의 영역을 확보할 때, 재그 배열에서는 차원마다 영역 확보를 반복할 필요가 있지만, 직사각형 배열에서는 한 번의 new 연산자 사용으로 영역을 확보할 수 있다. 하지만 직사각형 배열은 모든 요소가 담길 연속된 영역을 확보해야 하므로, 희소 행렬과 같은 드문드문한 배열에는 공간적 오버헤드가 커져 적합하지 않다. 또한, .NET Framework의 중간 언어에는 1차원 배열의 요소 접근에 관한 전용 명령어가 존재하기 때문에, 직사각형 배열보다 재그 배열이 속도 성능 면에서 유리한 경우도 존재한다[39]。
C 언어에서는, 배열을 가리키는 포인터는 그 배열의 크기를 고정해야 한다. 배열을 가리키는 포인터가 아닌, "『배열의 첫 번째 요소를 가리키는 포인터』의 배열"을 사용하여 재그 배열과 같은 데이터 구조를 만들 수 있다.
"자그 배열과 유사한 구조로 구현된 다차원 배열"이라는 의미로, Iliffe vector라는 용어가 있다. 이에 반해, 연속된 영역을 다차원 배열로 취급하는 데이터 구조를 가리키는 dope vector(:en:Dope vector)라는 용어가 있다.
5. 응용
배열은 수학적 좌표 벡터 및 행렬 구현에 사용된다. 크고 작은 많은 데이터베이스는 요소가 레코드인 1차원 배열로 구성되거나 이를 포함한다.
배열은 리스트, 힙, 해시 테이블, 데크, 큐, 스택, 문자열 등 다양한 자료 구조 구현에 사용된다. 배열 기반 자료 구조 구현은 단순하고 공간 효율적이지만, 수정될 때 트리 기반 자료 구조에 비해 공간 복잡성이 좋지 않을 수 있다.
하나 이상의 큰 배열은 프로그램 내 동적 메모리 할당, 특히 메모리 풀 할당을 에뮬레이션하는 데 사용되기도 한다.
배열은 프로그램에서 제어 흐름을 결정하는 제어 테이블로 사용될 수 있으며, 배열에 포함된 값에 따라 제어 흐름이 변경된다.
6. 한국에서의 활용
7. 관련 기술 및 정책
8. 기타
8. 1. 계산 복잡도
배열의 '저장'과 '선택' 연산은 결정적 최악의 경우 상수 시간이 소요된다. 배열은 저장하는 요소의 수 'n'에 대해 선형 (O(''n'')) 공간을 차지한다.요소 크기가 ''k''인 배열과 B 바이트의 캐시 라인 크기를 가진 머신에서, ''n''개의 요소를 순회하려면 최소한 ceiling(''nk''/B)번의 캐시 미스가 필요하다. 그 이유는 배열의 요소들이 연속적인 메모리 위치를 차지하기 때문이다. 이는 무작위 메모리 위치에서 ''n''개의 요소에 접근하는 데 필요한 캐시 미스 횟수보다 대략 B/''k''배 더 좋다. 결과적으로, 배열을 순차적으로 순회하는 것은 다른 많은 데이터 구조를 순회하는 것보다 실제로 눈에 띄게 빠르며, 이를 참조 지역성이라고 한다. 라이브러리는 메모리 범위 복사를 위한 하위 수준의 최적화된 기능(예: memcpy)을 제공하며, 이를 사용하여 개별 요소 접근을 통해 달성할 수 있는 것보다 훨씬 빠르게 배열 요소의 연속적인 블록을 이동할 수 있다.
메모리 측면에서 배열은 요소당 오버헤드가 없는 컴팩트한 데이터 구조이다. 배열당 오버헤드가 있을 수 있지만, 이는 언어에 따라 다르다. 또한 배열에 저장된 요소가 개별 변수에 저장된 동일한 요소보다 ''더 적은'' 메모리를 필요로 할 수 있다. 여러 배열 요소를 단일 워드에 저장할 수 있기 때문이다. 이러한 배열을 종종 '팩' 배열이라고 한다. 극단적이지만 일반적으로 사용되는 사례는 모든 비트가 단일 요소를 나타내는 비트 배열이다.
배열에 요소를 삽입/삭제할 때, 요소 사이에 "틈"이 없도록 하려면, 선형 리스트와 달리 삽입/삭제 위치에서 뒤의 영역에 있는 모든 데이터를 이동(복사)해야 한다. 따라서 삽입/삭제에 걸리는 시간은 O(''n'')이 된다. 또한 배열은 연속된 영역을 필요로 하기 때문에, 삽입 시 영역이 부족한 경우 확장할 때 메모리 재확보 비용이 높다.
탐색은 일반적으로 선형 탐색이 되므로 O(''n'')이지만, 데이터가 정렬되어 있으면 이진 탐색을 사용하여 O(log ''n'')으로 줄일 수도 있다.
8. 2. 다른 자료 구조와의 비교
(인덱스)평균