TIL - 21.07.22 👨‍💻

자료구조

자료구조란 여러 데이터들의 묶음을 저장하고 사용하는 방법을 정의한 것이다.

대부분의 자료구조는 특정 상황에 놓인 문제 해결에 특화되어 있어 여러 구조를 알고 있으면 빠른 해결에 도움이 된다.

대표적인 자료구조로는 Stack, Queue, Tree, Graph등이 있다.

---

Stack

스택은 쌓다 포개다 등의 뜻에서 짐작할 수 있듯 데이터를 순서대로 쌓는 자료구조이다.
스택형 자료구조는 입력과 출력이 한 방향으로 이루어지는 제한적 접근 방식을 가지고 있으며 이를 LIFO(Last In First Out) 또는 FILO(First In Last Out) 라고 부르기도 한다.

스택형 자료구조 같은 경우에는 브라우저의 뒤로가기 앞으로 가기 기능을 구현할때 사용되고 있다.

---

Queue

큐는 줄서서 기다리다, 대기 행렬 이라는 뜻에서도 짐작할 수 있듯 데이터가 들어간 순서대로 처리하는 자료구조이다.
큐형 자료구조는 스택형과 반대되는 개념을 가지고 있는데, 먼저 들어간 데이터가 먼저 나오는 이 자료구조를 LILO(Last In Last Out) 또는 FIFO(First In First Out)라고 부르기도 한다.

큐는 음악 어플에서 순서대로 노래를 들을때 사용하기도 하고 컴퓨터에서 광범위하게 사용되는데,
컴퓨터에서 작업한 문서를 출력하면 차례대로 큐에 보내고 프린터에서 차례대로 큐의 문서를 출력한다.
이처럼 임시로 쌓은 큐를 저장하는 곳을 Buffer(버퍼)라고 하며, 이는 CPU의 이벤트는 불규칙적으로 처리되는 반면, 보통 이벤트를 처리하는 장치(프린트 등)은 일정한 속도로 이벤트를 처리하기에 이 간격을 맞추기 위해서 버퍼를 사용한다.

---

Graph

그래프형 자료구조에서는 각 자료를 정점(Vertex)이라 하고, 각 정점간 연결이 되어 있으면 직접적 관계라고 하고 이 연결을 간선(Edge)이라 한다. 직접 연결이 아니라도 다른 정점을 거쳐서 연결 되기만 하면 간접적 관계라고 한다.
여기서 간선은 연결되어 있음만 확인할 수 있고 정점간 연결정도가 어떻게 되는지에 대한 정보는 포함하고 있지 않다.
이렇게 추가 정보가 없는 그래프형 자료구조를 비가중치 그래프라고 한다.
이와 반대로 연결 정보가 있는 그래프를 가중치 그래프라 한다.

주요 그래프 용어

• 무방향 그래프(Undirected Graph) - 서로 오고 갈 수 있는 그래프를 무방향 그래프라 하고, 이와 반대되는 개념이 일방통행으로 설명할 수 있는 단방향 그래프(Directed Graph)이다.

• 진입 차수(In-degree), 진출 차수(Out-degree) - 한 정점에 진입하는 간선과 진출하는 간선이 몇개인지 표기한다.

• 인접(Adjacency) - 두 정점이 직접적으로 연결되어 있으면 인접하다고 한다.

• 자기 루프(Self-loop) - 한 정점에서 진출한 간선이 자신에게 돌아와 진입하는 경우 그 정점은 자기 루프를 가졌다고 한다.

• 싸이클 (Cycle) - 한 정점에서 출발해 다른 정점을 거쳐 다시 출발한 정점으로 돌아올 수 있다면, 사이클이 존재하는 그래프라 한다.

인접 행렬

인접 행렬은 정점간 인접하다면 1, 아니라면 0으로 표기하는 일종의 표이다.
만약 가중치 그래프라면 1 대신 유의미한 정보가 들어갈 수 있다.

인접 행렬은 두 정점간 관계를 확인할때 용이하며 가장 빠른 경로를 찾을때 주로 사용된다.

인접 리스트

인접 리스트는 정점이 어떤 정점과 인접한지 리스트 형태로 표기하며 인접한 정점만 표기 되기에 모든 정점과의 관계를 표현하는 인접 행렬에 비해 메모리를 효율적으로 사용할 수 있다.

---

Tree

트리 구조는 무방향 그래프의 한 구조로 뿌리부터 가지 뻗어나가는 모습이 닮았다고 해서 트리 구조라고 한다.

트리 구조는 데이터가 바로 아래 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조이며, 한 데이터 뒤에 여러 데이터가 존재할 수 있는 비선형 구조이다.
트리구조는 아래로만 뻗어 나가기에 싸이클은 없다.

