Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++ 유니온-파인드로 공통 약수 그래프의 최대 연결 요소 크기 구하기

서로 다른 양의 정수로 이루어진 배열 A가 있다고 가정해 보겠습니다. 이 배열을 바탕으로 다음과 같은 그래프를 생각할 수 있습니다.

그래프에는 배열 A의 길이만큼 노드가 존재하며, 각 노드는 A[0]부터 A[A.size() - 1]까지의 값으로 라벨링됩니다. 두 노드 A[i]와 A[j]가 1보다 큰 공통 약수(공통 인수)를 가질 때 두 노드 사이에 간선이 연결됩니다. 우리가 구해야 하는 것은 이 그래프에서 가장 큰 연결 요소(Connected Component)의 크기입니다.

예를 들어 입력이 [4, 6, 15, 35]라면 출력은 4가 됩니다. 4와 6은 공통 약수 2를, 6과 15는 공통 약수 3을, 15와 35는 공통 약수 5를 공유하기 때문에 네 개의 숫자가 모두 하나의 연결 요소로 이어지기 때문입니다.

접근 방법: 유니온-파인드(Union-Find)

이 문제는 서로소 집합(Disjoint Set) 자료구조, 즉 유니온-파인드 알고리즘을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 숫자를 소인수분해한 뒤, 같은 소인수를 공유하는 숫자들을 하나의 집합으로 묶는 것입니다.

알고리즘 단계

  • 각 노드의 부모를 저장하는 parent 배열을 정의합니다.
  • 집합의 크기를 추적하는 rank 배열을 정의합니다.
  • getParent(x): x의 루트 부모를 찾습니다. parent[x]가 -1이면 x 자체가 루트이므로 x를 반환하고, 그렇지 않으면 경로 압축(path compression) 기법을 적용하여 재귀적으로 부모를 갱신하며 반환합니다.
  • unionn(x, y): x와 y가 속한 집합을 병합합니다.
  • parX := getParent(x), parY := getParent(y)
  • parX와 parY가 같다면 이미 같은 집합이므로 아무 작업도 하지 않습니다.
  • rank[parX] >= rank[parY]라면 rank[parX]에 rank[parY]를 더하고 parent[parY]를 parX로 설정합니다.
  • 그렇지 않으면 rank[parY]에 rank[parX]를 더하고 parent[parX]를 parY로 설정합니다.

메인 로직

  • ret := 0, n := 배열 A의 크기로 초기화합니다.
  • parent 배열은 크기 n으로 생성하고 모든 값을 -1로 채웁니다.
  • rank 배열은 크기 n으로 생성하고 모든 값을 1로 채웁니다.
  • 소인수를 키로, 해당 소인수를 처음 가진 노드의 인덱스를 값으로 저장하는 맵 m을 정의합니다.
  • i를 0부터 n-1까지 반복하며 다음을 수행합니다.
    • x := A[i]
    • j를 2부터 j*j <= x까지 반복하며:
      • x mod j == 0이라면 j는 x의 약수입니다.
        • 맵 m에 j가 이미 존재하면 unionn(m[j], i)로 두 노드를 병합하고, 없으면 m[j] := i로 저장합니다.
        • 짝인 약수 x/j에 대해서도 동일하게 처리합니다. m에 x/j가 있으면 unionn(m[x/j], i)를 호출하고, 없으면 m[x/j] := i로 저장합니다.
    • x 자체도 소수일 수 있으므로 맵에 x가 있으면 unionn(m[x], i)를 호출하고, 없으면 m[x] := i로 저장합니다.
    • ret := max(ret, rank[getParent(i)])로 현재까지의 최대 연결 요소 크기를 갱신합니다.
  • 최종적으로 ret을 반환합니다.

아래 구현 예시를 통해 더 잘 이해해 보겠습니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   vector<int> parent;
   vector<int> rank;
   int getParent(int x){
      if (parent[x] == -1)
      return x;
      return parent[x] = getParent(parent[x]);
   }
   void unionn(int x, int y){
      int parX = getParent(x);
      int parY = getParent(y);
      if (parX == parY)
      return;
      if (rank[parX] >= rank[parY]) {
         rank[parX] += rank[parY];
         parent[parY] = parX;
      } else {
         rank[parY] += rank[parX];
         parent[parX] = parY;
      }
   }
   int largestComponentSize(vector<int>& A) {
      int ret = 0;
      int n = A.size();
      parent = vector<int>(n, -1);
      rank = vector<int>(n, 1);
      unordered_map<int, int> m;
      for (int i = 0; i < n; i++) {
         int x = A[i];
         for (int j = 2; j * j <= x; j++) {
            if (x % j == 0) {
               if (m.count(j)) {
                  unionn(m[j], i);
               } else {
                  m[j] = i;
               }
               if (m.count(x / j)) {
                  unionn(m[x / j], i);
               } else {
                  m[x / j] = i;
               }
            }
         }
         if (m.count(x)) {
            unionn(m[x], i);
         } else {
            m[x] = i;
         }
         ret = max(ret, rank[getParent(i)]);
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {4,6,15,35};
   cout << (ob.largestComponentSize(v));
}

입력

{4,6,15,35}

출력

4

복잡도 분석

각 숫자에 대해 제곱근까지만 약수를 검사하므로 시간 복잡도는 O(N·√M)입니다. 여기서 N은 배열의 길이, M은 배열 내 최댓값입니다. 유니온-파인드에 경로 압축과 크기 기반 병합을 함께 사용하면 집합 연산이 거의 상수 시간에 처리되어 전체 성능이 크게 향상됩니다.