[ Data Structure ] 배열(Array)

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

배열의 주요 연산

배열의 주요 연산은 검색(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: 리스트로 구현되며, 동적 타이핑을 지원한다. 다양한 타입의 요소를 하나의 리스트에 저장할 수 있다.