자료구조와 알고리즘 이해하기 글에서 알아본 것처럼 자료구조란 데이터를 효과적으로 다루기 위한 방법을 뜻한다.
서비스나 어플리케이션에서 필요한 데이터를 메모리에 어떻게 구조적으로 담아두고 관리할지 생각하고, 최종적으로 가장 효율적인 자료구조를 채택하여 데이터를 빠르게 읽고(read), 검색(search)하거나, 수정(modify), 추가(add) 및 삭제(delete)를 할 수 있다.
- 읽기(read)
- 검색하기(search)
- 수정하기(modify)
- 추가하기(add)
- 삭제하기(delete)
서비스나 어플리케이션에서 클라이언트에 데이터를 제공 또는 사용자에게 데이터를 보여주고, 수정할 때 효율적으로 일을 처리하기 위해선 기능에 적합한, 알맞는 자료구조를 쓰는 것이 중요하다. 어떤 자료구조를 쓰냐에 따라 사용자가 원하는 기능을 수행하는데 0.2초가 걸릴 수도 있고, 2초가 걸릴 수도 있기 때문이다.
자료구조 주안점
자료구조에 대해 특히 중점을 두어 살펴야 할 점들이 있다.
- Order: 데이터들이 순서가 보장 되어 있는지
- Unique: 중복된 데이터를 제거할 수 있는지
- Search: 검색 시 얼마나 효율적인지
- Modification: 원하는 기능에 따라 수정 시 얼마나 효율적인지
자료구조의 종류
자료구조는 다양한 종류가 있다.
- 배열(Array)
- 연결 리스트(Linked list)
- 이중 연결 리스트(Doubly linked list)
- 스택(Stack)
- 해시 테이블(Hash table)
이 중 가장 베이직한 자료구조인 배열(array)에 대해서 알아보자.
배열(Array)
배열의 구조는 메모리 관점에서 굉장히 읽기 좋은 구조를 갖고 있다.
프로그램이 돌아가고, 변수를 생성할 때의 데이터는 모두 RAM(Random Access Memory)에 저장이 된다. 이름에서의 랜덤(random)은 '무작위'가 아닌 '임의 접근'을 뜻한다. 즉 어느 위치에서든 똑같은 속도로 접근하여 읽고 쓸 수 있다는 의미이다.
RAM을 박스 그룹이라고 상상해보자. 그리고 박스들은 데이터를 보관할 수 있으며 각각의 박스 위치에 대한 식별자로 '메모리 주소(memory address)'라고 하자.
프로그램이 RAM 메모리에게 "메모리 주소 002로 가줘~"라고 한다면 해당 주소에 빠르게 접근할 수 있다. 말 그대로 랜덤하게 접근이 가능하기 때문이다. 메모리 주소가 005든, 030이든 상관이 없다.
그렇다면 배열은 어떨까? 배열을 만들 때는 컴퓨터에게 '이 배열이 얼마나 긴지를 설명해야 한다.
그 후 컴퓨터는 이 배열이 얼마나 긴지를 기억하고, 해당 길이만큼 박스를 나란히 위치하도록 해준다. 이렇게 메모리상에서 여러 값(데이터)을 연이어서 저장하고 사용할 수 있는 방법이 배열이다.
따라서 최대 길이를 설정해주어야 컴퓨터가 어디서 배열이 시작되고, 마지막 배열의 위치까지 기억을 하는데 자바스크립트의 경우 직접 길이를 설정할 필요가 없다. 자바스크립트가 알아서 핸들링 해주기 때문이다.(JS 고마워!)
대신 배열의 길이를 직접 핸들링 해야하는 C의 경우엔 자바스크립트보다 속도가 빠르다.
그래서 이렇게 하면 뭐가 좋고 나쁠까?
읽기(Read) 📖
컴퓨터는 배열의 시작점과 끝점을 기억한다. 시작점 0을 시작으로 끝점까지 인덱싱을 한다. 즉, 위치만 알면 배열의 데이터에 쉽게 접근할 수 있다.
따라서 배열에서 읽기는 굉장히 빠르다. 배열의 요소가 100개든 1000개든 상관없다. 컴퓨터는 배열의 시작점과 끝점을 알고 있고 있기때문에 빠르게 읽어낼 수 있다.
다시 말해 많은 데이터를 읽어야한다면 배열이 좋은 자료구조가 될 수 있다.
이것은 RAM의 랜덤 엑세스덕분이다. 인덱스의 요소를 읽어내는 속도가 동일하기 때문이다.
검색하기(Search) 🔍
RAM은 위에서도 설명 했듯이 메모리 주소엔 빠르게 접근할 순 있지만 어떤 데이터가 들어 있는지는 알 수가 없다. 즉, 랜덤 액세스로 메모리 주소에 빠르게 접근은 가능하지만 박스 안의 값은 모르는 것이다.
따라서 배열의 요소를 검색할 때는 박스를 하나하나 다 열어보고 해당 값이 나올 때까지 반복을 해야한다.
내가 필요한 데이터를 찾으려면 배열의 요소를 하나하나 열어보고 맞는지 체크하는 과정을 거쳐야 한다.
그래서 배열은 그냥 읽는 것보다 시간이 더 오래 걸린다. 내가 찾는 데이터가 최악의 경우엔 인덱스의 맨 끝에 있을 수도 있다. 더 최악의 경우엔 해당 데이터가 배열 안에 없을 수도 있는 것이다.
이런걸 바로 선형 검색(linear search)라고 한다. 찾고자 하는 값을 맨 앞에서부터 끝까지 순차적으로 검색하기 때문이다.
결국 배열에서의 검색은 생각보다 빠르지 않다는 것이다. 하지만 우리의 든든한 선배 개발자들이 검색을 더 빠르게 할 수 있는 알고리즘을 만들어냈다. 같은 자료구조에서도 어떤 알고리즘을 쓰냐에 따라 속도 차이가 난다는 사실이 참 흥미롭다.
추가하기(Add) 또는 삽입하기(Insert) 📥
배열을 만들 때는 메모리 공간을 미리 확보 해야한다. "이건 4개의 아이템 길이야"처럼 말해주어야 한다.
먼저 5개의 길이(공간)을 확보하고 공간의 걱정 없이 4개의 요소가 있다고 가정해보자. 그 후 4가지의 상황을 통해 요소를 추가해보자.
1. 데이터를 배열의 맨 끝에 추가하는 경우
최고의 상황이라고 할 수 있다. 컴퓨터는 배열의 시작점과 끝점을 기억하기 때문에 그냥 끝점에 요소를 추가하면 된다. 가장 빠른 속도의 작업이다.
2. 데이터를 배열의 중간에 추가하는 경우
데이터를 배열의 중간에 추가하고 싶을 때는 어떻게 해야할까? 먼저 공간을 확보하기 위해 추가하려는 위치의 오른쪽 요소들을 끝쪽으로 옮겨야 한다. 보통 속도의 작업이다.
3. 데이터를 배열의 맨 앞에 추가하는 경우
위의 2가지 상황 중 가장 느린 속도의 작업이다. 요소 하나를 추가하기 위해 배열의 모든 요소들을 옮겨야 한다.
4. 할당한 공간이 꽉 찼는데 데이터를 추가하는 경우
배열은 정해진 길이가 있고 만들 때 해당 공간을 미리 할당을 하게 되어있다. 위와 같은 경우엔 더 큰 배열을 만들어서 이전 배열을 복사하고 그 이후 새로운 데이터를 추가해야 한다. 따라서 4번의 상황이 제일 오래 걸리는 작업이다.
결국 배열은 '어디에' 데이터를 추가할 것인가에 따라 속도 차이가 나게 된다.
삭제하기(Delete) 📭
삭제는 배열에 데이터를 추가하는 것과 비슷하다. 배열의 요소들을 이리저리 움직여야 한다. 마찬가지로 배열의 맨 끝 데이터를 삭제하고 싶다면 그냥 삭제하면 된다. 하지만 배열의 중간 또는 첫 번째의 데이터를 삭제하게 된다면? 삭제된 공간의 공백을 채우기 위해 요소들이 한칸씩 움직여야 한다.
앞서 설명한 배열에서 4~5개의 요소만 있다면 그렇게 크게 걱정할 필요는 없다. 하지만 몇천개 또는 몇만개의 데이터가 있는 상황이라면 속도에 있어 차이가 클 수 밖에 없다.
따라서 배열로 추가 및 삭제를 하고 싶은 상황이라면 배열의 맨 끝에서 작업하는걸 우선으로 해야한다. 그렇지 않은 상황은 다른 자료구조를 고려해보자.
마무리
배열은 읽기(read)에선 굉장히 빠른 속도를 자랑한다. 하지만 검색, 추가 및 삭제에서는 약한 모습을 보인다.
느린 검색 속도를 개선하기 위한 알고리즘이 존재하고 자료구조와 알고리즘은 밀접한 관계가 있다. 배열에서 데이터를 추가 및 삭제할 때는 배열의 맨 끝에서 작업하는걸 우선으로 생각하자.
자바스크립트의 경우 배열의 맨 앞에 새로운 요소를 추가하거나, 삭제 할 수 있는 unshift(), shift() 메서드가 있다. 이제는 해당 메서드가 느리고, 성능에 좋지 않다는 것을 알게 되었으니 사용하는 것을 최대한 피하자.
참고
'Algorithm > 자료구조와 알고리즘' 카테고리의 다른 글
| 자료구조 더 알아보기 - 해시 테이블 (0) | 2021.11.10 |
|---|---|
| 자료구조와 알고리즘 이해하기 (0) | 2021.11.06 |