[배열] 동적 배열 크기 줄이기

동적 배열 크기 줄이기

 

동적 배열은 내부적으로 정해진 크기의 정적 배열을 사용하고 있습니다. 값을 추가하다가 내부 배열이 꽉 차면, 더 큰 내부 배열을 사용하도록 자동으로 늘려 주는 거죠. 반대로 삭제를 할 때에는 내부 배열의 크기를 줄이기도 하는데요...

 

왜 내부 배열의 크기를 줄여야 될까?

 

데이터 요소 10000 개가 들어 있는 동적 배열이 있다고 생각해 봅시다. 편의상 배열의 크기가 꽉 찼다고 생각할게요. 여기서 요소 9900 개를 삭제하면 100 개밖에 남지 않는데요. 그러면 나머지 9900 개의 요소를 저장할 수 있는 메모리는 낭비되겠죠? 동적 배열은 요소의 개수가 어느정도 줄어들면 내부 배열의 크기도 적절히 줄여서 공간을 좀 더 효율적으로 사용합니다.

내부 배열의 크기는 어떻게 줄어들까?

위의 동적 배열 int_array를 봅시다. int_array는 9 개의 요소를 담고 있습니다. 내부 배열 크기가 9 개인 꽉 찬 동적 배열이라고 할게요.

 

여기서 맨 뒤 요소 6 개를 삭제합니다.

그럼 요소가 3 개로 줄어들죠? 그럼 정수 6 개를 저장할 수 있는 공간이 낭비되네요. 이렇게 낭비하는 공간이 너무 많아지는 경우에 내부 배열의 크기를 줄일 수 있습니다.

 

그런데 정확히 어떤 시점에 줄이면 좋을까요?

 

크기를 늘릴 때는 내부 배열이 꽉 찼을 때였는데요. 크기를 줄일 때는 내부 배열의 사용 비율이 특정 값 이하로 떨어질 때입니다.

 

이 비율이 1/3​이라고 가정하고 볼게요. 요소가 4 개에서 3 개로 줄어든 상황이라고 합시다. 내부 배열에 요소 9 개를 담을 수 있는데, 현재 사용 중인 공간은 3 칸밖에 없습니다. 그러니까 총 사용할 수 있는 공간 중 1331​밖에 사용을 안 하게 된 거죠.

 

이때:

1. 새로운 내부 배열을 정의합니다. 이번에는 크기가 3인 내부 배열을 만듭니다:
2. 그리고 기존의 3 개 요소를 새로 만든 내부 배열에 옮겨서 저장합니다:

전에는 6 칸을 낭비하고 있었는데 이제는 낭비하는 공간이 하나도 없습니다.

 

내부 배열의 크기를 요소 수에 맞게 줄이면, 낭비하는 공간을 최소한으로 할 수 있습니다.

 

그렇다고 방금 예시처럼 꼭 사용 비율이 1/3일 때 크기를 줄여야 하는 것은 아닙니다. 1/2​, 1/4​, 1/5​일 때 줄일 수도 있죠. 개발자나 프로그래밍 언어에 따라 이 비율은 다릅니다.

 

일단 저희는 생각하기 편하게 내부 배열의 크기를 늘릴 때에는 2 배로 늘리고, 줄일 때에는 요소 수가 크기의 1/2​가 됐을 때 줄인다고 가정할게요.

 

시간 복잡도

 

동적 배열 맨 끝 데이터 삭제 시간 복잡도

 

맨 끝 요소를 삭제했을 때 걸리는 시간 복잡도에 대해서 생각해 봅시다.

 

최악의 경우를 가정합시다. 가장 오래 걸리는 경우는, 더 작은 배열로 모든 요소들을 옮겨 저장해야 될 때인데요.

 

배열 안에 있는 요소 수가 n이라고 할 때, 총 n 개의 데이터를 모두 새 배열에 복사해서 넣어야겠죠. 맨 뒤 데이터를 삭제하는 건 O(1)이 걸립니다. 하지만 n 개의 데이터를 모두 새 배열에 복사해서 넣어야 되기 때문에 n에 비례하는 시간, O(n)이 걸립니다.

 

맨 끝 데이터 삭제 분할 상환 분석

 

하지만 내부 배열의 크기가 줄어드는 건 드문 경우입니다. 대부분의 경우 그냥 마지막 인덱스에 있는 데이터를 지워 주기만 하면 됩니다.

 

위에서 봤던 예시를 다시 생각해 봅시다. 요소가 9 개에서 3 개로 줄어들 때까지, 그러니까 마지막 데이터 6 개를 삭제할 동안 배열의 크기를 조절할 필요가 없었습니다. 이 6 번은 그냥 O(1)로 맨 끝 데이터를 삭제한 거죠.

 

근데 요소 수가 4 개에서 3 개로 줄어들 때에는, 마지막 데이터를 삭제하고 남은 3 개의 데이터를 새롭게 만든 더 작은 배열로 복사해서 저장했습니다. 이 경우에 O(n)이 걸린 거죠.

 

동적 배열에서 마지막 데이터를 삭제할 때는 대부분의 경우 O(1)이 걸리지만, 드물게 O(n)이 걸립니다. 그렇기 때문에 추가 연산과 마찬가지로 분할 상환 분석을 적용할 수 있습니다. 분할 상환 분석을 적용하면 맨 끝 데이터 삭제 연산도 O(1)이 걸린다고 이야기할 수 있습니다.

 

정리

동적 배열에서 맨 끝 데이터를 삭제하는 연산은 최악의 경우 O(n)이 걸리지만, 분할 상환 분석을 적용하면 O(1)이라고 할 수 있다.

 

출처 코드잇