Graph
Graph란?
여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조
라고 표현할 수 있다.
서로 다른 점들이 직접적인 관계를 가지고 있다면 바로 이어주는 선이 존재하고, 간접적인 관계를 가지고 있다면 다른 점을 거쳐서 이어지는 선이 존재한다.
여기서 점은 그래프에서 정점(vertex)라 표현하고, 선은 간선(edge)라고 표현한다.<Graph 용어정리>
무향그래프(undirected graph) / 단방향그래프(directed graph)
말그대로 방향이 없는 그래프이다. 간선이 존재한다면 어느 방향이던 상관이 없다. 무향그래프와 다르게 단방향그래프는 방향이 정해져 있다. 정점 A에서 정점 B로 가는 간선이라고 할때, B에서 A로 갈 수 없다.
진입차수(in-degree) / 진출차수(out-degree)
한 정점에서 들어오는 간선과 나가는 간선의 개수를 뜻한다.
인접(adjacency) 두 정점간의 간선이 직접적으로 이어져있다면 두 정점은 인접한다고 표현한다.
자기 루프(self loop)
정점에서 진출하는 간선이 자기 자신일때 이를 자기 루프를 가진 정점이라 표현한다.
사이클(cycle)
정점에서 다른 정점으로 진출 한 뒤 다시 자기 자신으로 돌아 온다면 사이클이 있는 그래프라고 표현한다.인접행렬
인접행렬은 정점들간의 인접함을 표시 해주는 행렬이다.
A B C A 0 0 1 B 1 0 1 C 1 0 0 A의 진출차수는 1개이다. A->C
- [0][2] === 1
B의 진출차수는 2개이다. B->A, B->C- [1][0] === 1
- [1][2] === 1
C의 진출차수는 1개이다. C->A- [2][0] === 1
언제 인접행렬을 사용해야 하는가?
- 한 개의 큰 표와 같은 모습을 한 인접 행렬은 두 정점 사이에 관계가 있는지, 없는지 확인하기에 용이합니다.
- 예를 들어, A에서 B로 진출하는 간선이 있는지 파악하기 위해선 0 번째 줄의 1 번째 열에 어떤 값이 저장되어있는지 바로 확인할 수 있습니다.
- 가장 빠른 경로(shortest path)를 찾고자 할 때 주로 사용됩니다.
인접리스트
인접리스트는 정점간의 인접함을 리스트로 표현한 것이다.
- A -> C -> null
- B -> A -> C -> null
or- B -> C -> A -> null
- C -> A -> null
언제 인접리스트를 사용해야 하는가?
인접행렬은 인접의 유무를 0 또는 1로 모든 경우의 수를 행렬로 표시 한다.
이로 인해 메모리를 많이 차지한다.
메모리의 효율적인 사용을 위해 인접함만 표시 하고 싶다면 인접행렬 보다 인접리스트로 사용하는 것이 유리하다.
Tree
Tree란?
나무의 뿌리 모양처럼 데이터가 바로 아래에 있는 하나 이상의 데이터에 단방향으로 연결되는 계층적 자료구조라고 한다.
데이터를 순차적으로 나열시킨 형태인 선형구조가 아닌 하나의 데이터 뒤에 여러 데이터가 존재할 수 있는 비선형구조로 되어있다.Tree 용어정리
root
가장 상위에 있는 시작하는 데이터부모 노드(Parent Node) / 자식 노드(Child Node)
각 데이터를 노드(Node)라고 하며, 상위 노드와 하위 노드가 연결되면 부모/자식 관계가 되어 상위 노드를 부모 노드(Parent Node), 하위 노드를 자식 노드(Chlid Node)라 한다.리프 노드(leaf Node)
나무의 잎과 같이 자식 노드가 없는 노드를 말한다.레벨(Level)
노드와 노드의 간격을 뜻한다. 첫번째 자식 노드를 Lebel 1로 설정한다.높이(height) / 깊이(depth) / 형제 노드(sibling Node)
루트로 부터 가장 마지막의 자식 노드까지의 레벨을 트리의 높이(height)라고 하며, 특정 노드까지의 레벨을 트리의 깊이(depth)라고 표현한다. 같은 레벨의 노드들을 형제 노드(sibling Node)라고 표현한다.
Binary Search Tree
자식 노드가 최대 두 개인 노드들로 구성된 트리를 이진 트리라고 정의한다.
이진 트리는 자료의 삽입, 삭제 방법에 따라 3가지의 트리를 가진다.정 이진 트리(Full binary tree)
각 노드가 0개 또는 2개의 자식 노드를 갖는 트리완전 이진 트리(Complete binary tree)
마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 한다.포화 이진 트리(Perfect binary tree)
정 이진 트리이면서 완전 이진 트리인 경우를 말한다. 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리이다.왼쪽 자식노드들은 루트나 부모노드보다 작은 값이고, 오른쪽 자식노드들은 루트나 부모노드보다 큰 값인 특징을 가지고있다.
입력되는 값의 순서에 따라 한쪽으로 노드들이 몰리게 될 가능성이 있기 때문에 삽입과 삭제마다 트리의 구조를 재조정하는 과정을 거치는 알고리즘을 도입하여 문제를 해결할 수 있다.
