[03-2] 배열을 알아보자(Dynamic Array)

앞에서 배열을 알아보았다(Static Array).

우리가 쉽게 쓰는 것이지만, 어떻게 메모리에 저장되고 불러오고 활용하는지는 고민해본적이 없었을 것이다.

 

왜냐하면 파이썬에서는 Dyanmic Array를 기본으로 하니까.

 

그래서 이번에는 익숙한 동적배열(Dynamic Arrray)을 알아보자.

동적배열의 특징은 딱 하나!

1. 배열 선언 이후에 사이즈를 증가할 수 있다.

 

 

동적배열

동적배열의 원리를 알아보자

지난번처럼 {1,2,3,4}의 배열을 넣으려고 하는데, 정적배열은 4칸의 배열을 선언했다면, 동적배열은 그냥 추가하면 된다.

예를 들어 3개의 공간이 있었는데 {1,2,3,4}를 넣는다면? 4를 못넣게 되는데!

그 순간에 Resizing을 해서 기존에 있던 {1,2,3}을 다시 새로운 배열에 {1,2,3}을 넣고 {4}를 추가하는 방식으로 간다.

이때 Resizing 과정에서 3개의 공간이 있었기 때문에 2배인 6개의 공간으로 할당하게 된다(이건 규칙이다).

그리고 기존의 {1,2,3} 배열은 삭제(free)~

 

자 여기서보면 {1,2,3}을 한번 더 쓰기 때문에 O(n)의 복잡도를 갖게 된다.

 

배열을 선언하고, 인덱스로 찾거나 수정하는 것은 O(1)을 갖는다. 왜냐하면 기본 array와 같으니까.

다만 Resizing 하는 과정에서 O(n)이 걸린다. 앞서 사례에서 4를 추가할 때 Resizing을 하니까 O(n)이라고 볼 수 있다.

라고 하기엔 분할상환기법에 의해 O(1)으로 한다.

즉, 데이터 추가는 O(1)이다! (append, pop) 라고 이해하면 좋다.

하지만 insert와 같이 중간에 데이터 추가하는 경우는? O(n)이다.

 

 

이렇게 중간에 1을 넣으려면(insert) {2,3,4} 가 한칸씩 밀려야하기 때문에 복잡도는 n이 된다.

여기서 .pop(2)의 경우도 2를 빼고 다시 {1,5,3,4} 한칸씩 땡겨야 하니까 복잡도는 n이 된다.

어떤 느낌인지 알겠지?

 

 

정리해보면

1. 선언시 배열의 크기를 설정하지 않아서 자주 쓴다.

2. Resizing의 과정에서 배열을 늘리게 된다.

3. 우리는 파이썬에서 코딩테스트를 준비하기 때문에 귀찮은 연산과 구현은 필요없다.

4. list 자료형을 쓰면 된다.

 

Dynamic array 총정리

 

장점

1. 파이썬의 기본 array

2. list 자료형이 Dynamic array이기 때문에 따로 구현할 필요 없이 선언만 잘 하면 된다.

 

단점

1.없음

 

총평

우리의 Array는 Dynamic Array와 같다.