Kyongineer

Floyd-Warshall algorithm 최단거리알고리즘중하나다. 모든 최단경로를 구하는 문제다. 거리를 저장하는 구조는 2차원 배열이된다. obtimal substructure의 개념을 이용하여 최단 경로를 찾는다. obtimal substructure란 : 특정한 경로안에 무수히 많은 경로가 있을 때, 중간 정점들이 각각 최단이 된다면 이를 모두 이은 경로 또한 최단이 된다. 사용관계 img D(i에서 j까지 정점 K를 경로에 포함할 수...

백준1943 최소공배수, 최대공약수 #include<iostream> #include <stdio.h> using namespace std; //유클리드 호제법 int gcd(int a, int b) { int c; while (b != 0) { c = a % b; a = b; b = c; } return a; } int lcm(int a, int b) { return a * b /...

백준1977 완전제곱수 #include <iostream> #define max_size 9 using namespace std; /* 89011483755109777 은 완전제곱수가 아닌데도 제곱근이 정수로 출력되는 것을 볼 수 있다. 소숫점 이하가 아주 작을 경우 버림을 해버리기 때문에 발생하는 일이다. 따라서 이것만으로는 완전제곱수인지 판단하기 어려우므로, 제곱근을 다시 제곱해서 원래의 수가 나오는지 확인해야 한다. */ int main() { int...

Union-Find 알고리즘 tree로 구현한 union-find알고리즘이다. find()함수와 union()함수는 최적화 과정을 넣었다. #include <iostream> #define max_size 9 using namespace std; int root[max_size]; int rankk[max_size]; //트리 높이 저장 void make_set() { for (int i = 1; i < max_size; i++) { root[i] = i; rankk[i] = 0; } } //최적화 find int find(int...

Prim 알고리즘 #include <cstdio> #include<algorithm> #include<vector> #include<queue> #include <functional> #define max_size 9 using namespace std; vector<vector<pair<int, int>>> edge;//도착지, weight priority_queue<pair<int, int>, vector<pair<int, int>>,greater<pair<int,int>>> pq; bool visited[10001]; int v, e, c, k; void prim(int v) { visited[v] = true; printf("visit : %d\n", v); for (auto u : edge[v]) { if (!visited[u.second])...