동적 배열도 결국 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