배열 - 정적배열, 동적배열

배열은 가장 기본적인 자료구조 중 하나로, 복수의 데이터들을 목적을 위해 하나로 묶어 사용하기 위해 사용된다.

 

배열에는 저장된 데이터를 추가하거나 삭제하는데 자유로운 동적배열과 그렇지 않은 정적배열이 있다.

 

정적배열 (Static array)

일반적으로 배열이라고 하면 정적배열을 의미하는 거라고 생각하면 된다.

 

배열은 실제 데이터(원소)를 저장하기 전에 현재 사용중이지 않은 연속적인 메모리들을 미리 예약해두고 시작한다. 

 

즉, 데이터 저장 전에 "어떤 데이터를 몇 개 저장할 배열을 사용할거야" 라고 배열을 먼저 선언한 후 사용한다.

 

int numArray[4];

 

위 코드는 정수형 데이터를 4개 저장할 배열을 만들겠다는 말이다. 

 

이렇게 배열을 선언하면 정수 하나당 4바이트씩 총 16바이트만큼의 연속적인 메모리를 미리 예약해두게 되는 것이다.

 

numArray[0] = 1;
numArray[1] = 2;
numArray[2] = 3;
numArray[3] = 4;

 

이후, 정의된 배열에 데이터를 추가해주는 방식으로 하나의 배열을 완성할 수 있는 것이다.

 

 

정적배열의 데이터 접근, 저장, 탐색 시 걸리는 시간복잡도

 

배열의 특징 중 하나는, 배열에 저장된 데이터를 불러오는데 임의접근방식이 가능하다는 것이다.

 

정의된 배열 numArray는 해당 배열이 시작되는 주소를 가르키고 있으며 데이터들은 연속적인 메모리에 저장되어 있다.

 

따라서, 우리가 2번 인덱스를 불러오고 싶을 때는 시작 주소에서 4(정수 하나의 메모리값) * 2 = 8 만큼을 더하는 방식으로 값에 접근할 수 있다. 

 

즉, 데이터에 접근하는데 O(1) 시간이 소요된다는 것이다.

 

동일한 이유로 배열을 선언하고 배열 내에 데이터를 저장하는데도 O(1) 시간이 소요된다.

 

그렇다면 배열에서 특정 값을 찾는 탐색에서는 얼마만큼의 시간이 걸릴까?

 

배열에서는 데이터들이 정렬되어있거나 특정 순서를 따르지 않는다고 가정할 때, 최악의 경우 모든 데이터들을 봐야 찾고자 하는 값을 찾을 수 있다.

 

따라서, 탐색에 필요한 연산횟수는 배열의 데이터의 개수 N개에 비례하므로 O(n)만큼의 시간이 소요된다고 할 수 있다.  

 

 

정적배열의 값 삭제 및 추가

 

정적배열은 '정적'이라는 이름에 걸맞게 삭제 및 추가가 불가능하다.

 

앞서 말했듯, 정적배열은 데이터를 저장하기 전 미리 해당 배열이 무슨 데이터 몇 개를 위해 사용될 것인지 정의되고, 해당 정의에 따라 계산된 메모리의 값을 연속적으로 예약한다.

 

따라서, 나중에 배열의 뒤에 정수 하나를 추가하고 싶을 때도 이러한 연속적으로 저장된다는 특징을 지켜줘야 하는데,

 

이 배열에서 현재 사용중인 메모리값의 바로 뒷 부분이 다른 변수에 의해 이미 사용 중인지 아닌지 확신할 수 없기 때문이다. 

 

삭제 또한 마찬가지이다. [1, 2, 3, 4, 5] 라는 배열이 있으며, 여기서 맨 앞의 값인 1을 지우려 한다고 가정해보자.

 

해당 값을 지운다는 것은 무슨 의미인가? 예컨대 None이라던가 Null값을 넣어줘야하나?

 

아쉽게도 이 배열은 이미 정수형태의 데이터만 저장하겠다고 선언한 배열이므로 두 값 모두 삽입될 수 없다.

 

만약에 데이터 1을 뒤의 값으로 덮어쓰고, 뒤의 값은 그 뒤의 값으로 덮어쓰고, ... 하는 방식으로 데이터를 삭제하면 어떻게 될까?

 

그렇다고 하더라도 데이터는 [2, 3, 4, 5, 5]로, 마지막 값의 5를 덮어쓸 값이 없어져 실질적으로 특정 값이 삭제되었다고 할 수 없겠다.

 

