[ C.S 지식 정리 : 자료 구조 ] 자료구조 : 배열 (Array)

 

 

 

 

[ C.S 지식 정리 : 자료 구조 ] 자료구조 : 배열 (Array)

 

---

 

∇ CS지식 정리 _ 자료구조 : 배열 (Array)

목  차

1. 배열(Array)이란?
2. 배열의 사용.
3. 배열의 시간 복잡도
4. 단점

 

 

---

Ⅰ. 배열(Array) 이란?

---

 

    ◇ "배열"은 컴퓨터에서 리스트를 저장하는 데이터 타입 중 하나입니다.

    ◇ 대부분의 프로그램 언어에서 동일 타입의 데이터를 저장합니다.

          ["int" 타입으로 선언된 경우, 정수 요소만 저장 가능 ]

    ◇ 배열은 생성시 크기를 정하면, 그 크기로 고정.

    ◇ 배열을 구성하는 각각의 값을 요소(element)라고 하며,

            배열에서의 위치를 가리키는 숫자는 인덱스(index)라고 합니다.

           ->> 각 원소는 인덱스(index)를 사용하여 접근 가능.

    ◇ 반복문과 결합하면 많은 데이터도 효율적으로 처리 가능합니다.

 

 

---

Ⅱ. 배열(Array) 의 사용

---

        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);
 }

 

 

---

Ⅲ. 배열(Array) 의 시간 복잡도.

---

 

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

 

 

 

   A. 접근

 

        - 배열의 접근은 O(1)의 시간복잡도를 가집니다.

        - 찾고자 하는 값의 인덱스값을 알고 있다면 굉장히 빠른 검색 속도를 가집니다.

 

 

   B. 검색

 

        - 배열의 검색은 순차검색 이므로, 인덱스를 알지 못하는 경우, 원하는 값을 찾기 위해서 

               배열을 하나하나 확인해야합니다.

   A[3]의 값을 찾기 위해서 A[0], A[1]... 을 순서대로 검색하기 때문에 

   최대 O(n)의 시간 복잡도를 가집니다.

 

 

 

   C. 추가, 삭제

 

          - 추가, 삭제의 시간 복잡도는, 접근과 검색의 방법 차이에 따라서 시간복잡도가 나누어집니다.

 

        - A[6]에 5라는 값을 넣거나 빼고 싶을 때 해당 인덱스 값을 알고 있다면

             접근의 개념으로 O(1)의 시간복잡도를 가지겠지만,

              해당 인덱스를 찾아야 한다면 검색의 시간복잡도인 O(n)에 해당하는 시간복잡도를 가지게 됩니다.

 

 

---

Ⅳ. 단점.

---

 

     ◎ 고정된 크기

             - 배열은 생설할 때 크기가 정해지며, 크기를 변경하기가 어렵습니다.

             - 만약 배열의 크기를 초과하려면 새로운 배열을 생성하고 기존 배열의 요소를 복사해야 합니다.

 

     ◎ 메모리 낭비

             - 배열은 고정된 크기를 가지므로 필요한 크기보다 큰 배열을 생성하면 메모리가 낭비될 수 있습니다.

 

     ◎ 같은 데이터 타입의 요소만 저장 가능.

             - 배열은 동일한 데이터 타입의 요소만 저장할 수 있습니다.

             - 서로 다른 데이터 타입의 요소를 저장하려면 객체나 다른 자료구조를 활용해야 합니다.

 

     ◎ 삽입과 삭제의 어려움.

             - 배열에서 요소를 삽입하거나 삭제하는 것은 복잡하며 비효율적입니다.

             - 배열 중간에 요소를 삽입하거나 삭제하면 모든 뒤따라오는 인덱스를 조정해줘야 합니다.