[자료구조] 배열 (Array)

---

👉배열(Array)이란?

배열은 컴퓨터에서 리스트를 저장하는 데이터 타입 중 하나이다.
연속된 메모리 공간에 순차적으로 데이터가 저장되며(선형구조) 다음과 같은 특징을 갖습니다.

• 배열은 같은 타입의 데이터를 여러개 나열한 선형 자료구조 입니다.
• 대부분에 프로그램 언어에서 동일 타입의 데이터를 저장합니다.
  ("int" 타입으로 선언된 경우 정수 요소만 저장가능)
• 배열은 생성시 크기를 정하면, 그 크기로 고정이 됩니다.
• 배열을 구성하는 각각의 값을 요소(element)라고 하며, 배열에서의 위치를 가리키는 숫자는 인덱스(index)라고 합니다.
  (각 원소는 인덱스(Index)를 사용하여 접근할 수 있습니다.)
• 반복문과 결합하면 많은 데이터도 효율적으로 처리할 수 있습니다.

---

👉배열의 사용

1. 각 언어별 배열의 선언 방법

🤜 파이썬

// 1차원 배열 선언
arr1 = [1, 2, 3, 4, 5]

// 2차원 배열 선언
arr2 = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

🤜 자바: 해당 배열의 자료형과 크기를 지정해야 합니다.

// 1차원 배열 선언
int[] arr1 = new int[5];

// 2차원 배열 선언
int[][] arr2 = new int[3][3];

🤜 C: 자료형과 크기를 명시해야 합니다.

// 1차원 배열 선언
int arr1[5];

// 2차원 배열 선언
int arr2[3][3];

2. 배열의 복사(Java)

1. 배열의 얕은 복사 -> 주소 값 복사

int[] a = {1,2,3,4,5};
int[] b;
b = a;

2. 배열의 깊은 복사 -> 요소 값 복사

int[] a = {1,2,3,4,5};
int[] b;
b = a.clone();

3. for문을 이용한 배열의 간단한 예시(Java)

// 정수형 배열 선언과 초기화
   int[] arr = {5, 10, 15, 20, 25};
   
// 배열 요소들의 합을 저장할 변수 초기화
	int sum = 0;

// for 문을 이용하여 배열 요소들의 합 계산
	for (int i = 0; i < arr.length; i++) {
		sum += arr[i];
 }
 
// 결과 출력
   System.out.println("배열 요소들의 합: " + sum);
 }

---

👉배열의 시간복잡도

🤜 배열 내 연산은 크게 접근(access), 검색(search), 추가(add), 제거(remove) 가 있습니다.

1.접근

배열의 접근은 O(1)의 시간복잡도를 갖습니다. 따라서 찾고자 하는 값의 인덱스값을 알고 있다면 굉장히 빠른 검색 속도를 갖습니다.

2.검색

배열의 검색은 순차검색 이므로 인덱스를 알지 못할 때 원하는 값을 찾기 위해 배열을 하나하나 확인해야합니다.

A[3]의 값을 찾기 위해 A[0], A[1]... 을 순서대로 검색하기 떄문에 최대 O(n)의 시간 복잡도를 가집니다.

3. 추가,삭제

추가, 삭제의 시간복잡도는 앞서 말한 접근과 검색의 방법 차이에 따라 시간복잡도가 나뉩니다.
A[6]에 5라는 값을 넣고, 혹은 빼고 싶을 때 해당 인덱스값을 알고 있다면 접근의 개념으로 O(1)의 시간복잡도를 가지지만 해당 인덱스를 찾아야한다면 검색의 시간복잡도인 O(n)에 해당합니다.

---

👉 단점

• 고정된 크기:
  배열은 생성할 때 크기가 정해지며, 크기를 변경하기 어렵습니다. 만약 배열의 크기를 초과하려면 새로운 배열을 생성하고 기존 배열의 요소를 복사해야 합니다.
• 메모리 낭비:
  배열은 고정된 크기를 가지므로 필요한 크기보다 큰 배열을 생성하면 메모리가 낭비될 수 있습니다.
• 같은 데이터 타입의 요소만 저장 가능:
  배열은 동일한 데이터 타입의 요소만 저장할 수 있습니다. 서로 다른 데이터 타입의 요소를 저장하려면 객체나 다른 자료구조를 활용해야 합니다.
• 삽입과 삭제의 어려움:
  배열에서 요소를 삽입하거나 삭제하는 것은 복잡하며 비효율적입니다. 배열 중간에 요소를 삽입하거나 삭제하면 모든 뒤따라오는 요소들의 인덱스를 조정해야 합니다.

---

---

참고 자료
시간복잡도
https://opentutorials.org/module/1335/8677
https://chanyeong.com/blog/post/49