자바스크립트의 자료구조

*Udemy의 "Master the Coding Interview : Data Structures + Algorithms" 강의에서 학습한 내용을 정리한 포스팅입니다.

*자바스크립트를 배우는 단계라 오류가 있을 수 있습니다. 틀린 내용은 댓글로 말씀해주시면 수정하겠습니다. 감사합니다. :)

---

1. 자료 구조? 알고리즘?

자료 구조란, 말 그대로 정보(자료)를 저장하는 형태를 의미한다.

알고리즘이란, 자료 구조의 정보를 사용하기 위한 일련의 과정을 의미한다.

 

각각의 자료 구조는 형태가 다르고, 따라서 각각의 장단점도 다르다. 예를 들어 옷장, 서랍, 파일철 모두 무언가를 담는다는 의미에서 모두 같은 container이지만, 각각의 용도와 장단점이 모두 다른 것과 유사하다.

자료 구조의 종류는 굉장히 많다. 하지만 모든 자료 구조형을 알 필요는 없으며, 5-6개 정도의 아주 중요하고 자주 쓰이는 자료 구조형만 알면 된다. 

 

자료 구조를 이해한다는 것은 아래 2개를 할 줄 안다는 것이다.

 

1. 자료 구조를 만들기 위해 어떻게 코드를 작성할 것인가?(How to build Data Structure?)

2. 만든 자료 구조를 어떻게 사용할 것인가?(How to use it?) 

 

여기서 2번째, 어떻게 사용할 것인가에 집중해서 공부하면 된다.

 

2. 컴퓨터가 데이터를 저장하는 방법

컴퓨터에 데이터를 저장하는 방법은 크게 2가지가 있다. 첫번째는 각 컴퓨터의 저장공간(ssd, hdd 등)에 저장하는 것, 두번재는 RAM(Random Access Memory)에 저장하는 것이다. 컴퓨터가 코드를 읽고 실행할 때 변수, 함수, 자료구조 등이 저장되는 공간은 RAM이다. 컴퓨터는 왜 코드의 내용을 저장공간이 아닌 RAM에 저장할까?

 

저장 공간은 컴퓨터를 껐다가 켜도 이용자가 정보를 삭제하기 전까지는 영구적으로 해당 공간에 데이터가 저장되어 있다는 장점이 있다. 하지만 결정적으로 저장 공간에 접근해서 정보를 가져오는 것은 속도가 느리다.

RAM의 경우 컴퓨터를 껐다 키거나, 실행 중인 프로그램을 종료할 경우 저장된 정보가 삭제된다. 하지만 정보를 가져오는 속도는 저장 공간에 비해서 월등하게 빠르다. 그렇기 때문에 빠르게 실행하기 위해 코드의 실행에 필요한 정보들을 RAM에 저장하는 것이다.

 

CPU와 RAM

 

RAM은 쉽게 생각하면 각 선반마다 넘버링이 된 선반들이 모여 있는 공간이다. 해당 넘버링이 바로 그 선반의 주소가 된다. 그리고 각 선반에는 0과 1로 이루어진 8자리 숫자가 보관된다. 이 때 0과 1 숫자 하나 하나를 비트(bit)라고 한다. 비트는 작은 전자 스위치여서 켰다 껐다를 할 수 있다. 켜지면 1, 꺼지면 0이다. 8개의 비트가 모여서 1개의 바이트를 이룬다. 결론적으로 각 선반(쉘)은 1개의 바이트를 저장하는 공간이다.

 

CPU는 메모리 컨트롤러를 내장하고 있다. 메모리 컨트롤러는 RAM의 모든 쉘(선반)과 직접적으로 연결되어 있어, RAM에 데이터를 저장하거나 가져오거나 삭제하는 등의 작업을 수행한다. 메모리 컨트롤러가 RAM의 쉘에 접근할 때, 0번째 선반부터 1억번째 선반까지 모두 접근이 가능하며, 1억번째 선반에 접근할 경우 0번째부터 1억번째까지 차례차례 내려가서 접근하는 것이 아니라, 직접적으로 바로 1억번째 선반에 접근이 가능하다. 그렇기 때문에 메모리 컨트롤러를 통해서 RAM과 데이터를 주고 받는 과정을 아주 빠르게 할 수 있다.

 

하지만 아무리 빠르게 왔다갔다 하더라도, RAM 내의 쉘 간의 거리가 짧을수록 속도는 조금이라도 더 빨라진다. 예를 들어 0번째 선반과 1억번째 선반에 접근하는 것보다, 0번째 선반과 1번째 선반에 접근하는 것이 더 빠르다는 것이다.

사실 나도 완벽하게 이해는 안되지만,, 이렇게 이해해보았다.

예를 들어 메모리 컨트롤러가 도서관의 사서이고, 각 쉘이 가져와야 하는 책의 주소라고 하면, 사서가 주소 z에 있는 책을 가져오기 위해서 a부터 z까지 쭉 훑으면서 갈 필요는 당연히 없다. 사서가 바로 z에 가서 책을 가져올 수 있는 것은 맞다.

하지만 만약에 2개의 책을 가져와야 되는데 a와 b에 있으면, a에서 가져오고 바로 옆에 있는 책장 b에서 책을 가져올 수 있다. 반면 a와 z에 있으면 a에서 책을 챙긴 다음에 책장 z까지 이동해서 책을 가져와야 되니까..

그런 의미에서 메모리 컨트롤러와 모든 쉘(선반)은 직접적으로 연결되어 있기는 하지만, 가져와야 하는 데이터 사이의 거리가 짧을 수록 속도가 빠른 것이 아닐까..... 하고 생각해 보았다....

 

참고로 CPU에는 LRU 캐시라는 것도 존재한다. 이는 CPU가 내장한 아주 작은 메모리 공간으로, 가장 최근에 사용한 메모리들을 복사해서 보관하는 장소이다.(위 사진 속에서 cpu 옆에 cache라고 쓰여 있는 공간이다.)

---

 

비트 수에 따른 정보 저장량의 차이

 

모든 종류의 데이터 타입은 할당된 비트 수가 정해져 있으며, 정보를 저장하면 RAM 일정 부분의 저장공간을 해당 데이터를 위해서 내어준다. 그리고 해당 데이터를 이용할 때 RAM에 정보를 가져와서 읽는 것이다.

 

자료 구조는 이러한 데이터 하나하나들이 모여 집합을 이룬 형태이다. 위에서 공부한 것으로 미루어 볼 때, 각 데이터들을 RAM에 어떻게 정렬시킬 것인지, 어떤 자료구조는 RAM에서 서로 가깝게 위치하도록 하고, 또 어떤 자료구조는 떨어지게 설정할 것인지, 그리고 그 데이터들과 CPU가 어떻게 상호작용하게 할 것인지를 자료 구조와 알고리즘을 통해서 익힐 수 있다.

 

이 공부의 최종 목표는 CPU가 정보를 가져올 때 해야 하는 작업의 수와 거리를 최소화하여 가장 빠르고 효율적으로 동작하도록 하는 것이다!