이런 그래프를 코드로 작성 한다면 어떻게 될까?
1. Graph
- 우리가 생각하는 그 그래프가 맞다.
- 하지만 이것을 코드로, 그리고 글로 작성한다는 것을 생각해 보면 된다.
2. Graph에서 사용하는 용어
- 정점(vertex) : 그래프에서 볼 수 있는 하나의 점
- 간선(edge) : 연결된 선
- 무(방)향 그래프(undirected graph) : 서로 연결되어 있어서 서로가 서로에게 접근이 가능한 그래프.
- 단방향 그래프(directed graph) : 한쪽에서만 연결되어 있는 그래프
- 진입 차수(in degree)와 진출 차수(out degree) : 몇 개의 간선으로 들어오고 몇 개의 간선으로 나가는지
- 인접(adjacency) : 정점들 사이에 아무것도 없고 서로 한 번에 간선으로 연결된 경우
- 자기 루프(self loop) : 간선이 진출되어 다시 자신에게 돌아오는 경우
- 사이클(cycle) : 다시 돌아서 각각의 정점들을 거쳐 자신으로 돌아오는 형태의 그래프
3. Tree
- 나무를 뒤집어 놓은것 처럼 계층으로 나누어 뻗어나가는 그래프
- 토너먼트 대진표 같은 모양을 생각하면 된다.
4. Tree에서 사용하는 용어
- 노드(Node) : 각각 하나의 요소에 해당하는 데이터
- 루트(Root) : 트리의 시작점이 되는 노드
- 부모 노드(parent node) : 부모가 되는 상위의 노드
- 자식 노드(child node) : 자식이 되는 하위의 노드
- 리프(leaf) : 더 이상 자식이 없는 끝이 되는 노드
5. Binary Search Tree
- 트리는 자료를 탐색할때 사용할 수 도 있다.
- 이때, 처음 루트에서 두 가지 노드로 빠져나오는 형태를 가진 이진트리(Binary Tree)를 대표적으로 사용할 수 있다.
아무리 자료구조를 안다고 해도 알고리즘 문제를 풀기는 쉽지 않았다.
그래서 가장 처음으로 다시 돌아가서 용어 정리부터 다시 시작해본다.