[2020모각코] 1회차 2020.12.23

트리(Tree)의 개념

Tree는 하나 이상의 노드로 구성되는 유한집합으로, 각 노드들은 서로 다른 유일한 자식을 가지는 구조이다.

tree 에는 여러가지 특징들이 존재한다.

1. tree 의 서로 다른 임의의 두 노드에 대해 두 노드를 연결하는 경로는 유일하다.
2. tree 에는 사이클을 가지는 노드 집합이 존재하지 않는다.
3. tree 반드시 하나의 root가 존재한다. 

tree는 여러 종류가 존재한다. 이번 시간에 푼 문제는 이진 트리에 관한 문제이다.

이진 트리란 각각의 노드가 최대 두개의 자식 노드를 가지게 되는 트리이다.

이 문제의 핵심은 주어진 입력을 가지고 이진 트리를 구현하는 것과 후위순회를 하여 노드의 값을 읽는 것이다.

 

첫번째 입력을 root로 지정한 다음 root의 key값보다 작은 값이 입력된다면 왼쪽 자식으로 이동 후 비교, 큰 값이 입력된다면 오른쪽 자식으로 이동 후 비교하는 과정을 통해 이진트리를 구현하였다.

후위순회란 하위에 있는 노드들을 모두 방문 한 후 root에 방문하는 방식이다. 

 

 

 

그래프(Graph)의 개념

노드와 그 노드를 연결하는 간선으로 이루어진 자료구조

 

이 문제의 핵심은 주어진 입력을 가지고 그래프를 구현하고,  그 그래프를 DFS와 BFS방법으로 탐색하는 것이다.

DFS는 깊이 우선 탐색(Depth First Search)의 약자이고 BFS는 너비 우선 탐색(Breadth First Search)의 약자이다.

 

DFS는 그래프를 탐색하는 방법 중 하나로써 시작점부터 다음 분기로 넘어가기 전에 해당 분기를 완전히 탐색하는 방법이다. 즉 넓게 탐색하기 전에 깊게 탐색하므로 DFS(Depth First Search)의라는 이름을 가진다. 재귀나 스택(Stack)을 이용하여 구현 가능하다. 이번에는 재귀를 이용하여 구현하였다.

BFS는 그래프를 탐색하는 방법 중 하나로써 시작점부터 인접한 노드를 먼저 탐색하는 방법이다. 즉 깊게 탐색하기 전에 넢게 탐색하므로 BFS(Breadth First Search)라는 이름을 가진다. 재귀적으로는 동작하지 않아 큐(Queue)를 이용하여 구현하였다.