2024 - 06 - 06 C++ 코딩테스트 10주완성 D+14

2주차 개념 정리

 

정점과 간선

 

정점(Vertex)는 노드라고도 불리며 그래프를 형성하는 기본 단위이다.

정점은 분할할 수 없는 객체이자 "점" 으로 표현되는 위치, 사람, 물건 등이 될 수 있다.

간선(Edge)은 정점을 잇는 선을 의미합니다. 관계, 경로 등이 될 수 있다.

 

예를 들어
"어떠한 위치나 어떠한 사람"으로부터 "무언가를 통해 간다"라고 했을떄
"어떠한 위취니 어떠한 사람" 정점(Vertex)이 되고 "무언가를 통해 간다"는 간선(Edge)이 됩니다.

 

(정점 간선 이미지 예시)

 

정점에서 다른 정점으로의 간선이 일방적인것을 단방향 간선이라고 하며,

정점끼리 서로 간선이 있을 경우는 양방향 간선이라고 합니다.

양방향 간선일 경우

정점으로 나가는 간선을 해당 정점의 outdegree 라고 하며 

 

들어오는 간선을 해당 정점의 indegree 라고 합니다.

 

 

예로 들어,
임의의 정점 u와 v가 있고, 서로를 잇는 간선이 있다고 하자
임의의 정점 u를 기준으로,
"u에서 v로 가는 간선"을 outdegree 라고 하며,
"v에서 u로 가는 간선"을 indegree 라고 합니다. 

 

간선 이미지 예시

가중치

 

정점과 정점사이에 드는 비용을 뜻합니다. 

 

u와 v까지 가는 비용이 한칸이라면 u에서 v까지 가는 가중치는 한칸입니다.

 

그래프

 

정점과 간선들로 이루어진 집합

 

트리 

 

무방향그래프의 일종이자, 자식노드와 부모노드로 이루어진 계층적인 구조를 가지며, 

사이클이 없는 자료구조를 의미합니다.

---

 

트리의 특징

• 부모, 자식 계층 구조를 가집니다. 지금 보면 5번 노드는 6번 노드와 7번 노드의 부모 노드이고, 6번 노드와 7번 노드는 5번 노드의 자식노드입니다.
  같은 경로 상에서 어떤 노드보다 위에 있으면 부모, 아래에 있으면 자식 노드가 됩니다.
• V - 1 = E 이라는 특징이 있습니다. 간선 수는 노드 수 - 1 입니다.
• 임의의 두 노드 사이의 경로는 '유일무이'하게 '존재' 합니다.  즉,트리 내의 어떤 노드와 어떤 노드까지의 경로는 반드시 있으며 하나밖에 없습니다.

---

 

루트노드

가장 위에 있는 노드를 뜻합니다. 보통 트리문제가 나오고 트리를 탐색할 때 루트 노드를 중심으로 탐색하면 문제가 쉽게 풀리는 경우가 있습니다.

내부노드

루트노드와 리프노드 사이에 있는 노드를 뜻합니다.

리프노드

자식노드가 없는 노드를 뜻합니다.

---

트리 이미지 예시

트리의 높이와 레벨

 

다음 그림은 트리의 높이와 레벨을 설명한 그림입니다.

 

트리 높이 및 레벨 이미지 예시

---

• 깊이 : 트리에서의 깊이는 각각의 노드마다 다르며 루트 노드에서 특정 노드까지 최단 거리로 갔을 때의 거리를 말합니다.
• 높이 : 트리의 높이는 루프 노드부터 리프 노드까지의 거리 중 가장 긴 거리를 의미합니다.
• 레벨 : 트리의 레벨은 주어지는 문제마다 조금씩 다르지만 보통 깊이와 같은 의미를 지닙니다. 1번 노드를 0레벨이라고 하고 2번 노드, 3번 노드까지의 레벨을 1레벨이라고 할 수도 있고, 1번 노드를 1레벨이라고 할 수 있습니다.
  다시 예를 들어 1번 노드를 1레벨이라고 한다면 2번 노드와 3번 노드는 2레벨이 됩니다.
• 서브트리 : 트리 내의 하위 집합을 서브트리라고 합니다. 트리 내에 있는 부분집합이라고 보면 됩니다.
• 숲 : 트리로 이루어진 집합을 숲이라고 합니다.

---