01 - 1. 연속된 자료구조와 연결된 자료구조 (vector, array, forward_list)
연속된 자료구조 (Contiguous Data Structure) 연속된 자료구조는 모든 원소를 단일 청크(하나의 연속된 메모리 덩어리를 의미)에 저장한다. 데이터에 접근하는 시간은 O(1)로 항상 일정하지만 삽입, 삭제시 O(n)의 시간복잡도를 보인다. 연속된 배열의 유형을 크게 정적 배열과 동적 배열로 나눌 수 있다. - 정적 배열(Static Array) : 스택(Stack) 메모리 영역에 할당됨 -> 함수 혹은 스코프를 벗어날 때 자동으로 해제됨 - 동적 배열(Dynamic Array) : 힙(Heap) 메모리 영역에 할당됨 -> 사용자가 직접 해제하기 전까지 유지됨 캐시 지역성(Cache Locality)이 뛰어나다. 연속된 자료구조의 각 원소는 서로 인접해 있기 때문에 어떤 원소에 접근할 때 ..
Algorithm
2022. 6. 21. 22:30