[자료구조] 배열 (Array)

배열이란?

배열 : 동일한 데이터 유형의 요소들을 일렬로 나열한 것

• 논리적 저장 순서와 물리적 저장 순서가 일치한다.

• 각 요소는 인덱스를 통해 접근할 수 있다.

• 메모리 상에 연속적으로 할당된다.

 

배열의 장단점

장점

1. 빠른 접근 : 인덱스를 통해 요소에 빠르게 접근할 수 있다. 시간복잡도는 O(1)이다.

단점

1. 크기 제한 : 생성할 때 크기를 정해야 하며, 이 크기는 변경할 수 없다.

2. 메모리 낭비 : 미리 정해진 크기를 사용하기 때문에 요소가 모두 채워지지 않는 경우 메모리를 낭비할 수 있다. 크기를 크게 설정하면 필요 이상의 메모리를 사용하게 되고, 작게 설정하면 요소를 저장할 공간이 부족해질 수 있다. 또한, 빈 메모리 공간이 배열의 크기 보다 작으면 사용할 수 없다.

3. 삽입/삭제 어려움 : 배열의 어느 요소를 삭제했다고 했을 때, 배열에 빈 공간이 생기며 연속적인 특징이 깨진다. 따라서 삭제한 요소보다 큰 인덱스를 갖는 요소들을 이동시켜야한다. 이때, 시간 복잡도는 O(n)이 된다. 삽입의 경우도 해당 요소보다 인덱스가 큰 요소들을 이동시켜야하기 때문에 이 경우도 O(n)의 시간이 요구된다.

 

배열을 사용하면 좋은 경우

• 표 형태의 데이터 : 배열은 다차원으로 구성될 수도 있는데, 2차원 배열은 행과 열로 구성되어 표 형태의 데이터를 표현하는 데 사용될 수 있다. 예를 들어, 2차원 배열은 행렬, 게임 보드, 이미지 픽셀 등을 다루는데 유용하다.

• 고정된 크기의 데이터 : 배열은 처음에 크기를 정해야 하기 때문에 데이터 개수가 변하지 않는 상황에서 유용하다. 예를 들어, 알파벳 문자열, 색상 목록, 각 월의 일수 등과 같이 크기가 일정한 데이터를 저장하는 데에 배열을 사용할 수 있다.

• 정렬된 데이터 : 정렬된 배열은 이진 탐색과 같은 효율적인 검색 알고리즘을 적용할 수 있어 빠른 검색 속도를 제공할 수 있기 때문에 데이터가 이미 정렬되어 있는 경우 배열은 유용한 선택일 수 있다.

• 인덱스 기반 접근이 필요한 경우 : 특정 위치에 있는 요소를 직접 참조해야 하는 경우에도 배열을 사용하는 것이 유리하다. 

 

배열을 사용하면 좋지 않은 경우

• 크기가 동적으로 변경되어야 하는 경우 : 배열은 크기가 고정되어 있으므로, 요소의 추가/제거가 빈번하게 발생하는 경우에는 사용이 적합하지 않다. 이 경우에는 동적 배열이나 연결 리스트와 같은 다른 데이터 구조를 고려해야 한다.

• 다양한 데이터 유형의 그룹 : 배열은 동일한 데이터 유형의 요소들을 저장하기 위한 것이다, 따라서 서로 다른 데이터 유형의 요소들을 저장하는 경우 배열의 사용이 적합하지 않다. 예를 들어, 학생 정보로 이름(문자), 나이(숫자) 라는 서로 다른 유형의 데이터를 저장해야 한다면, 배열 대신 구조체나 객체를 사용하는 것이 더 적절하다.