[자료구조와 알고리즘] 빠르게 읽을 때 효율적인 Array 자료구조

안녕하세요. Doi 입니다.

자료구조와 알고리즘은 최적화를 위해서 필요한 지식인데요.

이에 대해서 공부한 내용에 대해서 정리하도록 하겠습니다. 

 

[알고리즘과 자료구조에 대한 짧은 설명]

Algorithm은 여러 개의 지시사항입니다.

어떠한 액션을 취하기 위해서 컴퓨터가 처리해야 되는 지시사항입니다.

 

Data Structure는 데이터를 정리하는 방법입니다.

이는 프로그램의 효율(스피드)에 영향을 줍니다.

 

[메모리에 대한 짧은 설명]

메모리는 두 가지로 분류할 수 있습니다. 

휘발성 메모리(volatile memory)와 비휘발성 메모리(non volatile memory)가 그 분류 기준인데요. 

 

휘발성 메모리에는 대표적으로 Ram이 있습니다.

비휘발성 메모리에는 대표적으로 Hard Drive가 있습니다.

 

휘발성 메모리는 비휘발성 메모리에 비해서 속도가 빠르지만 비싼 가격으로 인해서 용량이 작습니다.

비휘발성 메모리는 휘발성 메모리와는 반대로 속도가 느리지만 싸고 용량이 큽니다.

 

이에 대해서 더 궁금하면 아래 메모리 계층 구조 관련 설명 링크를 참고하시면 됩니다.

https://m.blog.naver.com/sjc02183/221998493348

메모리 계층 구조 - Register, Cache, Ram, HDD, SSD

 

 

 

[Array의 구조] 

Array는 선형 구조를 갖습니다. 아래의 이미지를 참고해서 array가 ram에서 어떻게 공간을 차지하는지 봅시다.

array는 공간의 수가 정해져 있고 연결된 상태로 공간을 차지합니다.

ram에서 array가 공간을 차지하는 방식

[Array의 특징]

자료구조의 효율성에 대해서는 4가지 operation(상황)으로 생각해볼 수 있습니다.

1. Reading(읽기)

2. Searching(검색)

3. Insert(추가)

4. Delete(삭제)

 

Array를 이 4가지 operation에 맞추어 설명해보도록 하겠습니다.

1. Reading - 많은 자료를 읽을 때 속도가 빠릅니다. 그 이유는 컴퓨터가 배열이 어디서 시작되는지 정확히 알고 있기 대문입니다.

2. Searching - array는 선형적으로 검색하기 때문에 '검색'에 시간이 많이 걸립니다.

3. Insert - 값이 중간이나 앞에 있을 때 '공간 확보'를 위해서 다른 값들을 이동시켜야 하기 때문에 시간이 많이 걸립니다.

4. Delete - 값이 중간이나 앞에 있을 때 삭제 후 '빈 공간을 채우기'위해서 다른 값들을 이동시켜야 하기 때문에 시간이 많이 걸립니다.

 

[어떻게 사용?]

Array는 데이터를 빠르게 읽을 때 사용하면 유리합니다. 다만, 데이터의 사이즈가 자주 바뀌지 않고, 요소가 자주 삭제 되거나 추가되지 않을 때 유리합니다.

 

만약 요소를 추가, 삭제 해야 되는 경우에는 배열의 가장 뒤에 추가, 삭제를 하는 것이 효율적입니다.