서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조서로소 집합 자료구조는 두 종류의 연산을 지원한다 \- 합집합(Union): 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 \- 찾기(Find): 특정한 원소가 속한 집합이 어떤 집합
만약 우리가 여러 개의 단어들을 가지고있고, 그 단어들을 저장하고 검색하고싶다면 어떤 방식을 사용하면 좋을까? 우리가 배운 자료구조들은 많다. 예를들어 배열,리스트,트리,그래프,해시테이블등등말이다. 배열과 리스트를 적용시켜보자. 단순하게 일일이 비교해보면 된다. 하지만
만약 우리가 여러 개의 단어들을 가지고있고, 그 단어들을 저장하고 검색하고싶다면 어떤 방식을 사용하면 좋을까? 우리가 배운 자료구조들은 많다. 예를들어 배열,리스트,트리,그래프,해시테이블등등말이다. 배열과 리스트를 적용시켜보자. 단순하게 일일이 비교해보면 된다. 하지만
자신이 어떠한 입력값들 즉 리스트를 넘겨줬다고 하자. 그때 자신이 지정한 영역의 합을 구하고싶다. 만약 이때 자신이 입력한 리스트가 배열에 담겨있다고 할때는 이런 식으로 순차적 탐색을 통한 영역 질의 합을 구하게 된다. 참고로 여기서 시간 복잡도는 O(n)이다. 여기서
자신이 어떠한 입력값들 즉 리스트를 넘겨줬다고 하자. 그때 자신이 지정한 영역의 합을 구하고싶다. 만약 이때 자신이 입력한 리스트가 배열에 담겨있다고 할때는 이런 식으로 순차적 탐색을 통한 영역 질의 합을 구하게 된다. 참고로 여기서 시간 복잡도는 O(n)이다. 여기