자료구조 - 배열(Array)

 

이번 글에서는 자료구조의 기본 중의 기본인 배열에 대해서 살펴보고자 한다.

 

배열의 기본 개념

배열은 동일한 데이터 타입을 가진 요소들이 연속적으로 메모리에 저장되는 자료 구조이다. 각 요소(element)의 값(value)에는 인덱스(index)를 통해 접근할 수 있다. 배열의 인덱스는 일반적으로 0부터 시작한다.

 

 

메모리 관점에서 배열의 특징

메모리는 휘발성 메모리(ex. RAM-Random Access Memory)와 비휘발성 메모리(ex. 하드디스크)의 두 종류가 있다. 비휘발성 메모리는 말그대로 컴퓨터의 전원을 껐다가 다시 켜도 저장된 정보가 그대로 남아있다. 반면 휘발성 메모리는 컴퓨터의 전원을 껐다 키면 저장했던 정보가 날아가게 된다. 우리가 작성한 코드를 실행시켜서 프로그램이 돌아가고, 변수가 생성되면 변수가 가리키는 값은 모두 RAM에 저장된다.

이때, RAM에서 데이터를 읽어오는 것이 하드디스크에서 데이터를 가져오는 것보다 빠르다. 그 이유는 위 그림과 같이 RAM이 메모리 주소를 가진 셀들로 이루어져 있기 때문에, RAM의 메모리 주소만 알면 바로 그 셀에 저장된 값을 알 수 있기 때문이다. 즉 5번 주소의 값을 알고싶다면 순차적으로 1번 2번 3번.. 이렇게 찾아나가는 게 아닌, 바로 5번에 "임의 접근"해서 빠르게 데이터를 읽어 올 수 있다.

우리가 배열을 선언할 때 배열의 길이를 알려주면, 컴퓨터는 배열이 시작되는 위치와 배열이 어디서 끝나는 지 알 수 있게된다. 배열의 각 요소는 메모리에서 고정된 크기의 연속된 공간에 저장되며, 컴퓨터는 배열의 시작 주소와 인덱스를 이용해 원하는 요소에 빠르게 접근할 수 있게 된다.

 

 

배열의 데이터 처리 방법

1. 읽기 (Access)

배열의 인덱스를 알고 있으면 해당 요소에 상수 시간에 접근할 수 있다. 즉 배열의 몇번째에 위치한 값을 알고 싶다면 이때는 상수 시간에 해당 값에 접근할 수 있는 것이다. 

시간복잡도: O(1)

2. 검색 (Search)

정렬된 배열에서 이진 탐색을 사용하면 O(log n) 시간에 검색할 수 있지만, 일반적으로는 순차 탐색이 사용되므로 O(n)이 된다.

시간복잡도: O(n)

3. 삽입 (Insertion)

배열의 끝에 요소를 추가하는 것은 O(1)이지만, 특정 위치에 삽입할 때는 그 위치 이후의 모든 요소를 이동해야하므로 O(n)의 시간이 걸린다.

시간복잡도: O(n) (특정 위치에 삽입할 때), O(1) (끝에 삽입할 때)

4. 삭제 (Deletion)

배열에서 특정 요소를 삭제할 때, 삭제한 위치 이후의 모든 요소를 이동시켜야 하므로 O(n) 시간이 소요된다.

시간복잡도: O(n)

 

배열의 장점과 단점

장점

• 인덱스를 이용해서 크기가 아무리 큰 배열이라도 모든 요소에 빠르게 접근할 수 있다.
• 포인터 등과 같은 부가 정보 없이 데이터만 저장하기 때문에 효율적인 공간 사용이 가능하다.
• 구조가 간단하고 사용하기 쉽다.

단점

• 배열을 선언한 후 할당된 정적 메모리 때문에 크기를 변경할 수 없다.
• 배열의 특정 위치에 요소를 삽입 혹은 삭제하는 데에 비용이 많이 든다.
  • 배열은 항상 메모리가 순차적으로 이어져 있어야하기 때문에 요소들의 이동이 필요하다.
• 배열의 크기가 미리 정해지기 때문에 삽입과 삭제가 동적으로 발생하는 상황에서 적절한 배열의 크기를 미리 결정하는 것이 어렵다.
  • 이 때문에 오버플로우 혹은 저장공간의 낭비를 초래할 수 있다.

위와 같은 장단점으로 인해 배열은 아래와 같은 경우에 사용하기 적합하다.

• 순차적인 데이터를 저장하며 값보다 순서가 중요한 경우
• 다차원 데이터를 다룰 때, 특정 위치의 요소를 빠르게 읽어야하는 경우
• 데이터의 크기가 자주 변경되지 않는 경우
• 요소의 추가, 삭제가 빈번하지 않는 경우

 

정적 배열과 동적 배열

위에서 설명한 내용의 대부분은 정적 배열에 해당되는 내용이다. 하지만 많은 사람들이 사용하는 프로그래밍 언어 중 하나인 파이썬에서 사용하는 리스트는 동적 배열의 특징을 갖는다. 정적 배열과 동적 배열의 특징과 차이점을 알아보자.

 

정적 배열은 이때까지 설명했던 내용과 같이 고정된 크기를 가지는 배열로, 컴파일 시점에 메모리 크기가 결정된다. 배열을 생성할 때 크기를 명시해야하며, 생성된 후에는 그 크기를 변경할 수 없다.

 

반면 동적 배열은 크기를 유동적으로 조정할 수 있는 배열이다. 따라서 배열의 크기를 미리 지정할 필요가 없으며, 데이터가 추가될 때마다 배열의 크기가 자동으로 늘어난다.

 

동적 배열은 처음에는 작은 크기의 배열로 시작하고, 공간이 부족하면 자동으로 배열의 크기가 증가한다. 메모리가 가득 차면, 기존 배열을 복사하고 더 큰 메모리 공간을 할당한다. 때문에 추가적인 오버헤드가 발생할 수 있다.

 

오버헤드(Overhead)란?
시스템이 특정 작업을 수행하기 위해 필요한 추가적인 자원이나 비용. 즉, 실제로 하고자 하는 일 외에 부가적으로 발생하는 작업이나 부하를 의미한다.
동적 배열에서는 배열의 크기를 확장할 때, 메모리가 부족해지면 새로운 메모리 공간을 할당하고 기존 배열의 모든 데이터를 복사하는 과정이 발생한다. 이때 복사하는 작업 자체가 오버헤드이고, 성능에 영향을 미치게 된다.

 

정적 배열 vs 동적 배열

	정적 배열(Static Array)	동적 배열(Dynamic Array)
크기	고정	동적으로 조정
메모리 할당 시점	컴파일 시점	런타임 시점
메모리 할당 방식	연속적인 메모리 블록	초기에는 연속적, 크기 조정시 복사
메모리 낭비	크기가 고정되어 발생 가능	크기를 조정하여 최소
연산 오버헤드	거의 발생하지 않음	크기 조정 과정에서 발생 가능

 

---

참고

https://youtu.be/NFETSCJON2M?feature=shared

https://chanos.tistory.com/entry/자료구조-순차적-자료구조-배열과-리스트의-이해

https://yoongrammer.tistory.com/43

https://ongveloper.tistory.com/403