동적 배열(Dynamic Array)

선언 이후에 size를 변경할 수 없는 정적배열(static array)과 다르게 동적 배열(dynmic array)은 size를 늘릴 수 있다.

 

# Static Array vs Dynamic Array

- static array 한계점 : 고정된 저장공간. array는 선언 시 크기를 지정해야하고 딱 그만큼만 메모리를 할당받기 때문에, 프로그램이 실행되는 중간에 추가적으로 더 데이터가 들어온다면 저장을 할 수 없다.

- dynamic array : 그런 상황이 왔을 때, 배열의 크기를 늘림으로써, 엄밀히 말하면 더 큰 배열을 새로 다시 할당함으로써 데이터를 더 추가할 수 있다.

(static) array에 대해서 ↓

2023.09.06 - [자료구조알고리즘] - 배열(Array)

 

# Dynamic Array

Dynamic array도 (static) array로 구성되어있다. 

이렇게 데이터를 추가하는 과정이 O(1)으로 바로바로 추가할 수 있다.

이렇게 10까지 추가하다보니 Dynamic array에 할당된 메모리가 가득 찼다.

하지만 우리는 11, 12, 13도 추가해야한다. 이런 경우 static array는 더이상 추가할 수 없다.

 

## Resizing

dynamic array는 기존에 있던 배열보다 더 큰 배열을 새로 할당받아 그 새 배열에 옮겨적고, 비로소 11을 저장한다.

이 과정을 Resizing과정이라고 하고, 앞에서 데이터를 추가하는 과정은 O(1)이었지만, dynamicArray.insertBack(11) 경우만 O(n)이 된다.

 

여기서 중요한건, Dynamic Array가 resizing하는 과정이다.

1/ 기존에 있던 배열보다 2배 더 큰 배열을 할당한 다음에 일일이 옮겨적고,

2/ 그 2배 더 큰 배열에 새로운 데이터를 추가한다.

3/ 그리고 기존에 있던 배열을 삭제한다.

 

이렇게 되면 결과적으로 dynamic array의 사이즈가 늘어난 것이 된다.

다만, 그 과정에서 데이터를 하나하나 옮겨야하기때문에 시간복잡도는 O(n)이 된다.

 

이런 의문이 들 수 있다.

Q. 기존에 10개짜리 배열이 있다면, 11이 있다면 한자리 수만 더 늘리면 되지 않나?

→ 이 Resizing 과정은 굉장히 오래 걸리는 과정이다. 그런데 이 과정에서 array를 한칸씩만 늘린다면 데이터가 추가되자마자 다시한번 꽉차는 상황이 발생한다. 그럼 그 다음 데이터를 저장할때 또 Resize를 해야한다. 그럼 그때도 시간복잡도가 O(n)이다.

이렇게 옮기는 과정으로 시간을 엄청 할애하게된다.

 

 

그렇다고 Resize를 10배 큰 배열을 할당받기에는 메모리낭비가 클 수도 있기 때문에 대부분 언어에서 타협으로 기존 크기의 배열보다 2배 더 큰 배열을 할당한다.

"기본적으로 Dynamic Array는 Resize를 할 때 2배 더 큰 새 배열을 할당한다."라고 알고있으면 된다.

 

이렇게 Resize가 끝나면, 그 다음 데이터들은 또 자유롭게 O(1)으로 데이터를 추가할 수 있다.

 

 

Python의 list 자료구조는 Dynamic array로 구현한 것이다.

- The growth pattern is : 0, 4, 8, 16, 24, 32, 40, 52, 64, 75..

-  list의 크기가 4, 8, 16, 이렇게 2배씩 증가하다가 24로 커진다. 그다음 32, 40, 52 이렇게 커진다. 처음에는 사이즈를 2배씩 늘리다가 커지면 커질수록 2배까지는 아니고 1.x배로 Resize하게된다.

- 이런 식으로 동적배열은 resize를 한다.

 

 

결국 우리에게 중요한건, Dynamic Array의 사용법.

 

Dynamic Array를 쓰면 편한 경우가 굉장히 많다.

우리가 Array List를 구현할 때, (Static) Array로 구현할 수도 있고, Dynamic array로 구현할 수도 있다.

 

 

# Static array vs Dynamic Array 시간복잡도

 

지금 Python에서는 Array List로 List 자료구조를 쓰고 있다. 만약 Array List를 Static array로 구현했다면 시간복잡도가 왼쪽과 같아질거고, (Python처럼) Dynamic Array로 구현했다면 오른쪽의 시간복잡도가 된다.

 

그래서 access/update를 한다면 둘다 시간복잡도가 O(1)이고,

