배열

배열 (Array)

번호와 번호에 대응하는 데이터들로 이루어진 가장 기본적인 자료구조 중 하나이다.

(Python 은 C 언어를 기반으로 만들어졌으며, Python의 List 자료형은 C언어의 배열을 기반으로 만들어졌다. 같지는 않다.)

---

1. 정적 배열

크기가 고정돼 있다.

같은 타입의 데이터만 담을 수 있다.

 

메모리에 필요한 공간만큼을 미리 할당(예약)한다.

보통 C의 배열에서는 정수하나가 4 Byte를 차지하기 때문에 아래와 같이 크기가 4인 배열은

총 16Byte의 메모리를 차지하게 된다.

이처럼 데이터가 메모리에 순서대로, 연속적으로 저장된다.

 

배열 접근

순서대로 연속적으로 저장하기 때문에 시작되는 주소를 참고하여 배열의 인덱스에 빠르게 접근할 수 있다.

어떠한 인덱스든 O(1)으로 접근할 수 있는 램의 특성을 활용하는 자료구조이다.

---

배열 탐색

배열에서의 탐색은 특정 조건을 만족하는 값을 찾기 위해서는 배열 하나하나 일일이 찾아야하기 때문에

O(n)의 시간복잡도를 갖는다.

선형 탐색/ 이진 탐색의 방법이 있으며, 배열이 정렬되어 있지 않는 이상 선형 탐색보다 효율적인 방법은 없다고 한다.

---

파이썬에서의 리스트

정수 하나하나를 저장하는것이 아닌 정수를 가르키는 레퍼런스가 저장된다.

따라서, 2 , 3, 5, 7을 담고있는게아닌 가르키고있다는 표현이 맞으며 레퍼런스를 저장하기 때문에 파이썬의 리스트에서는 형식에 상관없이 다양한 타입의 값들을 저장할 수 있는 것이다.

---

2. 동적 배열(Dynamic Array)

정적 배열로 만들어진 자료구조이

이름 그대로, 정적 배열과 달리 배열의 크기를 상황에 맞게 바꿀 수 있다.

반대로 낭비하는 공간을 최소화하기 위해 요소 수의 크기가 1/3, 1/4, 1/5 등으로 줄었을때 배열을 늘리는 방식과 동일하게 배열의 크기를 줄이기도 한다.

 

처음 정의하였던 배열의 크기에서 추가로 크기를 늘려야하는 경우

보통 이전 배열의 2배에 해당하는 연속된 메모리 공간을 할당하여 이전 배열을 복사하여 메모리 공간이 늘어난 배열을 만든다. (항상 2배는 아니다.)

 

21을 추가할 경우

---

추가 연산

정적 배열을 기반으로 하는 동적 배열의 추가 연산의 경우

배열에 남아 있는 공간이 있다면 O(1)

배열에 남아 있는 공간 없다면 크기를 늘린 배열에 이전 배열을 복사해야하 기에 O(n)

---

삽입 연산

배열에 남아 있는 공간이 있다면 O(n)

삽입 연산에서의 최악의 경우는 맨 앞에 삽입을 하게 될 경우

시간복잡도는 (최선/평균/최악) 경우의 수행 시간의 상한을 나타낸다

 

배열에 남아 있는 공간이 없다면 O(n)

---

삭제 연산

아무 위치에 값을 삭제할 때 O(n)

값을 삭제하고 모든 요소들을 한 칸씩 앞으로 밀어서 저장하기 때문

 

맨 마지막 값을 삭제할 때 O(1)

값을 찾아서 삭제하기만 하면 된다.

여기서, 낭비된느 공간이 많아져 더 작은 배열로 모든 요소들을 옮겨 저장해야 할때 O(n)이 되기도 한다

그러나 배열을 줄이는 경우는 드문 경우로 이때 분활 상환 분석을 통해 O(1)이라 할 수 있다.

---

정리/비교

 

출처 : 코드잇(자료구조)

자료 구조 | 코드잇 (codeit.kr)