1. 개요
Array, Configure. 프로그래밍 언어에서 지원하는 자료형 또는 컴퓨터공학에서 사용하는 자료구조의 하나이다. 순서대로 번호가 붙은 원소들이 연속적인 형태로 구성된 구조를 뜻하며, 이때 각 원소에 붙은 번호를 흔히 첨자(인덱스, index)라고 부른다. 원소들이 연속적으로 배치되어 있기에, 임의의 첨자로 각 원소를 접근하는 데에 드는 시간복잡도는 [math(O(1))]이다. 따라서 임의 접근(random access)이 가능한 자료구조에 속한다. 메모리 주소가 연속될 것을 요구하기 때문에 배열의 크기를 늘리는 것은 절대 불가능하며, 배열의 크기를 늘릴 필요가 있을 때에는 크기가 큰 새 배열을 만들고 기존 내용을 복사하거나, 배열의 일부를 연결 리스트 등으로 다른 곳과 연결하는 등의 방법이 쓰인다.배열에서 사용할 수 있는 연산은 보통 다음과 같다.
- 일정한 길이의 빈 배열을 만든다.
- 배열의 길이를 알아본다.
- 주어진 위치에 있는 원소를 알아본다. 원소를 찾는 데에 드는 시간은 O(1).
- 주어진 위치에 새로운 원소를 대입한다. 마찬가지로 위치를 찾는 데에 걸리는 시간은 O(1).
- 주어진 위치에 있는 원소를 삭제한다. 이때 배열의 길이가 하나 줄어들며 O(n)만큼의 시간이 걸린다.
연결 리스트와 비교하면 임의 접근이 가능하지만 요소의 삽입/삭제가 느린 단점이 있다. 반면 연결 리스트는 순차 접근만 가능하기 때문에 임의의 위치에 있는 원소를 찾는 것은 느리지만 일단 위치를 알면 삽입/삭제는 배열에 비해 빠르다.
튜링 머신의 현신이나 마찬가지인 현대 컴퓨터 구조의 특성상[1] 하드웨어적인 버프를 상당히 많이 받는 자료구조로[2], 다른 자료구조를 구현할 때도 이런 특성을 활용해서 최적화를 하는 경우가 있다.[3] 물론 그만큼 성능이 엄청나게 절실할 때의 얘기.
2011년 대학수학능력시험 언어영역에 연결 리스트와 비교하는 문제가 등장하여 수많은 문과생들을 충공깽에 빠뜨렸다. #
배열의 첨자는 보통 주어진 범위 사이의 연속적인 숫자로 제한되는데, 이 제한을 없애고 임의의 값을 첨자로 쓸 수 있게 하는 대신 순서성을 포기하면 연관 배열이 된다.
2. 자료형(Data Type)과 자료구조(Data Structure)의 차이
자료구조로서 배열은 인덱스를 가지며, 이 인덱스에 의해 접근이 가능한 순차적으로 구성된 자료구조를 뜻한다. 자료형으로서 배열은, 해당 프로그래밍 언어의 문법 수준에서 이러한 자료구조인 배열을 기본적인 자료형으로 지원하는 경우를 말한다.컴퓨터 사이언스 초기에 등장한 어셈블리어와 여러 프로그래밍 언어는 배열을 문법수준에서 지원하지는 못했다. 그러나 현실적인 필요성으로 FORTRAN, COBOL, ALGOL 등 초기의 고급언어에서 이를 기본적으로 지원하기 시작했고, 이후 거의 모든 프로그래밍 언어의 필수 요소가 되었다.[5]
보통 타입 시스템이 있는 언어에서는 기본적으로 한 종류의 타입을 가진 원소만 받아들이는 경우가 많은데 이것도 하드웨어적인 이유 때문으로, 보통 그냥 연속된 메모리 공간상에 값이 일렬로 붙어있는 식으로 구현되기 때문이다. C에서 이 점을 가장 극명하게 느낄 수 있다.
마찬가지 이유로, 대부분의 프로그래밍 언어는 배열 첨자를 0부터 시작한다. N개의 원소를 가진 배열 A를 만들었으면 그 원소들을 참조할 때에는 A[0], A[1], ..., A[N-1] 로 참조하게 된다. 즉 첫번째 원소가 A[1] 이 아니라 A[0]이 되기 때문에 프로그래밍에 익숙하지 않은 사람들이 혼동을 겪는 원인 중 하나가 된다.[6] 이러한 방식을 채택하는 데에는 하드웨어적인 이유와 역사적 이유, 그리고 논리적 이유가 모두 존재한다.[7][8] 이를 이용해서 공대 개그에서는 '공대생(특히 컴공)은 번호를 붙일 때 0부터 붙인다'라는 식으로 써먹힌다.
3. 프로그래밍 언어에서의 모습
3.1. C
C에서도 기본적인 자료형으로 제공되며, 배열은 말 그대로 고정된 크기의 연속된 메모리이다. 실제 데이터가 위치하고 있는 가장 처음 메모리 주소를 갖고 있으며 배열 변수명 자체를 포인터로서 활용할 수 있다.배열은 연속적인 위치를 보장하므로 (포인터 값 + 데이터형의 크기)의 형태로 다음 요소에 접근할 수 있다.[9]
int staticArray[10];
int* dynamicArray = (int*)malloc(sizeof(int)*10); [3], dynamicArray[3]과 같은 형태로 접근할 수 있다. 정적으로 할당하면 무조건 컴파일 시간에 크기를 결정해야 하며 실행중에 크기를 변경할 수 없다. 동적으로 할당하게 되면 실행 시간에 크기를 결정할 수 있으며 재할당도 가능하나 프로그램 종료전에 반환 해주어야 한다. OS에 따라 적절하게 처리해 주기도 하지만 보통은 문제를 야기할 수 있다.C에서 주의할 것은, 배열의 크기는 유한하고 접근할 수 있는 범위도 처음 선언했던 크기만큼으로 제한되어 있지만, 실제로 배열 원소에 접근할 때에는 이게 맞는 범위에 접근하는지 전혀 체크하지 않는다. 때문에 잘못 짜면 컴파일할 때는 조용히 있다가 실행할 때 세그멘테이션 오류(Segmentation fault)가 발생하거나, 더 운이 안 좋은 경우에는 오류도 안 내면서 조용히 다른 범위의 메모리를 건드려 찾기 어려운 버그를 일으킨다.
사실 C에서 배열은 굉장히 애매한 지위를 차지하고 있는데, C에서 배열(배열 이름을 포함해서, 배열 타입을 결과값을 갖는 모든 수식)은 딱 세 가지 경우[10]를 제외하면 그냥 배열 첫 원소의 주소로 변환된다. 그래서 사실 C에서 배열에 대고 한다고 생각하는 연산들은 사실 그냥 포인터에 대고 하는 거랑 다를 게 없다. 심지어 n번째 원소에 접근하는 것도 배열 시작주소에서 n만큼 떨어진 메모리의 값을 구하는 것과 정확히 똑같다. 즉
a[i] == *(a + i)다.[11] 그리고, 다른 게 하나 더 있는데, 배열 이름은 상수처럼 취급되어서 대입이 안 된다.[12][13] 어떻게 보면 실행중에 포인터로 가리킨 배열의 길이를 알아내거나 배열 범위 검사를 안 하는 게 이런 이유 때문인데, 사실 C에는 배열 '자료구조'가 있는 게 아니라 그냥 연속된 메모리 공간을 직접 다루게 해 주는 것뿐이므로 길이를 알래야 알 수가 없는 거다. 다차원 배열의 경우에는 얘기가 좀 더 복잡해지는데, 다차원 배열도 배열의 전체 영역이 전부 일렬로 메모리에 배치된다. 그래서
int a[5][5]; 같은 배열이 있으면 &a[0]의 타입은 int **이 아니라 int (*)[5]이다. 그래서 일반 포인터는 일차원 배열처럼 쓸 수 있는데, 다차원 포인터는 다차원 배열처럼 쓸 수가 없다. 다차원 배열을 함수 인자로 넘길 때 void f(int a[][5])처럼 맨 앞 첨자만 []로 쓰는 데에는 이런 이유가 있다.[14] 이게 문제를 엄청나게 복잡하게 만들기 때문에 사람에 따라서는 아예 다차원 배열을 전혀 쓰지 않고 전부 다차원 포인터에 동적할당시켜서 쓰는 경우도 있다. 그럼에도 중간에 다차원 배열을 인자로 받는 함수가 하나라도 있으면 골치썩는다. 차라리 일차원 배열을 강제 형변환해서 넘기는 게 더 쉽다.(...)자세한 이야기는 다음 문서를 참조하자. C Programming FAQs - 6. Arrays and Pointers[15]
3.2. Java
#!syntax java
int[] arr = new int[10] // 데이터 타입은 정수, 배열의 크기는 10, 배열의 이름은 'arr'
String[] names = new String[5] // 데이터 타입은 문자열, 배열의 크기는 5, 배열의 이름은 'names'
배열과 관련된 다양한 함수들이 미리 정의되어 있으므로 편하게 사용할 수 있다.
3.3. PHP
#!syntax php
$static_array=array(1,2,3,4,5);
echo $static_array[0]." ";
echo $static_array[1];
//print : 1 2
foreach($static_array as $k=>$v){
echo "$v ";
}
//print : 1 2 3 4 5
$static_array를 다음과 같이 표현 가능하다.#!syntax php
$static_array=[1,2,3,4,5];
3.4. C#
1차원 배열#!syntax csharp
int[] i = new int [5] {1, 10, 100, 1000, 10000}; //물론 값을 나중에 지정해 줘도 무관
//i[0]~i[4] 이렇게 5개 생성
i[2] = 3;
Console.WriteLine(i[2]); //출력 결과:3
string[] str = new string[10]
//str[0]~str[9] 이렇게 10개 생성
str[8] = "Hello world";
Console.WriteLine(str[8]); //출력 결과: Hello World
2차원 배열
#!syntax csharp
int[] i = new int [3, 5]; //가로로 5, 세로로 3 총 15개
i[1, 2] = 20;
3차원 배열
#!syntax csharp
int[] i = new int [3, 7, 5]; //앞으로 3, 세로로 7, 가로로 5 총 105개
i[0, 5, 2] = 30
3.5. 포트란
포트란 95 자유형식 기준.Program arraytest
integer:: A(5); !인덱스가 1부터 5인 1차원 배열
integer:: B(0:5); !인덱스가 0부터 5인 1차원 배열
integer:: C(2,3); !2줄 3행 2차원 배열
integer:: D; !처음에 그냥 정수형 변수 선언
Character(50):: E; !최대길이가 50인 문자열 선언
a(2) = 50;
Print *, A(2); !50이 출력됨
b(0) = 1;
Print *, B(0); !0 출력
C(1,2) = 45;
C(2,3) = 7;
write(*, "(I0, A, I0, A, I0)") C(1,2), " + ", C(2,3), " = ", c(1,2)+c(2,3); ! 45 + 7 = 52
D = [1,2,3,4,5]; !D 변수를 배열로 만든다.
DO 10 i = 1, 5
write(*, "(I0, A)", advance="no") D(i), " ";
10 Continue !1 2 3 4 5 출력됨.
E = "Hello, world!";
Print *, e; !Hello, world! 출력
End
기본적으로 인덱스는 1부터 시작한다.[18][19]
포트란은 배열 선언 시
배열이름(시작인덱스:끝인덱스) 형식으로 인덱스를 0부터 시작하게 할 수 있다. 음수 인덱스도 가능하다.3.6. Python
#!syntax python
# 1차원 배열
array = [1, 2, 3, 4]
# 2차원 배열
array = [[1, 2], [3, 4]]
# 다만 파이썬 기본 2차원 배열은 열이 달라도 실행이 가능하다. 예) [[1,2],[3],[4,5,6]] , 3차원 배열은 행렬이 달라도 된다. 다만 넘파이 에서는 에러이다.
3.7. JavaScript
#!syntax javascript
var A = [];
var B = new Array;
var C = new Array();
var D = Array();
var E = [1, 2, 3];
var F = new Array(1, 2, 3);
var G = Array(1, 2, 3);
for(arr of [A, B, C, D, E, F, G])
{ console.log(arr, arr.length);
console.log(arr instanceof Array); } // true
4. 관련 문서
[1]
메모리 모델 자체가 일종의 커다란 배열이며 메모리 주소가 곧 인덱스나 다름없다.
[2]
대부분의 CPU가 캐시를 적용하는 기준이 일정 크기의 연속된 메모리 영역이며, 심지어 SIMD처럼 고정 길의의 메모리에 한번에 연산하는 기계어 셋도 존재한다.
[3]
예: 연결 리스트를 그냥 구현하면 사용하는 메모리 영역이 사방에 흩어지는데, 메모리 풀을 구현해서 접근하는 메모리 영역의 범위를 좁혀 캐시 적중률을 높일 수 있다.
[4]
배열은 그렇다 쳐도 연결 리스트는 컴퓨터공학 전공과정에서도 보통 2학년은 되어야 등장하는 개념으로,
프로그래밍에 대한 경험이 전혀 없는 사람이 주어진 지문만으로 이해하는 것은 어렵다. 물론, 언어영역 자체가 지문에서 질문에 해당하는 내용을 찾는 것만 요구하기 때문에, 배경지식과 관계없이 지문을 파악하는 능력만 갖춰진다면 맞출 사람은 다 맞추는 게 함정. 원래 수능 언어영역에는 오만가지 전문개념이 등장하므로 연결 리스트가 출제된게 전혀 특별한 일은 아니지만, 이공계열 지식은 특히나 일반인들에게는 '범접할 수 없는 것' 등의 더욱 동떨어진 인식이다 보니 유독 임팩트가 크게 다가오곤 한다. 철학이나 법 같은 인문계열처럼 일단 '한국어만 할 줄 알면' 파악할 수 있는 분야와 달리 이쪽은 한국어로 적어놔도 내용이해에서 막히기 때문.
[5]
람다대수와
리스트에 기반한
LISP 정도가 예외였는데 결국 현실을 넘지는 못했다... 때문에
아예 LISP만을 위한 LISP 머신 같은 것마저 만들어졌지만... 요즘은
객체 지향 프로그래밍 같은 개념도 등장하고 컴퓨터 성능도 좋아져서 다른 자료구조도 기본으로 지원해주는 경우도 꽤 늘긴 했다.
[6]
숙련된 개발자들도 종종 실수해서 에러를 터뜨릴 정도로 은근히 프로그래밍에 있어서 함정이 되는 부분. 한편으로는 이러한 방식에 너무 익숙해지다보니 일상에서 번호를 메길 때 1부터 메겨진 걸 보면 묘하게 어색하게 느껴지는 경우도 있다. 일종의 직업병.
[7]
다익스트라가 쓴 '왜 숫자는 0부터 세어야 하는가'(영문)
앞의 링크의 내용을 한국어로 정리한 글
[8]
요약하자면 0부터 시작해서 N-1로 끝나는 것이 직관적으로도 생각하기 편하고 보기에 깔끔하며(논리적 이유), 메모리를 다룰 때에도 효율적이며 실제로 이러한 방식을 따르지 않는 환경에서 코드를 짜서 실험을 해본 결과 오류가 발생한 사례가 있다.(하드웨어적인 이유) 게다가 이런 방식의 넘버링 관습은 C언의 전신인 BCPL 시절부터 있었던 유서깊은 관습이다.(역사적 이유) 이러한 넘버링 관습을 따르지 않았던
포트란이나
알골 등의 구세대 언어가 C언어에 완전히 대체된 것도 여러 이유가 있겠지만 이 점 역시 원인으로 작용했을 가능성이 있다.
[9]
각 원소 사이에 빈공간(padding)이 들어가지 않는다는 얘기다.
구조체 같은 경우는 정렬 제한을 맞추기 위해 맴버 변수 사이 혹은 그 끝에 빈공간이 들어갈 수 있다.
[10]
그렇다고 실제로 프로그래밍할 때 저런 코드 쓰진 말고
[12]
위에서 말한 규칙 때문이다. 대입 연산자 = 의 좌변에 배열 이름을 적으면 배열 첫 원소의 주소로 변환되며, 따라서 l-value가 아니게 된다. 배열을 매개변수로 가지는 구조체조차도 대입 연산이 되는데, 배열은 안 된다.
[13]
그래서 배열 이름을 포인터 상수라고도 한다.
[14]
사실 C언어에서는 함수 인자에 배열을 사용할 수 없다. 함수 인자에서 배열 타입으로 선언된 매개변수는 포인터 타입으로 자동 변환되어 처리된다. n차원 배열의 경우에는 (n-1)차원 배열에 대한 포인터로 변환된다.
[15]
한글이 올바로 출력되지 않는다면 인코딩을 UTF-8로 고쳐보자
[16]
일반적으로 언어 구현에서 미리 제공해주는 표준 라이브러리의 경우 웬만한 상황에서 무난한 성능 이상을 발휘하도록 구현되어 있다. 0.1마이크로세컨드라도 성능을 올려야 하는 극단적인 상황이 아닌 이상에야 대다수의 경우 표준 라이브러리를 활용하는 것이 최선이다. 밥먹고 그런거만 연구하고 구현하는 양반들이 만든 거다. 웬만하면 그냥 있는거 써도 괜찮다.
[17]
다만 해당 함수들이 어떻게 동작하는지 원리 자체는 알고 있어야 한다. 안 그러면 배열가지고
연결 리스트마냥 막 중간에다 삽입삭제하다가 개차반나는 수가 있다.
[18]
배열의 인덱스가 1부터 시작하는 언어는 대표적으로 R, 포트란, 매트랩 등이 있다. 자세한 내용은 다음 위키피디아를 참고.
[19]
https://en.wikipedia.org/wiki/Comparison_of_programming_languages_%28array%29#Array_system_cross-reference_list
sizeof 연산자를 쓸 때, & 연산자를 쓸 때, 문자 배열을 문자열 상수로 초기화할 때.
[11]
농담하는 게 아니다. 실제로 int a[3] = {2, 4, 8}; printf("%d", 1[a]); 같은 코드가 멀쩡히 동작한다.
#참고