본문 바로가기

알고리즘

 (6)
위상 정렬 알고리즘 (Topology Sort) 위상 정렬 알고리즘 : 순서가 정해져 있는 작업을 순차적으로 탐색하는 알고리즘 위와 같은 그래프가 주어졌을 때 화살표는 작업의 순서를 나타낸다. ex) 1이 끝나면 3을 시작할 수 있다. ex) 2와 3이 끝나면 5를 시작할 수 있다. 단순하게 자신으로 들어오는 indegree가 모두 제거되면 자신의 일을 시작하면 된다. #include #include #include using namespace std; vector a[10]; int indegree[10]; int n = 7; void topology() { queue q; for (int i = 1; i
플로이드 와샬 (Floyd Warshall) 플로이드 와샬 알고리즘 : 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘. 1. 시작점에서 목적지로 가는 경로에 한 정점을 지나갈 때 거리가 더 짧아지면 해당 경로로 갱신한다. 2. 모든 시작점과 모든 목적지 쌍에 대해 1을 반복한다. 당연히 O(n^3)이다. 그냥 코드만 봐도 3중첩 for문이다. 갱신될 때 마다 지나야 하는 k를 저장해두면 되돌아가면서 경로를 찾을 수 있다. #include using namespace std; int INF = 987654321; int PAD = 0; int dist[6][6] = // 그래프 셋팅 //직관적이기 쉽게 index0은 패딩으로 채움 { {PAD,PAD,PAD,PAD,PAD,PAD}, {PAD,0,6,8,INF,2}, {PAD, INF,0,..
다익스트라 알고리즘 (Dijkstra Algorithm) 다익스트라 알고리즘 : 한 정점에서 다른 정점들로 가는 최단경로를 구하는 알고리즘 그냥 기본적인 알고리즘은 노드를 선택할 때 계속 최단 거리의 노드를 찾아주어야 하기에 O(n^2) 시간복잡도가 걸린다. 그렇기에 넣을 때 logn시간이 걸리는 priority_queue를 사용하면 O(nlogn)시간 복잡도로 줄일 수 있다. 그렇기에 현재 코드는 priority_queue로 구현 하였다. 1. 시작노드에서부터 해당 노드로의 최단 거리(배열에 저장된 거리) 중 가장 짧은 노드 선택.(전에 선택된 것들 제외) 2. 선택된 노드에서부터 다음 노드로 가는 경로가 배열에 저장된 최단 경로보다 작으면 갱신 3. 1-2를 끝날 때까지 반복 1. 최단 거리가 갱신될 때마다 pre배열에 그 전 노드를 기록해둠. 2. 나중에..
크루스칼 알고리즘 (Kruskal algorithm) 최소 신장 트리 : 노드를 모두 연결하는 트리에서 가장 짧게 연결할 수 있는 트리 (가장 적은 비용으로 모든 노드를 연결) 크루스칼 알고리즘은 그래프가 주어졌을 때 최소 신장 트리를 찾는 알고리즘이다. 위 그래프에서 최소 신장 트리는 선으로 굵게 칠해진 부분들이다. 우선 크루스칼 알고리즘을 구현 하기전에 Union-Find 알고리즘을 알아야 한다. 또 다른 이름으로는 서로소 집합(disjoint-set)알고리즘 이라고도 부른다. 이 알고리즘은 두 개의 노드가 주어졌을 때 서로 같은 집합인지 아닌지 판별해준다. #include using namespace std; int d[11]; int n = 10; int find_parent(int a) //집합의 부모(루트)를 찾아줌 { if (d[a] == a)..
DFS (Depth First Search)(깊이 우선 탐색) DFS란 다음 분기로 넘어가기전에 해당 분기를 모두 탐색하는 탐색 방법입니다. 즉 임의의 노드에서 갈수있는 만큼 깊게 들어간 후 더 이상 진행할 수 없으면 그전으로 다시 돌아가 탐색을 시작합니다. 1을 시작으로 DFS 탐색을 한다면 1-2-3-6-7-4-5 이런 식으로 탐색이 진행됩니다. (인접해있는 노드 중 작은 노드부터 탐색한다고 가정했을 때) 물론 정확한 탐색순서는 저장되어있는 노드 순서에 따라 다르지만, 중요한 것은 하나의 노드로부터 가장 깊게까지 탐색을 하고 막히게 되면 그전으로 돌아가 다시 탐색을 진행한다는 것입니다. BFS는 큐를 사용하지만 DFS는 스택을 사용하여 쉽게 구현할 수 있습니다. 하지만 굳이 스택 STL을 이용하지 않고 재귀함수를 이용하면 편합니다. (재귀함수 자체가 스택처럼 저..
BFS (Breath First Search)(너비 우선 탐색) BFS란 임의의 노드에서 인접한 노드를 먼저 탐색하는 방법입니다. 즉 끝까지 깊게 먼저 탐색하는 dfs랑 대비됩니다. 1을 시작으로 bfs탐색을 한다면 (1)->(2->3)->(4->5->6->7) 이런 식으로 탐색을 합니다. 괄호를 친부분은 같은 거리를 표시한 것 입니다. 즉 괄호 안에서의 탐색 순서는 큐에 넣은 순서에 따라 달라지기 때문에 코드에 따라 달라질 수 있습니다. 그래프는 vector를 이용하면 쉽게 표현 할 수 있습니다. 위의 그래프는 아래와 같이 표현됩니다. a[1].push_back(2); //노드 1에서 노드 2로 연결 a[1].push_back(3); a[2].push_back(1); a[2].push_back(3); a[2].push_back(4); a[2].push_back(5)..

티스토리툴바