Arrays.md

배열

1. 정의
2. 특징
   1. 장점
   2. 단점
3. 활용
4. 시간복잡도와 공간복잡도
5. 데이터의 숫자가 배열의 크기를 넘어서는 경우
6. 참고 자료

정의

연관된 데이터를 메모리상에서 연속적이며 순차적으로 미리 할당된 크기만큼 저장하는 자료구조.

배열은 연속된 메모리 공간에 순차적으로 저장된 데이터 모임이다. 대부분의 프로그램 언어에서 동일 타입의 데이터만 저장할 수 있다. 배열을 구성하는 각각의 값을 요소(element)라고 하며, 배열에서의 위치를 가리키는 숫자를 인덱스(index)라고 한다.

특징

• 배열은 같은 타입의 데이터를 여러개 나열한 선형 자료구조
• 순차적인 데이터 저장(order) -> 논리적 순서와 물맂거 순서가 일치
• 고정된 저장 공간(fixed-size, 정적 메모리 할당) -> 배열은 선언할 때 크기를 정하면, 그 크기로 고정
• 선언된 값은 배열을 다시 선언하지 않으면 변경 불가능
• Random Access를 지원. 즉, 인덱스를 통해서 각 요소에 직접 접근할 수 있음

장점

• lookup과 append가 빠르다. 따라서 조회를 자주 사용하는 작업에서는 배열이 많이 사용된다.

단점

• 정적 메모리 할당(fixed-size) 특성상 선언시에 배열의 크기를 미리 정해야 한다. 이는 메모리 낭비 혹은 추가적인 오버헤드를 발생시킬 수 있다.

활용

• 순차적인 데이터를 저장하며, 값보다는 순서가 중요할 때.
• 다차원 데이터를 다룰 때.
• 어떤 특정 요소를 빠르게 읽어야 할 때.
• 데이터의 크기가 자주 바뀌지 않으며 데이터의 추가, 삭제가 뜸한 경우.

시간복잡도와 공간복잡도

• 시간복잡도

  Operation	Average	Worst
  Access	Θ(1)	O(1)
  Appened	Θ(1)	Θ(1)
  마지막 원소 Delete	Θ(1)	Θ(1)
  Search	Θ(n)	O(n)
  Insertion	Θ(n)	O(n)
  Deletion	Θ(n)	O(n)

  • 탐색 : 특정 원소가 몇번째 인덱스에 있는지 알아내기 위해 모두 방문해야 함.
  • 삽입 : 새 원소를 삽입시 기존 원소들을 밀어내야 함.
  • 삭제 : 특정 원소 삭제시 남은 원소들을 당겨줘야 함.

• 공간복잡도
  O(n)

데이터의 숫자가 배열의 크기를 넘어서는 경우

예상한 것보다 더 많은 수의 데이터를 저장하느라 배열의 크기를 넘어서는 경우에는 어떻게 해야할까? 크게 두가지 해결 방법이 있다.

1. 동적 배열(Dynamic Array) 사용
   기존의 크기보다 더 큰 배열을 선언하고, 데이터를 옮겨 할당한다. 모든 데이터를 옮겼다면 기존 배열은 메모리에서 삭제한다. 이런 방식으로 배열의 크기를 조절하는 자료구조를 동적 배열(Dynamic Array)이라고 부른다.
2. 링크드 리스트 사용
   크기를 예측하기 어렵다면 배열 대신 링크드 리스트(Linked List)를 사용함으로써 데이터가 추가될 때마다 메모리 공간을 할당받는 방식을 사용한다.

참고 자료

• PRACTICAL DATA STRUCTURE 데이터 구조 - 오상엽, 장성식, 정호일 저
• #정의
  • [자료구조] 배열 (Array)
• #특징, #활용
  • [자료구조] 배열(Array)
• #시간복잡도와 공간복잡도
  • Big-O Cheat Sheet