시작하며
오늘은 여러 데이터들의 묶음을 저장하고 사용하는 방법을 정의한 자료구조에 대해서 학습하였다. 실제 현업에서는 수많은 데이터를 처리하기 때문에 데이터들의 특성에 맞는 자료구조를 통해 관리하는 것이 중요하다. 다양한 자료구조를 이해하고 javaScript의 배열 혹은 class를 이용해 구현해보았다.
자료구조
Stack
데이터(data)를 순서대로 쌓는 자료구조로 LIFO(Last In First Out) 혹은 FILO(First In Last Out)의 정책을 가지고 있다. 가장 먼저 입력된 데이터는 가장 나중에 나올 수 있으며 웹브라우저의 뒤로가기와 앞으로 가기 기능을 구현할 때 활용된다.
Queue
줄을 서서 기다리다, 대기 행렬 이라는 뜻을 가지고 있으며 Stack과 반대되는 개념으로, 먼저 들어간 데이터(data)가 먼저 나오는 FIFO(First In First Out) 혹은 LILO(Last In Last Out) 을 특징으로 가지고 있다. 프린터에서 인쇄 대기열이나 속도의 차이나 시간 차이를 극복하기 위해 사용하는 임시 기억 장치의 자료구조(buffer)로 Queue를 사용한다.
Graph
여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조로 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있고 간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어진다. 하나의 점을 그래프에서는 정점(vertex)이라고 표현하고, 하나의 선은 간선(edge) 이라고 한다.
- 무(방)향그래프(undirected graph) : 정점 간 방향없는 간선으로 이어진 그래프를 말하며, 반대로 한 뱡향으로 정해져 있는 그래프를 단방향 그래프라고 한다.
- 진입차수(in-degree) / 진출차수(out-degree) : 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타낸다.
- 인접(adjacency) : 두 정점간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점이라고 표현한다.
- 자기 루프(self loop) : 정점에서 진출하는 간선이 다른 정점을 거치지 않고 곧바로 자기 자신에게 진입하는 경우를 말한다.
- 사이클(cycle) : 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있는 경우를 말한다.
Tree
무방향 그래프의 한 구조로, 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조이다.
- 노드(Node) : 트리 구조를 이루는 모든 개별 데이터
- 루트(Root) : 트리 구조의 시작점이 되는 노드
- 부모 노드(Parent node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드
- 자식 노드(Child node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드
- 리프(Leaf) : 트리 구조의 끝지점이고, 자식 노드가 없는 노드
이진 트리
자식 노드가 최대 두 개인 노드들로 구성된 트리이며, 이진 탐색 트리(Binary Search Tree)는 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 특징이 있다.
| 이진 트리 종류 | 영어 표기 | 설명 |
|---|---|---|
| 정 이진 트리 | Full binary tree | 각 노드가 0 개 혹은 2 개의 자식 노드를 갖는 이진 트리 |
| 포화 이진 트리 | Perfect binary tree | 정 이진 트리이면서 완전 이진 트리인 경우로 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리 |
| 완전 이진 트리 | Complete binary tree | 마지막 레벨을 제외한 모든 노드가 가득 차 있고, 마지막 레벨의 노드는 전부 차 있지 않더라도 왼쪽은 채워져 있는 이진 트리 |
마치며
자료구조의 개념을 이해하는 것은 어렵지 않았지만 실제로 코드로 구현하는 과정이 쉽지 않았다. Stack이나 Queue 같은 경우는 기존에 배열을 통해 비슷한 자료구조를 사용해 왔기 때문에 어렵지 않았지만 Tree나 Graph는 코드로 구현하는 것이 상당히 어려웠다. 단순히 데이터를 추가해주는 과정도 말로 설명하면 쉽지만 실제로 구조게 맞게 추가하는 코드를 생각해 내는 것이 어려웠지만 해당 구조의 작동원리를 이해하게 되어 도움이 되었다. 실제 데이터들의 종류에 따라 어떤 자료구조를 사용하는 것이 좋은지에 대해 예를 찾아보고 더 자세하게 이해할 수 있도록 공부해야 겠다.
