배열

Array

1 개요

프로그래밍 언어에서 지원하는 자료형 또는 컴퓨터 과학에서 사용하는 자료구조의 하나. 순서대로 번호가 붙은 원소들이 연속적인 형태로 구성된 구조를 뜻하며, 이때 각 원소에 붙은 번호를 흔히 첨자(인덱스, index)라고 부른다. 원소들이 연속적으로 배치되어 있기에, 임의의 첨자로 각 원소를 접근하는 데에 드는 시간복잡도는 O(1)이다. 따라서 임의 접근(random access)이 가능한 자료구조에 속한다. 정의에 의하면 고정된 크기를 가지지만 크기를 더 늘릴 수 있는 경우도 있다.[1]

배열에서 사용할 수 있는 연산은 보통 다음과 같다.

  • 일정한 길이의 빈 배열을 만든다.
  • 배열의 길이를 알아본다.
  • 주어진 위치에 있는 원소를 알아본다. 원소를 찾는 데에 드는 시간은 O(1).
  • 주어진 위치에 새로운 원소를 대입한다. 마찬가지로 위치를 찾는 데에 걸리는 시간은 O(1).
  • 주어진 위치에 새로운 원소를 삽입한다. 이때 배열의 길이가 하나 늘어나며 O(n)만큼의 시간이 걸릴 수 있다.[2]
  • 주어진 위치에 있는 원소를 삭제한다. 이때 배열의 길이가 하나 줄어들며 삽입의 경우와 마찬가지로 O(n)만큼의 시간이 걸린다.

연결 리스트와 비교하면 임의 접근이 가능하지만 요소의 삽입/삭제가 느린 단점이 있다. 반면 연결 리스트는 순차 접근만 가능하기 때문에 임의의 위치에 있는 원소를 찾는 것은 느리지만 일단 위치를 알면 삽입/삭제는 배열에 비해 빠르다.

튜링 머신의 현신이나 마찬가지인 현대 컴퓨터 구조의 특성상[3] 하드웨어적인 버프를 상당히 많이 받는 자료구조로[4], 다른 자료구조를 구현할 때도 이런 특성을 활용해서 최적화를 하는 경우가 있다.[5] 물론 그만큼 성능이 엄청나게 절실할 때의 얘기.

2011년 대학수학능력시험 언어영역에 연결 리스트와 비교하는 문제가 등장하여 수많은 문과생들을 충공깽에 빠뜨렸다. # C언어영역[6]

배열의 첨자는 보통 주어진 범위 사이의 연속적인 숫자로 제한되는데, 이 제한을 없애고 임의의 값을 첨자로 쓸 수 있게 하는 대신 순서성을 포기하면 연관 배열이 된다.

2 배열: 자료형(Data Type)과 자료구조(Data Structure)의 차이

자료구조로서 배열은 인덱스를 가지며, 이 인덱스에 의해 접근이 가능한 순차적으로 구성된 자료구조를 뜻한다. 자료형으로서 배열은, 해당 프로그래밍 언어의 문법 수준에서 이러한 자료구조인 배열을 기본적인 자료형으로 지원하는 경우를 말한다.

컴퓨터 사이언스 초기에 등장한 어셈블리어와 여러 프로그래밍 언어는 배열을 문법수준에서 지원하지는 못했다. 그러나 현실적인 필요성으로 FORTRAN, COBOL, ALGOL 등 초기의 고급언어에서 이를 기본적으로 지원하기 시작했고, 이후 거의 모든 프로그래밍 언어의 필수 요소가 되었다.[7]

보통 타입 시스템이 있는 언어에서는 기본적으로 한 종류의 타입을 가진 원소만 받아들이는 경우가 많은데 이것도 하드웨어적인 이유 때문으로, 보통 그냥 연속된 메모리 공간상에 값이 일렬로 붙어있는 식으로 구현되기 때문이다. C에서 이 점을 가장 극명하게 느낄 수 있다.

마찬가지 이유로, 대부분의 프로그래밍 언어는 배열 첨자를 0부터 시작한다. N개의 원소를 가진 배열 A를 만들었으면 그 원소들을 참조할 때에는 A[0], A[1], ..., A[N-1] 로 참조하게 된다. 즉 첫번째 원소가 A[1] 이 아니라 A[0]이 되기 때문에 프로그래밍에 익숙하지 않은 사람들이 혼동을 겪는 원인 중 하나가 된다. 이러한 방식을 채택하는 데에는 하드웨어적인 이유와 역사적 이유, 그리고 논리적 이유가 모두 존재한다. 논리적 이유에 대한 링크 영어다 이를 이용해서 공대 개그에서는 '공대생(특히 컴공)은 번호를 붙일 때 0부터 붙인다'라는 식으로 써먹힌다.

