저번 시간에는 동적 배열에 관한 추가 연산과 삽입 연산, 그리고 각 연산에 따른 시간 복잡도와 분할 상환 분석에 대해 알아봤습니다.
이번 시간에는 동적 배열의 삭제 연산과 삭제 연산 후, 배열의 크기를 줄이는 이유에 대해 학습하고 정적 배열과 동적 배열을 비교하여 정리하는 시간을 가져보겠습니다.
👬 동적 배열 삭제 연산
이번에는 동적 배열에서 특정 위치에 있는 데이터를 지우는 삭제 연산에 대해 알아보겠습니다.
❗ 삭제 연산 동작
{1, 2, 3, 5, 7}위 배열에서 인덱스 1에 있는 2를 지우려고 합니다. 어떻게 하면 될까요?
우선, 인덱스 1 뒤에 있는 데이터를 모두 한 칸씩 앞으로 밀어서 저장해야 합니다. 인덱스 2에 있던 3을 인덱스 1에 저장하고 인덱스 3에 있던 5를 인덱스 2에, 인덱스 4에 있던 7을 인덱스 3에 저장합니다.
다음으로 동적 배열은 배열의 크기가 개발자가 사용하는 인덱스들의 범위를 따로 관리하는데요. 데이터를 삭제했으니 동적 배열에서 접근할 수 있는 인덱스 범위도 한 칸 줄어듭니다.
{1, 3, 5, 7}이 상태에서 동적 배열에 남은 데이터를 확인해보면 1, 3, 5, 7입니다. 인덱스 1에 있던 2가 잘 삭제되었습니다.
❗ 삭제 연산 시간 복잡도
삭제 연산의 시간 복잡도도 알아보겠습니다. 삭제 연산도 이전 연산들과 마찬가지로 아무 위치의 데이터를 삭제할 때와 맨 뒤의 데이터를 삭제할 때, 두 가지 경우로 나누어 생각할 수 있습니다.
먼저, 최악의 경우인 맨 앞 데이터를 지울 때를 보겠습니다. 가장 앞 데이터를 삭제할 때는 인덱스 1부터 끝까지 모든 요소들을 한 칸씩 앞으로 밀어서 저장해야 되기 때문이죠. 이 횟수가 n에 비례하기 때문에 시간 복잡도는 O(n)입니다.
다음으로, 맨 뒤의 데이터를 지울 때를 보겠습니다. 이때는 아무 요소도 밀 필요 없이 그냥 동적 배열의 사용 공간을 한 인덱스 줄이기만 하면 됩니다. 이는 요소의 개수와 무관하고 일정한 시간에 할 수 있으므로 O(1)이라고 할 수 있습니다.
정리하자면, 아무 위치의 데이터를 삭제할 때는 원하는 위치 뒤에 있는 데이터를 옮겨 저장해야 하므로 O(n)이 걸리는 반면, 가장 뒤에 있는 데이터를 삭제할 때는 다른 데이터를 옮겨 저장할 필요가 없어 O(1)이 걸립니다.
👬 동적 배열 크기 줄이기
동적 배열은 내부적으로 정해진 크기의 정적 배열을 사용하고 있습니다. 값을 추가하다가 내부 배열이 꽉 차면 더 큰 내부 배열을 사용하도록 자동으로 늘려주는 것이죠. 반대로 삭제를 할 때에는 내부 배열의 크기를 줄이는데요.
❗ 배열의 크기를 줄이는 이유
그렇다면 왜 내부 배열의 크기를 줄여야 할까요? 데이터 요소 1000개가 들어 있는 동적 배열이 있다고 생각해봅시다. 그리고 이 배열은 꽉 차있습니다. 여기서 요소 990개를 삭제하면 10개만 남겠죠? 이 말은 반대로 생각하면 990개의 요소를 담을 수 있는 메모리가 낭비될 수 있다는 것입니다. 이러한 낭비를 방지하기 위해 동적 배열은 요소의 개수가 어느 정도 줄어들면 내부 배열의 크기를 적절히 줄여 공간을 좀 더 효율적으로 사용합니다.
❗ 배열의 크기가 줄어드는 원리
{1, 3, 5, 7, 9, 11}위 배열은 6개의 요소를 담고 있습니다. 배열의 크기가 6이라고 하면 현재 이 배열은 꽉 찬 상태입니다. 이 상태에서 맨 뒤 요소 네 개를 삭제하겠습니다.
{1, 3, , , , }그럼 요소가 2개로 줄어들죠? 그럼 정수 4개를 저장할 수 있는 공간이 낭비될 수 있습니다. 이렇게 낭비하는 공간이 많아지면 내부 배열의 크기를 줄일 수 있습니다.
그런데 정확히 어떤 시점에 줄이면 좋을까요? 크기를 늘리는 기준은 내부 배열이 꽉 찼을 때로 정해져 있었는데요. 반대로 크기를 줄일 때는 내부 배열의 사용 비율이 특정 값 이하로 떨어질 때입니다. 이 비율을 3분의 1이라고 가정해보겠습니다.
현재 총 여섯 칸에서 4개의 요소가 삭제되어 네 칸이 남고 두 칸이 찬 상황인데요. 여기서 두 칸은 여섯 칸을 기준으로 볼 때, 3분의 1에 해당하는 수입니다. 총 사용할 수 있는 공간 중에서 단 3분의 1만큼 밖에 사용하지 않는다는 것이죠.
이때, 새로운 내부 배열을 정의합니다. 요소가 두 개로 줄었으니 크기가 2인 내부 배열을 만듭니다. 그리고 기존에 있던 2개의 요소를 새로 만든 내부 배열에 옮겨서 저장합니다.
전에는 네 칸을 낭비하고 있었는데 이렇게 새로운 배열을 정의하면 낭비되는 공간이 없습니다. 이와 같이 내부 배열의 크기를 요소 수에 맞게 줄이면 낭비하는 공간을 최소한으로 줄일 수 있습니다.
그러나 항상 사용 비율이 3분의 1일 때만 크기를 줄여야 하는 것은 아닙니다. 그 기준은 2분의 1이 될 수 있고 5분의 1이 될 수도 있죠. 이는 개발자나 프로그래밍 언어에 따라 다릅니다.
❗ 시간 복잡도
맨 끝 요소를 삭제했을 때 걸리는 시간 복잡도에 대해서 생각해 봅시다. 최악의 경우를 가정하면 가장 오래 걸리는 경우는 더 작은 배열로 모든 요소들을 옮겨 저장해야 될 때인데요. 이 경우, 배열 안에 있는 요소 수가 n이라고 하면, 총 n개의 데이터를 모두 새 배열에 복사해서 넣어야 합니다.
맨 뒤 데이터를 삭제하는 건 O(1)이 걸리고 n개의 데이터를 모두 새 배열에 복사해서 넣는 것은 n에 비례하는 시간 즉, O(n)이 걸립니다.
❗ 분할 상환 분석
그러나 내부 배열의 크기가 줄어드는 경우는 드뭅니다. 대부분은 그냥 마지막 인덱스에 있는 데이터를 지우기만 하죠. 이런 경우, 더 합리적인 시간 복잡도를 구하기 위해 분할 상환 분석을 적용한다고 했습니다.
위의 예시로 설명하자면, 요소가 6개에서 2개로 줄어들 때까지 다시 말해, 마지막 데이터 4개를 삭제할 동안에는 배열의 크기를 조절할 필요가 없었습니다. 따라서, 이 네 번은 O(1)로 맨 끝 데이터를 삭제하고 있었던 것이죠.
그런데 요소 수가 3개에서 2개로 줄어들 때에는 마지막 데이터를 삭제하고 남은 2개의 데이터를 새롭게 만든 더 작은 배열로 복사해서 저장했습니다. 이 과정에서 O(n)이 걸린 것이죠.
요약하자면, 동적 배열에서 마지막 데이터를 삭제할 때는 대부분의 경우 O(1)이 걸리지만 드물게 O(n)이 걸리기도 합니다. 그렇기 때문에 추가 연산과 마찬가지로 분할 상환 분석을 적용할 수 있는데요. 이를 적용하면 맨 끝 데이터 삭제 연산도 O(1)이 걸린다고 할 수 있죠.
다시 말해, 동적 배열에서 맨 끝 데이터를 삭제하는 연산은 최악의 경우 O(n)이 걸리지만 분할 상환 분석을 적용하면 O(1)이 걸린다고 할 수 있습니다.
👬 배열과 동적 배열 정리/비교
지금까지 배운 내용을 정리해보겠습니다.
배열과 동적배열, 두 구조의 차이부터 봅시다. 먼저, 각 자료 구조가 어떤 연산을 할 수 있고 이 연산들을 얼마나 효율적으로 할 수 있는지 비교해보겠습니다.
표를 보면 각 연산에 따른 효율성이 정리되어 있습니다. n은 배열의 요소 개수를 의미합니다.
접근과 탐색은 배열과 동적 배열 모두에서 가능한 연산입니다. 접근 연산은 원하는 인덱스에 저장된 데이터를 가지고 오거나 바꾸는 연산이었죠? 인덱스를 통해 주소를 계산하는 데 O(1)이 걸리고 계산한 메모리에 접근하는 데도 O(1)이 걸리기 때문에 총 O(1)이 걸립니다.
탐색 연산은 배열 안에서 특정 조건을 만족하는 데이터를 찾는 연산입니다. 배열을 처음부터 끝까지 돌면서 원하는 데이터가 있는지 확인합니다. 최악의 경우, 배열의 모든 데이터를 확인해야 되기 때문에 O(n)이 걸립니다.
배열은 크기가 고정되어 있기 때문에 삽입과 삭제 연산에 제한이 있습니다. 반면, 동적 배열은 저장하는 요소 수에 따라 배열의 크기를 바꾸기 때문에 삽입과 삭제가 가능합니다.
동적 배열에서의 삽입과 삭제 연산은 최악의 경우 O(n)의 시간 복잡도를 가집니다. 그러나 가장 끝에 삽입과 삭제를 하게 되면 분할 상환 분석이 적용되어 O(1)이 됩니다.
시간 복잡도가 O(1)인 연산들 즉, 접근 연산과 맨 끝 값에 대한 삽입, 삭제 연산들은 매우 효율적인 반면에 탐색, 일반 삽입, 삭제 연산들은 O(n)으로 비효율적입니다.
다음으로 낭비하는 공간에 대해 정리해보겠습니다. 낭비하는 공간이란, 자료 구조 중 데이터가 저장되는 공간 외의 공간을 말합니다. 정적 배열은 크기가 고정되어 있기 때문에 낭비하는 공간이 없습니다. 그에 반해, 동적 배열은 상황에 따라 크기가 변하므로 공간을 낭비할 수도 있고 안 할 수도 있습니다.
예를 들어, 수용 공간이 4인 배열에 네 개의 요소가 있다면 낭비되는 공간이 없지만 하나의 요소를 추가하는 순간 공간이 8로 늘어나면서 총 세 개의 낭비되는 공간이 생깁니다.
그럼 낭비하는 공간을 어떻게 표현할 수 있을까요? 우선, 최악의 경우부터 생각해봅시다. 낭비하는 공간이 가장 많을 때는 새로운 배열을 만들 때입니다. 저장 공간이 부족하면 수용 공간의 두 배인 새로운 배열을 만들기 때문이죠. 낭비되는 공간을 정확히 표현하면 총 요소 수가 n일 때, n-2가 됩니다. 위 사례에 적용해보면, 요소의 개수가 5이므로 낭비되는 공간은 3이 됩니다.
따라서, 낭비하는 공간은 최소 0에서 최대 n-2라고 할 수 있습니다. 이에 대한 시간 복잡도는 O(n-2), 그러나 상수는 무의미한 수치이므로 O(n)이 됩니다.
👬 정적 배열에 삽입/삭제 못하는 이유
정적 배열에는 삽입과 삭제가 불가능합니다. 왜 그런지 C 배열을 통해 알아봅시다.
❗ 배열에 데이터 삽입을 못하는 이유
정적 배열은 크기가 정해져 있습니다. 따라서, 더 많은 데이터 요소를 저장하고 싶으면 더 큰 배열을 정의해야 하죠.
❗ 배열에 데이터 삭제를 못하는 이유
int numArray[2];
numArray[0] = 2;
numArray[1] = 4;
numArray[2] = 6;위 배열은 크기가 3인 배열에 정수 2, 4, 6이 저장되어 있습니다. 이때, 인덱스 1의 값 4를 지우고 싶으면 어떻게 해야 할까요?
동적 배열 삭제 연산에서처럼 인덱스 1 자리에 인덱스 2의 데이터를 저장해서 2, 6, 6 이렇게 하면 될 것 같네요.
문제는 인덱스 2에 저장되어 있던 6을 메모리에서 자연스럽게 지울 수 있는 방법이 없다는 것입니다. 만약 None(Python), Null(그 외 언어)과 같이 공간이 비었다는 것을 나타내는 값을 대신 넣으면 어떻게 될까요? 오류가 날 겁니다. 왜냐하면 두 값은 정수형이 아니어서 numArray에 저장될 수 없기 때문이죠.
정리하자면, 배열 numArray에서 인덱스 1을 지우기 위해서는 2, 4, 6의 데이터를 2, 6으로 만드는 게 아니라 2, 6, 6 이런 식으로 밖에 못 만듭니다. 다시 말해, 지우고 싶은 요소를 자연스럽게 삭제할 수 없기 때문에 삭제를 못한다는 겁니다.
❗ 동적 배열 삭제와의 차이
동적 배열에서는 어떻게 데이터를 삭제했었죠? Python의 리스트를 포함한 많은 언어들에서 자체적으로 제공하는 동적 배열은 사용하는 배열의 크기와 사용하는 인덱스 범위를 따로 처리한다고 했습니다.
동적 배열이 내부적으로 정수 3개를 저장할 수 있는 배열에 2, 4, 6을 저장하고 있다고 하겠습니다. 이 상태에서 인덱스 1을 삭제하고 싶으면 인덱스 1에 6을 저장합니다. 그럼 내부적으로는 2, 6, 6 이렇게 저장되어 있을 텐데요(동적 배열의 내부적 원리는 정적 배열이므로). 그 다음에 인덱스 2에 있는 6을 지우는 게 아니라 Python 내부적으로 개발자가 접근할 수 있는 인덱스 범위를 0~1로 만들어 버립니다. 더 이상 인덱스 2에 접근할 수 없도록 만드는 거죠.
실제로 인덱스 2에 어떤 값이 저장되어 있든지 개발자는 더 이상 그 인덱스에 접근할 수 없습니다. 삭제 후, 접근할 수 있는 데이터가 2, 6 밖에 없기 때문에 실질적으로 마지막 인덱스의 값이 삭제된 것처럼 보이는 것이죠.
이번 시간에는 동적 배열과 정적 배열에서의 삭제 연산, 그리고 정적 배열에서 삽입과 삭제에 제한이 있는 이유에 대해서 알아봤습니다. 마지막 인덱스의 값을 자연스럽게 삭제하지 못하는 문제를 해당 인덱스에 접근하지 못하도록 제한하여 해결했다는 것이 대단하다는 생각이 듭니다.
다음 시간에는 또 다른 자료 구조인 링크드 리스트에 대해 함께 알아보겠습니다.
* 이 자료는 CODEIT의 '자료 구조' 강의를 기반으로 작성되었습니다.