배열(프로그래밍) 편집하기

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

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

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

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

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

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

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

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

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

<syntaxhighlight lang="python">
numbers = [1, 2, 3, 4, 5]
print(numbers[2])  # 출력: 3
</syntaxhighlight>

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

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

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

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

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

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

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

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

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

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

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

== 장단점 ==
=== 장점 ===
* 빠른 요소 접근 (O(1))
* 메모리 효율성
* 캐시 지역성으로 인한 성능 향상

=== 단점 ===
* 고정된 크기 (일부 언어에서는 동적 배열을 지원)
* 삽입과 삭제의 비효율성
* 메모리 낭비 가능성 (크기를 너무 크게 설정한 경우)

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

== 참고 문헌 ==
* 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.

<!--분류-->
[[분류:자료구조]] [[분류:프로그래밍]] [[분류:알고리즘]]