알고리즘 배열[Array]

배열[Array]

배열은 연속된 메모리 공간에 순차적으로 저장된 데이터 모음입니다

 

대부분에 프로그램 언어에서 동일 타입의 데이터를 저장합니다. 예를 들어 배열이 "int"타입인 경우 정수 요소만 저장할 수 있으며 double, float, char 등과 같은 다른 타입의 요소는 저장할 수 없습니다.

 

배열을 구성하는 각각의 값을 요소(element)라고 하며, 배열에서의 위치를 가리키는 숫자는 인덱스(index)라고 합니다.

 

-연속된 메모리 공간에 데이터들을 순차적으로 저장된다.

-인덱스는 0번 부터 시작됩니다.

-배열의 크기는 4이므로 4개의 요소를 저장 할 수 있습니다.

 

시간복잡도

- 임의의 위치에 있는 원소를 확인/변경 = O(1)

- 원소를 배열 끝에 추가 = O(1)

- 마지막 원소를 제거 = (O(1)

- 임의의 위치에 원소를 추가 / 임의 위치의 원소제거 O(N)

 

특징

-동일한 데이터 유형을 가지고 있습니다.

-배열의 각요소에 접근하는 시간은 O(1)로 모두 동일 합니다.

-연속된 메모리에 단일 블록화하여 데이터를 저장합니다. (낭비되는 공간이 없다.)

-실제 메모리 상에서 물리적으로 데이터가 순차적으로 저장되어 순서가 있으며 index가 존재한다.

 

장점

인덱스를 이용한 접근이 가능하기 때문에 모든 요소에 빠르게 접근할 수 있습니다.

기록 밀도가 1이기 때문에 공간 낭비가 적습니다.

간단하고 사용하기 쉽습니다.

 

단점

-배열을 선언 한 후에는 할당 된 정적 메모리 때문에 크기를 변경할 수 없습니다.

 

-중간에 특정 요소를 삽입 및 삭제하는 경우 항상 메모리가 순차적으로 이어여 있어야

하기 때문에 삽입 및 삭제된 요소로부터 위에 잇는 모든 요소들을 이동시켜주어야합니다.

 

-배열의 크기가 대부분 정적으로 결정되기 때문에 삽입과 삭제가 동적으로 발생하는 상황에서

적절한 배열의 크기를 미리 결정하는 것이 어렵고, 이로 인해 오버플로나 저장공간의 낭비를 초래할 수 있습니다.

 

배열 사용 EX)

-순차적인 데이터를 저장하며 값보다는 순서가 중요할때

-다차원 데이터를 다룰 때

-어떤 특정 요소를 빠르게 읽어야 할 때

-데이터 사이즈가 자주 바뀌지 않으며 요소가 자주 추가되거나 삭제되지 않을 때