자료구조는 데이터를 효율적으로 관리하고 사용하기 위한 구조이다. 그 중에서도 배열은 가장 기본적이면서도 널리 사용되는 자료구조 중 하나이다. 이 글에서는 배열의 기본 개념부터 실제 활용 사례, 그리고 고급 주제까지 다뤄보고자 한다.

배열의 주요 연산#

배열의 주요 연산은 검색(Search), 삽입(Insert), 삭제(Delete)이다. 이는 모든 자료구조에 해당하는 것은 아니지만, 많은 자료구조에서 핵심적인 기능을 한다. 저장된 대상을 Item이라고 부른다.

배열(Array)의 기본#

배열은 동일한 데이터 유형의 요소들이 순서대로 저장된 연속적인 메모리 공간이다. 배열의 강점은 다음과 같다:

1. 빠른 접근 속도: 인덱스를 통해 O(1) 시간에 원하는 요소에 접근할 수 있다.
2. 간단한 구현: 대부분의 프로그래밍 언어에서 기본적으로 제공한다.
3. 메모리 효율성: 연속된 메모리 공간을 사용하여 캐시 지역성(Cache Locality)이 좋다.

배열에 Item 저장하기#

배열에 Item을 저장하는 방식은 크게 네 가지로 나눌 수 있다.

1. Packed, Unsorted: 가장 간단한 방식으로, 빈 공간 없이 정렬되지 않은 상태로 저장한다.
2. Packed, Sorted: 정렬된 상태로 저장하여 이진 검색이 가능하다.
3. Unpacked, Unsorted: 빈 공간이 있는 상태로, 각 Item의 사용 여부를 별도로 표시한다.
4. Unpacked, Sorted: 빈 공간이 있으면서 정렬된 상태를 유지한다.

각 방식에 따라 검색, 삽입, 삭제 연산의 성능이 달라진다.

배열 검색 알고리즘#

1. Linear Search: O(N) 시간 복잡도를 가지며, 정렬되지 않은 배열에서 사용한다.
2. Binary Search: O(log N) 시간 복잡도를 가지며, 정렬된 배열에서 사용한다.

다차원 배열#

실제 세계의 많은 데이터는 다차원적 특성을 가진다. 이를 표현하기 위해 다차원 배열을 사용한다.

1. 2차원 배열: 표나 행렬을 표현할 때 사용한다.(예: 체스판의 상태 저장)
2. 3차원 배열: 3D 공간의 데이터를 표현할 때 사용한다. (예: 3D 게임의 맵 데이터)

동적 배열#

정적 배열의 크기 제한을 극복하기 위해 동적 배열을 사용한다. C++의 vector, Java의 ArrayList 등이 이에 해당한다. 동적 배열은 내부적으로 크기를 자동으로 조절하여 더 유연한 데이터 관리가 가능하다.

캐시 지역성(Cache Locality)#

배열은 연속된 메모리 공간을 사용하므로 캐시 효율이 좋다. 이는 특히 대용량 데이터를 처리할 때 성능상 이점을 가져올 수 있다.

배열의 한계와 대안#

배열은 강력하지만 몇 가지 한계가 있다

1. 크기 변경의 어려움
2. 중간 삽입/삭제의 비효율성

이러한 한계를 극복하기 위해 다음과 같은 자료구조들이 사용된다.

• linked list: 동적인 크기 조절과 효율적인 삽입/삭제가 가능하다.
• hash table: 빠른 검색과 삽입이 가능하다.

시간 복잡도와 공간 복잡도#

배열 연산의 효율성은 다음과 같다.

• 접근: O(1)
• 검색: O(N) (정렬되지 않은 경우) 또는 O(log N) (정렬된 경우, 이진 검색)
• 삽입/삭제: O(N) (최악의 경우)

공간 복잡도는 항상 O(N)이다.

언어별 배열 사용의 차이점#

1. C: 저수준 언어로, 포인터를 이용한 직접적인 메모리 조작이 가능하다.
2. Java: 객체로 취급되며, 길이 정보를 포함한다. 기본 타입 배열과 객체 배열이 구분된다.
3. Python: 리스트로 구현되며, 동적 타이핑을 지원한다. 다양한 타입의 요소를 하나의 리스트에 저장할 수 있다.