[자료구조] 배열 (Array)

0820

---

1. 배열(Array) 이란?

배열은 자료를 구성하는 원소들을 하나씩 순차적으로 나열시킨 형태인 선형 구조이며,
동일한 크기와 형식으로 구성된 연속적인 기억공간을 의미합니다.

---

2. 배열의 구성 요소

배열을 구성하는 각각의 값을 배열 요소(element) 라고 하며, 배열에서의 위치를 가리키는 숫자는 인덱스(index) 라고 합니다.

---

3. 배열의 특징

배열은 기본적으로 다음과 같은 이론을 가집니다.

1. 한 배열 속의 데이터는 타입이 모두 동일합니다.

2. 연속적인 메모리 공간에 순차적으로 데이터를 저장합니다.

3. 배열은 한 번 선언하면 크기가 고정됩니다.

4. 선언된 값은 다시 배열을 선언하지 않는 이상 변경이 불가능합니다.

5. 배열의 한 칸마다 배열의 자료형의 크기를 지닙니다.

   • 만약 배열이 타입이 int라면 배열 한 칸의 크기는 4byte(int)가 되는 겁니다.

6. 배열은 인덱스를 통해 배열 안의 데이터(요소)에 접근할 수 있습니다.

3.1. 추가적으로 소모되는 메모리 양(overhead)가 거의 없다.

앞서 말씀드렸듯 배열은 한 번 선언하면 크기가 고정되기 때문에 데이터의 양에 맞게 크기가 정해지기 떄문입니다.

3.2. 배열 안의 각 값들에 개별적으로 접근할 수 있다.

배열의 인덱스를 통해 배열 속의 요소에 접근이 가능합니다.

3.3. 효율적이다.

여러 값들을 하나의 반복문으로 접근할 수도 있고, 여러 변수를 생성할 필요가 없어 네이밍에도 매우 효율적입니다.

---

4. 접근, 검색, 추가, 삭제와 시간복잡도

배열 내 연산은 크게 접근(access), 검색(search), 추가(add), 제거(remove) 으로 나뉩니다.

4.1. 접근

접근 : 배열 내에서 n번째 인덱스에 해당하는 값을 찾아내는 연산

• 시간복잡도 : O(1)

O(1)의 시간복잡도는 굉장히 빠릅니다.
따라서 어떤 값을 찾고자 할 때 굉장히 빠른 속도로 찾을 수 있습니다.

이는 배열의 첫 번째 변수에 시작 주소가 저장되고, 하나하나의 값을 찾을 때에 단순 사칙연산이 사용되기 때문입니다.

int[] a = {1,2,3,4,5};

만약 위의 배열에서 a[0]의 주소값이 100이고, 4라는 요소를 찾고자 한다면 어떻게 해야할까요?

배열의 타입이 int(4byte)이므로 시작 주소값(a[0])에 4를 총 3번 더하여 112주소값을 가지고 있는 요소 4를 찾을 수 있습니다.

이렇게 타입에 따라 더하기만 해주면 되니 아주 빠른 시간복잡도를 가지겠죠?

4.2. 검색

검색 : 인덱스를 알지 못할 때 원하는 값을 찾기 위해 배열을 하나하나 확인

• 시간복잡도 : O(n)

배열의 검색은 순차 검색입니다.

int[] a = {1,2,3,4,5};

만약 위의 배열에서 a[4]의 값을 찾는다면 어떻게 찾을 수 있을까요?

a[4]의 값을 찾기 위해 a[0]부터 a[0], a[1], a[2]...이렇게 순서대로 검색해나갈 것입니다.

만약 배열의 요소의 개수가 1000개인데 999번째 인덱스의 값을 찾고자 했다면 1000번을 검색을 했어야 했겠죠?

이렇듯 검색은 데이터의 개수에 따라 시간이 달라지므로 최대 O(n) 의 시간복잡도를 가지게 됩니다.

4.3. 추가, 삭제

추가, 삭제 : 배열 안의 요소를 넣거나 빼는 연산 (단, 빈 공간이 마련되어 있다는 전제)

추가, 삭제의 시간복잡도는 앞서 말한 접근과 검색의 방법 차이에 따라 시간복잡도가 나뉩니다.

비어있는 공간에 값을 추가하거나, 내가 원하는 값을 삭제해야하기 때문에 인덱스를 정확히 알고 있다면 접근의 방법이 되어 O(1)의 시간복잡도를 가집니다.

하지만 인덱스를 알고 있지 않다면 원하는 공간을 찾아야하기 때문에 검색의 방법이 되어 O(n)의 시간복잡도를 가지게 됩니다.

---

5. 배열 활용문제 풀어보기

public class ArrayTest {
	public static void main(String[] args) {
		int[] a = new int[4];
		char[] ch = {'a', 'r', 'r', 'a', 'b'};
		
		// 1. 
		System.out.println(a);
		// 2. 
		System.out.println(ch[4]+1);
		// 3.
		for ( int i = 0; i < ch.length; i++) {
			if ( ch[i] == 'b' ) {
				ch[i] = 'y';
			}
		}
	}
}

• Q.1. 1번은 무엇을 출력하려 한 것일까요?
• Q.2. 2번의 실행 결과는 무엇일까요?
• Q.3. 3번 for문의 시간복잡도는 무엇일까요?

5.1. 정답

1. a 배열의 시작주소값

2. 99

3. O(n)

   • ch의 요소 중 b인 것을 y로 바꾸기 위해 a[0]부터 순서대로 검색하고 있기 때문에 O(n)의 시간복잡도를 가집니다.

---

Reference

자료구조.pdf
mdn web docs_배열(Array)

---