[코딩 테스트 합격자 되기 C++ 스터디] STEP 5. 집합

인프런 강의 링크: https://inf.run/DuvN7

[지금 무료] 코딩 테스트 합격자 되기 - C++ 강의 | dremdeveloper - 인프런

5주 차

스터디 일자: (2024. 08. 04(일) ~ 2024. 08. 10(토))

 

시작에 앞서

관광 공사 2차 면접 준비로 이번 주 알고리즘 스터디 마감을 늦추었다

면접도 끝났으니 이제 결과를 기다리면서 다시 스터디를 진행해야겠다

 

기존 알고리즘 문제 풀이에서 집합을 고를 때 DFS(또는 재귀) 형태를 많이 사용하였다

기존에 문제를 풀었던 방식과 비교하며 학습을 진행 해야겠다

 

1. 상호 배타적 집합이란

상호 배타적 집합: 교집합이 없는 관계(집합은 2개 이상)

 

X = {1, 2, 3}

Y = {4, 5, 6}

중복 원소가 없으므로 상호 배타적 집합

 

X = {1, 2, 3}

Y = {3, 4, 5}

3이 중복되므로 상호 배타적 집합이 아님

 

1-1. 집합 표현하기

- 집합 내의 각 원소가 어떤 집합에 속하는 지 알 수 있어야 한다

- 각 집합을 서로 구별할 수 있어야 한다

- 두 집합을 하나로 합칠 수 있어야 한다

 

각 집합의 대표 원소를 만드는 방법으로 해결할 수 있다

 

2. 집합의 연산

2-1. union 연산과 find 연산

find 연산

특정 노드의 루트 노드를 확인하는 연산

- 특정 노드로 부터 루트 노드가 나올 때 까지 거슬러 올라간다

- union 연산에서도 활용된다

 

노드 값과 부모 노드 값이 일치할 때 까지 진행한다

 

루트 노드 탐색 연산은 $$O(N)$$ 시간 복잡도를 가진다

따라서 속도 개선을 위해서는 경로 압축 알고리즘 활용이 가능하다

 

경로 압축

find 연산을 하는 노드가 루트 노드일 경우 루트 노드 반환

루트 노드가 아닐 경우, 자신의 부모 노드를 find로 설정

find(5) → find(4) → ... → find(1) / find(1)은 루트 노드이므로 반환

 

Union 연산

두 개의 집합을 하나의 집합으로 합치는 연산

find 연산을 통해 각 집합 대표 원소를 구하고, 루트 노드를 하나로 통일

(보통 루트 노드가 작은 쪽으로 합침)

 

2-2. 경로 압축 / 랭크 기반 알고리즘으로 개선하기

집합에 랭크(특정 노드 기준 최대 깊이)를 활용

랭크가 더 큰 쪽으로 합치는 것이 효율적이다

 

경로 압축이나 랭크 기반 까지는 구현하지 않아도 괜찮음

 

3. 집합의 구현

초기화 단계

for(int i = 0; i < n; ++i) {
	parent[i] = i;
}

루트 노드 배열을 자기 자신으로 초기화 해준다

 

find 함수

int find(int x) {
  while(parent[x] != x) {
    x = parent[x];
  }
    
  return x;
}

최적화 되지 않은 상태, while문으로 탐색한다

 

int find(int x) {
  if(parent[x] != x) {
    parent[x] = find(parent[x]);
  }
  
  return parent[x];
}

경로 압축을 진행한 상태

 

union

void union(int x, int y) {
  int a = find(x);
  int b = find(y);
  
  if (a != b) {
    if (rank[x] > rank[b]) {
      parent[b] = a;
    } else if (rank[a] < rank[b]) {
      parent[a] = b;
    } else {
      parent[b] = a;
      ++rank[a];
    }
  }
}

rank 기반으로 최적화 한 상태

4. 문제 풀이

https://school.programmers.co.kr/learn/courses/30/lessons/42861

프로그래머스

 

이 문제는 BFS 방식으로 해결했던 문제

Union-Find 방식으로도 해결할 수 있는 것 같다

import java.util.*;

class Solution {
    
    static class Node {
        int next, cost;
        
        public Node(int next, int cost) {
            this.next = next;
            this.cost = cost;
        }
    }
    
    public int solution(int n, int[][] costs) {
        int answer = 0;
        
        ArrayList<ArrayList<Node>> adj = new ArrayList<>();
        
        for (int i = 0; i <= n; i++) {
            adj.add(new ArrayList<>());
        }
        
        for (int[] cost : costs) {
            int x = cost[0];
            int y = cost[1];
            int z = cost[2];
            
            adj.get(x).add(new Node(y, z));
            adj.get(y).add(new Node(x, z));
        }
        
        answer = createRoad(n, costs, adj);
        
        
        return answer;
    }
    
    static int createRoad(int n, int[][] costs, ArrayList<ArrayList<Node>> adj) {
        int answer = 0;
        
        boolean[] visited = new boolean[n+1];
        PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> o1.cost - o2.cost);
        // int[] dist = new int[n+1];
        // Arrays.fill(dist, 100_000_000);
        // dist[1] = 0;
        // visited[1] = true;
        pq.offer(new Node(1, 0));
        
        while(!pq.isEmpty()) {
            Node cur = pq.poll();
            int now = cur.next;
            int cost = cur.cost;
            
            if (!visited[now]) {
                visited[now] = true;
                answer += cost;
                
                for (Node next : adj.get(now)) {
                    int nextV = next.next;
                    int nextCost = next.cost;
                    pq.offer(new Node(nextV, nextCost));
                }
                
            }
        }
        
        return answer;
    }
}

 

마무리

지금까지 코딩 테스트 문제에서 딱 한 번 집합과 관련된 문제를 본 경험이 있다(현대 오토에버 코딩 테스트)

기존에 정리했던 내용도 적으며 마무리 해야겠다

https://velog.io/@montag/%EC%9C%A0%EB%8B%88%EC%98%A8-%ED%8C%8C%EC%9D%B8%EB%93%9C

유니온 파인드