집합

집합

1. 자료구조 개념:

• 순서와 중복이 없는 원소들을 갖는 자료구조
• 종류:
  • 유한 집합: 원소 개수가 유한
  • 무한 집합: 원소 개수가 무한
  • 상호 배타적 집합: 교집합이 없는 집합 관계
    • 공통 원소가 있는것은 상호 배타적인 것이 아니다.

2. 해당 자료구조를 활용하는 분야:

   • 그래프 알고리즘에서 많이 활용한다.
   • 이미지 분할: 이미지를 서로 다른 부분으로 나누는데 사용
     • 예) 사람과 배경을 겹치지 않게 분할하는 데 사용
   • 도로 네트워크 구성: 토로를 구축할 때 각 도로를 서로 교차하지 않도록 설계하는 데 사용가능, 교차로의 혼잡을 줄일 수 있다.
   • 최소 신장 트리 알고리즘 구현: 최소 신장 트리 알고리즘을 구현에서 간선을 추가할 때마다 사이클을 형성하는지 여부를 체크할 때 사용
   • 게임 개발: 캐릭터 동작을 자연스럽게 구햔 가능
     • 플레이어와 적군이 충돌할 때 이 두 캐릭터가 겹치지 않도록 하는데 사용 가능
   • 클러스터링 작업: 각 작업이 서로 겹치지 않도록 구성 가능, 작업 간의 의존 관계가 없으면 동시에 여러 작업을 진행 할 수 있다.

3. 자료구조의 시간 복잡도:

   • O(N)

4. 상세 내용:

   • 배열을 활용한 트리로 집합 표현
     • 대표 원소: 집합의 원소 중 집합을 대표하는 역할, 집합의 형태를 트리로 표현할 것이기 때문에 루트노드

       개념적으로 집합의 대표 원소와 루트 노드는 같다.

     • 배열의 인덱스는 자신을, 배열값은 부모 노드를 의미한다.
       • 배열의 인덱스가 모든 딥합의 원소를 표현할 수 있을 정도로 배열의 크기가 존재하면 된다.
     • 배열내의 각 노드는 자기 자신을 루트 노드로 설정, 집합에 없는 인덱스의 값은 -1로 설정

5. 유니온-파인드 알고리즘

   • 집합 알고리즘에 주로 쓰이는 연산은 합치기와 탐색
   • 합치기는 유니온(union), 탐색을 파인드(find), 둘을 묶어 유니온-파인드 알고리즘이라한다.
   • 파인드 연산
     • 특정 노드의 루트노드가 무엇인지 탐색하는 방법
     • 특정 노드가 같은 집합에 있는지 확인할 때 사용
       • 예) A,B 두 노드가 있을 때, 노드의 루트 노드가 서로 같다면 같은 집합에 속한 것
     • 찾기 연산: 특정 노드부터 재귀로 거슬러 올라가며 루트 노드를 찾았던 과정
       1. 현재 노드의 부모 노드 확인, 부모 노드가 루트 노드이면 찾기 연산을 종료
       2. 1에서 찾기 연산이 종료되지 않으면 1을 반복
       • 최악의 경우 시간 복잡도 O(N) => 경로 압축으로 해결
   • 경로 압축
     • 효율적으로 파인드 연산을 하기 위해서는 집합 형태를 유지하면서도 트리 높이를 줄이면 된다.
     • 트리의 높이를 줄이므로 파인드 연산의 부모 노드를 거치는 과정을 줄일 수 있다.
     • 트리 깊이가 낮아지면 최악의 경우 수행해야 할 연산 횟수가 줄어듬을 의미한다.
   • 유니온 연산
     • 두 집합을 하나로 합치는 연산
     • 두 집합의 루트노드를 같게 하는 것, 두 집합의 루트 노드 중 하나가 되면 된다.
     1. 두 집합에서 찾기 연산을 통해 루트 노드를 찾는다.
     2. 찾은 두 루트 노드의 값을 비교한다.
     3. 두 집합을 합친다. 두 집합의 루트 노드를 같게한다. 이떄, 루트 노드는 두 집합 중 어떤 루트 노드로 해도 상관 없다.
     • 단점 : 트리의 깊이가 깊어지면 깊어질 수록 연산 비용이 커진다.
   • 유니온 연산 비용 문제는 랭크로 해결
     • 랭크: 현재 노드를 기준으로 하였을 때 가장 깊은 노드까지의 경로 길이
     • 랭크 기반으로 유니온 연산 하기
       1. 두 노드의 루트 노드 구하기
       2. 구한 루트 노드의 랭크를 비교
          1. 랭크 값이 다르면 큰 르투 노드를 기준으로 삼는다. 랭크가 더 큰 루트 노드를 랭크가 작은 루트 노드의 부모노드로 변경.
          2. 랭크 값이 같으면 아무거나 선택해서 바꾸고 최종 루트 노드의 랭크에 1을 더함