ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • union find
    알고리즘/자료구조 2015. 6. 27. 11:04

    알고리즘 문제를 풀다 보면 노드들 간의 집합이 존재하는 경우가 있다.


    이때 해야할 일이 크게 두 가지 있다.

    1. 두 노드가 같은 집합에 포함되어 있는지, 다른 집합에 있는지 확인하는 작업

    2. 두 집합을 병합하는 작업



    사람마다 위 과정을 처리하는 방법이 모두 다르고 시간복잡도도 다르다.

    나 또한 무식하게 문제를 풀때는 O(n^2)이렇게 풀기도 했다. 


    하지만 위 작업을 최적화한 자료구조로 union find가 있다.

    (양교수님께서 알려주신 내용인데 당시에는 학점받기에 급급해 제대로 공부하지 못했다.)


    그림파일 올리려고 했는데 귀찮아서 못올리겠다

    http://blog.secmem.org/521

    좋은 블로그가 있으니 여기를 참고하길..





    '알고리즘 > 자료구조' 카테고리의 다른 글

    c++ priority_queue에서 comparator 선언해주는 방법  (0) 2015.08.26
    인덱스 트리  (0) 2015.07.07
    union find  (0) 2015.06.27
    오일러회로  (0) 2015.02.27
    트라이  (0) 2015.02.27
    트립(Treap)  (0) 2015.02.25

    댓글 0

Designed by Tistory.