2023/3월/4주차 알고리즘 스터디

✅ 팀원

👱🏻‍♂️ 하정헌 ✅ 

👱🏻‍♂️ 조현일 ❌

👱🏻‍♂️ 송명우 ✅

👩🏻‍🦳 강수진 ❌

✅ 규칙

1. 한 주 동안 주어진 문제를 모든 팀원이 풀어와야한다.

2. 일요일 1시에 모든 팀원이 모여 문제를 랜덤으로 추첨한다.

3. 순서대로 디스코드를 이용해 자신이 푼 문제를 설명하고 다른 팀원들은 피드백을 해준다.

✅ 문제

문제는 매 주 월요일의 문제로 선정한다.

https://github.com/tony9402/baekjoon/blob/main/picked.md

GitHub - tony9402/baekjoon: 코딩테스트 대비 문제집(Baekjoon Online Judge)

✅ 스터디 내용

할당문제 : 동방 프로젝트 (Large)

https://www.acmicpc.net/problem/14595

14595번: 동방 프로젝트 (Large)

문제 풀이 : 문제의 목표는 빌런이 벽을 부수는 모든 행동을 시행한 후 남아 있는 동아리 방의 총 갯수를 구하는 문제이다. 시간 제한이 1초이고 동아리 방의 최대 갯수는 백만 개이기 때문에 벽을 부수는데 O(n) 이내의 시간복잡도를 갖는 알고리즘을 이용해야한다. 여기서 문제는 벽을 부수는 행동 횟수가 최대 5000번이기 때문에 백만 * 5000번을 부숴야한다. 따라서 5000번 중 중복되는 행동 횟수를 없애서 최대 백만번의 연산으로 벽을 부술 수 있도록 해야한다. 따라서 x < y까지의 동아리 방의 벽을 부수는 부분을 유니온 파인드를 이용해서 x < y사이에 있는 모든 동아리 방을 하나의 집합으로 표현해주고 x, y 순서로 우선순위를 갖는 우선순위 큐에 모든 행동 패턴을 저장한다. 이렇게 되면 왼쪽 방에서 부수는 행동 패턴을 순서대로 꺼내므로 중복된 행동을 구분하기 쉬워진다. 이때 right 포인터를 이용해서 큐에서 꺼낸 값에 중복된 부분이 있으면 이전에 부순 마지막 방을 시작 점으로 놓고, 이전에 부순 마지막 방을 넘어가면 right포인터에 현재 부순 마지막 방을 저장한다. 이렇게 하면 중복된 부분을 for문을 돌지 않아도 되며 최대 백만번의 연산으로 모든 행동 패턴을 계산할 수 있다.

import java.util.*;
import java.io.*;

public class Main {

    private static class Node {
        int x, y;

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }
    }

    static int n, m, cnt;
    static int[] parent;
    static int[] rank;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());

        parent = new int[n + 1];
        rank = new int[n + 1];

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

        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(Node::getX)
                .thenComparingInt(Node::getY));

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            pq.add(new Node(x, y));
        }

        int right = 0;
        int a, b;
        while (!pq.isEmpty()) {
            Node cur = pq.poll();

            a = cur.x;
            b = cur.y;

            if (a <= right) a = right;
            if (b > right) right = b;

            for (int i = a; i < b; i++) {
                union(a, i+1);
            }
        }

        for (int i = 1; i < n + 1; i++) {
            if (parent[i] == i) cnt++;
        }

        System.out.println(cnt);
    }

    private static void union(int u, int v) {
        int rootU = find(u);
        int rootV = find(v);

        if (rootU == rootV) return;

        if (rank[rootU] < rank[rootV]) {
            parent[rootU] = rootV;
        }

        if (rank[rootU] > rank[rootV]) {
            parent[rootV] = rootU;
        }

        if (rank[rootU] == rank[rootV]) {
            parent[rootU] = rootV;
            rank[rootV]++;
        }
    }

    private static int find(int u) {
        if (u == parent[u]) return u;
        parent[u] = find(parent[u]);
        return parent[u];
    }
}

피드백 : 유니온 파인드를 시행할 때 rank를 사용하지 않는 분이 있어 rank의 중요성에 대해서 얘기했다. rank를 사용하지 않을 경우 한 쪽 방향으로만 union 연산을 시행하기 때문에 최악의 경우 구조는 LinkedList와 같아지며 union의 시간복잡도는 O(n)이 된다. 따라서 루트 노드들의 level을 기록하여 level이 더 높은 루트 노드에 level이 낮은 루트 노드를 합침으로써 level을 맞춰야 최악의 경우에도 union의 시간복잡도는 O(logN)이 된다는 것을 스터디원에게 설명해 주었다.