[자료구조] 배열

리스트 in 파이썬

파이썬 리스트는 C 배열을 기반으로 만들어졌다.

1. c 배열
   - 선언 시 타입과 크기를 선언하여 배열 크기가 고정되어 있고,
   - 같은 타입의 데이터만 담기 가능하다.
   - 배열이 사용할 공간을 미리 할당한다.
   - 각 메모리 공간에 데이터가 그 자체가 연속적으로 바로 할당되는 형식이다
2. 파이썬 리스트
   - 데이터 자체는 연속적인 공간에 할당되어 있지 않지만,
   - 각 연속적 공간에 각 레퍼런스가 할당되어있어, 그 레퍼런스가 데이터를 가리킨다.
   - 따라서 그에 따라 리스트 자체로도 다양한 타입의 값을 저장할 수 있다.
   - (물론 그 크기의 제한도 없다. 레퍼런스가 가리키는 타입에 상관없이 레퍼런스의 크기는 일정하므로, 추가 시 레퍼런스의 크기만큼 추가를 해주면 되기 때문이다. 이에 더해 파이썬 자체의 구조적 이점도 있을 것으로 생각된다.)

---

배열에 데이터를 저장하고 가지고 오는 법

배열의 요소들이 메모리에 순서대로, 그리고 연속적으로 저장된다.

그리고 접근시에는 인덱스에 따라 시작 주소 + 데이터 크기 인덱스로 찾아간다.

 

따라서 배열에서 값을 받아오는 것은 O(1)으로 가능하다.

---

배열 탐색

특정 조건이 맞는지 확인하기위해 하나씩 인덱스의 값을 비교해가며 찾는다.

 

탐색 방법에는 여러가지가 있다. 하지만 그 중에서도 가장 기본적인 것은 처음부터 차근차근 찾는 것이다. 이를 순서대로 찾는 것이라고하여 '선형탐색' 이라고 한다. 시간 복잡도는 O(n)이다.

---

배열의 종류

배열의 종류는 크게 두가지가 있다.

1. 정적배열 : 크기 고정 (요소 갯수 고정)
2. 동적배열 : 크기 변경가능 (요소 계속 추가 가능)

정적배열에서 요소를 더 추가할 수 없는 이유는 정해진 저장공간을 넘어서면 그 메모리공간이 사용해도 되는 공간인지 알 수 없기 때문이다. 함부로 침범할 경우 프로그램에 심각한 문제를 초래할 수 있다. (우리는 C의 배열에서 이 성질을 알 수 있었다.) 물론 이를 해결하기 위해 매우 큰 크기로 배열을 선언할 수도 있다. 하지만 필요이상으로 크기를 선언하는 것은 메모리의 낭비가 생길 수 있어 보통 권장되지 않는다.

 

이를 해결하기 위해 만들어진 것이 동적배열이다. 하지만 동적배열도 결국은 정적배열을 기반으로 만들어진 배열이다. 메커니즘을 알기 쉽게 설명하자면, 원래 지정되어있던 배열의 크기를 넘어서서 요소를 새로 추가할 경우, 원래 배열의 크기보다 2배 큰 배열을 만들어 원래 배열의 값들을 하나씩 넣어주는 방식으로 작동한다고 이해하면 편한다. (무조건 이런식으로 돌아가는 것은 아니지만)

 

다만 파이썬에서는(그 외의 대부분의 언어에서도) 늘어난 배열의 크기에 대해서는 접근할 수 없도록, 즉, 사용자가 실질적으로 값을 넣은 부분만 활용할 수 있도록 자동적으로 사용하는 배열의 크기와 사용하는 인덱스 범위를 따로 처리한다.

이러한 동적배열은 사용자가 따로 배열의 크기를 신경쓰지 않아도 되어 편리하다.

---

동적배열 요소 추가의 시간복잡도 : 기본

동적 배열에 요소를 추가할 때의 시간복잡도는 만약 공간이 남아있는 경우에는 O(1), 공간이 꽉찬 경우에는 O(n+1) = O(n) 이다. (공간이 꽉찬 경우는 새로 배열을 만들어 배열의 크기 n만큼 값을 복사하는 과정이 필요하기 때문이다.)