3 C에서의 배열

C에서도 기본적인 자료형으로 제공되며, 배열은 말 그대로 고정된 크기의 연속된 메모리이다. 실제 데이터가 위치하고 있는 가장 처음 메모리 주소를 갖고 있으며 배열 변수명 자체를 포인터로써 활용할 수 있다.

배열은 연속적인 위치를 보장하므로 (포인터 값 + 데이터형의 크기)의 형태로 다음 요소에 접근할 수 있다. [8] 

int staticArray[10];
int* dynamicArray = (int*)malloc(sizeof(int)*10);

위의 staticArray와 dynamicArray는 모두 staticArray[3], dynamicArray[3]과 같은 형태로 접근할 수 있다. 정적으로 할당하면 무조건 컴파일 시간에 크기를 결정해야 하며 실행중에 크기를 변경할 수 없다. 동적으로 할당하게 되면 실행 시간에 크기를 결정할 수 있으며 재할당도 가능하나 프로그램 종료전에 반환 해주어야 한다. OS에 따라 적절하게 처리해 주기도 하지만 보통은 문제를 야기할 수 있다.

C에서 주의할 것은, 배열의 크기는 유한하고 접근할 수 있는 범위도 처음 선언했던 크기만큼으로 제한되어 있지만, 실제로 배열 원소에 접근할 때에는 이게 맞는 범위에 접근하는지 전혀 체크하지 않는다. 때문에 잘못 짜면 컴파일할 때는 조용히 있다가 실행할 때 세그멘테이션 오류(Segmentation fault)가 발생하거나, 더 운이 안 좋은 경우에는 오류도 안 내면서 조용히 다른 범위의 메모리를 건드려 찾기 어려운 버그를 일으킨다.

사실 C에서 배열은 굉장히 애매한 지위를 차지하고 있는데, C에서 배열(배열 이름을 포함해서, 배열 타입을 결과값을 갖는 모든 수식)은 딱 세 가지 경우[9]를 제외하면 그냥 배열 첫 원소의 주소로 변환된다. 그래서 사실 C에서 배열에 대고 한다고 생각하는 연산들은 사실 그냥 포인터에 대고 하는 거랑 다를게 없다. 심지어 n번째 원소에 접근하는 것도 배열 시작주소에서 n만큼 떨어진 메모리의 값을 구하는 것과 정확히 똑같다. 즉 a[i] == *(a + i)다.[10] 아, 다른 게 하나 더 있는데, 배열 이름은 상수처럼 취급되어서 대입이 안 된다.[11] 어떻게 보면 실행중에 포인터로 가리킨 배열의 길이를 알아내거나 배열 범위 검사를 안 하는 게 이런 이유 때문인데, 사실 C에는 배열 '자료구조'가 있는 게 아니라 그냥 연속된 메모리 공간을 직접 다루게 해 주는 것뿐이므로 길이를 알 래야 알 수가 없는 거다. 그리고 여기서 우리는 C가 우리가 생각하는 것보다 훨씬 저수준 언어였다는 것을 알 수가 있다.

다차원 배열의 경우에는 얘기가 좀 더 복잡해지는데, 다차원 배열도 배열의 전체 영역이 전부 일렬로 메모리에 배치된다. 그래서 int a[5][5]; 같은 배열이 있으면 &a[0]의 타입은 int **이 아니라 int (*)[5]이다. 그래서 일반 포인터는 일차원 배열처럼 쓸 수 있는데, 다차원 포인터는 다차원 배열처럼 쓸 수가 없다. 다차원 배열을 함수 인자로 넘길 때 void f(int a[][5])처럼 맨 앞 첨자만 []로 쓰는 데에는 이런 이유가 있다. [12] 이게 문제를 엄청나게 복잡하게 만들기 때문에 사람에 따라서는 아예 다차원 배열을 전혀 쓰지 않고 전부 다차원 포인터에 동적할당시켜서 쓰는 경우도 있다. 그럼에도 중간에 다차원 배열을 인자로 받는 함수가 하나라도 있으면 골치썩는다. 차라리 일차원 배열을 강제 형변환해서 넘기는 게 더 쉽다. (...)

