반응형 [C++로 배우는 알고리즘과 자료구조] Day 25: 다익스트라 알고리즘 (Dijkstra's Algorithm) 다익스트라 알고리즘 (Dijkstra's Algorithm)다익스트라 알고리즘은 가중치가 있는 그래프에서 단일 출발점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 음수 가중치가 없는 그래프에서 작동합니다.다익스트라 알고리즘의 시간 복잡도:일반적인 구현: (O(V^2))우선순위 큐를 사용한 구현 (힙): (O((V + E) \log V))다익스트라 알고리즘 구현그래프 구현 (인접 리스트 사용)#include #include #include #include #include // 그래프 클래스 정의class Graph {public: Graph(int vertices); void addEdge(int u, int v, int weight); // 간선 추가 vo.. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조] Day 12: 그래프 표현 방법 (인접 리스트, 인접 행렬) 그래프 표현 방법그래프는 다양한 방식으로 표현할 수 있습니다. 주요한 두 가지 방법은 인접 리스트와 인접 행렬입니다. 각 표현 방법은 공간 복잡도와 특정 연산에 대한 시간 복잡도에서 장단점이 있습니다.인접 리스트 (Adjacency List)인접 리스트는 그래프의 각 노드가 연결된 노드의 리스트를 가지는 방식으로 그래프를 표현합니다. 이 방법은 연결 리스트나 벡터를 사용하여 구현할 수 있습니다.인접 리스트의 특징:공간 복잡도: (O(V + E)), 여기서 (V)는 노드의 수, (E)는 간선의 수입니다.장점: 희소 그래프(Sparse Graph)에 적합하며, 메모리 사용이 효율적입니다.단점: 두 노드 간의 연결 여부를 확인하는 데 O(V)의 시간이 소요될 수 있습니다.인접 리스트 구현AdjacencyLis.. 2024. 8. 1. [C++로 배우는 알고리즘과 자료구조] Day 11: 그래프의 기본 개념 그래프 (Graph)그래프는 노드(정점, Vertex)와 간선(Edge)으로 구성된 자료구조로, 여러 노드가 간선으로 연결된 형태를 가집니다. 그래프는 다양한 문제를 모델링하고 해결하는 데 사용됩니다.그래프의 구성 요소:노드 (Vertex): 그래프의 개별 요소입니다.간선 (Edge): 노드 간의 연결을 나타냅니다.그래프의 종류:방향 그래프 (Directed Graph): 간선이 방향을 가지는 그래프입니다.무방향 그래프 (Undirected Graph): 간선이 방향을 가지지 않는 그래프입니다.가중치 그래프 (Weighted Graph): 간선에 가중치가 있는 그래프입니다.비가중치 그래프 (Unweighted Graph): 간선에 가중치가 없는 그래프입니다.그래프의 표현 방법그래프는 다음과 같은 방법으로.. 2024. 8. 1. [알고리즘] 9. 기타 그래프 이론 Index 1. 서로소 집합 자료구조 2. 서로소 집합을 활용한 사이클 판별법 3. 최소 신장 트리(크루스칼 알고리즘) 4. 위상 정렬 5. 추천 문제 6. 참고자료1. 서로소 집합 자료구조Disjoint Sets- 공통 원소가 없는 두 집합 서로소 집합 자료구조(= Union Find)- 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조- 두 종류의 연산을 지원- - Union: 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산- - Find: 특정한 원소가 속한 집합이 어떤 집합인지- 연결성을 통해 집합의 형태를 확인 (동작 과정)1) Union 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인 - A와 B의 루크 노드 A', B'를 각각 찾기 - A'를 B'.. 2024. 7. 20. [알고리즘] 7. 그래프 탐색 Index 1. 스택과 큐 2. 재귀 3. 유클리드 호제법 4. DFS 5. BFS 6. 추천 문제 7. 참고자료- Search란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정- 그래프 탐색 알고리즘으로 DFS/BFS가 있음 1. 스택과 큐Stack- FILO(First In Last Out)의 자료구조- 입구와 출구가 동일stack = []# 삽입stack.append(val)# 삭제stack.pop()# 최상단 원소 확인print(stack[-1])Queue- FIFO(First In First Out)의 자료구조- 입구와 출구가 양쪽으로 나있는 터널 형태queue = []# 삽입queue.append(val)# 삭제queue.pop(0)# 최하단/최상단 원소 확인queue[0]queue[-1.. 2024. 7. 19. [목차] 자료구조 1. 배열(Array)1.1 배열 정의1.2 배열 ADT1.3 프로그램 언어별 메서드2. 연결리스트(Linked List)2.1 연결리스트 정의2.2 연결리스트 종류: Singly Linked List, Doubly Linked List2.3 연결리스트 ADT2.4 연결리스트 구현2.5 프로그램 언어별 메서드3. 스택(Stack)3.1 스택 정의3.2 스택 ADT3.3 스택 구현3.4 프로그램 언어별 메서드4. 큐(Queue)4.1 큐 정의4.2 큐 ADT4.3 큐 구현4.4 프로그램 언어별 메서드5. 덱(Deque)5.1 덱 정의5.2 덱 ADT5.3 덱 구현5.4 프로그램 언어별 메서드6. 해시(Hash)6.1 해시 정의6.2 해시 ADT6.3 해시 구현6.4 프로그램 언어별 메서드7. 트리(Tree.. 2024. 7. 19. 이전 1 다음 반응형
