개발공부22 MST 알고리즘(크루스칼, 프림) 최소비용 신장트리 (Minimum Spanning Tree, MST)MST의 특징신장트리: 그래프의 모든 정점을 포함하며, 사이클이 없는 트리입니다.최소 비용: 간선 가중치의 합이 최소가 되는 트리입니다.유일성: 모든 간선의 가중치가 서로 다르면 MST는 유일합니다. 즉 여러 경로가 나올 수 없다는 것이다.MST 알고리즘MST를 구하는 알고리즘은 다음과 같은 두 가지 주요 방법이 있다.1. 크루스칼 알고리즘 (Kruskal’s Algorithm)방법: 간단하게 생각하면 sort하고 sort순서대로 간선연결하고 cycle이 발생하는지 검증만 하면 끝이다.그래프의 모든 간선을 가중치 기준으로 오름차순 정렬합니다.최소 가중치의 간선부터 하나씩 추가합니다.사이클이 발생하지 않는 경우에만 간선을 추가합니다.모든 .. 2024. 12. 7. Graph-다익스트라 알고리즘(Dijkstra Algorithm) 다익스트라 알고리즘이란?먼저 백번 글로 읽는 것 보다 움짤을 보자 1. 다익스트라 알고리즘의 특징그래프 유형: 방향 그래프 또는 무방향 그래프에 적용 가능.가중치 조건: 간선 가중치(Weight)가 음수일 수 없음.출발점 기준: 하나의 시작 정점에서 다른 모든 정점까지의 최단 경로를 계산.2. 알고리즘 동작 방식초기화:출발점 s에서 모든 정점까지의 거리 값을 무한대(∞)로 설정.출발점 s의 거리는 0으로 설정.우선순위 큐(최소 힙)를 사용하여 가장 가까운 정점을 효율적으로 추출.최단 거리 업데이트:현재까지 가장 짧은 경로로 방문하지 않은 정점을 선택.선택된 정점을 기준으로, 인접 정점의 거리 값을 업데이트.만약 새로운 경로가 기존 경로보다 짧다면, 해당 정점의 거리를 갱신.반복:모든 정점이 처리될 때까.. 2024. 12. 7. 그래프란?(Computer Science) bfs, dfs, scc, dag 1. 먼저 그래프란 뭘까?개체들과 개체들의 일대일 관계를 수학적으로 나타내는 표현 방법이다. 2. 그래프의 종류에는 이렇게 크게 세가지 정도가 있다.희소 그래프 (Sparse Graph): 간선의 수가 정점 수에 비해 상대적으로 적은 그래프.완전 그래프 (Complete Graph): 모든 정점이 서로 간선으로 연결된 그래프.밀집 그래프 (Dense Graph): 간선의 수가 정점 수에 비해 상대적으로 많은 그래프.3. 그리고 그래프의 기본 알고리즘은 bfs, dfs가 있는데 이를 응용한 알고리즘이 존재한다.BFS (Breadth-First Search)BFS는 그래프의 모든 정점을 층층이 탐색하는 알고리즘입니다. 큐(Queue)를 사용하여 시작 정점에서 가까운 정점부터 탐색한다.알고리즘 과정시작 정점.. 2024. 12. 6. 백준 1764 c++ https://www.acmicpc.net/problem/1764 이번에 set이라는 자로구조를 썼는데 집합과 같은 역할을 하는데 hash map을 기반으로 만들어져서 탐색이 빠르다는 장점이 있다. 그래서 사용했다.#include#include#include#includeusing namespace std;set unheard;vector notwo;int main() { int h, w; cin >> h >> w; for (int i = 0; i > temp; unheard.insert(temp); } for (int i = 0; i > temp; if (unheard.find(temp) != unheard.end()) { notwo.push_back(temp); } } sort(notwo... 2024. 12. 3. 백준 2606 그래프문제 C++ https://www.acmicpc.net/problem/2606 그냥 dfs로 순회했다.#include#include#include#includeusing namespace std;vector graph[101];bool visited[101] = { 0, };int v, n;int sum = 0;void dfs(int i) { visited[i] = true; for (int k : graph[i]) { if (visited[k] == false) { dfs(k); sum++; } }}int main() { cin >> v >> n; for (int i = 0; i > temp1 >> temp2; graph[temp1].push_back(temp2); graph[temp2].push_.. 2024. 12. 1. 백준 1966 C++ https://www.acmicpc.net/problem/1966 우선순위 큐가 있는지 모르고 vector로 sort돌려서 우선순위를 따로 체크했는데그냥 우선순위 큐를 쓰면 더 편하게 풀 수 있을 것 같다. #include#include#include#includeusing namespace std;struct MyStruct{ int num; int prior;};void solve(int n, int w) { queueq; vectorv; int num = 1; int vnum = 0; for (int i = 0; i > temp; q.push({i, temp}); v.push_back(temp); } sort(v.rbegin(), v.rend()); while (!q.empty()) { .. 2024. 11. 30. 이전 1 2 3 4 다음
