Algorithm
-
단절점 - 11266Algorithm/BOJ 2020. 1. 10. 15:15
무향그래프에서 dfs 스패닝트리를 만들고 특정 정점을 루트 노드로 하는 subtree에서 선조 노드로 갈수 있는 역방향 간선이 있는지 확인하는 방법을 사용해 풀었습니다. https://www.acmicpc.net/problem/11266 11266번: 단절점 첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B가 주어진다. 이는 A번 정점과 B번 정점이 연결되어 있다는 의미이며, 방향은 양방향이다. 입력으로 주어지는 그래프는 연결 그래프가 아닐 수도 있다. www.acmicpc.net 1 2 3 4 5 6 7 8 9 10 11 12 13..
-
algospot - wordchainAlgorithm/알고스팟 2020. 1. 10. 15:08
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 95 96 //Algospot - WORDCHAIN #include #include #include using namespace std; int N; int sidx, eidx, tidx; bool c_flag; vector..
-
algospot - dictionaryAlgorithm/알고스팟 2020. 1. 10. 15:01
dictionary를 풀어보았습니다. dfs를 이용한 위상정렬로 해결할수 있었습니다! https://algospot.com/judge/problem/read/DICTIONARY algospot.com :: DICTIONARY 고대어 사전 문제 정보 문제 아마추어 고고학자인 일리노이 존스는 시카고 근교에서 고대 문명의 흔적을 찾아냈습니다. 그 흔적 중에는 이 언어의 사전도 포함되어 있었는데, 이 사전에 포함된 단어들은 모두 영어의 소문자 알파벳으로 구성되어 있었지만 사전에 포함된 단어의 순서들이 영어와 서로 달랐습니다. 발굴팀은 단어들이 사전 순이 아닌 다른 순서대로 정렬되어 있는지, 아니면 알파벳들의 순서가 영어와 서로 다른 것인지를 알고 싶어합니다. 일리노이 존스는 이 언어 algospot.com 1 ..
-
DFSAlgorithm/그래프 2020. 1. 10. 14:47
시간복잡도 O(|V|+|E|) (인접행렬일 경우 O(|V^2|)) 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2