전체 글

크루스칼 알고리즘 (Kruskal Algorithm)

가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘 최소 비용 신장 트리 Idea. 간선을 거리가 짧은 순서대로 그래프에 포함시키면 어떨까? 간선 정보를 오름차순으로 정렬한 뒤에 비용이 적은 간선부터 차근차근 그래프에 포함 유의사항. 사이클이 형성되면 안된다. --> 사이클이 발생하는지의 여부는 Union-Find알고리즘을 사용 순서. 1. 정렬된 순서에 맞게 그래프에 포함시킵니다. 2. 포함시키기 전 사이클 테이블을 확인. 3. 사이클을 형성하는 경우 간선을 포함하지 않습니다. #include #include #include using namespace std; int getParent(int parent[], int x) { if (parent[x] == x) return x; retur..

Union-Find(합집합 찾기)

대표적인 그래프 알고리즘 여러 개의 노드가 존재 시, 두 개의 노드를 선택해서 이 두 노드가 서로 같은 그래프에서 속하는지 판별하는 알고리즘 #include int getParent(int parent[], int x) { if (parent[x] == x) return x; return parent[x] = getParent(parent, parent[x]); } // 두 부모 노드를 합치는 함수 void unionParent(int parent[], int a, int b) { a = getParent(parent, a); b = getParent(parent, b); if (a < b) { parent[b] = a; } else { parent[a] = b; } } int findParent(int..

깊이 우선 탐색(Depth First Search, DFS)

깊이 우선 탐색은 스택이 사용된다. 굳이 스택을 사용하지 않더라도, 구현이 가능하다. 간단한 알고리즘을 사용 1. 스택의 최상단 노드를 확인합니다. 2. 최상단 노드에게 방문하지 않은 인접 노드가 있으면 그 노드를 스택에 넣고 방문처리합니다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 뺍니다. #include #include using namespace std; int number = 7; int c[7]; vector a[8]; void dfs(int x) { if (c[x]) return; c[x] = true; cout

너비 우선 탐색(Breadth First Search, BFS)

너비 우선 탐색은 탐색을 할 때 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘 너비 우선 탐색은 '최단 경로'를 찾아준다는 점! 준비물은 큐 #include #include #include using namespace std; int number = 7; int checked[7]; vector a[8]; void bfs(int start) { queue q; q.push(start); checked[start] = true; while (!q.empty()) { int x = q.front(); q.pop(); printf("%d ", x); for (int i = 0; i < a[x].size(); i++) { int y = a[x][i]; if (!checked[y]) { q.push(y); ..

큐(Queue)

큐도 스택에 이어 같이 나오는 자료구조이다. 큐의 특징은? 먼저 들어 간 데이터가 먼저 나온다 스택과 다르다 그래서 입구와 출구가 각각 다른 구조라고 생각하면 된다. 앞에 스택과 같이 STL라이브러리를 사용해 큐를 구현할 예정이다. 똑같이 결과 값을 예상하고, 코딩을 했으면 좋겠다. #include #include using namespace std; int main(void) { queue q; q.push(7); q.push(5); q.push(4); q.pop(); q.push(6); q.pop(); while (!q.empty()) { cout