[자료구조] 배열(Array)

 

---

[출처] https://www.geeksforgeeks.org/difference-between-static-arrays-and-dynamic-arrays/

 

 

 

1. 자료구조 구분

자료구조는 크게 두 가지로 나뉘는데,

• 메모리 공간 기반의 연속 방식 - 배열은 여기에 해당!
• 포인터 기반의 연결 방식

 

 

 

2. 배열의 정의

• 메모리 상에 원소를 연속하게 배치한 자료구조

 

 

 

3. (정적) 배열

• 크기를 지정하고 해당 크기만큼 연속된 메모리 공간을 사용해 작업을 수행함
• 크기가 고정되어 있어, 크기를 변경하는게 불가능함
• 실제 데이터의 크기가 얼마나 클지 알기가 어려운데 어떻게 하나?
• 그리하여 (동적) 배열 등장!

 

 

 

4. (동적) 배열

• 초깃값은 작게 잡아 배열을 생성
• 데이터가 추가되어 현재 크기보다 커지면 재할당 비율(Gross factor)만큼 resizing 후 모두 복사
  • Doubling - 데이터를 추가하다가 메모리를 초과하면, 기존 배열의 2배 큰 배열을 선언하고 데이터를 일일이 옮기는 방법
• 그렇담 2배씩 커지면 항상 O(n)씩 복사해야 하는 것 아냐?
  • 이는 최악의 경우일 뿐. 항상 append가 size를 넘어서야하는 경우만 해당
  • append의 과정을 살펴보면, 데이터를 마지막 인덱스에 추가하는 O(1) 과정이 대다수고, resizing하는 O(n)은 아주 가끔 발생하기 때문에 전체적으론 O(1). 정확히 말하자면 amortized O(1)임
  • 정리하자면, append할 때 대부분 O(1)이고 아주 가끔 resizing하는 O(n)이 발생하므로 전체적으론 O(1)의 시간이 걸린다고함

 

 

 

5. 배열의 성질

• 원소 확인/변경 : O(1)
  • 인덱스를 통해 데이터에 바로 접근 가능함. 인덱스는 주소에 상응하는 의미를 갖게됨
• 원소 삽입/삭제 : 원소의 끝 - O(1), 임의의 위치 - O(N)
• (c언어에서의 배열) 메모리 할당 시점 : 컴파일 타임, 정적, stack에 저장됨

 

 

 

6. 배열의 장단점

• 인덱스를 통해 데이터에 바로 접근 가능함(lookup). 조회를 자주 해야하는 작업에 용이
• Cache hit rate가 높음
  • Cache hit rate는 요청한 데이터를 캐시 메모리에서 찾을 확률임
    • Cache는 주기억장치와 CPU 사이에 위치해, 자주 사용하는 프로그램과 데이터를 기억함. 이는 CPU가 메모리까지 접근하는 횟수를 줄여, 성능을 향상시킴
    • Cache hit은 요청한 데이터를 캐시 메모리에서 성공적으로 찾아 제공되는 것을 의미함(Cache miss는 데이터를 찾지 못한 경우)
• 정적 배열은 특성상, 선언시 미리 배열의 크기를 정해야 함 = 메모리 상에 연속한 구간을 잡아야함
  • 할당에 다소 제약이 있으며, 메모리 낭비나 추가적인 오버헤드(overhead)가 발생할 수 있음

 

 

 

7. 자문자답

• 배열은 무엇인가?
  • 메모리 상에 원소를 연속되게 배치한 자료구조
• 장점
  • O(1)에 조회 가능으로, 조회가 자주 필요한 경우 용이함
  • Cache hit rate이 높음
• 단점
  • 메모리 상에 원소를 연속되게 배치하기 때문에, 할당에 제약이 있음
  • 정적 배열은 선언시 미리 배열의 크기를 정하기 때문에, 메모리 낭비나 추가적인 오버헤드(overhead)가 발생할 수 있음
• Dynamic array vs. Linked list

 

 

 

 

 

 

[출처] 파이썬 알고리즘 인터뷰