(자료구조) 배열

1. 배열이란?

- 데이터를 나열하고 각 데이터를 인덱스에 대응하도록 구성한 데이터 구조

- 같은 종류의 데이터를 순차적으로 저장

 

2. 배열의 읽기

- 배열에서 읽기는 딱 한단계다. 특정 인덱스를 통해 한 번에 접근 가능하기 때문이다.

- 컴퓨터의 메모리는 셀로 구성된 거대한 컬렉션이라 할 수 있다. 프로그램에서 배열을 선언하면 컴퓨터는 프로그램이 쓸 수 있는 연속된 빈 셀들의 집합을 할당한다. 컴퓨터 메모리 내에 각 셀에는 특정 주소가 있다. 각 셀의 메모리는 앞 셀의 주소에서 1씩 증가한다. 

- 컴퓨터가 배열의 특정 인덱스에 있는 값을 읽을 때 한 번의 단계로 바로 갈 수 있는 것은 아래와 같은 점들이 복합적으로 작용한다.

• 컴퓨터는 모든 메모리 주소에 한 번에 갈 수 있다. 
• 각 배열에 저장된 내용은 메모리의 시작 주소이다. 따라서 컴퓨터는 손쉽게 시작 주소를 얻는다.
• 배열의 인덱스는 0부터 시작한다.

만약 컴퓨터에 인덱스 3에 있는 값을 읽으라고 명령하면 컴퓨터는 다음과 같은 과정을 밟는다.

• 배열의 인덱스는 0부터 시작하며 인덱스 0의 메모리 주소는 1010이다.
• 인덱스 3은 인덱스 0부터 정확히 세 슬롯 뒤에 있다.
• 따라서 인덱스 3을 찾으려면 1013 메모리 주소로 간다.

3. 배열의 검색, 삽입, 삭제

- 시간복잡도가 O(N)이다. 읽기보다 덜 효율적이다.

 

4. 장단점

- 장점 : 인덱스를 통해 빠른 접근이 가능하다

- 단점 : 어느정도 공간을 미리 설정해야 되기 때문에 데이터 추가/삭제가 어렵다

 

 

 

** 패스트캠퍼스의 '알고리즘/기술면접 완전 정복 올인원 패키지' 강의를 듣고 작성한 글입니다