[알고리즘] 집합

01. 집합과 상호배타적 집합의 개념

집합

• 순서와 중복이 없는 원소들을 갖는 자료구조
• 상호배타적 집합: 교집합이 없는 집합 관계
  • ex. A = {1,2,3} 과 B = {4,5,6,7}
  • 활용 알고리즘
    • 이미지 분할
      • 이미지를 서로 다른 부분으로 나누는 데 사용
      • ex. 사람과 배경을 겹치지 않게 분할
    • 도로 네트워크 구성
      • 도로 구축시 각 도로를 서로 교차하지 않도록 설계하는 데 사용
    • 최소 신장 트리 알고리즘 구현
      • 간선을 추가할 때마다 사이클을 형성하는지 여부를 체크할 때 사용
    • 게임 개발
      • 캐릭터의 동작 자연스럽게 구현 가능
      • ex. 플레이어와 적군 충돌 시 두 캐릭터가 겹치지 않도록 함
    • 클러스터링 작업
      • 각 작업이 서로 겹치지 않도록 구성 가능
      • 작업 간의 의존 관계가 없으면 동시에 여러 작업 진행 가능

02. 집합의 연산

• 보통 집합은 트리로 표현
  • 대표적인 연산: 합치기, 탐색

(1) 배열을 활용한 트리로 집합 표현

• 집합은 배열을 활용한 트리로 구현
  • 각 집합에는 대표 원소가 있어야 함
• 대표 원소
  • 집합의 원소 중 집합을 대표하는 역할
  • 트리의 루트 노드
• 배열로 집합 표현
  • 하나의 배열로 상호배타적 관계를 가지는 집합을 모두 표현한다는 것
  • 배열의 인덱스는 자신, 배열 값은 부모 노드를 의미
    • disjoint_set[9] = 3 ⇒ 노드 9의 부모는 3
    • 루트 노드는 값 자체가 배열의 인덱스와 동일
  • 배열의 크기는 가장 큰 원소 + 1
    • 보통 0 사용 안 하므로
  • 예시
    
    • 각 집합의 루트 노드는 1과 4
      • disjoint_set[1] = 1
      • disjoint_set[4] = 4
    • 배열 크기는 10
    • 원소 3은 원소 1이 루트 노드인 집합에 속함
      • disjoint_set[3] = 2
      • disjoint_set[2] = 1
      • disjoint_set[1] = 1
    • 구현
    • 초기 상태: 자기 자신을 부모 노드로
      

      disjoint_set = { -1, 1, 1, 2, 4, 1, -1, -1, 4, 3};
      

    • 집합 완성
      

      int{} disjoint_set = { -1, 1, 2, 3, 4, 5, -1, -1, 8, 9};
      

(2) 유니온-파인드 알고리즘

• 집합 알고리즘에 주로 쓰이는 연산
  • 유니온: 합치기
  • 파인드: 탐색
  • 활용 시나리오
    • 조건: 여러 개의 그룹이 형성되어 있음
    • 문제: 특정 원소가 주어졌을 때, 이 원소들이 같은 그룹인지 판단해야 할 경우
• 파인드 연산
  • 특정 노드의 루트 노드가 무엇인지 탐색하는 방법
    • 보통 특정 노드가 같은 집합에 있는지 확인할 때 사용
      • 어느 두 노드의 루트 노드가 서로 같다면 같은 집합에 속한 것
  • 과정
    1. 현재 노드의 부모 노드 확인 → 부모 노드가 루트노드면 찾기 연산 종료
    2. 찾기 연산이 종료되지 않으면 전 단계를 반복
  • 재귀 함수로 구현
    • 최악의 경우 시간 복잡도 O(N)
      
      • find(4) 수행해서 루트노드가 1임을 알면 노드 2,3,4는 루트 노드가 아님이 명확하므로 find(4)를 다시 수행했을 때 노드 2,3을 다시 확인할 이유가 없음
      • 경로 압축
        • 파인드 연산의 연산 비용 문제 해결
        • 집합 형태를 유지하면서도 트리 높이를 줄이면 됨
          
• 합치기 연산
  • 두 집합을 하나로 합치는 연산
    • 두 집합의 루트 노드를 같게 하는 것
    • 루트 노드는 두 집합의 루트 노드 중 하나가 되면 됨
  • 과정
    1. 주어진 두 노드의 루트 노드를 파인드 연산을 통해 찾음
    2. 각 노드가 속한 집합을 합침
       1. 두 집합의 루트 노드를 같게 함
       2. 루트 노드는 두 집합 중 어떤 노드로 해도 상관 X
  • 예시: A와 B의 말단 노드 중 임의의 노드 5와 7의 루트 노드를 찾는 경우
    
    • 1. 배열

         int{} disjoint_set = { -1 , 1, 2, 1, -1, 1, -1, 2, -1, 2};

      2. 루트 노드가 2인 집합의 루트 노드를 1로 바꿈 
         
  • 랭크
    
    • 합치기 연산 비용 문제 해결
      • 트리의 깊이가 깊을수록 연산 비용 커짐
    • 현재 노드를 기준으로 하였을 때 가장 깊은 노드까지의 경로 길이
    • 랭크 기반 합치기 연산
      
      1. 두 노드의 루트 노드를 구함
      2. 1에서 구한 루트 노드의 랭크를 비교
         1. 랭크 값이 다르면 랭크값이 큰 루트 노드를 기준으로 삼음
            1. 랭크가 더 큰 루트 노드를 랭크가 작은 루트 노드의 부모 노드로 바꿈 (트리의 깊이는 더 깊어지지 않으므로 랭크의 값은 변하지 않음)
               
         2. 랭크값이 같으면 루트 노드를 아무거나 선택해서 바꾸고 최종 루트 노드의 랭크 1을 더함