Array(배열)

1. 배열의 정의와 기본 개념

배열(Array)은 같은 자료형의 데이터를 연속된 메모리 공간에 저장하는 자료구조이다.
배열에 저장된 데이터는 각자의 인덱스(index)를 가지며, 이 인덱스를 통해 빠르고 효율적으로 데이터를 읽거나 수정할 수 있다.

 

배열의 가장 큰 특징은 다음과 같다.

• 연속된 메모리 할당:
  배열은 메모리상에 데이터가 연속적으로 배치되어 있어서 특정 데이터에 빠르게 접근할 수 있다.
• 인덱스를 통한 접근:
  각 데이터는 정수형 인덱스를 통해 접근할 수 있으며, 이를 통해 일정한 시간(O(1)) 내에 데이터를 찾거나 변경할 수 있다.
• 고정된 크기:
  일반적인 배열은 선언 시 크기가 정해지며, 나중에 변경할 수 없다. 동적 배열(ArrayList 등)은 크기가 가변적이지만, 내부적으로는 배열의 크기를 조정하여 작동한다.

이처럼 배열은 데이터에 대한 접근성이 뛰어나며, 기초적이면서도 다양한 알고리즘 구현에 널리 쓰이는 기본적인 자료구조이다.

 

2. 배열의 메모리 구조와 동작 원리

배열을 이해하기 위해서는 배열이 메모리에서 어떻게 동작하는지 구체적으로 살펴볼 필요가 있다.

 

배열은 컴퓨터 메모리(RAM) 상에서 연속적인 주소 공간에 데이터를 저장한다. 예를 들어, 정수형 배열 int arr[5]를 선언하면, 운영체제는 메모리 내에서 이 배열을 위한 연속된 공간을 미리 확보하고, 이 공간을 배열에게 할당한다.

 

배열의 메모리 구조 예시

int arr[5] = {10, 20, 30, 40, 50};

이 배열이 메모리에 할당되는 방식은 다음과 같다.

[메모리 주소]
   ↓
+------+------+------+------+------+
|  10  |  20  |  30  |  40  |  50  |
+------+------+------+------+------+
   ↑      ↑      ↑      ↑      ↑
 arr[0] arr[1] arr[2] arr[3] arr[4]

 1000   1004   1008   1012   1016  <-- 주소 예시

 

• 배열의 기본 주소(Base address)는 배열의 첫 번째 요소( arr[0] )의 주소를 나타내며, 그림에서  1000번지 에 해당한다.
• 각 배열 요소는 메모리에서 연속적으로 배치되며, 인덱스가 증가할 때마다 주소 값이 자료형의 크기만큼 증가한다
  (int는 4byte).

이 구조 덕분에 배열의 특정 요소에 대한 접근이 다음 공식으로 O(1)의 시간 복잡도로 가능해진다.

arr[i] 주소 = 기본 주소(base address) + (자료형 크기 × i)

 

 

3. 배열 연산별 시간 복잡도 (접근, 탐색, 삽입, 삭제)

배열은 메모리 구조상 특정 연산에서는 매우 효율적인 반면, 또 다른 연산에서는 비효율적인 특성을 보인다. 배열의 주요 연산인 접근, 탐색, 삽입, 삭제의 시간 복잡도는 다음과 같다.

 

① 접근(Access): O(1)

• 배열은 메모리상 연속된 주소 공간을 차지하고 있으므로, 인덱스를 이용하여 특정 요소에 접근할 때 바로 주소를 계산할 수 있다.
• 따라서 배열의 요소에 대한 접근은 언제나 상수 시간(O(1)) 내에 이루어진다.

② 탐색(Search): O(n)

• 탐색이란 배열에서 특정 값을 찾는 것을 의미한다.
• 배열은 특정 값이 위치한 인덱스를 미리 알 수 없으므로, 처음부터 순차적으로 모든 요소를 비교해야 한다.
• 최악의 경우 배열의 모든 요소를 검사해야 하므로 선형 시간(O(n))의 복잡도를 갖는다.

③ 삽입(Insert): O(n)

