Union

서로소 집합(Disjoint-set)

📔 서로소 집합(Disjoint-set) 이란 서로소 또는 상호배타 집합들은 서로 중복 포함된 원소가 없는 집합들( 교집합이 없는 상태 ) 집합에 속한 하나의 특정 원소를 통해 각각의 집합들을 구분 ( 이를 대표자라고 함 ) 상호 배타 집합을 표현하는 방법 연결 리스트 같은 집합의 원소들은 하나의 연결리스트로 관리 연결리스트의 맨 앞의 원소를 집합의 대표로 한다 각 원소는 집합의 대표원소를 가리키는 링크를 갖는다 트리 하나의 집합을 트리로 표현 자식 노드가 부모 노드를 가리키며 루트 노드가 대표자가 됨 상호배타 집합 연산 make_set(x) find_set(x) union(x,y) 📔 서로소 집합(Disjoint-set) 구현 def make_set(x): p[x] = x def find_set(x):..

[python] 집합 자료형 set()

📗 집합 set() set은 리스트와 비슷하게 볼 수 있다. 하지만 인덱스로 접근이 불가능하고, 정렬도 할 수 없다. for 문으로 하나하나 출력해봐도 그때 그때 순서가 뒤죽박죽으로 다르게 나온다. set 을 사용하는 이유는 중복이 없다 특정 원소가 있는 지 확인할 때 O(1)의 시간 복잡도를 가진다. ( 리스트의 경우 O(N) ) ex) if 원소 in 셋: 집합 관련 🔵 교집합, 합집합, 차집합 교집합: & or intersection 합집합: | or union 차집합: - or difference set1 = {1, 2, 3, 4, 5} set2 = {3, 4, 5, 6, 7} # 교집합 print(set1.intersection(set2)) # {3, 4, 5} print(set1 & set2)..