본문 바로가기
반응형
[C++로 배우는 알고리즘과 자료구조 심화] Day 13: 이분 그래프 매칭 (Hopcroft-Karp 알고리즘) 이분 그래프 매칭 (Bipartite Graph Matching)이분 그래프 매칭은 두 개의 분리된 정점 집합을 가지는 그래프에서 최대 매칭을 찾는 문제입니다. 이분 그래프 매칭은 네트워크 플로우, 작업 할당 문제, 매칭 문제 등 다양한 응용 분야에서 사용됩니다.Hopcroft-Karp 알고리즘Hopcroft-Karp 알고리즘은 이분 그래프에서 최대 매칭을 찾는 효율적인 알고리즘입니다. 이 알고리즘은 BFS와 DFS를 결합하여 구현됩니다.Hopcroft-Karp 알고리즘의 시간 복잡도:(O(\sqrt{V}E)), 여기서 (V)는 정점의 수, (E)는 간선의 수입니다.Hopcroft-Karp 알고리즘 구현다음은 C++로 Hopcroft-Karp 알고리즘을 구현한 예제입니다. 그래프 클래스 정의#includ.. 2024. 8. 1.
[C++로 배우는 알고리즘과 자료구조 ] Day 10: 트라이 (Trie) 트라이 (Trie)트라이는 문자열을 효율적으로 저장하고 검색하기 위한 트리 기반 자료구조입니다. 트라이는 주로 문자열 집합의 검색, 삽입, 삭제에 사용되며, 접두사 검색에 매우 효율적입니다.트라이의 특징:노드 구조: 각 노드는 문자와 자식 노드를 가집니다.루트 노드: 루트 노드는 빈 문자열을 나타냅니다.경로: 문자열은 루트 노드에서 시작하여 각 문자에 해당하는 노드를 따라 내려가면서 표현됩니다.접두사 검색: 공통 접두사를 가진 문자열을 효율적으로 검색할 수 있습니다.트라이 구현TrieNode.h#ifndef TRIENODE_H#define TRIENODE_H#include // 트라이의 노드 구조체struct TrieNode { std::unordered_map children; // 자식 노드를 .. 2024. 8. 1.
[C++로 배우는 알고리즘과 자료구조 심화] Day 10: 위상 정렬 (Topological Sorting) 위상 정렬 (Topological Sorting)위상 정렬은 유향 비순환 그래프(DAG, Directed Acyclic Graph)의 정점을 순서대로 나열하는 방법입니다. 이 순서는 모든 간선 (u, v)에 대해 정점 u가 정점 v보다 먼저 나오는 순서를 의미합니다. 위상 정렬은 주로 작업 스케줄링, 컴파일러에서의 심볼 테이블 생성 등에 사용됩니다.위상 정렬의 주요 특징DAG: 위상 정렬은 반드시 유향 비순환 그래프에서만 가능합니다.순서: 정점 u에서 정점 v로 가는 모든 경로에 대해 정점 u는 정점 v보다 먼저 나옵니다.위상 정렬의 구현 방법Kahn's Algorithm: 진입 차수를 이용한 위상 정렬DFS 기반 알고리즘: 깊이 우선 탐색을 이용한 위상 정렬Kahn's AlgorithmKahn's Al.. 2024. 8. 1.
[C++로 배우는 알고리즘과 자료구조] Day 11: 그래프의 기본 개념 그래프 (Graph)그래프는 노드(정점, Vertex)와 간선(Edge)으로 구성된 자료구조로, 여러 노드가 간선으로 연결된 형태를 가집니다. 그래프는 다양한 문제를 모델링하고 해결하는 데 사용됩니다.그래프의 구성 요소:노드 (Vertex): 그래프의 개별 요소입니다.간선 (Edge): 노드 간의 연결을 나타냅니다.그래프의 종류:방향 그래프 (Directed Graph): 간선이 방향을 가지는 그래프입니다.무방향 그래프 (Undirected Graph): 간선이 방향을 가지지 않는 그래프입니다.가중치 그래프 (Weighted Graph): 간선에 가중치가 있는 그래프입니다.비가중치 그래프 (Unweighted Graph): 간선에 가중치가 없는 그래프입니다.그래프의 표현 방법그래프는 다음과 같은 방법으로.. 2024. 8. 1.
[C++로 배우는 알고리즘과 자료구조 심화] Day 11: 강한 연결 요소 (Kosaraju, Tarjan 알고리즘) 강한 연결 요소 (Strongly Connected Components, SCC)강한 연결 요소(SCC)는 방향 그래프에서 각 정점이 서로 도달 가능한 최대 부분 그래프입니다. 즉, SCC의 모든 정점 u, v에 대해 u에서 v로 가는 경로와 v에서 u로 가는 경로가 모두 존재합니다.Kosaraju's AlgorithmKosaraju's Algorithm은 그래프를 두 번의 DFS로 탐색하여 SCC를 찾는 알고리즘입니다.Kosaraju's Algorithm의 단계:DFS: 원본 그래프에서 DFS를 수행하여 정점을 완료된 순서대로 스택에 저장합니다.전치 그래프 생성: 모든 간선의 방향을 반전시킨 그래프를 만듭니다.DFS: 스택에서 정점을 꺼내어 전치 그래프에서 DFS를 수행합니다.Kosaraju's Alg.. 2024. 8. 1.
[C++로 배우는 알고리즘과 자료구조] Day 8: 균형 이진 탐색 트리 (AVL 트리) 균형 이진 탐색 트리 (AVL Tree)AVL 트리는 자가 균형 이진 탐색 트리의 일종으로, 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하로 유지되도록 합니다. AVL 트리는 삽입, 삭제 연산 후 트리의 균형을 유지하기 위해 회전을 사용합니다.AVL 트리의 특징:높이 균형: 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하입니다.높이 제한: AVL 트리의 높이는 (O(\log n))로 제한됩니다.시간 복잡도: 검색, 삽입, 삭제 연산의 평균 및 최악의 경우 시간 복잡도는 (O(\log n))입니다.AVL 트리의 주요 연산:삽입 (Insert)삭제 (Delete)검색 (Search)회전 (Rotation): 트리의 균형을 유지하기 위해 사용됩니다. (단순 회전과 .. 2024. 8. 1.
[C++로 배우는 알고리즘과 자료구조 심화] Day 8: 최소 신장 트리 (Minimum Spanning Tree) 심화 최소 신장 트리 (Minimum Spanning Tree, MST)최소 신장 트리(MST)는 가중치가 있는 연결된 무향 그래프에서 모든 정점을 포함하며, 간선의 가중치 합이 최소가 되는 트리입니다. MST를 찾는 대표적인 알고리즘으로는 크루스칼 알고리즘(Kruskal's Algorithm)과 프림 알고리즘(Prim's Algorithm)이 있습니다.크루스칼 알고리즘 (Kruskal's Algorithm)크루스칼 알고리즘은 간선을 가중치의 오름차순으로 정렬한 후, 사이클을 형성하지 않는 간선을 선택하여 MST를 구성하는 알고리즘입니다.크루스칼 알고리즘의 시간 복잡도:(O(E \log E + E \log V)), 여기서 (E)는 간선의 수, (V)는 정점의 수입니다.프림 알고리즘 (Prim's Algorit.. 2024. 8. 1.
[C++로 배우는 알고리즘과 자료구조] Day 9: 힙과 우선순위 큐 힙 (Heap)힙은 완전 이진 트리의 형태를 가지며, 각 노드가 특정한 우선순위를 가지는 자료구조입니다. 힙은 주로 최대값이나 최소값을 빠르게 찾기 위해 사용됩니다. 힙에는 최대 힙(Max-Heap)과 최소 힙(Min-Heap)이 있습니다.힙의 종류:최대 힙 (Max-Heap): 부모 노드의 값이 자식 노드의 값보다 크거나 같습니다.최소 힙 (Min-Heap): 부모 노드의 값이 자식 노드의 값보다 작거나 같습니다.우선순위 큐 (Priority Queue)우선순위 큐는 힙을 기반으로 구현되며, 각 요소가 우선순위를 가지는 큐입니다. 우선순위 큐는 삽입과 삭제 연산에서 우선순위에 따라 요소를 정렬합니다. 따라서 가장 높은 우선순위를 가진 요소를 O(log n) 시간 복잡도로 삽입하거나 삭제할 수 있습니다... 2024. 8. 1.
[C++로 배우는 알고리즘과 자료구조 심화] Day 9: 최단 경로 알고리즘 심화 (벨만-포드, 존슨 알고리즘) 최단 경로 알고리즘최단 경로 알고리즘은 가중치 그래프에서 주어진 두 정점 간의 최단 경로를 찾는 알고리즘입니다. 대표적인 알고리즘으로는 다익스트라 알고리즘(Dijkstra's Algorithm), 벨만-포드 알고리즘(Bellman-Ford Algorithm), 그리고 존슨 알고리즘(Johnson's Algorithm)이 있습니다.오늘은 벨만-포드 알고리즘과 존슨 알고리즘에 대해 심화 학습하겠습니다.벨만-포드 알고리즘 (Bellman-Ford Algorithm)벨만-포드 알고리즘은 음의 가중치가 있는 그래프에서 최단 경로를 찾을 수 있는 알고리즘입니다. 그러나 음의 사이클이 있는 경우에는 사용할 수 없습니다.벨만-포드 알고리즘의 시간 복잡도:(O(VE)), 여기서 (V)는 정점의 수, (E)는 간선의 수입.. 2024. 8. 1.
[C++로 배우는 알고리즘과 자료구조 심화] Day 6: 스플레이 트리 (Splay Tree) 스플레이 트리 (Splay Tree)스플레이 트리는 자가 조정 이진 탐색 트리입니다. 각 연산 후, 스플레이 연산을 통해 접근한 노드를 트리의 루트로 이동시킵니다. 이는 자주 접근하는 노드를 트리의 상위로 올려, 평균적으로 빠른 접근을 가능하게 합니다.스플레이 트리의 주요 특징자가 조정: 각 연산 후 접근한 노드를 루트로 이동시키는 스플레이 연산을 수행합니다.평균 시간 복잡도: (O(\log n)) (최악의 경우 시간 복잡도: (O(n)))회전 연산: 좌회전, 우회전, 좌-좌 회전, 우-우 회전, 좌-우 회전, 우-좌 회전을 포함한 회전 연산을 사용합니다.스플레이 트리의 기본 연산삽입 (Insert): 새로운 노드를 삽입하고 스플레이 연산을 수행합니다.삭제 (Delete): 특정 키를 가진 노드를 삭제하.. 2024. 8. 1.
반응형

티스토리툴바