반응형 분류 전체보기272 [알고리즘] 섬 연결하기 포인트 섬을 연결을 하는 방법은 무엇인가? 모든 섬이 최소 비용으로 연결되어 있어야 한다. 최단거리가 아님을 인지하자 (최소 비용으로 연결된 MST 를 구하는 문제이다. ) 결국은 연결되는 cost 를 전부 더해주는 것입니다. MST 를 구하는 알고리즘은 크루스칼(union, find 를 사용합니다), 프림 등이 있다. (저는 프림을 애정합니다. ) 시간 복잡도 O(n^2) 을 가지고 있다. c++ 에서는 우선 순위 큐에서 greater 를 통해서 만들 수 있고, python 은 heapq 모듈을 통해서 만들 수 있다. 🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 프림 알고리즘(min_heap 을 이용하여 구현) #include #include #include #include using na.. 2020. 10. 23. [알고리즘] c++ cpp 최소비용 구하기 포인트 1. 최단거리를 구하는 방법으로 다익스트라 알고리즘을 사용하였습니다. (모든 정점에서 최단거리를 구하는 것은 플로이드 와샬 알고리즘 - 다이나믹) 2. MST 하고 다른 것을 알면 좋다. priority_queue //min heap 🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. #include #include #include using namespace std; int n, m; int s, e, c; int start, arrive; int dist[1001]; vector map[1001]; int main() { cin >> n >> m; for (int i = 0; i > s >> e >> c; map[s].push_back({c, e}); // .. 2020. 10. 22. [알고리즘] 최단 경로(다익스트라), MST (프림) 포인트 1. 다익스트라 알고리즘과 프림 알고리즘은 거의 차이가 없다. 다익스트라는 값을 계속해서 더해서 나간다고 생각을 하면 된다. 다익스트라 #include #include #include using namespace std; vector map[101]; vector dijkstra(int start, int goal) { vector dist (goal, 9876554321); dist[start]=0; priority_queue pq; pq.push ({ 0, start }); while(!pq.empty()) { int x, cost; tie (cost, x)=pq.top (); pq.pop (); if (dist[x] < cost) continue; for(auto ele : map[x]) {.. 2020. 10. 22. [알고리즘] c++ cpp Minimum Depth of Binary Tree 포인트 1. 이진트리의 깊이를 아는 방법, 이진트리는 dfs로 들어간다. 2. 이진트리는 왼쪽 오른쪽 🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. #include using namespace std; struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode() : val(0), left(nullptr), right(nullptr) {} TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {} }; class Solution {.. 2020. 10. 22. 이전 1 ··· 44 45 46 47 48 49 50 ··· 68 다음 반응형