알고리즘 - Array 기초개념

Array (배열) 이란? 

데이터들을 하나의 그룹으로 묶어서 효율적인 관리를 하기위한 자료구조이다.

알고리즘에서 배열을 공부하기 이전에 

Time Complexity (시간 복잡도)를 알아야 한다.

Time Complexity 란?

데이터 구조의 오퍼레이션의 속도를 측정하는 방법이다. 이 방법은 실제 시간을 측정하는 것이 아닌, 얼마나 많은 단계(step)가 있는가로 측정한다. 왜냐하면 하드웨어의 성능, 환경등 다른 요소에 의해 같은 코드여도 다른 변수로 인해 결과값이 달라질 수 있기 때문에 작은 단계(step)로 값을 얻을 수 있느냐가 중요한 척도가 된다.

메모리의 관점에서 Array 는 어떤가?

2가지의 메모리가 있다.

1. volatile (휘발성) 메모리: 휘발성 메모리중 RAM 은 Random Access Memory : 랜덤하게 데이터에 접속하며, 속도가 빠르다.
2. non - volatile (비휘발성) 메모리 : 하드 드라이브같은 개념이다.  컴퓨터를 껏다 켜도 데이터는 그대로인 경우와 같다.

 

보통 프로그래밍 언어에서 배열은 그 크기나 길이를 미리 선언해야한다.

오퍼레이션 4가지 

1. Reading : 배열을 어떻게 읽는가? 중요한점은 배열은 index 0 부터 시작한다. 그리고 컴퓨터는 배열이 어디서 시작하고, 얼마나 긴지 알고있기때문에 배열에서 읽는 건 빠르다.
2. Searching : 배열에서 검색은 느리다. 검색의 경우는 위치를 모르기때문에 배열을 한칸씩 모두 열어서 읽어봐야 하기 때문에 수행해야하는 단계가 많아질 수 있다. 0부터 하나씩 열어서 찾아보는 검색방법을 Linear Search (선형 검색) 이라고 한다.
   
   
3. Insert & 배열에 쓰기 : 배열을 만들떄는 메모리 공간을 확보해야한다. 여러가지 시나리오 중 예를 들어 무언가를 추가하고자 하는데 이미 선언한 배열의 크기중 남은 칸이 있을 때 '어디에 추가할 것인가'가 중요한 점이다. 그냥 마지막칸에 값이 삽입될 경우 컴퓨터는 시작위치와 길이를 알기때문에 쉽게 찾을 수 있게 된다. 하지만 배열의 중간위치에 삽입한다면? 그 앞뒤에 있는 배열값을 옮겨야 하기때문에 절차가 늘어날 수 있다. 최악은 배열의 선언된 크기가 이미 가득차서 더이상 값을 추가할 수 없는 경우이다.
   
   
4. Delete : 배열에 무언가를 추가하는 것과 비슷하다. 끝에 있는 값을 지울 경우는 길이와 위치를 알기에 빠른 처리가 가능하지만, 중간위치에 경우 값을 찾아서 지우고 비워진 칸만큼 땡겨서 위치를 옮겨야 하기에 느리다.