Algorithm
-
Union-Find algorithmAlgorithm/상호 배타적 집합 2020. 1. 30. 01:57
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 //최적화된 상호 배타적 집합의 구현 //트리를 이용해 상호 배제적 집합을 구현한다 struct OptimizedDisjointSet { vector parent, rank; OptimizedDisjointSet(int n) : parent(n), rank(n, 1) { for(int i = 0; i rank[v]) swap(u, v); //이제 rank[v]가 항상 rank[u]이상이므로 u를 v의 자식으로 넣는다 parent[u] = v; if(rank[u] == rank[v]) ++rank[v]; } }; Colored by Color Scripter cs Un..
-
algospot - promisesAlgorithm/알고스팟 2020. 1. 29. 22:40
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 //algospot - promises #include #include using namespace std; #define INF 100000000 int V, M, N; int ans; vector adj; void init() { ans = 0; cin >> V >> N >> M; adj = vector(V, vector(V, INF)); for (int i = 0; i x >> y >> r; if(..
-
algospot - drunkenAlgorithm/알고스팟 2020. 1. 29. 16:56
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 //algospot - drunken #include #include #include using namespace std; #define INF 1000000 int V, E; vector adj, ans; vector weight; void mkg() { cin >> V >> E; ans = adj = vector(V+1, vector(V+1, INF)); weight = vector(V); int x, y, r..
-
Floyd-Warshall algorithmAlgorithm/그래프 2020. 1. 23. 14:41
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 #include using namespace std; #define MAX_V 1111 //플로이드 알고리즘에서 실제 최단 경로 계산하기 //정점의 개수 int V; //그래프의 인접 행렬 표현 //adj[u][v] : u에서 v로 가는 간선의 가중치, 간선이 없으면 INF를 넣는다. int adj[MAX_V][MAX_V]; //via[u][v] : u에서 v까지 가는 최단 경로가 경유하는 점 중 가장 번호가 큰 정점 //-1로 초기화해 둔다 int via[MAX_V][M..
-
Karatsuba algorithmAlgorithm/분할정복 2020. 1. 21. 16:51
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 //카라츠바의 빠른 정수 곱셈 알고리즘 //a += b * (10^k);를 구현한다 void addTo(vector& a, const vector& b, int k); //a -= b;를 구현한다. a >= b를 가정한다. void subFrom(vector& a, const vector& b); //두 긴 정수의 곱을 반환한다. vector karatsuba(const vector& a, const vector& b) { int an = a.size(); bn = b.size(); //a가 b보다 짧을 경우 둘을..
-
Bellman-Ford algorithmAlgorithm/그래프 2020. 1. 20. 17:03
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 //벨만-포드 알고리즘의 구현 //정점의 개수 int V; //그래프의 인접 리스트, (연결된 정점 번호, 간선 가중치) 쌍을 담는다. vector adj[MAX_V]; //음수 사이클이 있을 경우 텅 빈 배열을 반환 vector bellmanFord(int src) { //시작점을 제외한 모든 정점까지의 최단 거리 상한을 INF로 둔다 vector upper(V, INF); upper[src] = 0; bool updated; //v번 순회한다 for (int iter = 0; iter
-
algospot - nthlonAlgorithm/알고스팟 2020. 1. 20. 06:08
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 //algospot - nthlon #include #include #include using namespace std; #define INF 1000000 int M; vector adj; void init() { cin >> M; adj = vector(400); int x, y, gap; for(int i = 0; i> x >> ..