[TIL] 코드스테이츠 SEB BE Day 23
💡 Today I Will Learn
- Graph
- Tree
- BST
✏️ Summary
Tree
그래프의 여러 구조 중 단방향 그래프 구조이며, 여러 방향으로 가지가 뻗은 형태이다.
하나의 노드에 여러 노드가 있는 비선형 구조이며, 계층적으로 표현된다.
Tree 구조의 특징
가장 최상층에 있는 Root로 부터 여러 간선(Edge)이 뻗어나간다. 각 데이터는 노드(Node)이며 Parent Node(부모), Child Node(자식), Leaf Node(자식이 없는)라 부른다.
- Depth (깊이)
루트로부터 해당 노드까지의 깊이를 의미한다. (0 ~ logn-1)
- Level (레벨)
같은 깊이를 가진 노드들의 집합이 Level이며 같은 레벨을 Sibling Node(형제)라 한다. (1 ~ logn)
- Height (높이)
리프노드로부터 루트까지의 높이이다.
- Sub tree
Tree 사용예제
윈도우 탐색기 같은 파일시스템은 트리구조로 이루어져있다.
루트 내부에 트리 구조를 가진 또 다른 작은 트리를 서브 트리라 한다.
Graph
여러 정점들이 얼키설키 연결되어있는 자료구조이다. 마치 거미줄같은 네트워크망의 모습을 지닌다.
Graph 구조의 특징
정점(vertex)과 간선(edge) 두 요소로 이루어져 있다.
- 인접 행렬(Adjacency matrix)
두 정점을 잇는 간선이 존재하다면 “인접하다” 표현한다. 이를 2차원 배열로 표현한 것이 인접 행렬이며 기본적으로 0(인접하지않다), 1(인접하다)로 구성한다.
- 인접 리스트(Adjacnecy list)
각 정점의 인접한 정점들을 리스트로 표현한다. 정점마다 리스트를 한개씩 보유하고 있으며 인접한 정점들을 요소로 갖고 있다.
순서는 중요하지 않지만, 우선순위가 있다면 이를 고려하여 구성할 수 있다. 또한 인접 행렬보다 메모리를 적게 사용하여 일반적으로 유리하다.
Graph 사용예제
각 지역마다 연결된 비용을 “가중치 그래프” 형태의 정보로 기반하여 길을 찾는 네비게이션이 예가 될 수 있다.
Binary Search Tree
트리 구조를 통해 효율적으로 탐색하기 위해 고안한 구조이다. 부모노드를 기준으로 Left노드는 작은 값, Right노드는 큰 값을 저장한다.
Binary Tree는 Tree 중에서 최대 2개의 자식 노드를 가질 수 있다.
| 종류 | 설명 |
|---|---|
| 정 이진트리(Full binary tree) | 각 노드의 자식이 0 or 2개 존재한다. |
| 포화 이진 트리(Perfect binary tree) | 정 이진트리이면서, 완전 이진트리이다. 리프 노드의 레벨이 동일하고, 모든 레벨이 가득차있다. |
| 완전 이진 트리(Complete binary tree) | 마지막 레벨을 제외하고 모든 노드가 가득차있으며, 마지막 레벨의 노드 중 left 노드는 전부 차있어야 한다. |
- Tree traversal (트리 순회)
| 종류 | 설명 |
|---|---|
| 전위 순회(preorder) | root-left-right 순으로 순회 |
| 중위 순회(inorder) | left-root-right 순으로 순회 |
| 후위 순회(postorder) | left-right-root 순으로 순회 |
📌 정리
👿 Problem
&&, || 연산 시 조건에 예외가 존재해도 실행이 된다?
👼 Solution
&&, || 논리 연산자는 앞의 조건이 만족되면 뒤는 실행하지 않는다. 즉, or의 경우 앞조건이 true, and의 경우 앞조건이 false이면 뒤의 조건에 예외가 존재한다 해도 정상적으로 실행 가능하다.
🎯 Next Week
- BFS / DFS
Back to [TIL] 코드스테이츠 SEB BE Day 22
