동적 배열 Dynamic Array

동적 배열도 결국 Array다

리사이징

넣어야 되는 데이터가 Array가 처음 할당 받은 메모리 크기보다 클 때, 리사이징이 동작한다.

새로운 메모리 주소를 할당받게 되는데, 그 크기는 기존 배열의 두 배가 기준이 된다. 왜냐하면, 리사이징은 기존에 있던 데이터를 새로운 메모리 주소에 옮기고 이전 데이터를 지워야 하는데, 이때만 O(n)의 시간복잡도를 가지게 된다. 이 리사이징 작업이 데이터를 추가할 때마다 동작하게 되면, 추가할 때마다 O(n)의 작업을 다시 해야 한다. 그래서 한 번 늘릴때 통크게 늘리는 것이다.

파이썬이 사용하게 되는 것이 dynamic array다

문제에서 list를 사용하게 될 때를 잘 구분해야함

선언 및 초기화

• 선언시에는 n개의 데이터를 넣어야하기 때문에 O(n)

접근

• O(1)

추가

• 데이터 사이즈가 남아있을 때는 O(1)

• 데이터가 꽉 차있을 때는 O(n)

• 분할상황기법으로 O(1)이 된다.

맨 뒤 데이터 삭제

• O(1) 데이터의 크기를 알고 있으므로 바로 삭제가능

중간 데이터 추가

• O(n) 데이터를 뒤로 밀어내고 데이터를 넣어야 하기 때문에 O(n)

중간 데이터 삭제

• O(n) 데이터를 앞으로 땡겨야 하기 때문에 O(n)

Uploaded by N2T