트리 구조에서 데이터를 노드(Node)라고 칭하며 루트(Root)라는 최상위 노드로부터 여러 데이터를 간선으로 연결한다.
그리고 두개의 노드가 상하로 연결되면 부모자식 관계를 가지며 자식이 없는 노드는 리프(Leaf)노드라고 한다.

트리구조 키워드

• 노드(Node) - 트리구조를 이루는 모든 개별 데이터이다.
• 루트(Root) - 트리구조의 시작점이 되는 최상위 노드이다.
• 부모(Parents)노드 - 두 노드가 인접할때 루트로부터 상대적으로 가까운 노드를 부모노드라고 한다.
• 자식(Child)노드 - 두 노드가 인접할때 루트로부터 상대적으로 먼 노드를 자식노드라고 한다.
• 리프(Leaf)노드 - 트리구조의 끝으로 자식노드가 없는 노드를 리프노드라 한다.

Depth, Level, Height, Sub-tree

• 깊이(Depth) - 트리 구조에서는 루트로 부터 하위 계층의 특정 노드까지의 깊이를 표현할 수 있다.
  루트를 기준으로 0이고, 자식으로 내려갈때마다 1씩 더해진다.

• 레벨(Level) - 트리구조에서 같은 깊이를 가지고 있는 노드를 묶어 레벨로 표현 할 수 있다.
  깊이가 0인 루트는 Level 1이며 깊이가 깊어 질수록 한단계 씩 레벨이 올라가며, 같은 레벨의 노드를 형제(Siblings)노드라고 한다.

  DOM에서는 같은 부모를 가지고 있어야 형제 노드로 본다.
  고로 DOM에서 형제 노드는 DOM의 정의에서도 형제 노드이고 트리형 자료구조의 정의에서도 형제 노드가 되는 것이다.
  다만 같은 레벨이나 다른 부모를 가진 노드 같은 경우는 DOM의 정의에서는 형제 노드가 아니고 트리형 자료구조의 정의에서는 형제 노드이다.

• 높이(Height) - 트리 구조에서 리프 노드를 기준으로 루트까지의 높이를 구할 수 있다.
  리프가 제 각각 기준이 되는데 자식이 있는 부모 노드는 가장 높이 있는 자식의 높이에 +1 한 높이를 가진다.

• 서브 트리(Sub-tree) - 루트로부터 나오는 큰 트리 내부에 트리 구조를 갖춘 작은 트리를 서브 트리라 한다.

---

이진 탐색 트리 ( Binary Search Tree )

이진 트리는 효율적인 검색을 위해 정의된 트리 구조이다.

이진 트리는 자식 노드가 최대 2개인 노드들로 구성된 트리이고 이 두개의 자식 노드는 왼쪽, 오른쪽 자식 노드로 나눌 수 있다.
이진 트리는 자료의 삽입, 삭제 방법에 따라 정 이진 트리, 완전 이진 트리, 포화 이진 트리로 나눌 수 있다.

• 정 이진 트리 (Full Binary Tree) - 정 이진 트리는 각 노드가 2개의 자식을 가지거나 아예 가지지 않는 트리를 말한다.
• 완전 이진 트리 (Complete Binary Tree) - 마지막 레벨을 제외한 노드가 모두 가득 채워져 있고, 마지막 레벨의 노드는 다 차진 않아도 왼쪽 노드는 채워져있는 트리를 말한다.
• 포화 이진 트리 (Perfect Binary Tree) - 정 이진 트리이며 완전 이진 트리인 트리이다.
  모든 리프 노드 레벨이 동일하고 모든 레벨이 채워져 있다.

이진 탐색 트리의 특징

• 모든 왼쪽 자식 노드의 값이 루트나 부모보다 작다.
• 모든 오른쪽 자식 노드의 값이 루트나 부모보다 크다.

이러한 특징 덕에 이진 탐색 트리는 한쪽으로 몰릴 수 있다.
한쪽으로 몰릴 경우 탐색 시간이 더 오래 걸릴 수 있으니 재조정과정 알고리즘을 추가 할 수 있다.

---

GOOD 😉

그래프형과 트리형 자료구조를 익혔다.
난관에 부딫힌 동기의 문제를 화두만 던져주는 방식으로 도와줬다.
토이 1번 풀었다!
내일 금요일

BAD 😥

익히는데 시간이 필요할 것 같다.

TO DO 🔥

• 자료 구조 익히기
• 노마드 코더 리액트 클론

Retrospect 🧐

재귀함수 다음에 튀어나오는 이 무시무시한 녀석들.
내일 금요일이고 그 다음 날은 토요일이니 조금 여유를 가지고 정리해보는 시간을 가져야할 것 같다.
이 와중에 여유찾는 덜깨진 머리의 소유자

이전에 배열 메소드 push, pop 같은 것들 정리하면서 스택형이랑 큐형은 조금 정리해놔서 오늘 다시 만났을때 부담이 덜했다.

아주 칭찬해 과거의 나!