✒️ 0. 들어가기 전
트리와 그래프는 비선형 자료구조의 대표적인 예시이다.
이 글에서는 트리와 그래프의 기본 개념부터 시작해, 다양한 종류의 트리, 그래프의 표현 방법(인접행렬과 인접리스트)에 대해 다뤄보자.
✒️ 1. 그래프 이론의 기초 (Graph, Vertex, Edge, Weight)
정점(Vertex)와 간선(Edge)으로 이루어진 집합을 그래프(Graph)라고 부른다.
정점은 노드(Node)라고도 불리며, 특정 객체, 위치, 사람 등을 나타낼 수 있다.
간선은 이 정점들을 잇는 선으로, 관계나 경로를 표현한다.
- 노드/정점(Node, Vertex): 그래프를 구성하는 기본 단위로, 점 또는 노드로 표현된다.
- 간선(Edge): 두 정점을 연결하는 선으로, 그래프 내의 관계나 경로를 나타낸다.
- 가중치(Weight): 간선에 부여된 비용이나 거리 등을 나타내는 값이다.
(건물은 노드, 길은 간선!)
Indegree와 Outdegree
- Indegree: 해당 정점으로 들어오는 간선의 수
- Outdegree: 해당 정점에서 나가는 간선의 수
✒️ 2. 트리(Tree Data Structure)
트리는 계층적인 구조를 가지며, 무방향 그래프의 일종이다.
트리의 핵심적인 특징은 사이클이 없고, 부모와 자식 간의 계층 구조를 가진다는 점이다.
- 루트 노드(Root Node): 트리의 가장 위에 있는 노드.
- 내부 노드(Internal Node): 루트 노드와 리프 노드 사이에 있는 노드.
- 리프 노드(Leaf Node): 자식 노드가 없는 노드.
- 트리의 높이: 루트 노드부터 리프 노드까지의 최대 거리.
- 트리의 깊이/레벨(Level): 특정 노드의 깊이를 기준으로 트리 내에서의 위치를 나타냄.
- 서브트리(Subtree): 트리 내의 하위 집합.
💡 트리의 특징
1. 부모, 자식 계층 구조를 가진다.
위 그림을 보면, 5번 노드는 6번 노드와 7번 노드의 부모 노드이고, 6번 노드와 7번 노드는 5번 노드의 자식 노드이다.
같은 경로 상에서 어떤 노드보다 위에 있으면 부모,아래에 있으면 자식 노드가 된다.
2. V-1=E라는 특징이 있다. 간선 수는 노드 수 -1 이다.
3. 임의의 두 노드 사이의 경로는 ‘유일무이’하게 ‘존재’한다.
즉, 트리 내의 어떤 노드와 어떤 노드까지의 경로는 반드시 있으며 하나밖에 없다.
✒️ 3. 이진 트리(Binary Tree)와 이진 탐색 트리(Binary Search Tree)
💡 이진 트리(Binary Tree)
이진 트리는 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리이다.
이진 트리의 유형
- 정이진 트리(Full Binary Tree): 모든 노드가 0 또는 2개의 자식 노드를 가짐.
- 완전 이진 트리(Complete Binary Tree): 왼쪽부터 채워진 트리로, 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있음.
- 포화 이진 트리(Perfect Binary Tree): 모든 레벨이 완전히 채워진 트리.
- 균형 이진 트리(Balanced Binary Tree): 모든 노드의 왼쪽 하위 트리와 오른쪽 하위 트리의 높이 차이가 1 이하인 트리.
💡 이진 탐색 트리(Binary Search Tree, BST)
이진 탐색 트리(BST)는 이진 트리의 일종이다.
다음과 같은 규칙을 가진다.
그림을 보고 이해해보자!
왼쪽 하위 트리의 모든 노드는 현재 노드보다 작은 값을 가짐.
오른쪽 하위 트리의 모든 노드는 현재 노드보다 큰 값을 가짐.
왜 이렇게 두는 걸까???
>> 바로 "검색"하기에 용이하기 때문이다.
10을 찾는다고 가정해보자!
왼쪽에는 작은 값, 오른쪽에는 큰 값이 이미 정해져있기 때문에
25의 왼쪽 노드들만 찾으면 된다는 것은 자명하기 때문이다!
💡 이진탐색트리의 시간복잡도
이렇게 균형잡히게 분포가 되었다면 탐색, 삽입, 삭제, 수정 모두 O(logN)이다.
그러나. 이는 삽입 순서에 따라 달라진다.
예를 들어 1, 2, 3 이렇게 삽입이 되어도, 이진탐색트리가 완성이 되었다.
그러나 이렇게 삽입할 경우 "선형적"인 자료구조
가 완성되어 버린다.
즉, 이진탐색트리는 삽입순서에 따라 영향을 받는다.
우리는 삽입순서가 어떻게 되든 균형잡히게 만들 필요가 있다.
>> 트리의 노드들을 회전시키는 등의 방법을 통해서 "균형잡히게 만든" 이진탐색트리를 만들 수 있다.
이렇게 발전된 트리로는 AVL트리, 레드블랙트리 등이 있다.
예를 들어 map이라는 자료구조는 삽입, 탐색, 삭제, 수정의 시간복잡도가 모두 O(logN)임을 확실하게 보장받는데,
그 이유가 균형잡힌 트리인 레드블랙트리를 기반으로 구현되어있기 때문이다.
✒️ 4. 인접 행렬(Adjacency Matrix)
지금까지 그래프라는 "자료구조"에 대해서 이야기 해보았다.
그러나 "자료구조"는 말 그대로 인간이 이해할 수 있는 "구조"일 뿐이다.
우리는 결국에는 컴퓨터가 이해할 수 있는 범주로 컴퓨터에게 알려줘야 한다.
(그래프 그림을 막 그려볼까..? NO...)
>> 우리는 인접행렬과 인접리스트 를 통해 그래프를 구현할 수 있다.
먼저 인접행렬에 대해 알아보자.
💡 인접행렬
인접행렬은 정점 간의 연결 관계를 나타내는 2차원 배열이다.
이 배열은 정사각형 모양이며, 각 요소는 0 또는 1을 가진다.
배열의 크기는 V x V (V = 노드 수)
<1 : 연결, 0 : 연결되어 있지 않음 을 의미>
💡 특징
공간복잡도
: O(V^2)
즉, 그래프의 정점 수가 많아질수록 공간 사용량이 급격히 늘어난다.
시간복잡도
- 특정 간선 존재 확인 : O(1)
두 정점이 연결되어 있는지 확인하는 데 걸리는 시간이 매우 빠르다.
- 모든 간선 찾기 : O(V^2)
모든 간선을 확인하는 데 걸리는 시간이 정점 수의 제곱에 비례하다.
💡 코드 예제
const int V = 4;
bool adj[V][V] = {
{0, 1, 1, 1},
{1, 0, 1, 0},
{1, 1, 0, 0},
{1, 0, 0, 0},
};
💡 적용 사례
그래프가 조밀할 때(dense)!
즉, 대부분의 정점이 다른 정점과 연결되어 있을 때 유리하다.
이 경우 인접행렬은 효율적이며 간선 존재 여부를 빠르게 확인할 수 있다.
✒️ 5. 인접 리스트(Adjacency List)
다음은 인접 리스트에 대해 알아보자.
💡 인접리스트
인접리스트는 각 정점에 연결된 다른 정점들을 리스트(또는 벡터)로 저장하는 방식이다.
정점마다 연결된 정점들을 저장한 리스트가 존재한다.
💡 특징
공간복잡도
: O(V+E)
여기서 E는 간선의 수.
즉, 간선이 적을 때 공간 효율성이 매우 좋다.
시간복잡도
- 특정 간선 존재 확인 : O(V)
두 정점이 연결되어 있는지 확인하는 데 시간이 많이 걸릴 수 있다.
- 모든 간선 찾기 : O(V+E)
간선의 수에 비례한 시간이 소요된다.
💡 코드 예제
const int V = 4;
vector<int> adj[V];
int main() {
adj[0].push_back(1);
adj[0].push_back(2);
adj[0].push_back(3);
adj[1].push_back(0);
adj[1].push_back(2);
adj[2].push_back(0);
adj[2].push_back(1);
adj[3].push_back(0);
for(int i = 0; i < V; i++) {
cout << i << " :: ";
for(int there : adj[i]) {
cout << there << " ";
}
cout << '\n';
}
}
💡 적용 사례
그래프가 희소할 때(sparse)!
즉, 정점 간의 연결이 드물 때 유리하다.
메모리 효율성이 높으며 간선의 수가 적은 그래프에서 공간을 아낄 수 있다.
✒️ 6. 인접 행렬 vs 인접 리스트
이렇게 배운 내용으로 하나만 유추해보자!
Q. 이러한 상황에서는 각각 무엇을 쓰면 될까?
A. 그래프(a)가 조밀할 때 (dense)할 때는 인접행렬이 인접 리스트보다 더 좋다.
그래프(b)가 희소할 때 (sparse)할 때는 인접행렬이 인접리스트보다 메모리를 더 많이 써야 한다.
고로, 인접리스트를 쓰는 것이 좋다.
- 보통은 인접리스트를 쓰면 된다! 문제에서 sparse한 그래프가 많이 나온다.
<트리는 간선의 수가 적고, 일반적으로 간선의 수가 𝑉 − 1 V−1이므로 희소한 구조이다.>
<따라서 메모리 효율성이 높은 인접리스트가 적합하다.>
- 다만, 문제 또는 코딩인터뷰에서 인접행렬로 주어진다면 그대로 인접행렬로 푸는 것이 좋다.
📝 면접 예상 질문
Q. 인접행렬과 인접리스트 중 어느 것을 사용할지 어떻게 결정하시겠습니까?
A. 인접행렬은 간선이 많은 조밀한 그래프(dense graph)에 적합합니다. 간선 존재 여부를 빠르게 확인할 수 있지만, 메모리 사용량이 크기 때문에 정점 수가 많을 때는 비효율적일 수 있습니다.
인접리스트는 간선이 적은 희소한 그래프(sparse graph)에 적합합니다. 메모리 사용이 효율적이며 간선의 수가 적은 경우 성능이 더 좋습니다.
즉, 그래프의 밀도와 메모리 제약을 고려해 선택합니다.
Q. 만약 그래프의 간선이 동적으로 자주 추가되거나 삭제된다면, 인접행렬과 인접리스트 중 어떤 것을 선택하시겠습니까?
A. 인접리스트를 선택합니다. 인접리스트는 간선을 추가하거나 삭제할 때 특정 정점의 리스트만 수정하면 되므로, 동적 변경에 더 적합합니다.
인접행렬은 간선 추가/삭제 시 배열의 요소를 수정하는 데 시간이 덜 들지만, 메모리 사용이 비효율적일 수 있습니다. 또한, 간선이 자주 변하는 상황에서는 비효율적일 수 있습니다.
Q. 그래프에서 간선이 10% 이하만 존재하는 경우, 인접행렬을 사용하면 어떤 문제가 발생할 수 있습니까?
A. 간선이 매우 적을 때, 인접행렬을 사용하면 많은 요소가 0으로 채워져 메모리 낭비가 발생합니다. 이로 인해 공간복잡도가 비효율적입니다.
이 경우 인접리스트를 사용하면 메모리를 더 효율적으로 사용할 수 있습니다.
Q. DFS와 BFS 중 특정 조건에서 어떤 탐색 알고리즘이 더 적합할까요?
A. DFS는 그래프의 깊이를 우선 탐색하므로, 경로 탐색이나 순환 여부를 확인하는 데 적합합니다. 예를 들어, 미로 찾기에서 경로를 찾는 경우 DFS가 적합합니다.
BFS는 그래프의 넓이를 우선 탐색하므로, 최단 경로를 찾는 데 적합합니다. 예를 들어, 각 간선의 가중치가 동일한 상황에서 두 정점 사이의 최단 경로를 찾을 때 BFS가 적합합니다.
