[Data Structure] 자료구조 - 배열(Array)

 

 

🗨 개인적인 공부 기록용으로 정리한 내용입니다. 잘못된 내용에 대한 피드백은 언제나 감사합니다 :)

 

 

 

 

 

⭐배열은 동일한 데이터 타입의 요소들이 연속된 메모리 위치에 저장되는 자료구조이다.

 

 

 

📌 배열의 정의

배열은 선형 자료구조이며, 대부분의 프로그래밍 언어에서 기본적으로 제공되는 만큼 가장 기초적인 자료구조이다. 

 

그럼, 배열이란 무엇일까?

배열은 동일한 데이터 타입의 요소들을 1열로 나열, 즉 연속된 메모리 위치에 저장하는 구조이다.

 

순차적으로 저장되기 때문에, 인덱스 번호가 배열의 시작점으로부터 값이 저장되어 있는 상대적인 위치를 뜻한다.

예를 들어, 인덱스 번호가 0인 arr[0]은 arr배열의 첫 번째 주소 즉, 기본 주소를 뜻한다.

또, 인덱스 번호가 1인 arr[1]은 arr배열의 기본 주소로부터 1만큼 떨어진 곳을 가리킨다. 

 

 

 

그림으로 표현해보면 아래와 같다.

크기가 5인 배열 arr에 int형 데이터인 {2, 3, 4, 5, 6}을 저장한 모습이다.

arr는 배열의 이름이고, 그 뒤의 [ ] 안에 있는 숫자는 배열의 몇 번째 요소인지를 가리킨다.

 

위 배열을 만드는 코드는 다음과 같다. (C++, C#)

/* C++ */
int arr[5] = {2, 3, 4, 5, 6}; // 정수 배열 선언 및 초기화

/* C# */
int[] arr = {2, 3, 4, 5, 6}; // 배열 선언 및 초기화 )이 방법은 배열의 크기가 자동으로 초기값의 개수에 맞춰짐)

 

배열의 특징은 고정된 크기를 가지며, 모든 요소가 같은 타입이다. (위의 경우 모든 요소가 int형으로 같다.)

 

그리고 0부터 시작하는 인덱스를 사용하여 각 요소에 접근할 수 있다.

예를 들어, 위의 그림처럼 길이가 5인 정수 배열 arr는 arr[0] ~ arr[4]까지 총 5개의 요소에 접근할 수 있다.

 

그리고 연속된 위치에 저장된 위 요소들의 메모리 주소는 다음과 같다.

배열의 요소	메모리 주소
arr[0]	기본 주소
arr[1]	기본 주소 + 1*sizeof(int)
arr[2]	기본 주소 + 2*sizeof(int)
arr[3]	기본 주소 + 3*sizeof(int)
arr[4]	기본 주소 + 4*sizeof(int)

예를 들어, arr[4]의 요소에 접근하는 것은 메모리의 기본 주소 + 4*sizeof(int)의 주소에 있는 값에 접근하는 것과 같다.

 

 

 

 

 

📌 배열의 장점

• 구현이 간단하다.
• 연속적인 공간을 사용하므로 메모리를 효율적으로 사용할 수 있다.
• 인덱스를 통해 각 요소에 직접 접근할 수 있어 접근 속도가 매우 빠르다. ⏱ 시간 복잡도는 $\mathbf{O(1)}$이다.

 

 

 

 

 

📌 배열의 단점

• 배열의 크기는 선언 시점에 고정되며, 이후에 변경할 수 없다.
  • 공간이 낭비될 수도 있다.
  • 이를 보완하기 위해 동적 배열이나 리스트와 같은 자료 구조가 사용된다.
• 삽입 및 삭제가 비효율적이다. 
  • 배열의 중간에 요소를 삽입하거나 삭제할 때 많은 요소들을 이동해야 하므로, ⏱ 시간 복잡도가 $\mathbf{O(n)}$이다.

 

 

 

 

 

📌 배열의 사용

• 고정된 크기의 데이터를 저장할 때 사용하기 좋은 자료구조이다.
• 삽입 및 삭제 작업은 적고, 배열에 저장된 데이터를 검색하는 작업이 많을 때 사용하기 좋다.
• 정렬 및 탐색 알고리즘에서 기본 자료구조로 자주 사용한다.
• 행렬 및 다차원 데이터 구조를 표현하는데 유용하다.
  • 다차원 배열(2차원, 3차원 등)을 통해 행렬 또는 격자 형태의 데이터를 표현하는 데 사용된다.
  • 예를 들어, 이미지 데이터(픽셀 값)이나 좌표(x, y)를 2차원 배열로 표현이 가능하다.

 

이차원 배열