[자료구조] 배열 : 기초 자료 구조

  배열은 컴퓨터 과학에서 기초적인 자료 구조 중 하나다. 배열은 리스트와 같은 개념이다. 

array - ['apple', 'bananas', 'cucumbers', 'dates', 'elderberries']

배열의 인덱스는 데이터가 어디에 있는지 알려주는 숫자이며, 예제의 경우 apple은 0, dates는 3의 값을 가진다.

대부분의 자료 구조는 4가지 기본 연산을 가지고 있다.

• 읽기 : 자료 구조 내 특정 위치를 찾아보는 것
• 검색 : 자료 구조 내 특정 값을 찾는 것
• 삽입 : 자료 구조에 새로운 값을 추가하는 것
• 삭제 : 자료 구조에 값을 제거하는 것

자료 구조에서 연산의 빠르기는 시간의 단위를 사용하지 않는다. H/W의 사양에 따라 달라질 수 있기 때문이다. 자료 구조에서 연산은 "얼마나 많은 단계가 필요한가?"를 분석하게 된다. 연산의 빠르기를 알아보자.

---

읽기

  읽기는 배열 내 특정 인덱스에 어떤 값이 들어 있는지 찾는 것이다. 배열에서 읽기는 실제로 딱 한 단계다. 배열의 특정 인덱스에 한 번에 접근해서 볼 수 있기 때문이다. 컴퓨터가 배열의 특정 인덱스에 있는 값을 읽을 때 한 번의 단계로 바로 갈 수 있는 것은 다음과 같다.

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

  배열은 읽기에 아주 효율적이다. 그렇기 때문에 강력하기도 하다.

---

검색

  검색은 배열에 특정 값이 있는지 알아본 후, 있다면 어떤 인덱스에 있는지 찾는 것이다. 배열에서 값을 찾을 때 컴퓨터는 인덱스 0부터 시작해서 값을 확인한 후 찾는 값이 아니면 다음 인덱스로 이동한다. 이 과정은 찾고 있는 값을 발견할 때까지 반복된다. 

 

  찾으려고 하는 값을 할 때까지 반복하는 횟수를 '단계'라고 한다. 4번에 거쳐 발견하였다면 이 연산에는 총 <4단계>가 걸렸다고 할 수 있다. <알고리즘>이 중요한 것은 이 검색에서의 연산에 사용되는 단계 때문이다. 위에서 설명한 것과 같이 처음부터 일일이 찾아가는 것을 <선형 검색>이라고 한다.

 

  선형 검색에 필요한 단계는 1부터 배열이 가지고 있는 마지막 인덱스까지 그 속도 차이가 엄청날 수 있다. 어떤 검색 방법을 사용하더라도 검색이라는 것은 읽기보다 덜 효율적인 것은 맞다.

---

삽입/삭제

  삽입은 배열의 어딘가에 데이터를 삽입하는 것이다. 따라서 어디 위치에 삽입을 하느냐에 따라서 그 효율성은 달라질 수 있다. 배열의 맨 마지막에 데이터를 추가하는 것은 1 단계로 끝날 수 있지만 처음이나 중간에 데이터를 삽입할 때에는 문제가 달라진다.

 

  처음이나 중간에 삽입하려면 삽입하려는 인덱스보다 뒷 쪽에 있는 데이터들을 뒤로 옮겨야 한다. 결국 뒤에 있는 데이터의 개수만큼의 <단계>가 필요하다. 그리고 데이터를 삽입하는 1 단계가 추가된다. 

 

  삭제는 삽의 반대 순서로 동작하고 그 효율은 비슷하다.