배열의 기초개념(Array) 공부

Array 배열 기초개념? 10분안에 정리해줌! 이라는 영상을 보고 내용을 정리한 글이다.

(영상은 최하단에 첨부)

 

배열의 무엇을 공부하는가?

가장 기본적인 데이터 구조이다.

 

이 영상에서 가장 먼저 소개하는 것은 시간복잡도(Time Complexity)이다.

 

배열의 Read, Search, Add, Delete의 4 Operation에 대한 시간복잡도를 공부한다.

 

먼저, 시간 복잡도(Time Complexity)란?

자료 구조의 오퍼레이션 혹은 알고리즘이 어느 정도의 속도인지 측정하는 방법이다.

 

얼마나 많은 단계(step)이 있는지를 갖고 측정한다.

 

메모리 관점에서의 배열

메모리는 먼저 2가지로 나뉜다. 휘발성(Volatile), 비휘발성(Non-Volatile) 메모리.

 

프로그램이 실행되고 변수를 생성할 때는 모두 RAM에 저장된다.

 

RAM에서 데이터를 읽는 것은 이름에서부터 더 빠른 이유를 찾을 수 있다.

 

Random Access Memory를 줄인 말인데, 말 그대로 랜덤하게 자료에 액세스할 수 있다.

 

데이터를 조회할 때 해당하는 주소에 바로 접근이 가능하기 때문이다. 하드 드라이브는 순차적으로 접근해야 한다.

 

우리가 배열을 만들 때, 메모리에 어느 정도의 길이의 배열을 생성할 것인지 미리 알려주어야 배열을 생성할 수 있다.

 

자바스크립트나 파이썬을 이를 개발자가 핸들링 해주지 않아도 되는데

이로 인해 모두 직접 핸들링해야하는 C와 속도 차이가 날 수 있다.

 

Array in 4 Operation

1. Read

먼저, 배열은 0부터 인덱싱을 한다. 따라서, 위치만 알면 배열의 데이터에 접근할 수 있다.

 

컴퓨터는 배열의 시작점과 종점을 알고 있기 때문에 '읽기'는 매우 빠르다.

 

배열이 매우 길어도 '읽기'에는 매우 빠르다. 인덱스에서 요소를 읽어내는 속도는 동일하기 때문.

 

2. Search

'읽기'와 다르게 '검색'은 해당 데이터가 어느 위치에 있는 지 모르기 때문에 시간이 더 걸린다.

 

하나씩 순차적으로 데이터를 접근해서 확인해야 하기 때문에

배열의 길이가 길어지고 검색 목표가 가장 뒤에 있다면 매우 오래 걸릴 것이다.

 

위의 작업을 선형 검색(Linear Search)이라고 한다.

 

배열에서의 검색을 다르게 하는 방법도 있지만 어쨌든 배열에서의 검색은 그닥 빠르지 않다.

 

3. Insert

배열을 만들 때는 메모리의 공간을 미리 확보해 두어야 한다.

 

배열에 남는 공간이 하나 있을 때를 가정하고 데이터 하나를 추가하는데 3개의 시나리오가 있다.

 

최고의 시나리오는 데이터를 배열 마지막에 추가하는 경우이다.

 

컴퓨터는 배열의 마지막에 데이터를 바로 추가하면 끝이다.

 

보통의 시나리오는 데이터를 중간에 추가하는 경우이다.

 

데이터를 추가할 오른쪽의 다른 데이터들을 배열의 우측으로 밀어내고 데이터를 추가하게 된다.

 

최악의 시나리오는 데이터를 배열의 맨 앞 쪽에 추가하는 경우이다.

 

이 경우, 배열의 모든 데이터를 우측으로 밀어내야한다.

 

만약 배열의 크기가 매우 크다면 이 작업은 매우 오래 걸릴 것이다.

 

또 다른 안 좋은 시나리오는 현재의 배열보다 더 큰 사이즈의 배열이 필요한 경우이다.

 

이 경우는 이전 배열을 새 배열을 생성한 후 복사하고 새로운 데이터를 추가해야 한다.

 

4. Delete

'삭제'는 '삽입'과 비슷하다. 배열을 움직여야 하기 때문이다.

 

시나리오는 '삽입' 작업과 반대의 위치부터 최고-보통-최악으로 흐른다.