• 배열의 특정 위치에 새로운 요소를 삽입하려면, 삽입될 위치 이후의 요소들을 모두 한 칸씩 뒤로 밀어내야 한다.
• 따라서 최악의 경우 배열의 모든 요소가 이동해야 하므로, O(n)의 시간이 소요된다.
• 다만 배열의 맨 뒤에 삽입하는 경우, 빈 공간이 미리 확보되어 있다면 O(1)의 시간만 소요된다.

④ 삭제(Delete): O(n)

• 배열에서 특정 위치의 요소를 삭제하면, 삭제된 요소 뒤의 요소들이 빈 공간을 채우기 위해 앞으로 한 칸씩 이동해야 한다.
• 역시 최악의 경우 배열 전체의 요소가 이동해야 하므로 O(n)의 시간이 걸린다.

 

요약

 

연산 종류	시간 복잡도	비고
접근 (Access)	O(1)	인덱스 기반으로 즉시 접근 가능
탐색 (Search)	O(n)	순차적으로 값을 검사해야 함
삽입 (Insert)	O(n)	중간에 삽입 시 다른 요소들 이동 필요
삭제 (Delete)	O(n)	삭제 후 요소들의 이동 필요

 

배열은 접근에는 매우 효율적이지만, 삽입과 삭제 같은 연산에서는 비효율적인 특징을 가진다. 따라서 배열의 사용처를 고려할 때는 이런 시간 복잡도를 충분히 이해하고 활용해야 한다.

 

실전 개념 점검 - 1.  배열의 크기를 변경하려면 어떻게 해야할까?

배열은 선언 시 고정된 크기를 가지며, 한 번 생성된 배열의 크기는 변경할 수 없다.
만약 배열의 크기를 변경하고 싶다면, 다음과 같은 과정을 거쳐야 한다.

 

1. 새로운 배열 생성
   원하는 크기를 가진 새 배열을 새로 만든다.
2. 기존 배열의 요소 복사
   기존 배열의 요소를 새 배열에 복사한다. 필요한 경우 일부 데이터만 복사하거나, 빈 공간을 추가할 수 있다.
3. 새 배열 참조로 교체
   프로그램 상에서는 원래 배열 대신 새로 생성한 배열을 사용하도록 참조를 변경한다.

메모리 관점에서는 기존 배열의 메모리 공간은 더 이상 사용되지 않으며, 가비지 컬렉션(언어에 따라 다름) 대상이 된다.

 

예시 (Java 기준) :

int[] oldArray = {1, 2, 3};
int[] newArray = Arrays.copyOf(oldArray, 5);

• Arrays.copyOf 메서드는 기존 배열을 원하는 크기만큼 복사해 새로운 배열을 만든다.
• 복사할 크기가 기존 배열보다 크면, 초과된 부분은 자료형의 기본값으로 초기화된다. (int형은 0)

따라서  newArray 는  [1, 2, 3, 0, 0] 의 값을 가지게 된다.

 

실전 개념 점검 - 2.  배열을 초기화하고 셈하는 과정을 메모상으로 설명하라

배열을 초기화하고 값을 세는 과정은 메모리 상에서 다음 단계로 진행된다.

 

1. 배열 공간 할당
   선언 시, 배열 길이 × 자료형 크기만큼 연속된 메모리 공간이 확보된다.
   예를 들어, int arr[5]를 선언하면 4바이트 × 5 = 20바이트의 연속된 공간이 확보된다.
2. 초기값 설정
   별도로 초기화를 하지 않는다면, 메모리 공간은 언어와 환경에 따라 쓰레기 값이나 0으로 초기화된다. (Java는 0)
   명시적으로 초기값을 지정하면, 컴파일러나 런타임이 이 값들을 해당 메모리 공간에 순서대로 채워 넣는다.
3. 값을 셈하는 과정
   배열을 순회하면서 각각의 인덱스를 참조하고, 값을 읽어온다.
   이때 메모리 접근은 base address + (자료형 크기 × 인덱스) 공식을 따라 빠르게 이루어진다.
   읽은 값들은 CPU 레지스터나 연산 유닛으로 옮겨져 연산(예: 합산, 카운트)이 진행된다.

요약하면, 배열 초기화 → 메모리에 값 쓰기 → 인덱스를 이용해 메모리 읽기 → 연산하는 흐름이다.
이 모든 과정은 배열이 메모리 상에 연속된 구조로 존재하기 때문에 빠르게 이루어질 수 있다.