[TIL_19] 자료구조 알고리즘 기초

[keyword]

 

자료구조, Stack, Queue, Tree, Graph

---

자료구조

➡️ 데이터를 효율적으로 다룰 수 있는 방법

선형구조

➡️ Stack, Queue

비선형구조

➡️ Tree, Graph

---

🔮Stack

- FILO(First In Last Out) 선입후출, 데이터의 입출력 방향 같고, 한가지뿐 

- 예시 ) 브라우저의 이전버튼, 다음버튼으로 페이지 이동

🔮Queue

- FIFO(First In First Out) 선입선출, 데이터의 입력과 출력 방향이 정해져 있으며 입력에 한 가지 출력에 한 가지 총 두가지로 정해져 있다. 

- 예시 ) 컴퓨터 프린터기 (먼저 들어온 데이터가 먼저 출력 되는 구조)

🔮Tree

- 나무를 거꾸로 뒤집어 놓은 듯한 모습을 가지고 있다해서 붙여진 자료구조

- 루트라는 하나의 꼭지점으로 여러개 데이터를 간선(edge)로 연결 각 데이터들을 노드라고 하며 두개의 노드가 상하 계층으로 연결되면 부모/자식 관계를 가짐

- 자식이 없는 노드는 나무의 잎과 같다하여 리프노드(Leaf Node)라 부름

- 예시 ) 컴퓨터 디렉토리 구조

- 이진트리(Binary tree) : 자식 노드가 최대 두개인 노드들로 구성된 트리 (왼,오)

   - 정 이진 트리 : 각 노드가 0 or 2 자식노드 가짐

   - 포화 이진 트리 : 정 이진 트리이면서, 완전 이진 트리 모든 리프 노드 레벨 동일, 모든 레벨 가득 차있는 트리

   - 완전 이진 트리(Complete binary tree) : 마지막 레벨을 제외한 모든 노드가 가득 차 있고, 마지막 레벨의 왼쪽은 채워져야함

- 트리 순회 : 특정 목적을 위해 모든 노드를 한 번씩 방문하는 것

   -전위 순회 : 루트 ➡️ 루트 기준 왼쪽 ➡️ 오른쪽

   -중위 순회 : 젤 왼쪽 노드 ➡️ 루트 ➡️ 오른쪽

   -후위 순회 : 젤 왼쪽 노드➡️오른쪽➡️루트

🔮Graph

- 직접적인 관계가 있는 경우 두 점을 이어주는 선 있다.

- 간접적이라면 몇 개의 점과 선에 걸쳐 이어짐

- 하나의 점을 그래프에서 정점(vertex) 하나의 선은 간선(edge)라 함

- 인접 행렬(metrix), - 인접 리스트(list)

---

CS50 강의를 들어서 개념은 아는 상태였는데 실제로 구현해보는건 차원이 다름을 느꼈다...