Algorithm
-
algospot - picnicAlgorithm/알고스팟 2020. 1. 17. 02:36
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 //algospot - picnic #include #include using namespace std; int N, M; vector duo; vector sold; int ans; int check; void init() { check = ans = 0; cin >> N >> M; duo = vector(N); sold = vector(N, false); int x, y; for..
-
algospot - boardcoverAlgorithm/알고스팟 2020. 1. 17. 02:33
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 //algospot - boardcover #include #include using namespace std; int H, W; int ans; vector board; int xa1[4] = {1, 1, 0, 0}; in..
-
algospot - routingAlgorithm/알고스팟 2020. 1. 15. 06:56
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 //algospot - routing #include #include #include using namespace std; int N, M; vector adj; vector c; void init() { cin >> N >> M; adj = vector(N); c = vector(N, 0); int x, y; double z; for(int i = 0; i> x >> y..
-
DijkstraAlgorithm/그래프 2020. 1. 15. 04:06
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 //다익스트라의 최단 거리 알고리즘의 구현 //정점의 개수 int V; //그래프의 인접 리스트, (연결된 정점 번호, 간선 가중치) 쌍을 담는다. vector adj[MAX_V]; vector dijkstra(int src) { vector dist(V, INF); dist[src] = 0; priority_queue pq; pq.push(make_pair(0, src)); while(!pq.empty()) { int cost = -pq.top().first; int here = pq.top().second..
-
algospot - sortgameAlgorithm/알고스팟 2020. 1. 10. 17:26
시작 수열을 최소한 reverse해 정렬된 수열을 만드는것은 가능한 수열들을 정점으로 하고, 특정 수열에서 reverse를 했을때 만들어 질수 있는 수열들을 간선으로 연결한 그래프에서 시작정점(시작수열) 에서 목적지정점(정렬된수열) 까지의 최단거리를 구하는것과 같습니다. 따라서 그래프를 만들고, BFS를 사용하면 문제를 해결할수 있습니다. https://algospot.com/judge/problem/read/SORTGAME algospot.com :: SORTGAME Sorting Game 문제 정보 문제 중복이 없는 정수 수열이 주어진다. 이 때, 우리는 이 수열의 임의의 구간을 선택해서 해당 구간을 뒤집을 수 있다. 이 뒤집기 연산을 통해 전체 수열을 정렬하고 싶다. 그런데, 같은 수열도 두 가지 ..
-
BFSAlgorithm/그래프 2020. 1. 10. 15:33
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 //BFS //그래프의 인접 리스트 표현 vector adj; //start에서 시작해 그래프를 너비 우선 탐색하고 각 정점의 방문 순서를 반환한다. vector bfs(int start) { //각 정점의 방문 여부 vector discovered(adj.size(), false); //방문할 정점 목록을 유지하는 큐 queue q; //정점의 방문 순서 vector order; discovered[start] = true; q.push(start); while(!q.empty()) { int here = q.front(); q.po..
-
단절선 - 11400Algorithm/BOJ 2020. 1. 10. 15:20
무향그래프에서 dfs 스패닝트리를 만들고 특정 정점을 루트 노드로 하는 subtree에서 선조 노드로 갈수 있는 역방향 간선이 있는지 확인하는 방법을 사용해 풀었습니다. https://www.acmicpc.net/problem/11400 11400번: 단절선 첫째 줄에 두 정수 V(1≤V≤100,000), E(1≤E≤1,000,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B가 주어진다. 이는 A번 정점과 B번 정점이 연결되어 있다는 의미이며, 방향은 양방향이다. 그래프는 항상 연결되어 있으며, 같은 간선이 두 번 이상 들어오는 경우는 없다. 또, A와 B가 같은 경우도 없다. 그래프의 정점은 1..