[(PS)DataStructure] 배열 (+vector)

바킹독님의 강의를 참고하였습니다.

https://blog.encrypted.gg/category/강좌/실전%20 알고리즘

'강좌/실전 알고리즘' 카테고리의 글 목록

+ 해당 카테고리엔 알고리즘 문제풀이와 관련된 내용을 업로드.

+ 기록해두고 싶은 부분만 정리해 둠.

---

정의&성질

음 그러하다.

 

• 배열은 메모리 상에 원소를 연속하게 배치한 자료구조라서, k번째 원소의 위치를 바로 계산할 수 있다. 시작 주소에서 k칸만큼 오른쪽으로 가면 되기 때문. => 그러기에 k번째 원소를 O(1)에 확인하거나 변경할 수 있다.
• 배열은 다른 자료구조와 다르게 추가적으로 소모되는 메모리의 양이 거의 없다.
• 메모리 상에 데이터들이 붙어있으므로 Cache hit rate 가 높다.
• 메모리 상에 연속한 구간을 잡아야 하니 할당에서는 다소 제약이 있다.

2,3,4번 성질은 코딩테스트 한정 큰 상관이 없으므로 여기선 그냥 그렇구나~ 하고 넘긴다.

---

기능&구현

 

여기까진 자명하니 pass

여기서부터 중요한데, 임의의 위치에 원소를 추가하는 과정은 O(N)이 된다.

위 사진에서 보면, 5번에 15를 추가했는데 이렇게 되면 그 뒤의 원소들을 전부 한 칸씩 밀어야 해서 O(N)이 필요하게 된다.

+ 추가하는 위치가 끝일수록 시간은 줄고, 앞일수록 시간은 늘어날 테지만, 평균적으론 N/2개를 밀어야 하니 O(N)이라고 해도 됨.

마찬가지로, 임의의 위치의 원소를 제거하는 것도 O(N)이다.

 

❗️메모리 상에 원소가 연속해서 존재해야 하기 때문에 O(1)로 임의의 위치의 원소를 추가/제거 가 불가능하다.

---

vector

 

STL의 vector는 배열과 거의 동일한 기능을 수행하는 자료구조지만,

배열과 달리 크기를 자유자재로 늘이거나 줄일 수 있다는 장점이 있다.

+배열과 동일하게 임의의 원소를 추가(insert)/ 제거(erase)의 시간복잡도는 O(N)이다.