---

분할상환 분석

시간복잡도는 최악의 상황을 가정해 시간복잡도를 계산하기 때문에 동적 배열에 요소로를 추가할 때의 시간복잡도를 O(n)이라 할 수 있다. 하지만, 배열에 요소를 추가할 때를 생각해보자. 공간이 꽉찼을 때 요소를 넣는 경우는 흔치 않다.따라서 이는 비합리적이라고 말할 수 있다.

 

이런 비합리성을 해소하기 위해 사용하는 것이 분할 상환 분석 개념이다.

 

일종의 할부적 개념으로서, 총 소요시간을 횟수로 나누어 평균적인 시간복잡도를 계산한다.

---

동적배열 요소 추가의 시간복잡도 : 분할상환 적용

동적배열의 요소 추가 시간복잡도에 분할 상환 분석 개념을 활용해보자. 어떤 빈 리스트에 n개의 데이터를 추가한다고 해보자. 배열의 크기확장없이 그냥 추가되는 값들은 각각 O(1)의 시간복잡도를 갖을 것이다. 그리고 확장이 일어나면, O(n)의 시간복잡도를 갖는다. 이를 정리하여 생각해보면 n개의 데이터 추가에 드는 시간복잡도의 합은 O(n-1) + O(n) 이다. 이는 합쳐도 O(2n - 1) 이다. 따라서 이를 n으로 나누면 결국 시간복잡도는 O(1) 이 된다.

 

보통 분할 상환 분석한 시간복잡도가 원래의 시간복잡도보다 더 적다면, 이를 차용하여 설명한다.

 

다만 정확하게 말하면 '동적 배열의 추가(append) 연산은 최악의 경우O(n)이 걸리지만, 분할 상환 분석을 하면O(1)이 걸린다.' 라고 할 수 있겠다.

---

동적배열 삽입 연산의 시간복잡도

배열 메모리의 공간이 남아있어도 데이터가 중간에 들어가면 기존에 있던 값들을 하나씩 다음 인덱스로 미뤄야하므로 최악의 경우, 그러니까 제일 처음에 데이터가 삽입될 때를 생각하면 시간복잡도는 O(n)이다. 꽉 찼을 때까지 생각하면 새로 배열을 만들어 값을 복사하고 미뤄내 더 많은 연산이 필요하지만, 결국은 O(2n) 이므로 최종 시간복잡도는 O(n)라고 할 수 있다. (cf. 맨 뒤에 삽입되는 것은 요소 추가이므로 제외하고 생각한다.)

 

즉, 삽입연산의 시간복잡도는 무조건 O(n)이다.

---

동적배열 삭제 연산의 시간복잡도

삭제 연산은 삽입연산과 유사하게 중간에 들어가면 기존의 값들을 밀어낸다. 따라서 단순계산시 최악의 경우 O(n)이므로 시간복잡도는 O(n)이라고 할 수 있다.

 

다만 삽입과는 다르게 맨끝을 생각할 수 있다. 맨끝 삭제의 경우는 조금 다르다. 요소 추가의 시간복잡도와 매우 유사한 메커니즘으로 일반적으로는 O(1), 배열의 크기가 줄어들 경우에는 O(n)이기 때문에 추가와 마찬가지로 분할 상환 분석을 적용하면 결국 최종적인 시간복잡도는 O(1)이다.

 

(참고로 동적배열은 크기가 줄어들때도 크기가 늘어날 때와 유사하게 새로운 배열을 만들고 기존의 값들을 복사해주는 메커니즘을 거친다.)

---

정적 배열에서 요소를 삽입, 삭제할 수 없는 이유

정적 배열은 크기가 정해져 있어서 크기만큼 값을 할당했다면 그 이후에는 새로운 값을 삽입할 수 없다. 그리고 기본적으로 정적 배열은 자료형을 지정하고 있기 때문에, 어떤 자료형의 정적배열에는 해당 자료형의 값밖에 들어가지 못한다. 따라서 해당 자리를 Null로 만드는 것은 불가능하다. 즉, 삭제가 불가능하다.

 

반면 동적배열에서는 삽입, 삭제가 원활하다.