PS
[개념정리] 선형 자료 구조(vector, linked list)
C++ 기준 다음의 헤더파일을 사용하면 쉽게 이용할 수 있다. #include #include 둘 다 선형 자료구조이지만, 둘의 차이점은 명확하다. 벡터 벡터는 배열을 이용해 만든 자료구조이다. 따라서 원소들은 메모리의 연속된 위치에 저장된다. 그래서 주어진 위치의 원소를 반환하거나 변경하는 동작을 O(1)에 할 수 있다.(index를 사용하기 때문!) 시간복잡도 resize() : O(N) (새 배열을 만들고, 기존 배열의 원소들을 하나씩 복사하기 때문) append() : O(1) *append()를 상수 시간안에 구현하려면, 처음 벡터를 선언할 때 미리 여유용량(capacity)을 확보해서 선언한다. 만약 capacity가 다 찬다면, 배열을 추가로 동적 할당한다. 이때, 기존 용량만큼 새로 할당하..
2021. 7. 10. 12:58