[자료 구조 #2] 배열(array)

기회는 준비된 자에게 온다 !

시작에 앞서… 시간 복잡도란?

시간 복잡도(Time complexity)는 자료 구조나 알고리즘이 얼마나 빠르고, 느린 지 측정하는 방법이다.

이렇다고 해서 실제로 실행에 소요된 시간(elasped time)을 측정하는 것이 아니다.

바로 얼마나 많은 단계(steps)가 있는 가로 측정된다.

따라서 같은 일을 하더라도 적은 단계의 프로그램이 효율적이라 할 수 있다.

여러 개의 동일한 박스를 붙여 놓았다고 생각하면 된다.

박스를 몇 개 이어 붙이는 지에 따라 박스의 총 길이가 정해져 있고, 안에 어떤 내용을 담는 지에 따라 배열의 자료형을 나타낸다.

배열을 선언할 때 메모리(통상적으로 RAM을 말함)에 배열의 길이와 어디서 시작하는 지 알려줘야 함.

즉, 박스의 총 길이를 알려줘야 한다.

배열은 0부터 인덱싱한다.

따라서 배열이 메모리에서 어디에 위치해있는 지 알고 있으면 접근 속도가 굉장히 빠르다.

읽기와 달리 시간이 조금 걸린다.

데이터를 읽을 때는 인덱스를 입력하면 되지만 검색은 다르다.

해당 값이 배열이 있는 지 없는 지도 모른다. 따라서 배열을 하나하나 다 뒤져야 하는 단점이 있다.

찾고자 하는 데이터가 배열의 제일 처음에 위치해 있으면 빨리 찾지만 최악의 경우는 제일 마지막 인덱스에 위치할 경우다.

=> 이 때 인덱스 0부터 순서대로 검색하는 것을 선형 탐색(Linear Search)라고 함

삽입의 경우 제일 최고의 경우는 배열 제일 마지막에 추가하는 것이다.

하지만 가운데 삽입하게 될 경우 삽입하려는 인덱스 기점 오른쪽 데이터를 모두 한 칸 밀어야한다.

심지어 배열의 제일 처음에 삽입할 경우 모든 데이터를 오른쪽으로 한 칸 밀어야 하니 최악의 경우라고 할 수 있다.

이 때 배열 크기를 초과하게 되면 새로운 배열을 만들고 값을 복사하는 등의 추가적인 절차로 인하여 속도가 저하될 수 있다.

배열의 요소를 이리저리 움직이는 동작 측면에서 삭제는 삽입과 비슷하다.

중간 요소나 제일 첫 요소를 삭제하게 될 경우 빈 공간을 메꾸기 위해 앞으로 한 칸 움직이는 동작을 수행해야 한다.

배열은 데이터를 읽기만 할 때는 굉장히 빠르다.

하지만 검색, 삽입, 삭제에 있어서 다소 프로그램이 느려질 수 있다.

따라서 앞으로 나올 자료구조는 이런 4종류 operation 상황에서 서로의 장단점을 잘 커버할 수 있는 자료 구조라고 생각해도 무방할 것이다.