/* 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘. 즉, 최소 비용 신장 트리를 만들기 위한 알고리즘. 예로 여러 도시가 있을 때 각 도시를 도로를 이용해 연결하고자 할 때, 비용을 최소한으로 하고자 사용되는 알고리즘. 노드 = 정점 = 도시 간선 = 거리 = 비용 모든 간선 정보를 오름차순으로 정렬한 뒤, 비용이 적은 간선부터 차례로 그래프에 포함시키면 됨. 사이클이 발생하면 안됨. 사이클 발생여부는 Union-find 적용. */ #include #include #include using namespace std; //부모 노드 가져오기. Union-Find 그대로 적용. int getParent(int set[], int x) { if (set[x] == x) return x; ..

/* Union-Find는 대표적인 그래프 알고리즘. 합집합찾기라는 의미. 서로소 집합(Disjoint-Set)알고리즘이라고도 부름. 여러 노드가 존재할 때, 두개의 노드를 선택해서 현재 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘. 모두가 연결되지 않은 각자 자기 자신만을 집합의 원소로 가지고 있을 때, 모든 값이 자기 자신을 가리키도록 만듬.(즉, 자신이 자신의 부모노드) 1 과 2 가 연결 되었을 때 이러한 연결성을 프로그래밍 언어로 어떻게 표현할 수 있을 지에 대한 내용이 바로 union-find. 재귀 함수를 통해 union(합침)이 완성. 일반적으로 부모를 합칠 때는 더 작은 값 쪽으로 합침. find알고리즘은 두개의 노드의 부모 노드를 확인하여 현재 같은 집합에 속하는지 확인하는..

/* 보다 깊은 것을 우선적으로 탐색하는 알고리즘. 맹목적인 탐색. 스택을 사용. 스택을 굳이 사용하지 않아도 구현 가능.(컴퓨터 구조적 특성으로 항상 스택의 원리를 사용) 그 자체로는 큰 의미가 없고, 다른 알고리즘에 적용되었을 때 의미가 있음. */ #include #include using namespace std; int number = 7; // 노드 갯수. int c[8]; // 접근확인 할 때 체크하기위한 배열. vector a[8]; void dfs(int x) { if (c[x]) //노드 방문처리를 했다면 리턴. return; c[x] = true; //노드 방문처리를 안했다면 방문처리. cout

/* 탐색을 할 때 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘. 맹목적인 탐색. 치단 경로를 찾아준다는 점에서 최단 길이를 보장해야 할 때 많이 사용. 큐를 사용. 그 자체로는 큰 의미가 없고, 다른 알고리즘에 적용되었을 때 의미가 있음. */ #include #include #include using namespace std; int number = 7; //원소의 갯수 int c[7]; //방문처리를 위한 배열 vector a[8]; //인덱스를 1부터 처리할려고 8. void bfs(int start) { queue q; q.push(start); c[start] = true; while (!q.empty()) { int x = q.front(); q.pop(); cout

#include #include using namespace std; int main() { queue q; q.push(1); q.push(2); q.push(3); q.push(4); q.pop(); q.pop(); q.push(5); while (!q.empty()) { cout

#include #include using namespace std; int main() { stack s; s.push(7); s.push(5); s.push(4); s.pop(); s.push(6); s.pop(); while (!s.empty()) { cout