알고리즘 이론
-
너비 우선 탐색을 통한 최단거리 구해보기알고리즘 이론/알고리즘 구현 2019. 9. 3. 02:47
너비 우선 탐색(BFS) 은 그래프에서의 최단 경로 문제를 푸는 용도로 사용 된다. 최단 경로 문제는 두 정점을 연결하는 경로 중 가장 길이가 짧은 경로를 찾 는문제 이다. 코드 ( C ++ ) #include #include #include #include using namespace std;vector adj; // start에서 시작해 그래프를 너비 우선 탐색하고 시작점부터 각 정점까지// 최단 거리와 너비 우선 탐색 스패닝 트리 계산// distance[i] = start부터 i까지의 최단 거리// parnet[i] = 너비 우선 탐색 스패닝 트리에서 i 의 부모의 번호, 루트일 경우 자신의 번호void bfs2(int start, vector& distance, vector& parent){di..
-
그래프의 너비 우선 탐색알고리즘 이론/알고리즘 구현 2019. 9. 3. 02:31
너비 우선 탐색(BFS)는 시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘이다. 너비 우선 탐색은 깊이 우선 탐색과는 달리 발견과 방문이 같지 않다. 1. 아직 발견되지 않은 상태 ( 큐에 넣기 전) 2. 발견되었지만 아직 방문되지 않은 상태 ( 큐에서 대기 중) 3. 방문된 상태 ( 큐에서 꺼낸다 ) 너비 우선 탐색이 시작점인 0 을 방문하면 정점 1 3 4 8이 목록에 추가 된다. 이들은 모두 0에서 간선 하나로 연결되기에 어느 정점을 먼저 꺼내도 상관 없다. 이 중 1을 꺼내 방문했다고 하면 2가 목록에 추가 된다. 이때 2는 자신보다 먼저 목록에 추가된 남은 정점 3 4 8이 방문되기 전까지는 결코 방문되어서는 안된다. 이를 구현하는 방법은 목록에 먼저 넣은 정점을 항상 먼저 꺼내야 하..
-
오일러 서킷을 찾아내는 알고리즘알고리즘 이론/알고리즘 구현 2019. 8. 28. 02:47
오일러 서킷이란? 깊이 우선 탐색을 이용해 풀 수 있는 유명한 문제로, 그래프의 모든 간성르 정확히 한 번씩 지나서 시작점으로 돌아오는 경로를 찾는 문제이다. 모든 정점이 짝수점이면서, 간선들이 하나의 컴포넌트에 포함된 그래프가 주어진다면 항상 오일러 서킷을 찾아내는 알고리즘을 만들 수 있다. findRandomCircuit(u)는 u와 인접한 간선들을 하나하나 검사하면서, 아직 방문하지 않은 간선 (u,v)가 있다면 또다시 findRandomCircuit(v)를 호출. 더이상 따라갈 간선이 없다면 재귀 호출 종료후 반환한다. 재귀 호출이 끝나고 반환할 때 경로에 추가해줌 으로서 경로의 끝점부터 역순으로 간선들이 추가된다. 코드 ( C+ + ) #include #include using namespace..
-
그래프의 깊이 우선 탐색알고리즘 이론/알고리즘 구현 2019. 8. 25. 02:45
깊이 우선 탐색(DFS)은 그래프의 모든 정점을 발견하는 가장 단순하고 고전적인 방법이다. 현재 정점과 인접한 간선들을 하나씩 검사하다가, 아직 방문하지 않은 정점으로 향하는 간선이 있다면 그 간선을 무조건 따라가는 것. 이 과정에서 더이상 갈 곳이 없는 막힌 정점에 도달하면 포기하고, 마지막에 따라왔던 간선을 따라 뒤로 돌아간다. 그래프에서는 모든 정점들이 간선을 통해 연결되어 있다는 보장이 없기 때문에, dfs() 만으로는 모든 정점을 순서대로 발견한다는 목적에 부핮하지 않는다. 따라서 dfsAll()을 통해 모든 정점을 방문해야 한다. 코드 ( C++ ) #include #include #include using namespace std; //그래프의 인접 리스트 표현vector adj;// 각 정..
-
크루스칼의 최소 스패닝 트리 알고리즘알고리즘 이론/알고리즘 구현 2019. 8. 23. 02:25
크루스칼 알고리즘은 그래프의 모든 간선을 가중치의 오름차순으로 정렬한 뒤, 스패닝 트리에 하나씩 추가해 간다. 가중치가 작다고 해서 무조건 간선을 트리에 더하는 것은 아니다. 결과적으로 사이클이 생기는 간선은 고려에서 제외해야 한다. 간선을 트리에 추가했을 때 이미 추가한 간선들과 합쳐 사이클을 이루는지 여부를 판단하는 부분이 크루스칼 알고리즘의 핵심이다. 이는 상호 배타적 집합 자료 구조를 통해 구현한다. 코드 ( C ++ ) #include #include #include using namespace std; // DisjointSet은 상호 배타적 집합 구현struct DisjointSet {vector parent, rank;DisjointSet(int n) : parent(n), rank(n) ..
-
플로이드 알고리즘알고리즘 이론/알고리즘 구현 2019. 8. 18. 01:28
모든 정점에서 모든 정점으로의 최단 경로를 구하고 싶다면 플로이드 알고리즘을 사용하자. 코드 ( C++ )// 플로이드 알고리즘으로 최단 거리와 최단 경로를 구해 보자.#include #include #include #include using namespace std;const int MAX = 100;// 그래프의 인접 행렬 표현// adj[u][v] = u 에서 v로 가는 간선의 가중치. 간선이 없으면 아주 큰 값을 넣는다.int adj[MAX][MAX];// via[u][v] = u에서 v까지 가는 최단 경로가 경유하는 점 중 가장 번호가 큰 정점int via[MAX][MAX];// 정점의 개수int V;// 플로이드의 모든 쌍 최단 거리 알고리즘void floyd(){for (int i = 0; ..
-
에라토스테네스의 체알고리즘 이론/알고리즘 구현 2019. 8. 15. 18:55
에라토스테네스의 체 에라토스테네스의 체는 소수 관련 문제를 풀 때 가장 자주 사용되는 방법입니다. 소수란 '양의 약수를 두개만 가지는 자연수' 를 의미합니다. 이러한 소수를 대량으로 빠른 시간 내에 구하는 방법이 에라토스 테네스의 체 입니다. -지워지지 않는 수를 찾을때는 루트 n까지만 찾습니다. 소수 판정 알고리즘과 동일한 최적화. - 배수들을 지울 때 i*i에서 시작합니다. 2*i는 이미 2의 배수를 지워졌을때 지워 졌을것 3*i도 마찬가지 코드 ( C++ ) #include #include #include using namespace std; int n;// 소수인지 아닌지// IsPrime[i] = i 가 소수인가?bool IsPrime[101];void eratosthenes() {// 1로 I..
-
다익스트라 알고리즘알고리즘 이론/알고리즘 구현 2019. 8. 11. 18:11
다익스트라의 최단 경로 알고리즘 다익스트라 알고리즘은 단일 시작점 최단 경로 알고리즘으로, 시작 정점 s에서부터 다른 정점들까지의 최단 거리를 계산한다. 다익스트 라 알고리즘은 너비 우선 탐색과 유사한 형태를 가진 알고리즘으로 가까운 순서대로 정점을 방문해 가지만 가중치가 있는 그래프에서는 너비 우선 탐색을 그대로 적용할 수 없다. 너비 우선 탐색은 각 정점을 발견한 순서대로 방문하지만 다익스트라 알고리즘은 더 늦게 발견 한 정점이라도 더 먼저 방문할 수 있어야 한다. 코드 ( C++ )// 우선순위 큐를 이용해서 구현한 다익스트라 알고리즘#include #include #include #include using namespace std;const int MAX_V = 100;const int INF =..