[공부] 인공지능을 위한 알고리즘과 자료구조: 이론, 코딩, 그리고 컴퓨팅 사고 3주차

본 포스팅은 강의를 바탕으로 공부하기 위해 작성되었습니다.

http://www.kmooc.kr/courses/course-v1:SKKUk+SKKU_46+2022_T2/course/

강좌 | SKKU_46 | K-MOOC

 

트리

• 노드들의 집합체, 계층 관계를 나타내는 자료구조
• 정보는 노드에 포함하게 된다. 
• 첫 번째 노드는 루트라고 불린다. 
• 각각의 노드는 하나의 노드만을 부모 노드로 가지게 된다.
• 모든 노드들은 0개 혹은 0 이상의 자녀들을 가지게 된다.
• 자녀의 숫자를 degree라고 표현한다.
• degree에 따라서 노드가 leaf 노드인지 internal 노드인지 구분을 한다.
• leaf 노드는 자녀가 없는 degree가 0인 노드들이다.
• 자녀가 있는 모든 노드들은 internal 노드라고 칭한다.
• 같은 노드를 부모로 가지는 노드들은 자매 노드, sibling 노드라고 불린다.

 

트리의 종류

자녀들의 순서가 있느냐 없느냐에 따라 unordered, ordered 트리로 구분한다.

• unordered 트리에서는 자녀의 순서가 무시된다.
• ordered트리는 자녀의 순서를 중요하게 생각한다.

 

트리의 경로(path)

• 트리에서 경로는 곧 노드들의 시퀀스이다. 
• 시퀀스가 표현 되었을 때, A노드 -> B노드 순서대로 표현되었다면 B노드의 부모 노드는 A노드이다. 
• 바로 앞의 노드가 부모 노드이고 그 다음 노드가 그 부모의 자식노드 여야 한다. 

 

트리의 깊이(depth)

• 어떤 노드를 선택했을 때, 루트노드로부터 그 노드까지의 경로는 unique하다. 
• 그 길의 경로를 노드의 깊이(depth)라고 한다. 

 

트리의 높이(Height)

• 존재하고 있는 모든 노드들 가운데 가장 큰 깊이(depth)이다.
• 노드의 수가 0개인 트리의 높이는 0이다.(루트 노드만 존재)
• 편리를 위해서, 비어있는 트리의 높이를 -1이라고 정의한다.

 

트리의 조상과 자손(Ancestor and Descendant)

• 임의의 두 노드 A, B의 A에서의 B path가 존재한다면 A는 B의 조상(ancestor)이고, B는 A의 자손(Descendant)이다. 
• 따라서, 루트 노드는 트리의 모든 다른 노드의 조상이다. 
• 트리는 실제로 list representation, 즉 linked-list로 많이 사용된다. 

 

그래프(Graph)

• 그래프는 데이터 사이의 인접한 정보를 저장하는 자료구조
• 그래프에는 Object와 Relationship이 존재한다. 
• Relationship은 edge로 연결하는 것이다. 
• 오브젝트를 표현하는 노드를 vertex라고 표현하기도 하며, 관계를 표현하는 edge들을 arc나 link 등의 용어로 표현하기도 한다. 
• 그래프는 자신의 이웃 개수를 degree로 정의한다. 
• 하나의 edge에서 갈 수 있는 노드 혹은 vertex의 집합을 neighbor, 이웃이라고 정의한다. 

 

Undirected graphs

• 방향이 없는 그래프에서 N개의 vertex가 있다면, 이들을 연결하는 edge가 순서가 없는 pair로 이루어져있다.
• V = {v1, v2, ..., vn}가 있다면 임의의 vi, vj 사이의 연결에는 순서가 상관 없다. {vi, vj}
• 본 강의에서는 자기 자신과의 edge는 없다고 가정한다. 

 

Sub-Graphs 

• 오리지널 그래프가 있을 때, 오리지널 그래프에서 edge와 vertex들을 이용하여, 추출해낸 그래프를 서브 그래프라고 한다. 

 

Graph의 Path

• undirected graph에서는 v0부터 vk까지의 노드의 시퀀스를 경로로 표현 가능 하며, 시퀀스 내의 인접한 두 개의 vertex 사이에는 반드시 edge가 존재해야한다. 
• S = (v0, v1, v2, ..., vk)가 있다면 임의의 j가 있다고 가정하면 (vj-1, vj) 사이에는 edge가 존재한다는 것.
• 위 식의 path의 길이는 k이다. 몇 개의 vertex로 이루어져 있느냐가 아닌, 몇 개의 edge들을 거쳐갔냐이기 때문이다.
• (위에 S는 k+1개의 vertex로 이루어져있지만, 거쳐간 엣지는 k+1이에서 -1 한 것이다. 착각 ㄴㄴ)

 

Connectedness 