동적배열 (Dynamic array)

 

정적배열의 데이터 삭제와 추가를 가능하게 하는 방법은 하나 있다.

 

바로 현재의 배열의 길이보다 1이 큰 새로운 배열을 만들고 이미 있던 값들과 새로 추가된 값들을 새 배열에 복사하는 것이다.

 

그리고 이 아이디어를 통해 만들어진 것이 바로 동적배열이다.

 

C언어의 배열을 기반으로 구현된 파이썬의 리스트가 동적배열의 대표적인 예시이다.

 

파이썬의 리스트는 데이터를 저장할 때, 현재 리스트가 담을 수 있는 길이 이상의 데이터가 들어온다면

 

현재 리스트의 길이의 2배가 되는 배열을 새로 만들고, 기존에 있던 데이터와 새로 입력된 데이터를 그대로 가져와 저장하는 방식으로 작동된다. 

 

이러한 방식 덕분에, 동적배열에선 삽입될 데이터를 미리 정의할 필요가 없다.

 

데이터가 추가되면 데이터의 메모리용량에 따라 더 긴 배열을 만들면 그만이기 때문.

 

 

동적배열의 동작에 대한 시간복잡도

 

동적배열 역시 내부적으로는 정적배열을 사용하고 있는 것이기 때문에 데이터 접근, 저장시에는 O(1)이,  데이터를 탐색하는데는 O(n)이 걸린다.

 

그렇다면 데이터의 추가와 삭제 연산은 어떨까?

 

먼저 추가에 대해서 알아보자.

 

동적배열에 값을 추가할 때는 두 가지 경우의 수가 있을 수 있다.

 

1) 배열에 아직 데이터를 저장할 수 있는 공간이 존재해 배열의 길이를 늘려줄 필요가 없을 때

 

- 해당 경우에는 임의접근방식으로 마지막으로 저장된 데이터 값에 접근해 그 뒤에 데이터를 저장하면 되므로 O(1)이 걸린다.

 

 

2) 배열이 꽉 차서 더 긴 새 배열을 만들어줘야 할 때

 

- 새 배열을 마련하고, 기존 배열의 데이터에 접근해 새 배열의 메모리로 옮겨가는 각 동작은 O(1)이 걸리지만, 이걸 배열의 길이 N만큼 해줘야하므로 O(n)의 시간이 걸린다.

 

 

 이번엔 삭제에 대해 알아보자.

 

동적배열에서 데이터를 삭제할 때는 그 뒤의 값들이 삭제된 데이터를 덮어쓰는 과정이 일어난다.

 

그렇다면 한 가지 의문이 생긴다.

 

동적배열은 내부적으로 정적배열을 사용하는데, 정적배열에서 데이터를 삭제하기 위해 그 뒤의 값들로 해당 값을 덮을 때 마지막에 위치한 값을 덮을 값이 없기 때문에 실질적으로 데이터가 삭제되었다고 보긴 어려웠다.

 

사실, 동적배열에서도 마찬가지이다. 데이터가 실제로 없어지진 않는다.

 

다만, 해당 인덱스로의 접근을 막음으로써, 개발자는 해당 데이터가 존재하지 않는 것처럼 취급할 수 있는 것이다. 

 

이렇게 접근이 제한되어 더 이상 사용되지 않는 데이터들은 나중에 일련의 과정을 통해 메모리에서 삭제된다.

 

 

삭제 연산의 시간복잡도 또한 두 가지 경우의 수로 나뉜다.

 

1) 맨 뒤의 값을 삭제할 때

 

- 뒤의 값들의 위치를 옮겨줄 필요 없이 맨 뒤의 데이터에 대한 인덱스 접근만 끊어주면 됨으로 O(1)이 걸린다.

 

 

2) 중간에 삽입된 값을 삭제할 때

 

- 중간에 삽입된 값들을 삭제해주려면 해당 값을 시작으로 뒤의 값들을 앞으로 하나씩 덮어씌워야한다. 삭제하려는 데이터의 위치에 따라 속도가 다를 수 있지만, 최악의 경우인 맨 앞 데이터를 삭제한다고 할 때, 총 데이터의 수 N개 - 1의 동작을 수행해야한다. 즉, O(n) 만큼의 시간이 걸리는 것이다.