[자료구조] 집합

김방울·2026년 6월 16일

자료구조

코딩테스트

목록 보기

5/5

집합

순서와 중복이 없는 원소들을 갖는 자료구조
A라는 그룹의 원소 구성이 {1, 6, 6, 6, 4, 3} 이면, 집합으로 생각 할 때 중복을 제외하고 {1, 6, 4, 3} 으로 생각해야 함

상호배타적 집합

서로 교집합이 없는 집합 관계
A = {1, 2, 3} 이고 B = {4, 5, 6, 7} 일 때 집합 A와 집합 B의 원소 중 겹치는 원소가 없으면 교집합이 없다고 할 수 있음

상호배타적 집합의 특성을 활용하는 분야

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

집합의 연산

보통 집합은 트리로 표현하며, 대표적인 연산은 합치기(Union)와 탐색(Find)이 있음

배열을 활용한 트리로 집합 표현하기

배열의 인덱스는 자신을, 배열값은 부모 노드를 의미한다. 예를 들어, disjointSet[3] = 9 면 노드 3의 부모 노드는 9임을 의미한다.
루트 노드는 집합의 대표이므로 부모가 없고, 부모 노드가 자기 자신임. 즉, 루트 노드는 값 자체가 배열의 인덱스와 동일함.
집합을 표현하는 데 사용하는 배열의 크기는 배열의 인덱스가 모든 집합의 원소를 표현할 수 있어야 함. 예를 들어 가장 큰 원소가 9면, 배열의 크기는 10으로 잡아야 함. (배열의 인덱스는 0부터 시작하는데, 보통 집합을 배열로 표현할 때 0부터 시작하지 않기 때문임)
집합의 개수는 루트 노드의 갯수를 보면 됨 (배열의 인덱스와 값이 같은 경우)

유니온-파인드 알고리즘

파인드 연산

특정 노트의 루트 노드가 무엇인지 탐색하는 방법. 특정 노드가 같은 집합에 있는지 확인할 때 사용

현재 노드의 부모 노드를 확인, 부모 노드를 확인하다 부모 노드가 루트 노드이면 찾기 연산을 종료
1에서 찾기 연산이 종료되지 않았을 경우 1을 반복

경로 압축

좀 더 효율적으로 파인드 연산을 하기 위해서는 집합 형태를 유지하면서도 트리 높이를 줄이면 됨. 트리의 높이를 줄이므로 파인드 연산의 부모 노드를 거치는 과정을 줄일 수 있음.
집합을 구성하는 트리를 평평하게(flatten) 만들어서 찾기 연산을 효율적으로 할 수 있게 됨.

유니온 연산

두 집합을 하나로 합치는 연산, 두 집합의 루트 노드를 같게 하는 것
이 때 루트 노드는 두 집합 중 어떤 루트 노드로 해도 상관이 없음.

랭크

유니온 연산은 찾기 연산처럼 트리의 깊이가 깊어질수록 연산 비용이 커진다는 단점이 있음. 이를 개선하려면 랭크라는 개념이 필요함.
랭크란 현재 노드를 기준으로 하였을 때 가장 깊은 노드까지의 경로 깊이를 말함.

랭크 기반으로 합치기 연산하기

두 노드의 루트 노드를 구한다.
1에서 구한 루트 노드의 랭크를 비교한다.
2-1. 랭크값이 다르면 랭크값이 큰 루트 노드를 기준으로 삼는다. 즉, 랭크가 더 큰 루트 노드를 랭크가 작은 루트 노드의 부모 노드로 바꾼다. 이 때 트리의 깊이는 더 깊어지지 않으므로 랭크의 값은 변하지 않음.
2-2. 랭크값이 같으면 루트 노드를 아무거나 선택해서 바꾸고 최종 루트 노드의 랭크에 1을 더한다.

간단한 유니온-파인드 알고리즘 구현하기

상호배타적 집합을 표현하고 관리하는 데 다음 두 연산이 필요함.

union(x, y): x와 y가 속한 두 집합을 합친다.
find(x): x가 속한 집합의 대표 원소(루트 노드)를 찾는다.

operations라는 배열은 수행할 연산을 의미한다. 연산 종류는 2개이다.

['u', 1, 2] 는 노드 1과 노드 2에 대해 union 연산 수행
['f', 3] 노드 3의 루트 노드 찾기, find 연산 수행

초기의 노드는 부모 노드를 자신의 값으로 설정했다고 가정하며, 각 집합의 루트 노드를 기준으로 루트 노드가 작은 노드를 더 큰 노드의 자식으로 연결하는 방법을 사용한다.
operations에 있는 연산을 모두 수행한 후 집합의 개수를 반환하는 solution 함수를 구현한다.

// 루트 노드 찾는 함수
function find (parents, x) {
  if (parents[x] === x) {
    // 만약 x의 부모가 자기 자신이면, 즉 x가 루트 노드라면
    return x;
  }

  // 그렇지 않다면 x의 부모를 찾아서 parents[x]에 저장
  // 그 부모 노드의 루트 노드를 찾아서 parents[x]에 저장
  // 이 부분이 경로 압축에 해당
  parents[x] = find(parents, parents[x]);
  return parents[x];
}

function union(parents, x, y) {
  const root1 = find(parents, x); // x가 속한 집합의 루트 노드 찾기
  const root2 = find(parents, y); // y가 속한 집합의 루트 노드 찾기

  parents[root2] = root1; // y가 속한 집합을 x가 속한 집합에 합침
}

function solution(k, operations) {
  // 처음에는 각 노드가 자기 자신을 부모로 가지도록 초기화
  const parents = Array.from({ length: k }, (_, i) => i);
  let n = k; // 집합의 개수를 저장할 변수, 처음에는 모든 노드가 서로 다른 집합에 있으므로 k

  for ( const op of operations ) { // operations 배열에 있는 연산들을 하나씩 처리
    if ( op[0] === 'u' ) {
      union(parents, op[1], op[2]);
    } else if ( op[0] === 'f' ) {
      find(parents, op[1]);
    }

    // 모든 노드의 루트 노드를 찾아서 집합의 개수를 계산
    n = new Set(Array.from({ length: k }, (_, i) => find(parents, i))).size;
  }

  return n;
}

console.log(solution(3, [['u', 0, 1], ['u', 1, 2], ['f', 2]])); // 1
console.log(solution(3, [['u', 0, 1], ['u', 2, 3], ['f', 0]])); // 2