집합

1. 집합?

• 순서와 중복이 없는 원소를 갖는 자료구조
• 예시
  • A 그룹 원소가 { 1, 1, 2, 3} 이라면 집합으로 생각할 때 중복된 1 빼고 {1, 2, 3}
• 종류
  • 유한집합 : 원소 갯수가 유한
  • 무한집합 : 원소 갯수가 무한
  • 공집합 : 원소가 없음
• 상호배타적 집합?
  • 교집합이 없는 집합 관계

집합 A랑, B는 상호배타적임. 왜냐? 교집합(공통원소)이 없으니까

• 코테서 어떻게 활용?
• 그래프 알고리즘 
• 이미지 분할 : 사람과 배경을 겹치지 않게 분할 할 때
• 도로 네트워크 구성 : 도로 구축 시, 서로 교차하지 않도록 설계
• 최소 신장 트리알고리즘 : 간선 추가시마다 사이클 형성하는지 체크할 때
• 게임 개발: 플레이어랑 에너미가 오버랩할 때 겹치지 않도록 처리할 때
• 클러스터링 작업: 각 작업이 겹치지 않도록 구성

2. 집합의 연산?

• 집합은 배열 활용해서 트리로 구현함
  • 각 집합에는 대표원소가 있어야 함 -> 대표 원소가 뭔데? (트리로 봤을 때 루트 노드임)
  • 배열 활용한단 말은? -> 하나의 배열로 상호배타적 관계를 가지는 집합을 모두 표현
    
    • 배열의 인덱스는 자신/ 배열 값은 부모노드임
    • 배열의 크기: 가장 큰 원소 값 +1
• 대표 연산은 합치기, 탐색

집합A를 배열로 표현했다 : 인덱스는 자신의 노드값, 배열의 값은 부모노드 값

 

3. 집합 표현하기 연습!

• 각각 루트노트가 8, 2임(루트노드는 인덱스와 값이 같음)
  
  • disjoint_set[8] = 8
  • disjoint_set[2] = 2
  • disjoint_set[1] = 7
  • disjoint_set[7] = 2
  • disjoint_set[2] = 2
• 배열 크기는 가장 큰 원소값 +1 이니까 여기선 9로 정하면 됨

집합에 없는 인덱스 값들은 -1로