반응형 [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. [C++로 배우는 알고리즘과 자료구조] Day 7: 이진 탐색 트리 (BST) 이진 탐색 트리 (Binary Search Tree, BST)이진 탐색 트리(BST)는 각 노드가 최대 두 개의 자식 노드를 가지는 이진 트리의 일종으로, 왼쪽 서브트리의 모든 값은 루트의 값보다 작고, 오른쪽 서브트리의 모든 값은 루트의 값보다 큰 속성을 가집니다. 이러한 속성 덕분에 BST는 효율적인 검색, 삽입, 삭제 연산을 지원합니다.BST의 주요 연산:삽입 (Insert): 새로운 값을 트리에 삽입합니다.검색 (Search): 특정 값을 트리에서 검색합니다.삭제 (Delete): 트리에서 특정 값을 삭제합니다.순회 (Traversal): 트리의 노드를 특정 순서로 방문합니다.BST 구현BinarySearchTree.h#ifndef BINARYSEARCHTREE_H#define BINARYSEAR.. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조 심화] Day 7: 스킵 리스트 (Skip List) 스킵 리스트 (Skip List)스킵 리스트는 연결 리스트에 인덱스를 추가하여 검색, 삽입, 삭제 연산의 시간 복잡도를 (O(\log n))으로 개선한 자료구조입니다. 여러 레벨로 구성된 연결 리스트로, 각 레벨마다 원소를 건너뛰어가며 검색할 수 있습니다. 이는 균형 이진 탐색 트리와 유사한 시간 복잡도를 가지면서도 구현이 간단합니다.스킵 리스트의 주요 특징시간 복잡도:평균: (O(\log n))최악의 경우: (O(n))레벨 구조: 여러 레벨의 리스트로 구성되며, 각 레벨은 원소를 건너뛰어가며 검색할 수 있도록 합니다.확률적 균형 유지: 랜덤하게 레벨을 선택하여 원소를 삽입함으로써 확률적으로 균형을 유지합니다.스킵 리스트의 기본 연산삽입 (Insert): 새로운 원소를 삽입하고 레벨을 랜덤하게 결정합니다.. 2024. 8. 1. 이전 1 ··· 3 4 5 6 7 8 다음 반응형
