배열 Array

배열은 여러 개의 값을 순차적으로 나열한 자료구조이다.

 

프로그래밍에서 배열은 사용 빈도가 매우 높은 기본적인 자료구조이다.

 

특징

위에서 기술한 것처럼 배열은 여러 개의 값을 저장하는 자료구조이다. 배열은 여러개의 동일한 타입의 값을 동일한 크기의 연속된 메모리 공간에 순차적으로 값을 저장하는 데이터 모음이다.

 

배열을 구성하는 요소 값을 배열에 저장하는데, 이때 요소를 저장하는 위치 번호를 나타내는 숫자를 인덱스라 한다.

인덱스는 0부터 배열 전체 요소의 수 - 1 까지 존재한다.

 

 

위의 사진에서 int로 타입을 선언했다면 int를 제외한 다른 타입의 값은 해당 배열에 저장할 수 없다.

 

배열의 표현

C언어의 배열을 살펴보자

int array [10] = { 35, 33, 11, 12, 52, 63, 13, 64, 38, 1 }

 

위의 코드에서 타입을 선언(int), 배열명(array), 배열 크기( [10] ), 배열 요소( {...} )로 배열을 선언해준다.

내가 주로 사용하는 Javascript는 배열이 객체로 구현되있으므로 패스....

 

위의 코드에서는 각 요소가 순서대로 0번 부터 9번까지 인덱스 번호를 갖는다. 이는 순서대로 저장되는 배열의 특징을 알 수 있다.

 

또한 배열에는 하나의 타입의 값만 저장할 수 있으므로 위의 코드에서 int 값만 저장하는 모습이다.

 

배열의 요소 참조의 경우 대괄호를 이용해 인덱싱을 하여 값을 참조할 수 있다.

array[0]; // 35

 

 

배열의 시간 복잡도

구분	평균	최악
읽기	O(1)	O(1)
삽입	O(n)	O(n)
삭제	O(n)	O(n)
탐색	O(n)	O(n)

 

위의 표에서 알 수 있듯이 배열에 저장되어 있는 요소에 대한 참조는 O(1)로 빠르게 참조할 수 있지만, 요소의 수정, 검색 동작에서는 O(n)으로 느린 모습을 알 수 있다.

 

 

왜 배열을 사용하는가?

배열은 연속된 메모리 블록에 저장되어 인덱스를 이용해 빠르게 요소를 참조할 수 있으며, 간단한 구조를 갖고 있어 구현에 용이성이 있으며, 마지막으로 고정된 메모리 크기를 갖기에 메모리 관리에 용이한 특징으로 인해 많은 코드에서 사용한다.

 

사실 필자가 가장 좋은 방법이라 생각하는 방법은 알고리즘을 잘 적용시키는 것이다. 마치 DP 알고리즘의 메모이제이션을 이용해 시간 복잡도를 줄이는 것과 같은 방법을 사용하는 방법이 좋은것 같다.