📖 그래프의 종류와 개념
그래프는 여러 개의 점(노드 또는 정점)들이 선으로 연결된 구조를 나타내는 수학적인 개념입니다. 그래프는 다양한 현실 세계의 문제를 모델링하고 분석하는 데 사용됩니다.
그래프의 용어
노드(Node) 또는 정점(Vertex)
: 그래프에서 하나의 점을 나타냅니다. 노드는 데이터를 저장하는데 사용될 수 있습니다.
간선(Edge)
: 그래프에서 노드와 노드를 연결하는 선을 나타냅니다. 간선은 노드 쌍 사이의 관계를 나타냅니다.
인접(Adjacent)
: 두 개의 노드가 간선으로 직접 연결되어 있는 상태를 말합니다. 인접한 노드는 서로 이웃이라고도 합니다.
차수(Degree)
: 노드에 연결된 간선의 수를 나타냅니다. 무방향 그래프에서는 노드의 차수는 해당 노드와 인접한 노드의 수입니다.
경로(Path)
: 그래프에서 노드들을 연결하는 간선의 순서를 나타내는 순서쌍입니다. 경로의 길이는 경로에 속한 간선의 수입니다.
사이클(Cycle)
: 그래프에서 동일한 노드로 되돌아오는 경로를 말합니다. 즉, 경로의 시작 노드와 끝 노드가 동일한 경우를 말합니다.
가중치(Weight)
: 가중치 그래프에서 간선에 할당된 값 또는 비용을 나타냅니다. 가중치는 간선의 특성을 나타내는데 사용됩니다.
그래프의 종류
무방향 그래프 & 방향 그래프
: 간선의 방향의 유무에 따라 구분되는 그래프
가중치 그래프
: 그래프에 가중치 또는 비용이 할당된 그래프(네트워크 이론이나 신경망 이론에 활용되는 개념)
연결 그래프 & 비연결 그래프
: 모든 노드에 대해 경로가 존재하면 연결 그래프, 특정 노드에 대한 경로가 하나라도 존재하지 않을 경우 비연결 그래프
사이클 그래프 & 비순환 그래프
완전 그래프
: 그래프의 모든 노드가 연결되어 있는 그래프
그래프의 한 종류인 트리에 대해🧐
트리(Tree)는 그래프(Graph)의 한 종류로, 계층적인 구조를 나타내는 비순환적인 연결 그래프입니다. 트리는 하나의 루트(Root) 노드에서 시작하여 다양한 자식(Child) 노드들로 확장되는 구조를 가지며, 각 노드는 하나의 부모(Parent) 노드와 연결되어 있습니다.
트리의 특징 🔎
계층 구조: 트리는 하나의 루트 노드에서 시작하여 계층적인 구조를 형성합니다. 각 노드는 부모-자식 관계를 가지며, 자식 노드들은 동일한 계층에 속합니다.
방향성: 트리는 방향 그래프의 한 형태로, 간선은 단방향으로 표시됩니다. 각 노드는 자식 노드들을 가리키는 방향으로 연결됩니다.
비순환성: 트리는 순환 구조를 가지지 않습니다. 즉, 어떤 노드에서 시작해도 동일한 노드로 되돌아갈 수 있는 순환 경로가 존재하지 않습니다.
유일한 경로: 루트 노드에서 어떤 노드까지의 경로는 유일합니다. 트리 내에서는 어떤 노드도 다른 경로를 통해 도달할 수 없습니다
트리에 종류
이진 트리 (Binary Tree)
: 각 노드가 최대 두 개의 자식을 가질 수 있는 트리입니다. 이진 트리는 왼쪽 자식과 오른쪽 자식으로 구성되며, 자식의 배치에는 순서가 있습니다. 이진 트리는 데이터 검색, 정렬, 압축 등 다양한 애플리케이션에서 사용됩니다.
이진 탐색 트리 (Binary Search Tree)
: 이진 트리의 한 종류로, 이진 탐색의 원리를 기반으로 합니다. 모든 노드는 왼쪽 서브트리의 값보다 작고, 오른쪽 서브트리의 값보다 큰 키 값을 가집니다. 이진 탐색 트리는 데이터 검색, 정렬, 범위 검색 등에 효율적으로 사용됩니다.
AVL 트리
: 균형 이진 탐색 트리로서, 모든 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 최대 1인 트리입니다. AVL 트리는 삽입, 삭제 시에 자동으로 균형을 유지하여 탐색 성능을 보장합니다.
레드-블랙 트리 (Red-Black Tree)
: 균형 이진 탐색 트리로서, 각 노드는 레드(Red) 또는 블랙(Black) 색깔을 가지며, 특정한 규칙을 따릅니다. 레드-블랙 트리는 AVL 트리보다 균형을 유지하는 데에 조금 덜 엄격한 규칙을 가지며, 데이터의 삽입과 삭제가 더 효율적입니다.
B-트리 (B-Tree)
: 다양한 자료 구조에서 사용되는 균형 탐색 트리입니다. B-트리는 노드마다 여러 개의 키 값을 가지며, 많은 수의 자식을 가질 수 있습니다. B-트리는 대용량 데이터베이스의 인덱스 구조나 파일 시스템에서 사용되는 것과 같은 곳에서 사용됩니다.
힙 (Heap)
: 이진 트리의 한 종류로, 최대 힙과 최소 힙으로 나눌 수 있습니다. 최대 힙은 부모 노드의 값이 자식 노드의 값보다 큰 힙이며, 최소 힙은 그 반대입니다. 힙은 우선순위 큐와 같은 자료 구조에서 사용되어 최댓값 또는 최솟값에 빠르게 접근할 수 있습니다.
그래프를 나타내기 위한 자료 구조
인접 행렬 (Adjacency Matrix)
: 2차원 배열로 그래프를 나타내는 자료 구조입니다. 노드의 개수를 N이라고 할 때, N x N 크기의 행렬을 사용하여 노드 사이의 연결 관계를 표현합니다.
📌 장점: 인접한 노드의 존재 여부를 확인하기 쉽고, 간선의 존재 여부를 O(1) 시간에 확인할 수 있습니다.
📌 단점: 노드 수가 많고 간선이 적은 희소 그래프의 경우 메모리를 많이 사용하는 단점이 있습니다. 또한, O(V^2)의 공간을 요구하므로 공간 효율성이 떨어진다.
인접 리스트 (Adjacency List)
: 각 노드마다 인접한 노드들을 연결 리스트로 표현하는 자료 구조입니다. 노드의 개수를 N이라고 할 때, N개의 리스트를 사용하여 그래프를 표현합니다.
📌 장점: 인접한 노드들을 순차적으로 접근할 수 있으며, 메모리를 효율적으로 사용할 수 있습니다.
📌 단점: 특정 노드의 인접 여부를 확인하기 위해선 연결 리스트를 순회해야 하므로, 인접 행렬에 비해 느린 접근 시간이 소요됩니다.
밀집 그래프(dense graph)는 간선의 수가 최대 간선의 수에 가까운 그래프이다. 그와 반대로, 간선이 얼마 없는 그래프는 희소 그래프(sparse graph)라고 한다.
알고리즘에서 그래프
알고리즘 코딩테스트에서는 다양한 그래프 알고리즘과 그래프 기반의 문제들이 출제될 수 있습니다. 주요한 그래프 알고리즘과 문제 유형은 다음과 같습니다:
깊이 우선 탐색 (Depth-First Search, DFS)
: 그래프의 모든 노드를 탐색하고, 각 노드를 방문한 순서를 기록하는 알고리즘입니다. 주로 그래프 탐색, 사이클 판별, 연결 요소 확인 등에 사용됩니다.
문제 풀어보기
너비 우선 탐색 (Breadth-First Search, BFS)
: 그래프의 가까운 노드부터 탐색하는 알고리즘입니다. 주로 최단 경로 탐색, 미로 탐색, 연결된 구성 요소 확인 등에 사용됩니다.
문제 풀어보기
다익스트라 알고리즘 (Dijkstra's Algorithm)
: 가중치 그래프에서 시작 노드로부터 모든 다른 노드까지의 최단 경로를 찾는 알고리즘입니다.
문제 풀어보기
벨만-포드 알고리즘 (Bellman-Ford Algorithm)
: 가중치 그래프에서 시작 노드로부터 모든 다른 노드까지의 최단 경로를 찾는 알고리즘입니다. 음수 가중치를 가진 간선이 있는 경우에도 동작합니다.
문제 풀어보기
크루스칼 알고리즘 (Kruskal's Algorithm)
: 가중치 그래프에서 최소 신장 트리를 찾는 알고리즘입니다. 모든 간선을 가중치 순으로 정렬한 뒤, 사이클을 형성하지 않는 간선을 추가하여 트리를 형성합니다.
문제 풀어보기
프림 알고리즘 (Prim's Algorithm)
: 가중치 그래프에서 최소 신장 트리를 찾는 알고리즘입니다. 시작 노드에서부터 출발하여, 현재 트리와 연결되지 않은 노드 중 최소 가중치의 간선을 선택하여 트리를 확장합니다.
문제 풀어보기
위상 정렬 (Topological Sorting)
: 방향 그래프에서 노드들을 선형적으로 정렬하는 알고리즘입니다. 선행 관계가 있는 작업의 우선 순위를 결정하는 데 사용됩니다.
문제 풀어보기
최소 공통 조상 (Lowest Common Ancestor, LCA)
: 트리에서 두 노드의 가장 가까운 공통 조상을 찾는 알고리즘입니다. 주로 트리 구조를 활용한 문제에서 사용됩니다.
문제 풀어보기
이 외에도 그래프 기반의 다양한 문제 유형이 있을 수 있으며, 각 문제에 맞는 적절한 알고리즘을 선택하여 문제를 해결하는 것이 중요합니다.
잘보고갑니다!