• 두 개의 임의의 vi, vj vertex가 존재할 때, 둘 사이의 path가 존재 한다면 그 둘은 connected 되어있다고 얘기한다. 
• 즉, vertex간의 path가 있느냐 없느냐가 connted되었느냐, 안 되었느냐랑 같은 뜻이다. 
• 그래프가  connected, 즉 a connected graph라면 그래프 상의 어떤 vertex들을 집더라도 그 둘 사이의 path가 존재한다.
• 방향성을 인정했을 때, 모든 pair 간에 경로가 존재한다면 Strongly connected한 그래프라고 한다.
• 방향성을 무시하고 연결성을 따졌을 때, 그래프가 연결되어 있다고 하면 weakly connected한 그래프라고 한다. 

 

Weighted Graphs

• Weighted graph는 edge가 연결성만을 표현하는 것이 아니라, 연결되어 있는 vertex들끼리의 사이에 숫자나 값을 부여한 것이다. 만약 방향성이 없다면 weighted undirected graph라고 표현한다.
• weighted graph의 길이(path length)는 경로를 따라 갔을 때 edge에 표현된 weight들의 합으로 표현한다.

 

is Tree graph too?

• 트리도 그래프의 한 종류라고 얘기할 수 있다. 그러려면 connected 그래프가 되어야 한다.
• 모든 vertex에서 모든 다른 vertex로의 경로가 존재해야 하며, 그 경로는 unique해야한다. 그러면 이 그래프는 트리라고 얘기할 수 있다.
• 트리 또한 edge의 개수가 vertex의 개수보다 하나가 적다. 
• 트리는 사이클이 존재하지 않다. 만약 주어진 트리에 엣지를 임의로 추가한다면 트리는 사이클이 생기게 된다.
• 만약 하나의 엣지를 제거하게 되면 트리는 disconnected되어 두 개의 서로 다른 그래프로 나눠지며, 그 그래프들은 두 개의 트리로 존재하게 된다. 

 

Forests

• 트리의 정의에서 connectedness의 constraint를 제거한 것이다. 
• Forest는 cycle을 가지지 않은 그래프를 칭한다. 
• Forest는 vertex 개수가 edge 개수보다 항상 많다. 
• 트리의 갯수를 구하고 싶으면, vertex개수에서 edge개수를 빼면 트리의 개수를 구할 수 있다.
• 만약에 포레스트에서 edge를 제거하면, 트리를 하나 더 만들게 되는 효과가 있다. 

 

Directed Graphs

• undirected 그래프와 다르게 edge의 방향성이 존재하게 된다.
• edge v1, v2가 있다면, v1에서 v2로 갈 수는 있지만 반대의 경로는 존재하지 않게 된다.

 

In and Out Degrees

• undirected graph에서는 degree가 neighbor의 개수로 정의 되었다면, directed graph에서는 in_degree, out_degree가 분리되어 정의된다. 
• in_Degree의 경우, 말 그대로 한 vertex에게로 들어오는 edge의 개수를 뜻한다. 
• Out_Degree의 경우에는 한 vertex에게로 나가는 edge의 개수를 뜻한다. 

 

Source and Sink

• in_degree가 0인 것, 즉 한 vertex가 나가는 edge만 가지고 있다면 그것을 source라고 이야기한다.
• sink는 out_degree가 0인 것, 즉 한 vertex에서 들어오는 edge만 가지고 있다는 것을 칭한다. 

 

Directed Acyclic Graphs(DAG)

• 방향이 있으나 사이클이 존재하지 않는 그래프이다. 
• 그래프의 edge에 direction이 있지만 사이클이 존재하지 않는다면 directed acyclic graph라고 한다.

 

그래프를 표현하는 방법

1. Binary relation list : edge를 쭉 나열해놓은 것, 이것을 저장하기 위해서 edge 개수만큼의 메모리가 필요하다. 두 vertex 사이에서 edge가 있는지 확인하기 위해 하나씩 살펴본다. 굉장히 비효율적인 자료구조이다. 
2. Adjacency Matrix : 2차원 매트릭스를 이용해 예를 들어 (1,4)에 edge가 있다면 True를 사용한다. 메모리를 많이 사용한다. 메모리는 vertex 개수가 V개라고 했을 때, V제곱개만큼의 메모리가 사용된다.(weighted directed graph에 이용하면 편할 듯)  이를 이용하여 weighted 그래프를 표현하고 싶다면, 각각의 cell에 True/False가 아니라 weight 값을 입력해주면 된다. 
3. Adjacency List : 각 노드들을 기준으로 자신과 연결되어있는 edge가 있는 vertex들을 리스트로 표현하는 경우이다. 이런 자료구조가 요구하는 메모리량은 전체 vetex 갯수만큼의 linked list가 필요하다.

 

교수님이 식 써줘서 설명하니 이해하기 진짜 편함 ㄷㄷ