배열의 자료구조 기초

그동안 자료구조에 대해 겉핡기씩으로만 배워서 쉽게 까먹고 그랬는데 유튜버 니꼴라스 선생님의 강의를 들으니 배열은 컴퓨터에 이렇게 저장이 되고 이래서 읽기가 빠르고 검색이 느리구나를 쉽게 이해할 수 있게 되었다.

오늘은 니꼴라스 선생님의 유튜브를 보고 배열에 대한 자료구조를 정리해보고 이해하는 시간을 갖겠다.

니꼴라스의 영상을 참고하실 분은 밑에 링크를 클릭해주세요!
https://youtube.com/watch?v=NFETSCJON2M&feature=share

1. 시간복잡도

먼저 배열에 들어가기 전에 시간복잡도에 대해서 알 필요가 있다. 시간복잡도란 데이터의 오퍼레이션(작업) 혹은 알고리즘이 얼마나 빠르고 느린지 측정하는 방법인데, 이것은 실제 시간을 측정하는 것이 아닌 "얼마나 많은 단계가 있는가" 로 측정하는 것이다. (초/분 측정 X) 즉, 어떤 작업을 하는데 5개 단계와 20개 단계가 있다면 5단계를 요구하는 작업이 20단계를 요구하는 작업보다 더 훌륭한 알고리즘이 되는 것을 의미한다.

5단계를 요구하는 작업이 20단계를 요구하는 작업보다 더 훌륭한 알고리즘이 된다.

2. 메모리 관점에서 배열(Array)은 어떻게 보일까

메모리는 일단 2가지로 나누어진다. 휘발성 메모리와 비휘발성 메모리로 나누어지는데, 보통 비휘발성 메모리는 하드 드라이브와 같은 것이라고 볼 수 있다. 하드 드라이브는 컴퓨터의 전원을 끄고 다시 켜도 메모리는 휘발 되지 않는다. 반대로 휘발성 메모리는 컴퓨터의 전원을 끄면 메모리가 휘발이 되는데 대표적으로 RAM이 있다. RAM은 Random Access Memory 의 줄임말이며, RAM은 하드 드라이브에서 데이터를 읽는 것보다 빠르다. 그 이유는 이름에서 알 수 있듯이 데이터 접속을 랜덤으로 할 수 있기 때문이다. 데이터의 접속을 랜덤으로 한다는게 무슨 뜻일까? RAM을 아래의 그림과 같이 하나의 박스라고 생각해보자. 이 박스는 여러 개의 데이터를 저장할 수 있는 공간이 있다.

프로그램이 RAM에게 "Memory Address 2번으로 가주세요" 라고 명령을 한다면 RAM은 002번으로 바로 빠르게 접속할 수 있다. 왜냐하면 랜덤하게 접속이 가능하기 때문이다. "Memory Address 5번으로 가주세요" 도 마찬가지로 1번, 2번, 3번...이렇게 순차적으로 가는 것이 아닌 바로 메모리 005번으로 랜덤으로 접속 할 수 있기 때문에 RAM은 데이터를 읽는 속도가 빠른 편이다.

그렇다면 배열은 메모리에서 어떤 모습일지 살펴보자. 보통 배열을 만들때 우리는 컴퓨터에게 배열의 길이를 먼저 할당하여야 한다. 예를 들어, 5개의 길이의 배열을 할당하고 싶으면 길이가 5인 배열이라고 먼저 명시를 해주어야 한다.

int a[5]

 

배열을 선언하기 위해서는 먼저 길이를 할당해주어야 한다.

컴퓨터는 이 배열의 최대 길이가 어느 정도인지를 알고 어디서 시작하는지를 알고 있다. 단 JS, Python의 경우 배열의 길이를 직접 할당할 필요가 없다. JS와 Python은 개발자들이 모르게 컴퓨터가 알아서 길이를 할당하는 핸들링해주는 기능을 갖추고 있기 때문이다. 따라서 JS와 Python는 컴퓨터가 핸들링해주는 기능 때문에 직접 배열의 길이를 할당해주는 C보다 속도는 느릴 수 있다.

< 작업1 : 배열의 Reading >

배열은 0부터 인덱싱을 한다. 즉, 위치를 알면 배열의 데이터에 접속을 빠르게 할 수 있다. 예를 들어 4개의 요소가 있는 배열이 있다고 해보자. 순서대로 파스타, 아이스크림, 피자, 감자가 있다. 이때 피자의 값을 얻고 싶다면 컴퓨터에게 인덱스 2번의 값을 달라고 하면 된다. (0부터 인덱싱을 하기 때문에 피자는 2번의 값이 되는 것이다.)

따라서 배열에서 데이터를 읽어내는건 빠르다는 것을 알 수 있다. 컴퓨터는 배열이 어디서 시작하는지를 알고 있기 때문이다. (앞에서 컴퓨터는 배열의 최대 길이를 알고 어디서 시작하고 있는지를 안다고 하였다.)

컴퓨터는 배열의 시작점을 알고 있기 때문에 데이터 리딩이 빠르다. 예를 들어, 빨간색 배열의 시작점은 008임을 기억하고 있다.

