graph
-
[백준] MooTube알고리즘 2021. 8. 10. 21:47
문제 https://www.acmicpc.net/problem/15591 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net Approach 동영상 유사도 정보로 그래프를 만든 후 쿼리로 주어진 동영상을 시작점으로 하여 BFS를 돌려 각 동영상들의 유사도를 측정 이전 정보와 비교하여 더 낮은 유사도로 유사도(dist) 배열 업데이트 이 후 유사도 배열을 탐색해 K보다 유사도가 높은 것만 탐색 Code https://github.com/chi3236/algorith..
-
Graph자료구조 2019. 9. 3. 17:12
Vertex와 Edge로 이루어진 자료구조 G=(V,E) Undirected graph - Vertex를 잇는 Edge에 방향이 없는 그래프. 최대 edge 수 n(n-1)/2 (n은 vertex개수) Directed graph - Vertex를 잇는 Edge에 방향이 있는 그래프. 최대 edge 수 n(n-1) Connected component - 현재 연결성을 유지하면서 더 이상 vertex나 edge를 추가할 수 없는 최대한의 subgraph. connected graph에는 오직 하나의 connected component만이 존재 Cycle - 그래프에서 edge를 통한 순환. cycle은 DFS를 활용해 O(V+E)만에 찾을 수 있음 # 사이클 찾기 그래프 문제를 풀다 보면 '사이클을 찾아라'..
-
Disjoint Sets자료구조 2019. 9. 2. 18:55
n개의 원소를 하나의 자료구조로 합쳐 조작하고 탐색하기 용이하게 만드는 자료구조 n개의 원소가 n개의 set으로 초기화됨 (MakeSet()) Tree를 사용하는 것이 효율적. Tree의 구현은 각 node의 parents를 저장하는 배열로 (parents[i] = j) Union() -> 두 set을 하나의 set으로 합치는 작업 (O(n)) void simpleUnion(int i, int j) {parent[i] = j;} 효율적인 union을 위해 set의 height정보도 같이 저장하고 union시 높이가 낮은 set을 높이가 큰 set에 붙여서 합침 두 set의 height가 같으면 union된 set의 height 증가 Find() -> 어떤 set안에 특정 element가 들어있나 찾음(포..