배열(프로그래밍)

개요[편집 / 원본 편집]

배열(Array)은 프로그래밍에서 가장 기본적이고 널리 사용되는 자료 구조 중 하나이다. 동일한 데이터 타입의 여러 요소를 연속된 메모리 공간에 저장하는 방식으로, 효율적인 데이터 관리와 접근을 가능하게 한다.

배열의 개념은 컴퓨터 과학의 초기부터 존재했다. 1950년대 초반, 프로그래밍 언어 FORTRAN에서 처음으로 배열이 도입되었으며, 이후 거의 모든 프로그래밍 언어에서 기본적인 자료 구조로 자리 잡았다.

배열의 가장 큰 특징은 연속된 메모리 공간에 데이터를 저장한다는 점이다. 이로 인해 인덱스를 통한 빠른 접근이 가능하다.

대부분의 프로그래밍 언어에서 배열은 생성 시 크기가 고정된다. 이는 메모리 관리의 효율성을 높이지만, 동적인 크기 조절에는 제한이 있다.

하나의 배열은 동일한 데이터 타입의 요소들만 저장할 수 있다. 이는 메모리 사용의 일관성과 효율성을 보장한다.

다양한 프로그래밍 언어에서 배열을 구현하는 방식을 살펴보자.

C언어에서 배열은 다음과 같이 선언하고 사용할 수 있다:

int numbers[5] = {1, 2, 3, 4, 5};
printf("%d", numbers[2]); // 출력: 3

Python에서는 리스트를 사용하여 배열과 유사한 기능을 구현한다:

numbers = [1, 2, 3, 4, 5]
print(numbers[2])  # 출력: 3

Java에서는 다음과 같이 배열을 선언하고 사용한다:

int[] numbers = {1, 2, 3, 4, 5};
System.out.println(numbers[2]);  // 출력: 3

배열의 특정 요소에 접근하는 것은 O(1)의 시간 복잡도를 가진다. 이는 배열의 가장 큰 장점 중 하나이다.

정렬되지 않은 배열에서의 검색은 O(n)의 시간 복잡도를 가진다. 정렬된 배열에서는 이진 검색을 통해 O(log n)으로 개선할 수 있다.

배열의 끝에 요소를 추가하거나 삭제하는 것은 O(1)의 시간 복잡도를 가진다. 그러나 중간에 삽입하거나 삭제하는 경우, 다른 요소들을 이동시켜야 하므로 O(n)의 시간 복잡도를 가진다.

배열은 여러 차원으로 확장될 수 있다. 2차원 배열은 행렬을 표현하는 데 자주 사용된다.

int matrix[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
printf("%d", matrix[1][1]); // 출력: 5

배열은 다양한 알고리즘과 자료 구조의 기본이 된다. 몇 가지 예를 들면:

버블 정렬, 선택 정렬, 퀵 정렬 등 대부분의 정렬 알고리즘은 배열을 기반으로 한다.

스택과 큐와 같은 추상 자료형은 배열을 사용하여 구현할 수 있다. 자세한 내용은 큐(프로그래밍), 스택(프로그래밍) 문서를 참고하자.

인접 행렬을 사용한 그래프 표현은 2차원 배열을 활용한다.

배열은 간단하면서도 강력한 자료 구조로, 프로그래밍의 기본이 되는 요소이다. 그 단순성과 효율성 때문에 다양한 알고리즘과 더 복잡한 자료 구조의 기반이 되며, 현대 프로그래밍에서도 여전히 중요한 역할을 하고 있다.

Knuth, Donald. The Art of Computer Programming, Volume 1: Fundamental Algorithms. Addison-Wesley, 1997.
Cormen, Thomas H., et al. Introduction to Algorithms. MIT Press, 2009.