•
정의
◦
가장 기본적인 데이터 구조로 인덱스와 인덱스에 해당하는 요소로 구성된다.
•
특징
◦
정적 메모리가 할당되므로 길이가 고정되어 생성된다.
◦
Random Access를 지원한다. 즉 인덱스를 통해서 각 요소에 직접 접근할 수 있다.
◦
배열은 논리적 순서와 물리적 순서가 일치한다. 각 요소들이 연속되어 메모리에 저장된다.
•
시간복잡도
조회 | 검색 | 삽입 | 제거 |
O(1) | O(n) | O(n) | O(n) |
•
용도
◦
백트래킹이나 다이내믹 프로그래밍에 주로 사용된다.
◦
정렬, 탐색, 이진 탐색이 배열을 주로 사용한다.
▪
정렬
•
Stable : merge
◦
2개 이상의 컬럼을 정렬할 때, 정렬 대상이 되는 컬럼이 아닌 것에 대해 그 순서가 유지되는 것이다.
⇒ 중복 항목의 순서가 유지된다.
•
Unstable : quick, heap
◦
2개 이상의 컬럼을 정렬할 때, 정렬 대상이 되는 컬럼이 아닌 것에 대해 그 순서가 유지되지 않는 것이다.
⇒ 중복 항목의 순서가 유지 되지 않는다.
•
이는 공간복잡도와도 연관이 있다.
◦
탐색과도 연관이 있다.
▪
정렬되어 있지 않은 배열의 특정 값을 찾는 경우 O(n)의 시간복잡도를 가진다.
▪
정렬되어있을 경우, 이진 탐색이 가능하므로 O(log n)의 시간복잡도를 가진다.
•
Dynamic Array란?
◦
Array의 경우, size가 고정되어있는 자료구조이기 때문에 size보다 많은 갯수의 data가 추가 되면 저장할 수 없다.
◦
Dynamic Array는 저장공간이 가득 차게 되면 리사이징하여 유동적으로 크기를 조절하여 데이터를 저장하는 자료구조다.
◦
일반적으로 dubbling 기법을 사용해 자동적으로 리사이징한다.
▪
2의 n 제곱만큼 사이징을 늘린다. 이렇게 해야 추가 시 발생하는 리사이징 연산이 시간복잡도에 영향을 끼치지 않는다.
◦
size를 넘지 않는 데이터 추가에 대해서는 O(1), 넘어서는 데이터 추가에 대해서는 resize 연산이 O(n)인데 이를 amortized O(1)이라고 부릅니다
