선형 자료구조 - 배열(Array)

배열(Array)

동일한 타입의 데이터를 연속적으로 나열한 선형 자료구조

• 많은 수의 데이터를 다룰 때 사용
• 각 데이터를 인덱스와 1:1 대응하도록 구성
• 데이터가 메모리 상에 연속적으로 저장됨

 

 

 

주요 특징

• 고정된 크기: 배열은 선언할 때 크기가 고정되며, 이 크기는 변경할 수 없음, 배열의 크기를 초과하는 요소를 추가할 수 없기 때문에, 필요한 크기를 미리 예상하여 배열을 생성해야 함(초과 시 새로 배열을 생성해야 한단 의미)
• 연속적인 메모리 할당: 배열은 메모리에서 연속적인 공간에 할당되며, 이로 인해 인덱스를 사용해 각 요소에 빠르게 접근 가능
• 인덱스를 통한 접근: 배열의 각 요소는 0부터 시작하는 인덱스를 가지며, 이 인덱스를 통해 O(1) 시간 복잡도로 임의의 요소에 접근 가능
• 동일한 데이터 타입: 배열의 모든 요소는 동일한 데이터 타입을 가지며, 이는 메모리 효율성과 접근 속도에서 중요한 역할을 함

 

 

배열의 장점

• 빠른 접근 속도: 배열은 인덱스를 통해 요소에 O(1) 시간 복잡도로 접근할 수 있어, 특정 요소를 빠르게 찾을 수 있음
• 메모리의 연속성: 배열은 메모리의 연속된 공간을 차지하기 때문에, 캐시 적중률이 높아져 성능이 향상될 수 있음

**캐시 적중률(Cache Hit Rate)**

캐시 메모리에서 필요한 데이터를 성공적으로 찾은 횟수의 비율을 의미

 

 

 

 

배열의 단점

• 고정된 크기: 배열은 크기가 고정되어 있어, 데이터의 추가/삭제가 번거로운 편  미리 충분한 크기를 예상해야 함 
  • 필요 이상의 크기를 할당하면 메모리 낭비가 발생하고, 가변 길이 배열은 배열의 크기를 변경할 때마다 새로운 배열을 생성
• 삽입과 삭제의 비효율성: 배열에서 요소를 삽입하거나 삭제할 때는 다른 요소들을 이동시켜야 하므로, 최악의 경우 O(n)의 시간이 소요됨

 

기본 연산

• 조회(Access): 특정 인덱스에 위치한 요소를 가져옴, 시간 복잡도는 O(1) 
• 삽입(Insertion): 배열의 특정 위치에 새로운 요소를 삽입, 고정된 크기의 배열에서는 삽입 시 요소들을 이동시켜야 하므로, 최악의 경우 시간 복잡도는 O(n)
• 삭제(Deletion): 배열에서 특정 위치의 요소를 제거하고, 나머지 요소들을 이동시킴, 시간 복잡도는 O(n)
• 수정(Update): 특정 인덱스에 위치한 요소를 수정, 시간 복잡도는 O(1)

 

 

 

배열의 확장: 동적 배열

배열의 크기 제한을 극복하기 위해 동적 배열(Dynamic Array) 개념이 도입

대표적인 동적 배열 구현체로는 Java의 ArrayList, C++의 std::vector, Python의 list가 있음

 

 

 

Q.  유연성이 뛰어난 동적 배열이 제공됨에도 불구하고 배열을 사용하는 이유

• 단순성과 성능: 배열은 고정된 크기를 가지므로, 메모리 할당과 접근이 매우 빠름. 배열 크기가 결정된 경우라면 동적 배열보다 효율적임
• 메모리 효율성:  동적 배열은 크기가 변할 때마다 메모리를 재할당하고 데이터를 복사해야 하므로 메모리 사용량이 더 많을 수 있음. 따라서 크기가 고정된 경우라면 메모리의 추가적 할당이 불필요한 배열이 나은 셈
• 간단한 구조: 배열은 구현이 간단하고, 관리가 쉬우며 예측 가능한 성능을 제공하기에 메모리 제약이 있는 환경에서는 배열의 단순성이 큰 장점이라고 함
• 예측 가능한 크기: 크기가 고정된 데이터 구조를 다룰 때는 정적 배열을 사용하여 불필요한 메모리 사용과 성능 저하를 방지할 수 있음