배열: 기초 자료 구조

배열이란?

• 배열은 컴퓨터 과학에서 기초적인 자료구조 중 하나이다.
• 배열은 단순히 데이터 원소들의 리스트다.
• 배열의 크기는 배열의 데이터 원소가 얼마나 들어 있는지 알려준다.
  
  위 사진은 크기가 5인 문자열 배열이다.

자료 구조 연산이란?

자료구조의 성능을 알려면 코드가 자료 구조와 일반적으로 어떻게 상호작용하는지 분석해야 한다.
대부분의 자료구조는 네 가지 방버을 사용하며, 이를 연산이라 부른다. 연산은 다음과 같다.

• 읽기: 읽기는 자료구조 내 특정 위치를 찾아보는 것이다. 배열에서는 특정 인덱스의 값을 찾아보는 것을 뜻한다. 가령 인덱스 2에 들어 있는 물건을 찾는 게 배열 읽기의 예다.
• 검색: 검색은 자료 구조 내에서 특정 값을 찾는 것이다. 배열에서는 특정 값이 배열에 들어 있는지, 만약 그렇다면 어떤 인덱스에 있는지 알아보는 것을 뜻한다. 예를 들어 "dates" 목록에 있는지, 어떤 인덱스에 있는지 알아보는 게 배열 검색이다.
• 삽입: 삽입은 자료 구조에 새로운 값을 추가하는 것이다. 배열이라면 배열 내에 슬롯을 더 만들어 새 값을 추가하는 것을 뜻한다.
• 삭제: 삭제는 자료 구조에서 값을 제거하는 것이다. 배열에서는 배열의 값 중 하나를 제거하는 것을 뜻한다.

배열 자료 구조 연산 속도 측정

연산의 속도 측정은 연산의 시간 복잡도 측정으로 알려져 있다. 시간 복잡도 측정 = 효율성 = 성능 이라고 표현 할 수 있다.

• 배열의 크가를 할당 하는 방법
  
  컴퓨터이 메모리는 위 그림과 같이 셀로 구성된 거대한 컬렉션이라 할 수 있다. 어떤 셀은 비어 있고, 어떤 셀에는 데이터가 들어 있다.
  이 때 프로그램에서 배열을 선언하게 된다면, 프로그램이 쓸 수 있는 연속된 빈 셀들의 집합을 할당한다.
  예를 들어 원소 다섯 개를 넣을 배열을 생성하게 된다면,
  

컴퓨터는 한 줄애서 5개의 빈 셀 그룹을 찾아 사용자가 사용할 배열을 지정한다.
컴퓨터 메모리 내에 각 셀에는 특정 주소가 있다. 간단한 수로 표시한다는 점만 제외하면 거리 주소는 앞 셀의 주소에서 1씩 증가한다.

• 읽기

1. 컴퓨터는 모든 메모리 주소에 한 번에 갈 수 있다.
2. 배열을 할 당 할 때 어떤 메모리 주소에서 시작하는지도 기록해 둔다. 그렇기에 배열의 첫 번째 원소를 찾으라고 요청하면 적적한 메리 주소로 가서 바로 찾는다.
   예로 배열의 시작 주소가 1010일 때 인덱스 3은 1010 + 3 = 1013이다.
   즉 배열의 읽기 시간 측정도는 1이다.

• 검색

1. 배열에서 원하는 값을 찾기 위해서는 각 셀을 하나씩 조사하는 방법밖에 없다.
2. 컴퓨터는 모든 메모리 주소에 한 번에 접근하지만 각 메모리 주소에 어떤 값이 있는지 바로 알지 못한다.
   따라서 특정 배열에서 원하는 값을 찾기 위해서는 배열의 시작 주소부터 배열의 끝 주소까지 이동을 하며 값을 확인해야 한다. 만약 크기가 5인 배열 인덱스 4에 "mellon"이 있다면 이 값을 찾기 위해서 5번 탐색을 해야한다.
   즉 배열의 검색 시간 측정도는 최대 N이다

• 삽입

1. 컴퓨터는 배열의 시작되는 메모리 주소를 알고 있으며, 배열을 할당 할 때 크기를 기록한다. 따라서 배열의 맨 마지막에 새 값을 삽입 할 경우 한 단계면 된다.
   

2. 배열의 크기인 N-1 이하의 인덱스의 새로운 원소를 삽일 할 경우, 원소를 삽입 할 인덱스를 비워야 한다.
   

마지막 원소를 차례대로 옮기는 과정을 거치고 해당 값을 삽입 할 수 있다.
만약 인덱스 0에 값을 삽입하게 된다면 N+1번의 반복이 필요하다.
따라서 시간 측정도는 N + 1 이다.

• 삭제

1. 크기가 5인 배열에서 인덱스 0을 삭제한다. 그 이후의 원소는 왼쪽으로 한칸씩 이동해야한다.

그렇기에 마지막 인덱스를 삭제 할 경우 한 단계면 되지만, 인덱스 0을 삭제할 경우 값을 삭제하고 배열의 원소를 이동시키는 과정 때문에 시간 측정도는 N이다.
즉 삭제의 최대 시간 측정도는 N이다

집합이란?

집합은 중복 값을 허용하지 않는 자료 구조다.

• 읽기
  중복을 허용하지 않지만, 배열 기반 집합의 값들은 단순 리스트로 배열과 거의 비슷하다. 그렇기에 컴퓨터가 메모리를 바로 바로 읽을 수 있다. 따라서 시간 측정도는 1이다.
• 검색
  집합의 검색 또한 배열의 검색과 아무런 차이가 없다. 즉 시간 측정도는 N이다.
• 삽입
  집한은 중복을 허용하지 않는다. 따라서 값을 삽입하기 전에 해당하는 값이 이미 배열에 존재하는지 확인하는 과정을 거쳐야한다. 그렇기에 데이터를 검색하는데 N, 데이터를 삽입하는데 N + 1,
  즉 최대 시간 측정도는 2N + 1이다.
• 삭제
  배열과 동일한 과정을 거친다. 따라서 시간 측정도는 N이다.