[Algorithm] 배열

배열(Array) - 정의: 메모리 상에 원소를 연속하게 배치한 자료구조. - 특징 (1) 다른 자료구조와 달리 원소를 저장하는 것 이외에 추가적으로 소모되는 메모리의 양(=오버헤드)이 거의 없는 것이 장점 (2) 메모리 상에 원소가 연속해서 있어야 한다는 성질로 인해 cache hit rate(https://parksb.github.io/article/29.html)가 높다는 장점이 있으나 할당에 제약이 걸린다는 단점도 있음 (3) 배열의 길이: 따로 변수를 하나 두어 배열의 길이 저장. 따라서 배열의 길이를 알고 있다고 가정 - 시간 복잡도 (1) 임의의 위치에 있는 원소를 확인/변경: 원소는 연속하므로 O(1) (2) 원소를 끝에 추가: 배열의 길이를 알고 있으니 마지막 위치에 원소를 두기만 하면 ..