많은 자료를 읽어야 할 때는 배열이 최고임을 알 수 있다. 모두 Ramdom Access 덕분이다. 다시 정리해보면 노란색 배열의 세번째 값을 읽고 싶을 때, 노란색 배열의 시작점을 컴퓨터는 알고 있고 인덱스 2번의 값을 찾으라고 하면 빠르게 2번의 값을 반환해준다.

< 작업2 : 배열의 Searching >

앞서서 배열의 읽기 기능에 대해서 알아보았다. 이제 배열의 검색 기능에 대해서 알아보자. 배열의 검색은 읽기와 비슷하다고 생각할 수 있는데 다른 기능이다. 배열의 읽기 기능은 그냥 값(피자)을 얻으면 되지만 검색할 때는 다르다. 해당 값에 피자가 배열에 있는지 없는지를 모를 때는 검색을 하여야 한다. 따라서 하나하나를 다 뒤져야 한다.

피자 값이 어디 있는지를 모를 때는 하나하나 뒤져보는 검색을 하여야 한다.

피자 값을 찾기 위해서 하나하나 뒤져봐야 하고 이때 피자값이 맞는지를 체크하는 과정도 하나하나 해야한다. 인덱스 0번을 열어보고 피자가 아니네, 인덱스 1번을 열어보고 피자가 아니네, 인덱스 2번을 열어보고 피자가 맞네! 이 과정을 거쳐야 한다는 것이다. 만약 피자가 마지막 인덱스에 존재한다면 앞에서부터 모든 인덱스를 열어보고 피자를 찾을 수 있기 때문에 시간은 오래 걸린다. 또한 피자가 배열에 없는 경우 배열의 인덱스를 모두 열어보고 없음을 판단하므로 배열의 검색기능은 꽤나 비효율적임을 알 수 있다. 이런 것을 참고로 선형 검색 "Linear Search" 라고 한다. (=0부터 모든 것을 찾는 것)

< 작업3 : 배열의 Insert (Add) >

먼저 배열을 만들 때에는 메모리 공간을 미리 확보하여야 함을 알았다. 즉 5개의 길이의 배열이다 라고 선언해주어야 한다. 아래의 예시처럼 5개의 길이의 배열을 선언하고 파스타, 아이스크림, 피자, 감자를 넣으면 하나의 빈공간이 남는다. 이때 토마토를 마지막에 있는 빈공간에 추가하고 싶다면 컴퓨터는 배열이 어디서 시작하고 얼마나 긴지를 기억하므로 별다른 무리 없이 토마토가 마지막에 삽입된다.

하지만 중간에 토마토 값을 넣을 때 배열은 문제가 발생한다. 감자를 먼저 오른쪽으로 한 칸 이동하고, 그 다음 피자가 오른쪽으로 한 칸 이동을 해야 토마토 값을 추가할 공간이 생긴다.

또한 첫 자리에 토마토 값을 추가하고 싶은 경우 감자, 피자, 아이스크림, 파스타 순으로 모두 하나하나씩 오른쪽으로 이동해야 첫 자리에 빈공간이 생겨서 토마토를 추가할 수 있다. 만약 배열의 크기가 100000개의 길이만큼 엄청 크다면 이 경우는 매우 비효율적으로 될 것이다.

공간이 꽉 차서 빈공간이 없는 경우 데이터를 삽입할 때에도 문제는 발생한다. 처음에 5개의 배열의 길이를 먼저 할당했는데 6개의 길이, 혹은 7개의 길이의 배열을 써야한다면? 더 큰 배열을 만들어서 이전 배열을 복사하고 그 다음에 새로 김치라는 값을 추가해야한다. 따라서 요소를 복사하고 등등... 빈공간이 없는 상태에서 배열의 삽입은 꽤나 오랜 시간이 걸림을 알 수 있다.

< 작업4 : 배열의 Delete >

삭제는 배열에 뭔가를 추가하는 것과 비슷하다. 즉 배열을 이리저리 움직이는 것은 동일하다.

이러한 배열이 있을 때, 마지막값 김치를 삭제하고 싶다면 이 경우는 쉽다. 왜냐하면 배열이 어디서 시작하고 얼마나 긴지 기억하기 때문에 마지막 값을 삭제하는 것은 별다른 무리 없이 진행된다.

문제는 배열의 중간 요소를 삭제할 때이다. 중간에 있는 값 토마토를 삭제하게 되면 가운데에 공백이 생기게 된다. 배열에 공백이 있으면 안되니까 그 공백을 채우기 위해서는 모든 배열의 값들이 앞으로 움직이게 된다.

또한 첫번째 요소를 삭제해야 하는 경우 그 공간을 메꾸기 위해서 모든 요소를 한 칸씩 앞으로 움직여야 한다.
이렇게 배열에서 오락가락 움직이는 것은 배열의 길이가 엄청나게 클 경우 조심하여야 한다.

▶ 정리

즉, 배열은 Random Access의 기능으로 데이터를 읽을 때는 정말 빠르지만, 검색하고 추가하고 삭제해야 할때 느리기 때문에 배열에서 추가하고 삭제하고 싶을 때에는 배열의 맨 끝에서 작업하는 것을 추천한다. 중간 혹은 맨 처음 값을 움직이게 되면 그때는 느려지므로 그때는 추천하지 않는 방법이다. 다음 시간에는 어느 위치에서 검색, 추가, 삭제해도 속도가 빠른 데이터 구조에 대해서 알아보겠다.