자료구조의 정리와 이해(Array)

Array

Array란 동일한 타입의 원소들이 연속적인 메모리 공간에 할당되어 각 항목이 하나의 원소에 저장되어 있는

기본적인 자료구조이다.

Array의 구성

배열의 인덱스 또는 키로 식별되는 요소 / 값의 컬렉션

인덱스는 0부터 시작

인덱스 떄문에 랜덤 엑세스 가능

Array의 특성

배열은 동일한 유형의 타입을 저장하기 위한 자료구조

배열은 인덱스를 키로 사용

배열은 원하는 만큼의 차원을 가질 수 있음, 1차원/2차원/3차원 배열 등

동적배열 : 배열의 크기가 동적으로 변경되는 경우

응용 프로그램에는 table,hashtable,heap이 있음.

---

Array의 장점

- 인덱스, 즉 키 때문에 랜덤 엑세스가 가능하다

- 구현 및 사용이 쉽다.

- 매운 빠른 자료구조로 항목을 반복해서 추가하거나, 삭제하려고 할 때 주어진 인덱스를 통해

빠르게 처리가 가능하다.

Array의 단점

- 컴파일 시점에 배열의 크기를 알아야하기 때문에 동적 자료구조가 아니다

- 배열을 다 찾을 경우, 더 큰 배열을 만들어야 하고 다 찬 배열의 데이터를 다시 복사해 옮겨야만 한다

- 다른 유형의 데이터를 저장할 수 없다.

 

 

---

Array의 연산

삽입연산

- 배열이 가득 차지 않는 한 배열에 값을 계속 추가할 수 있다.

- 새로운 값을 리스트에 추가할 때, 다음 인덱스에 삽입하면 되기 때문에 매우 빠르다

- 데이터의 양과 상관없이 빠르게 처리할 수 있기 때문에 O(1)의 시간 복잡도를 가진다.

 

특정 인덱스의 삽입 연산

문제점은 새로운 값을 주어진 인덱스 위치에 삽입하기 위해서는 기존에 저장된 값들을 이동해야한다.

저장된 데이터가 많으면 많을수록 처리시간이 증가하기 때문에 O(N)의 시간복잡도를 가진다.

 

삭제연산

배열에 저장된 값들을 뒤에서부터 삭제하는 연산은 매우 간단하다.

저장된 데이터의 양과 상관없이 빠르게 처리할 수 있기 때문에 O(1)의 시간복잡도를 가진다.

 

특정 인덱스의 삭제연산

배열의 특정인덱스의 값을 삭제하는 연산은 배열의 마지막 값을 삭제하는 것 처럼 간단하지않다.

해당 인덱스의 값을 삭제하고, 배열에 공백을 채우기 위해 값들을 앞으로 한칸씩 이동시켜야한다.

저장된 데이터가 많으면 많으수록 이동시켜야할 데이터가 증가하기 때문에 O(1)의 시간복잡도를 갖는다.

 

가능한 퀴즈

1.배열에 저장된 데이터의 순서 바꾸기

2.아나그램 문제 : 두개 문자 배열의 알파벳들이 일치하는지 확인하기

3.일차원 배열에서 중복된 정수값 찾기