자세한 이야기는 다음 문서를 참조하자. C Programming FAQs - 6. Arrays and Pointers[13]

4 자바에서의 배열

Java에서 배열은 객체이자 기본적으로 지원되는 자료형 중 하나이다.

배열과 관련된 다양한 함수들이 미리 정의되어 있으므로 편하게 사용할 수 있다. 다만 퍼포먼스 보장은 못한다.[14][15] C/C++와는 달리 항상 동적으로 할당되며 별도의 반환이 필요없이 제거되거나 재할당되면 GC에서 알아서 반환해준다.
  1. ↑ 물론 실제 메모리 크기 내에서
  2. ↑ 원소들이 연속된 순서를 유지해야 하기 때문에 중간에 값을 삽입하면 뒤에 있는 값들을 전부 한 칸씩 뒤로 밀어야 하기 때문이다.
  3. ↑ 메모리 모델 자체가 일종의 커다란 배열이며 메모리 주소가 곧 인덱스나 다름없다.
  4. ↑ 대부분의 CPU가 캐시를 적용하는 기준이 일정 크기의 연속된 메모리 영역이며, 심지어 SIMD처럼 고정 길의의 메모리에 한번에 연산하는 기계어 셋도 존재한다.
  5. ↑ 예: 연결 리스트를 그냥 구현하면 사용하는 메모리 영역이 사방에 흩어지는데, 메모리 풀을 구현해서 접근하는 메모리 영역의 범위를 좁혀 캐시 적중율을 높일 수 있다.
  6. ↑ 배열은 그렇다 쳐도 연결 리스트는 컴퓨터공학 전공과정에서도 보통 2학년은 되어야 등장하는 개념으로, 프로그래밍에 대한 경험이 전혀 없는 사람이 주어진 지문만으로 이해하라는 것 자체가 상당한 무리였다.
  7. ↑ 람다 대수와 리스트에 기반한 LISP 정도가 예외였는데 결국 현실을 넘지는 못했다... 때문에 아예 LISP만을 위한 LISP 머신 같은 것마저 만들어졌지만... 요즘은 객체 지향 프로그래밍 같은 개념도 등장하고 컴퓨터 성능도 좋아져서 다른 자료구조도 기본으로 지원해주는 경우도 꽤 늘긴 했다.
  8. ↑ 각 원소 사이에 빈공간(padding)이 들어가지 않는다는 얘기다. 구조체 같은 경우는 정렬 제한을 맞추기 위해 맴버 변수 사이 혹은 그 끝에 빈공간이 들어갈 수 있다.
  9. ↑ sizeof 연산자를 쓸 때, & 연산자를 쓸 때, 문자 배열을 문자열 상수로 초기화할 때.
  10. ↑ 농담하는 게 아니다. 실제로 int a[3] = {2, 4, 8}; printf("%d", 1[a]); 같은 코드가 멀쩡히 동작한다. #참고 그렇다고 실제로 프로그래밍할 때 저런 코드 쓰진 말고
  11. ↑ 위에서 말한 규칙 때문이다. 대입 연산자 = 의 좌변에 배열 이름을 적으면 배열 첫 원소의 주소로 변환되며, 따라서 l-value가 아니게 된다. 배열을 매개변수로 가지는 구조체조차도 대입 연산이 되는데, 배열은 안된다.
  12. ↑ 사실 C언어에서는 함수 인자에 배열을 사용할 수 없다. 함수 인자에서 배열 타입으로 선언된 매개변수는 포인터 타입으로 자동 변환되어 처리된다. n차원 배열의 경우에는 (n-1)차원 배열에 대한 포인터로 변환된다.
  13. ↑ 한글이 올바로 출력되지 않는다면 인코딩을 UTF-8로 고쳐보자
  14. ↑ 일반적으로 언어 구현에서 미리 제공해주는 표준 라이브러리의 경우 웬만한 상황에서 무난한 성능 이상을 발휘하도록 구현되어 있다. 0.1마이크로세컨드라도 성능을 올려야 하는 극단적인 상황이 아닌 이상에야 대다수의 경우 표준 라이브러리를 활용하는 것이 최선이다. 밥먹고 그런거만 연구하고 구현하는 양반들이 만든 거다. 웬만하면 그냥 있는거 써도 괜찮다.
  15. ↑ 다만 해당 함수들이 어떻게 동작하는지 원리 자체는 알고 있어야 한다. 안그러면 배열가지고 연결 리스트마냥 막 중간에다 삽입삭제하다가 개차반나는 수가 있다.