Javascript를 활용해 '자료구조'라고 부르는 데이터 형태를 구현하는 것은 중요합니다.
Computer Science(CS)를 공부하면서 필연적으로 만나게 되는 영역이 있는데, 이를 'CS 기초'라고 불립니다.
기초적이고 트렌드를 이해하기 위해 필수적으로 알고 있어야 하는 영역입니다.
CS 기초는 대표적으로 다음의 내용이 있습니다.
Data structure - 자료구조
Algorithm - 알고리즘
Computer network - 컴퓨터 네트워크
Computer architecture - 컴퓨터 구조
Operating system - 운영체제
Database - 데이터 베이스
더 많은 영역들이 있지만 이 영역들은 다양한 분야에서 공통적으로 통용되는 영역입니다.
따라서 보편적으로 모든 내용을 학습하고 익히는 것이 중요합니다.
그 중, 자료구조에 대해서 공부하도록 하겠습니다.
자료구조(Data Structure)
자료구조는 하나 이상의 데이터를 구성하기 위한 구조를 나타냅니다.
그 종류는 다양하지만 대표적으로 6가지가 존재합니다.
Array - 배열
List - 리스트
Queue - 큐
Stack - 스택
Graph - 그래프
Tree - 트리
** 보편적으로 6가지로 분류되지만 크게 보면 배열과 리스트를 이용해 구현하는 자료들의 구조라고 볼 수 있습니다.
큐와 스택, 그래프, 트리는 배열을 통해 구현되거나 리스트를 통해 구현될 수도 있기 때문입니다.
☞ 자료구조가 중요한 이유?
자료구조는 적은 수의 데이터를 관리하기 위해 만들어진 것이 아닙니다.
1개의 데이터를 처리하는데 1초가 걸리는 크기 1의 구조가 있다면, 이 구조를 이용해 1000개의 데이터를 처리할 땐 1000의 크기와 1000초가 필요합니다.
이때 자료구조는 1개의 데이터를 처리하는 시간과 크기를 줄여 데이터를 처리하는데 적은 크기와 시간을 필요하게 하는 역할을 합니다.
즉, 프로그램 내에서 자료를 가장 효율적으로 처리하고 그 과정을 통해 보다 성능 좋은 프로그램을 만들기 위해서 중요한 것입니다.
☞ 논리적인 생각의 구현
자료구조는 논리적인 형태를 말합니다.
이것은 구현자가 '어떻게 의도하느냐'에 따라 형태가 변한다는 것을 의미합니다.
모든 데이터의 형태는 논리적인 구조이고, 구현자가 직접 구현하고 해당 자료구조의 형태로 동작하게 만들어야 합니다.
해서 구현자는 의도와 명확하게 부합하는 자료구조를 만들 수 있어야 합니다.
선형 구조와 비선형 구조
일반적으로 자료구조를 구분할 때 선형과 비선형 구조로 구분합니다.
각 선의 형태를 띠는 것과 그렇지 않은 것으로 풀어 말할 수 있기 때문입니다.
선형 구조 - 배열, 리스트, 큐, 스택
비선형 구조 - 그래프, 트리
Array(배열)
배열은 대부분의 언어에서 그 형태를 제공하기에 다음과 같은 선언만으로 구현할 수 있습니다.
let colors = ['빨강','노랑','파랑'];
colors[0];//빨강
이 배열은 '빨강','노랑','파랑'이라는 문자를 저장하고 있는 크기 3의 colors의 배열을 의미합니다.
이처럼 하나의 배열은 특정 데이터의 집합을 의미합니다.
이 배열은 문자열을 저장하고 있기에 문자열 배열이라고 말하기도 합니다.
각각의 문자열에는 index(인덱스)라는 개념이 존재합니다. 인덱스는 0에서 부터 시작해 각 데이터의 위치를 의미합니다.
☞ 왜 index는 0부터 시작하나요?
= 모든 데이터가 0부터 시작하기 때문입니다. 데이터를 최대한 효율적으로 사용하기 위해 고안된 구조입니다.
또한 Javascript의 배열은 리스트 형태로 제공됩니다. 따라서 List의 특징을 아는 것도 중요합니다.
Array 형태의 List를 Array라고 하며 배열과의 차이는 '데이터에 대한 인덱스 종속 여부'라는 것도 중요합니다.
배열은 보편적으로 동일한 형태의 여러 데이터를 저장하기 위해 사용합니다.
배열의 한계
배열은 한번 고정적으로 선언된 배열은 선언되면 크기를 변경하기 어렵습니다.
따라서 배열은 정해진 크기의 데이터를 저장할 때 사용하면 유용합니다.
Javascript등의 언어에서는 배열의 크기를 변경하는 문법들이 존재하고, 변경할 수 있습니다.
하지만 일반적인 관점에서 배열을 관리할 때 크기를 변경하는 것은 까다롭다고 합니다.
그래서 배열은 크기가 정해진 구조에서 사용하는 것이 좋습니다.
또한 배열은 다수의 데이터를 그룹핑해서 효율적으로 관리한 후 각각을 인덱스로 구분합니다.
따라서 인덱스를 알고 있다면 해당 자료를 찾기 쉽습니다.
다만, 인덱스를 이용해 데이터를 가져오기 위해서는 인덱스가 데이터에 종속적으로 연결되어 있어야 합니다.
= 이는 한 데이터가 삭제되면 해당 인덱스를 비워둬야 한다는 것을 의미합니다.
3번째 인덱스에 존재했던 40이라는 데이터가 삭제되면 해당 자리를 비워두게 됩니다.
다른 배열들의 인덱스는 그대로입니다.
List(리스트)
리스트는 배열과 달리 인덱스가 데이터에 종속적이지 않습니다.
배열이 갖는 인덱스 구조의 장점을 버리고 각 데이터의 빈틈을 없애는 방식을 가집니다.
따라서 리스트는 데이터 삽입과 삭제에 대한 데이터 낭비가 줄어들게 됩니다.
하지만 그만큼 검색 시간이 길어졌다는 특징을 가지고 있습니다.
- 자료를 순서대로 한줄로 저장.
- 제일 처음 데이터를 Head로 부르고 마지막을 Tail이라고 부름
- 순서가 있는 데이터의 모임
40의 데이터가 삭제되면 뒤의 50이 40의 자리를 차지하게 됩니다.
list의 기능
- 처음, 끝, 중간에 엘리먼트를 추가/삭제 가능
- 리스트에 데이터가 있는지를 체크할 수 있다.
- 리스트의 모든 데이터에 접근할 수 있다.
리스트는 빈 데이터 껍데기는 허용하지 않기 때문에 리스트를 사용할 때 유의해야 합니다.
☞ set이라는 데이터와의 차이
= 리스트는 중복을 허용하지만 set은 중복을 허용하지 않습니다.
Array List와 Linked List
'데이터의 연결 구조'가 가장 큰 차이점이다.
- Array List : 배열을 이용해 Javascript의 배열 구조처럼 리스트를 구현한 것.
ex) const color = ['red', 'blue'];
- Linked List
Array List는 내부적으로 배열을 사용하기에 인덱스를 이용해 데이터에 접근하는 것이 가능합니다.
따라서 데이터를 조회하는 속도는 빠릅니다. 하지만 데이터를 추가하거나 삭제하게 되면
각 순서가 일정하게 변경되어야 하기에 데이터의 삽입과 삭제에 상대적으로 오랜 시간이 소요됩니다.
▶ 중간 데이터가 한 칸 이동하면 다른 데이터들도 이동이 필요하기 때문
반면 Linked List는 배열을 사용하지 않고 하나의 데이터에 다음 엘리먼트의 위치 정보를 포함합니다.
이런 구조는 특정 데이터를 조회하는 인덱스가 존재하지 않기 때문에 조회하는 속도는 느립니다.
하지만 데이터를 추가하거나 삭제할 때 다른 데이터에 영향을 주지 않아 상대적으로 빠른 시간 내에
데이터의 삽입/삭제를 진행합니다.
데이터 삽입/삭제 속도
Array List < Linked List
인덱스 검색 속도
Array List > Linked List
두 List 구조는 각각 장단점이 존재합니다.
따라서 구현자가 적재적소에 사용해야 합니다.
일반적으로 고정된 데이터의 검색이 필요한 경우 = Array List
검색이 필요없는 가변적인 데이터가 필요한 경우 = Linked List를 사용합니다.
Queue(큐)
큐는 선입선출(FIFO, First In First Out)로 데이터가 쌓입니다.
데이터를 삽입하는 enqueue와 데이터를 추출하는 dequeue라는 키워드로 데이터를 관리합니다.
일반적인 큐는 선형이지만 크기가 제한되어 있고 빈 공간을 사용하게 되면 모든 자료를 꺼내거나 한 칸씩 옮겨야 합니다.
따라서 환(둥근 고리)형 큐를 구현해 선형 큐의 문제점을 보완할 수도 있습니다.
선형 큐의 문제점 = 배열로 큐를 선언할 때 큐의 삭제와 생성 시 마지막 배열에 도달 후
실제로는 데이터 공간이 남아있지만 오버플로우가 발생합니다.
일상 속에서의 예제
- 줄서기
- 편의점의 음료수 배치
큐는 보편적으로 순서대로 처리해야 하는 작업을 임시로 저장해두는 버퍼(Buffer)로서 사용됩니다.
그래서 대부분의 Buffer타입이 큐의 형태를 가지고 있습니다.
Stack (스택)
스택은 하나의 바구니에 데이터들이 순차적으로 담겨 있는 형태를 가진다고 할 수 있습니다.
큐와는 다르게 선입 후출(FILO, First In Last Out) 혹은 후입 선출(LIFO, Last In First Out)로 데이터가 쌓입니다.
데이터의 삽입에는 push, 삭제는 pop이라는 용어가 사용되며 다음과 같이 데이터를 관리하게 됩니다.
일상 속에서의 예제
- 물건을 쌓아 올리는 상황
- 질서있게 스쿨버스를 탄 상황(내릴 때도 먼저 탄 순서대로 내릴 때)
- 웹 브라우저의 '앞으로 가기', '뒤로 가기' 동작
실제 사례로는 트리 구조의 탐색에서
깊이 우선 탐색(Depth First Search:한 노드 끝까지 탐색 후 옆으로 이동하는 방식) 알고리즘에서 사용됩니다.
Graph(그래프)
상하위 개념이 없는 Node(노드 혹은 버텍스(vertax))와
각 노드 사이의 Edge(에지 혹은 아트(Arc))의 집합으로 데이터를 이루는 형태를 말합니다.
Node = {0, 1, 2, 3}
Edge = { (0,1), (0,2), (0,3), (1,2) }
Graph = {Node, Edge}
코드는 2차원 개념으로 표현됩니다.
그래프는 배열과 리스트로도 구현될 수 있으며 일반적으로 다음의 형태로 제공된다.
인접 행렬 (Adjacency Matrix)
인접 리스트(Adjacency List)
각 엣지는 벡터와 스칼라로 재현되고 방향성의 여부에 따라 그래프의 형태가 달라집니다.
스칼라 에지로 구현된 그래프는 무방향성(Undirected)그래프,
벡터 엣지로 구현된 그래프는 방향성(Directed) 그래프라고 이야기하며 다음과 같은 형태를 가집니다.
방향성(Directed)과 무방향성(Undirected) 그래프
일상 속의 예제
- 지하철의 노선도를 생각하면 됩니다.
- 일반적으로 매칭 알고리즘이나 추천 알고리즘에서 사용됩니다.
그래프는 비선형적 구조를 가지며 관계를 표현하는 데이터에 주로 사용됩니다.
Tree(트리)
트리는 여러 데이터가 계층 구조로 연결된 형태를 표현할 때 사용됩니다.
이름 그대로 뿌리(root)를 기준으로 잎사귀들(Leafs)이 아래로 자라는 나무를 생각하면 됩니다.
트리는 다음의 용어로 표현됩니다.
- node(노드) : 트리의 데이터를 저장하는 각 항목을 이야기합니다.
- child node(자식 노드) : 노드 A의 하층에 노드 B가 있다면 노드 B를 노드 A의 '자식 노드'라 부릅니다.
- parent node(부모 노드) : 노드 B의 상층에 노드 A가 있다면 노드 A를 노드 B의 '부모 노드'라고 합니다.
- root node(뿌리 노드) : 트리의 가장 상층에 있는 노드를 의미합니다.
- leaf node(잎 노드) : 자식 노드가 없는 모든 노드를 말합니다.
- ancestor node(조상 노드) : 노드 A의 자식을 따라 내려갔을 때 노드 B에 도달할 수 있다면 노드 A는 노드 B의 조상 노드입니다.
- descendant node(자손 노드) : 노드 A가 노드 B의 조상 노드일 때, 노드 B를 노드 A의 자손 노드라고 부릅니다.
- sibling node(형제 노드) : 같은 부모 노드를 갖는 다른 노드를 보고 형제 노드라 부릅니다.
트리는 여러 형태가 있지만 가장 기초라고 할 수 있는 2진(Binary) 트리만 살펴보겠습니다.
2진 트리는 다음과 같은 구조를 가집니다.
일상에서의 예제
- 계층구조를 나타내거나 계층 구조를 통해 알고리즘의 효율을 높일 때 사용합니다.
- 일반적으로 댓글이나 카테고리 구분
참고자료 : https://github.com/rayleighko/js4newbie/blob/master/Data_structure/README.md
rayleighko/js4newbie
신입 엔지니어를 위한 js 가이드. Contribute to rayleighko/js4newbie development by creating an account on GitHub.
github.com
'개발 개념 살펴보기_' 카테고리의 다른 글
| LifeCycle API (0) | 2020.03.17 |
|---|---|
| 동기와(Synchronous) 비동기(Asynchronous) (0) | 2020.02.28 |
| 명령형(Imperative)언어와 선언형(Declarative)언어 (0) | 2020.02.26 |
