[자료구조] 2. 배열(Array)

2. 배열(Array)

 

배열(Array)

 

Array의 요소(element)와 인덱스(index)

정의

동일한 데이터 타입을 가진 요소들이 연속적인 메모리 공간에 저장된 자료구조, 요소(element)와 인덱스(index)로 구성

특징

1. 고정된 크기 : 배열의 크기는 생성시 결정되며 이후에는 변경할 수 없음
2. 연속적인 메모리 : 배열의 요소들은 메모리 상에서 연속적으로 저장되며, 인덱스를 통해 빠르게 접근할 수 있음
3. 동일한 데이터 타입 : 배열은 동일한 데이터 타입의 요소들만 저장할 수 있어서 메모리를 효율적으로 사용할 수 있음

활용 예시

1. 데이터 목록 저장
2. Matrix 데이터 저장
3. 버퍼로 사용되어 임시로 데이터 저장
4. 정렬/탐색 알고리즘
5. 스택, 큐, 그래프, 트리의 기본 구조 역할
   
   

연산과 시간 복잡도

 

 

연산	설명	시간 복잡도
접근 (Access)	인덱스를 통해 특정 위치의 요소에 접근. 예: array[i]	O(1)
탐색 (Search)	배열에서 특정 값을 찾는 연산. 선형 탐색은 배열의 모든 요소를 순회함. ① 선형 탐색 : 배열을 처음부터 끝까지 순회하며 값을 확인하는 방법 ② 이진 탐색 : 배열이 정렬된 상태에서만 사용할 수 있는 탐색 방법	① 선형 탐색 : O(n) ② 이진 탐색 : O(log n)
삽입 (Insertion)	- 끝에 삽입: 배열의 마지막에 요소를 추가 - 중간/처음에 삽입: 특정 위치에 요소를 추가하고, 나머지 요소를 이동	끝에: O(1) 중간/처음에: O(n)
삭제 (Deletion)	- 끝에서 삭제: 배열의 마지막 요소를 제거 - 중간/처음에서 삭제: 특정 위치의 요소를 제거하고, 나머지 요소를 이동	끝에서: O(1) 중간/처음에서: O(n)
정렬 (Sort)	배열의 요소를 오름차순이나 내림차순으로 정렬	평균 : O(n log n) 최악 : O(n^2)

 

배열 확장의 메모리 처리 과정

• 배열이 가득 찬 상태에서 새로운 요소를 추가하려면 기존의 메모리를 확장해야 한다.
• 하지만, 배열은 고정된 크기와 연속된 메모리 공간을 사용하기 때문에 배열의 크기를 직접 늘리지 않고, 새로운 배열을 할당하고 복사하는 방식으로 배열을 확장한다. 확장 과정에서 O(n)의 비용이 발생한다.
• 메모리 처리 과정
  
  1. 새로운 메모리 할당 : 기존 배열 크기의 두 배나 일정 비율로 더 큰 크기의 새로운 배열을 메모리에 할당
  2. 데이터 복사 : 기존 배열의 모든 요소를 새로운 배열에 복사(시간 복잡도 O(n))
  3. 기존 배열 메모리 해제 : 기본 배열의 메모리를 해제하여 사용하지 않는 공간을 반환
  4. 새로운 배열 참조 : 이제 프로그램은 기존 배열 대신 확장된 배열을 사용
• 이 과정은 배열이나 리스트 같은 동적 자료 구조에서 자주 사용되는 방식이다.
  ex) Python의 List, Java의 ArrayList
• 일반적으로, 배열의 크기를 자주 확장해야 하는 상황이면 Linked List와 같은 자료 구조가 더 적합하다.