insert_back은 둘다 O(1)인데, Dynamic array는 resize하는 과정은 O(n)이다. 하지만 분할상황기법에 의해 O(1)라고 볼 수 있다.

insert_at : 중간에 데이터를 삽입하는건 둘다 O(n)

delete_at : 중간에 데이터를 삭제하는것도 O(n)

 

각각 operation들의 시간복잡도가 왜 이런식으로 나오는지 보자.

 

a = [1, 2, 3]

일단 list를 선언하고 초기화를 했다. 선언 및 초기화에서는 시간복잡도가 O(n)이 걸린다. 왜냐하면 배열에 n개의 데이터를 저장해야되므로.

그리고 배열에 데이터를 저장하면 size를 따로 저장한다. 지금은 데이터가 3개이므로, size:3 저장.

 

## access

만약 0번째 index에 저장된 데이터를 접근하려면, O(1)로 접근가능.

Dynamic array도 결국 array로 구현이 되어있고, array는 random access로 바로 접근가능하므로 시간복잡도는 O(1).

 

## update

접근 뿐만 아니라 수정도 O(1)로 가능하다. 왜냐하면 일단 random access로 O(1)로 접근 가능한 다음에, 그 메모리 공간에 데이터만 바꾸면 되기 때문에 O(1)로 가능한 연산.

 

## append(insert_back)

size를 미리 알고 있기 때문에, 마지막 index에 바로 접근이 가능하다.

size가 3이므로 0, 1, 2번째 index는 전부 데이터가 저장되어있겠구나. 내가 append를 해야될 위치는 3번째 index이겠구나, 라고 바로 알 수 있고, 이것도 random access로 바로 접근해서 데이터를 추가만 하면 된다.

그래서 append도 시간복잡도 O(1)로 가능.

 

 

## append 시, resizing

만약 아래와 같이 배열이 가득 찼다. 그때 append를 하려고 하면, resizing 과정을 거친다. → O(n)의 시간복잡도를 갖는다.

하나씩 데이터를 옮겨주고, 비로소 6을 저장하고 기존 배열은 삭제.

그래서 resizing 과정은 O(n)의 시간복잡도가 걸린다.

 

Resizing을 할 때 시간복잡도가 O(n) 걸린다고 해서, 데이터 추가에 시간복잡도가 O(n)이 걸린다고 말하기는 애매하다. 왜냐하면 대부분의 과정 중에서는 대부분의 append를 할 때는 O(1)이기 때문.

그래서 이런 경우에는 O(n) 시간복잡도가 '가끔' 발생한다면, '분할상황기법'이라는걸 사용해서 O(1)라고 표기한다.(나중에 설명)

append를 하는, 데이터 추가하는 과정은 시간복잡도 O(1)으로 가능.

 

## a.pop()

맨 뒤의 데이터를 삭제하는건 다 O(1)으로 가능하다. 이것도 우리가 size를 알고 있기 때문에 맨 마지막 index가 몇 번째 index인지 알고있고, 그곳에 접근하는건 O(1) 시간복잡도로 random access가 가능하고, 마지막 데이터를 삭제하는 과정은 O(1)이 된다.

 

## a.insert(1, 10)

list 중간에 데이터를 삽입하는건 시간복잡도가 몇일까?

1번 index에 10을 넣으려고 준비하고 있다.

배열은 결국 연속적/순차적으로 저장이 되어있어야 하기때문에 얘네들을 한 칸씩 뒤로 밀고 1번 index에 저장해야한다.

즉, 중간에 데이터를 삽입하는 과정을 끝내려면 거의 'n'개에 가까운 데이터를 한칸씩 한칸씩 옮겨주는 작업을 해야한다. 그래서 시간복잡도가 O(n).

 

## a.pop(2)

비슷한 이유로 중간에 데이터를 삭제하는 것도, 한칸씩 한칸씩 앞으로 옮겨줘야하므로 O(n)이 된다.

 

 

 

이렇게 대표적인 연산에 대해서만 시간복잡도를 알아봤다.

내부적으로 어떻게 돌아가는지만 안다면 이 연산들 말고도 다른 연산들의 시간복잡도를 충분히 구할 수 있다.

 

더 나아가 코딩테스트에서도 시간복잡도가 얼마나 걸리는지를 알고 있어야 코드를 짤 때 내가 이 operation을 썼을때 시간복잡도가 몇인지를 생각하고 있어야 한다.

달달 외우는건 도움이 안되므로, 내부적으로 어떻게 동작하는지를 알아야만 문제를 풀때 훨씬 도움이 된다.

 

 

**출처 : 모든 내용은 인프런의 '코딩테스트 [ALL IN ONE]'강의를 기반으로 작성하였습니다.