📙[Algo] 24.04.10 알고리즘

알고리즘 문제) BOJ 9985. Claws

• 링크 : https://www.acmicpc.net/problem/9885

문제 요약

• 이진 트리가 주어짐
• 힌지 등급 = 해당 노드에서 루트 노드까지 경로 상에 있는 간선 가중치 합
  • 이때 서브트리의 힌지 등급을 누적해서 더해줌
• unladen load : 힌지가 견딜 수 있는 최대 무게
  • 즉 노드 1의 unladen load = 노드 1의 힌지등급(50) + 부모 노드 4의 힌지등급(60) + 부모 노드 5의 힌지등급(110) = 220 이된다.
• 이때 최대 unladen load를 출력하기

시간 제한

• 2초

입력

• 노드 개수 N
  • 1≤N≤12000
• 자식 노드, 부모노드, 가중치가 N-1개 주어짐
  • 가중치는 100이하

출력

• 최대 unladen load를 출력하기

접근법

각 노드별 unladen load 구하기

먼저 노드별 힌지 등급들을 구해준다

그 배열값을 이용해서 unladend load 값 구해준다.

코드

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

public class Main {
    static int N;
    static ArrayList<Node>[] list;
    static int[] parent;
    static int root;
    static int[] hinge;

    static class Node {
        int no;
        int weight;

        Node(int no, int weight) {
            this.no = no;
            this.weight = weight;
        }
    }

    // 힌지 등급 구하기
    static void getHinge(int cur, int prv, int w) {

        hinge[cur] = w;

        for (Node nxt : list[cur]) {
            if (prv == nxt.no) continue;

            getHinge(nxt.no, cur, w + nxt.weight);

            hinge[cur] += hinge[nxt.no] - w;
        }
    }

    // unladen load 구하기
    static int getLoad(int node, int sum) {
        sum += hinge[node];

        if (node == root) return sum;

        return getLoad(parent[node], sum);
    }

    public static void main(String[] args) throws  IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());

        list = new ArrayList[N + 1];
        for (int i = 0; i < N + 1; i++) {
            list[i] = new ArrayList<>();
        }

        parent = new int[N + 1];
        int thisNode, parNode, weight;
        for (int i = 0; i < N - 1; i++) {
            st = new StringTokenizer(br.readLine());
            thisNode = Integer.parseInt(st.nextToken());
            parNode = Integer.parseInt(st.nextToken());
            weight = Integer.parseInt(st.nextToken());

            list[parNode].add(new Node(thisNode, weight));
            parent[thisNode] = parNode;
        }

        for (int i = 1; i < N + 1; i++) {
            if (parent[i] == 0) {
                root = i;
                break;
            }
        }

        hinge = new int[N + 1];
        getHinge(root, 0, 0);

        int max = 0;
        for (int i = 1; i <= N; i++) {
            max = Math.max(getLoad(i, 0), max);
        }

        bw.write(String.valueOf(max));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 2533. 사회망 서비스(SNS)

• 링크 : https://www.acmicpc.net/problem/2533

문제 요약

• 새로운 아이디어 수용은 자신의 모든 친구들이 얼리 아답터일 경우 진행
• 친구 관계 트리가 주어졌을 때, 모든 개인이 새로운 아이디어를 수용하기 위하여 필요한 최소 얼리 어답터의 수를 구하는 프로그램을 작성

시간 제한

• 3초

입력

• 친구 관계 트리 정점 개수 N
  • 2 ≤ N ≤ 100만
  • 각 정점은 1번 ~ N번
• 두번째 줄부터 친구 관계 트리 에지 u v가 주어짐

출력

• 주어진 친구 관계 그래프에서 아이디어를 전파하는데 필요한 얼리 아답터의 최소 수를 하나의 정수로 출력

접근법

• 내 모든 친구가 얼리어답터여야 한다.
  • 이걸 의미하는 게 뭐지!
  • 최상위 뿌리 노드를 제외한 부모노드들이 칠해져야 한다.

코드

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

public class Main {
    static int N;
    static ArrayList<Integer>[] list;
    static int cnt = 1;
    static int ans;
    static int[][] dp;

    // 각 노드마다 어답터인경우 아닌경우 고려하면서 탑다운 dp로 풀기

//    static int dfs(int cur, int prv, int prvIsAdapter) {
//
//        if (list[cur].isEmpty() && prvIsAdapter == 0) return 1;
//        else if (list[cur].isEmpty() && prvIsAdapter == 1) return 0;
//
//        int ret = 0;
//        for (Integer nxt : list[cur]) {
//            if (prv == nxt) continue;
//
//            if (prvIsAdapter == 0) {
//                ret += dfs(nxt, cur, 1) + 1;
//            } else {
//                ret += Math.min(dfs(nxt, cur, 0), dfs(nxt, cur, 1) + 1);
//            }
//        }
//
//        return ret;
//    }

    static void dfs(int cur, int prv) {
        dp[cur][0] = 0;
        dp[cur][1] = 1;

        for (Integer nxt : list[cur]) {
            if (nxt == prv) continue;

            dfs(nxt, cur);
            dp[cur][0] += dp[nxt][1];
            dp[cur][1] += Math.min(dp[nxt][0], dp[nxt][1]);
        }
    }

    public static void main(String[] args) throws  IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());

        list = new ArrayList[N + 1];
        for (int i = 0; i < N + 1; i++) {
            list[i] = new ArrayList<>();
        }

        int node1, node2;
        for (int i = 0; i < N - 1; i++) {
            st = new StringTokenizer(br.readLine());
            node1 = Integer.parseInt(st.nextToken());
            node2 = Integer.parseInt(st.nextToken());

            list[node1].add(node2);
            list[node2].add(node1);
        }

        dp = new int[N + 1][2];

        dfs(1, 0);

        bw.write(String.valueOf(Math.min(dp[1][0], dp[1][1])));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 13325. 이진 트리

• 링크 : https://www.acmicpc.net/problem/13325

문제 요약

• 포화 이진 트리가 주어짐
• 루트에서 어떤 리프까지의 거리는 경로상 간선 가중치를 모두 더한 값
• 이때 특정 간선의 가중치를 증가시켜 루트에서 모든 리프까지 거리가 같도록 하려고 함, 또한 가중치들의 총합은 최소가 되게 하려고함

시간 제한

• 1초

입력

• 입력의 첫째 줄에는 포화이진트리의 높이를 나타내는 양의 정수 k(1 ≤ k ≤ 20)가 주어진다
• 두 번째 줄에는 모든 에지들의 가중치가 주어진다
  • 에지들의 가중치는 루트에서 가까운 레벨에 있는 것부터, 같은 레벨에 있는 경우는 왼쪽부터 오른쪽의 순서로 주어진다
  • 각 에지의 가중치는 1 이상 1,000 이하인 정수로 주어진다.

출력

• 에지들의 가중치를 증가시킨 다음에 얻어지는 트리에 있는 모든 에지들의 가중치들의 총합을 한 줄에 출력

코드

import java.awt.event.KeyListener;
import java.io.*;
import java.util.*;

public class Main {
//    static ArrayList<Node>[] tree;
//
//    static class Node {
//        int no;
//        int weight;
//
//        Node(int no, int weight) {
//            this.no = no;
//            this.weight = weight;
//        }
//    }
//
//    static void makeTree() {
//        // 트리 만들기
//        int startIdx = 1;
//        int lastIdx;
//        int v = 1;
//        int nodeNo = 2;
//        for (int h = 1; h <= K; h++) {
//            lastIdx = startIdx + (int) Math.pow(2, h) - 1;
//
//            for (int j = startIdx, k = 0; j <= lastIdx; j++) {
//                tree[v].add(new Node(nodeNo++, w[j]));
//                k++;
//                if (k % 2 == 0) v++;
//            }
//
//            startIdx = lastIdx + 1;
//        }
//    }

    static int K;
    static int[] w;
    static int answer;

    static int dfs(int node) {

        if (node * 2 >= w.length - 1) {
            answer += w[node];
            return w[node];
        }

        int leftNode = dfs(node * 2);
        int rightNode = dfs(node * 2 + 1);

        answer += w[node] + Math.abs(leftNode - rightNode);
        return w[node] + Math.max(leftNode, rightNode);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        // 타입 주의 -> 간선 총 합 구할 때 long타입으로 할 것

        // 일단 루트노드부더 리프노드까지의 합계를 모두 구해보자!
        // 높이별로 간선 묶음은 다음과 같이 끊기
        // 1, 2 / 3, 4, 5, 6 / 7, 8, 9, 10, 11, 12, 13 ,14 / 15, 16, .... , 30 /
        // lastIdx =  startIdx + pow(2, 높이) - 1
        // startIdx = lastIdx + 1 (초기값 1)
        // 경로 묶기
        // 1 - 3 - 7 - 15 ..
        // 1 - 3 - 8 -
        // 트리를 그냥 만들까.. ? 😢 어렵다

        K = Integer.parseInt(br.readLine());

        w = new int[(int) Math.pow(2, K + 1)];

        st = new StringTokenizer(br.readLine());
        for (int i = 2; i < w.length; i++) {
            w[i] = Integer.parseInt(st.nextToken());
        }
//
//        tree = new ArrayList[(int)Math.pow(2, K + 1)];
//        for (int i = 0; i < tree.length; i++) {
//            tree[i] = new ArrayList<>();
//        }
//        트리 만들 필요 없다 ㅠㅠㅠ 바보같다.. 그냥 맨 리프노드부터 간선 두개씩 비교하면서 같게 맞춰준다...
//        makeTree();

        // 간선이랑 노드랑 따로 구분해서 생각하니까 어려웠던거 같다.
        // 그냥 간선을 노드라고 생각하고 풀자
        // 각 노드마다 차이값만큼 더해주며 올라간다.
        // 이때 올라갈때 자식 노드(왼,오)의 차이값을 더해줬기 때문에 결국,
        // 왼쪽 자식 노드와 오른쪽 자식 노드 중 큰 쪽의 값을 따라간거다. 그래서
        // 둘 중 최댓값만큼 더해주고 위로 올려 보낸다.

        dfs(1);

        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 2132. 나무 위의 벌레

• 링크 : https://www.acmicpc.net/problem/2132

문제 요약

• 루트 없는 일반적인 트리 그래프 생각
• 각 노드마다 열매가 몇 개 매달려있음
• 노드끼리 간선으로 이루어져있음
• 한 번 방문한 간선은 재방문 X
• 벌레의 이동은 더 이상 이동할 수 있는 정점이 없을 때에 끝난다
• 나무의 모양이 주어졌을 때, 벌레가 최대로 먹을 수 있는 열매의 수와 이때 어느 정점에서 이동을 시작해야 하는지를 알아내는 프로그램을 작성

시간 제한

• 2초

입력

• 트리의 정점의 개수를 나타내는 정수 n(1 ≤ n ≤ 10,000)
• 다음 줄에는 차례로 1번, 2번, …, n번 정점에 매달려 있는 열매의 개수가 주어진다
  • 나무에 매달려 있는 열매의 총 개수는 2^31-1 (2,147,483,647)개를 넘지 않는다
• 다음 n-1개의 줄에는 트리의 각 간선을 나타내는 서로 다른 두 자연수 A, B(1 ≤ A, B ≤ n)가 주어진다

출력

• 첫째 줄에 벌레가 먹을 수 있는 열매의 최대 개수와, 이때 이동을 시작할 정점의 번호를 출력
• 답이 여러 개 있을 경우에는 정점의 번호가 가장 작은 경우를 출력

코드

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

public class Main {
    static int N;
    static int[] fruit;
    static ArrayList<Integer>[] list;
    static int max;
    static int nodeNo = 1;
    static int minNode = 1;

    static void dfs(int cur, int prv, int sum) {

        sum += fruit[cur];

        if (max <= sum) {
            if (max == sum) {
                nodeNo = Math.min(cur, nodeNo);
            } else {
                nodeNo = cur;
            }
            max = sum;
        }

        for (Integer nxt : list[cur]) {
            if (nxt == prv) continue;

            dfs(nxt, cur, sum);
        }
    }

    public static void main(String[] args) throws  IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());

        fruit = new int[N + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i < N + 1; i++) {
            fruit[i] = Integer.parseInt(st.nextToken());
        }

        list = new ArrayList[N + 1];
        for (int i = 0; i < N + 1; i++) {
            list[i] = new ArrayList<>();
        }

        int node1, node2;
        for (int i = 0; i < N - 1; i++) {
            st = new StringTokenizer(br.readLine());
            node1 = Integer.parseInt(st.nextToken());
            node2 = Integer.parseInt(st.nextToken());

            list[node1].add(node2);
            list[node2].add(node1);
        }

        // 트리의 지름으로!
        dfs(1, 0, 0);
        minNode = nodeNo;
        max = -1;
        dfs(nodeNo, 0, 0);
        minNode = Math.min(nodeNo, minNode);

        bw.write(max + " " + minNode);
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 1949. 우수 마을

• 링크 : https://www.acmicpc.net/problem/1949

문제 요약

• N개의 노드가 있고, 각 마을마다 주민수가 있음
• 마을과 마을을 있는 N-1개의 간선이 있다.
  • 방향성X
• 이때 N개의 마을 중 몇몇 마을을 다음 조건에 맞춰서 우수 마을로 선정하려고함
  • 우수마을로 선정된 주민 총 합이 최대일 것
  • '우수 마을'끼리는 서로 인접해 있을 수 없다
  • '우수 마을'로 선정되지 못한 마을은 적어도 하나의 '우수 마을'과는 인접해 있어야 한다

시간 제한

• 2초

입력

• 첫째 줄에 정수 N이 주어진다. (1 ≤ N ≤ 10,000)
• 둘째 줄에는 마을 주민 수를 나타내는 N개의 자연수가 빈칸을 사이에 두고 주어진다
  • 1번 마을부터 N번 마을까지 순서대로 주어지며, 주민 수는 10,000 이하
• 셋째 줄부터 N-1개 줄에 걸쳐서 인접한 두 마을의 번호가 빈칸을 사이에 두고 주어진다

출력

• 첫째 줄에 '우수 마을'의 주민 수의 총 합을 출력

코드

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

public class Main {
    static int N;
    static int[] human;
    static ArrayList<Integer>[] list;
    static int[][] dp;

    static int dfs(int cur, int prv) {
        dp[cur][0] = 0;
        dp[cur][1] = human[cur];
        int ret = human[1];
        for (Integer nxt : list[cur]) {
            if (nxt == prv) continue;

            dfs(nxt, cur);
            dp[cur][1] += dp[nxt][0];
            dp[cur][0] += Math.max(dp[nxt][0], dp[nxt][1]);
        }

        return ret;
    }

    public static void main(String[] args) throws  IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        // 탑다운 dp로 풀어보장!....?

        N = Integer.parseInt(br.readLine());

        st = new StringTokenizer(br.readLine());
        human = new int[N + 1];
        for (int i = 1; i < N + 1; i++) {
            human[i] = Integer.parseInt(st.nextToken());
        }

        list = new ArrayList[N + 1];
        for (int i = 0; i < N + 1; i++) {
            list[i] = new ArrayList<>();
        }

        int node1, node2;
        for (int i = 0; i < N - 1; i++) {
            st = new StringTokenizer(br.readLine());
            node1 = Integer.parseInt(st.nextToken());
            node2 = Integer.parseInt(st.nextToken());

            list[node1].add(node2);
            list[node2].add(node1);
        }

        dp = new int[N + 1][2];

        dfs(1, 0);

        bw.write(String.valueOf(Math.max(dp[1][0], dp[1][1])));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 12947. 트리 만들기

• 링크 : https://www.acmicpc.net/problem/12947

문제 요약

• 정점 N개로 이루어진 트리는 N-1개의 간선으로 이루어져 있다
• 두 정점 사이의 거리는 한 정점에서 다른 정점으로 갈 때, 지나는 간선 개수의 최솟값
• 아래와 같은 조건을 만족하는 트리 중에서 지름이 가장 긴 것을 만들어보자.
  • 트리의 루트 : V
  • V에서 가장 먼 정점과의 거리 D
  • 1보다 크거나 같고, D보다 작거나 같은 모든 i에 대해, 거리가 i인 정점의 개수는 cnt[i]
  • cnt 배열이 주어졌을 때 만들 수 있는 트리 중 지름이 가장 큰 것의 지름 출력

시간 제한

• 2초

입력

• cnt 배열 크기 N
  • 1≤N≤50
• cnt배열의 값이 cnt[1]부터 cnt[N]까지 차레대로 주어짐
  • 1≤cnt[i]≤1000

출력

• 첫째 줄에 문제의 조건을 만족시키는 트리 중에서 지름이 가장 큰 것의 지름을 출력

접근법

2 2

cnt[1] : 거리가 1인 정점 개수 = 2

cnt[2] : 거리가 2인 정점 개수 = 2

 

4 1 2 4

cnt[1] : 거리가 1인 정점 개수 = 4

cnt[2] : 거리가 2인 정점 개수 = 1

cnt[3] : 거리가 3인 정점 개수 = 2

cnt[4] : 거리가 4인 정점 개수 = 4

• 노드 개수는 cnt배열의 원소값의 합 + 1(루트 노드)
• 만들 수 있는 트리 중 가장 큰 트리의 지름 출력해야함
  • 가장 큰 트리의 지름을 만들기 위해서는
    • 노드를 배치할 때 최대한 분산을 해야함
    • 즉, 최대한 노드마다 자식을 갖게 할 것
    • 그러나 만약 직전 cnt[i]개수가 1이라면 부모가 하나밖에 존재하지 않으니까 해당 노드는 카운트할 때 +1만 해야함
      • 그 외에는 +2

코드

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

public class Main {
    static int N;
    static int[] cnt;
    static ArrayList<Integer>[] list;
    static int max, idx;

    static void makeTree() {
        int root = 1, no = 2, count, pCnt = 1, div;
        for (int i = 1; i <= N; i++) {
            count = cnt[i];
            div = 0;
            while (count-- > 0) {
                if (pCnt > 1) {
                    list[root].add(no);
                    list[no].add(root);
                    no++;
                    div++;
                    root--;
                    if (div >= pCnt){
                        root += pCnt;
                        div = 0;
                    }
                } else {
                    list[root].add(no);
                    list[no].add(root);
                    no++;
                }
            }
            pCnt = cnt[i];
            root = no - 1;
        }
    }

    static void dfs(int cur, int prv, int d) {

        if (max < d) {
            max = d;
            idx = cur;
        }

        for (Integer nxt : list[cur]) {
            if (prv == nxt) continue;

            dfs(nxt, cur, d + 1);
        }
    }

    public static void main(String[] args) throws  IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());

        cnt = new int[N + 10];

        st = new StringTokenizer(br.readLine());
        int sum = 0;
        for (int i = 1; i <= N; i++) {
            cnt[i] = Integer.parseInt(st.nextToken());
            sum += cnt[i];
        }
//        System.out.println(Arrays.toString(cnt));

        // 자식 노드를 배치할 때 최대한 분산해야 지름이 길어진다...
        // 최대한 분산하면서 트리를 만든다면?
        list = new ArrayList[sum + 10];
        for (int i = 0; i < sum + 10; i++) {
            list[i] = new ArrayList<>();
        }

        makeTree();

        dfs(1, 0, 0);
        max = -1;
        dfs(idx, 0, 0);

        bw.write(String.valueOf(max));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 2263. 트리의 순회

• 링크 : https://www.acmicpc.net/problem/2263

문제 요약

• n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다
• 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오

시간 제한

• 5초

입력

• 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다
• 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고
• 그 다음 줄에는 같은 식으로 포스트오더가 주어진다

출력

• 첫째 줄에 프리오더를 출력

코드

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

public class Main {
    static int N;
    static int[] inorder;
    static int[] postorder;
    static int[] inorderIdx;
    static StringBuilder sb = new StringBuilder();

    /*
     인오더, 포스트오더 모두 가장 왼쪽 서브트리 노드부터 방문한다.(왼쪽 서브트리 노드 존재할 경우 첫번쨰 노드가 같음)
     인오더 : 왼 -> 루 -> 오
     포스트오더 : 왼 -> 오 -> 루 => 가장 최상위 루트가 최종적으로 맨 마지막에 도착
        결국 포스트오더는 서브트리 타고 내려갈때마다(?) 맨 마지막 원소가 해당 서브트리의 루트가 됨

     프리오더 : 루 -> 왼 -> 오 => 루트노드를 우선으로 방문(루 -> 왼쪽 서브트리 이동(루트 우선))

     어렵다 ㅠㅠㅠ 다른 사람 접근법 참고해서 풀었다 <https://loosie.tistory.com/345>
     분할정복으로 푸는 문제인데,, 이거 관련해서 좀더 공부해봐야곘따
    * */

    // 전위 순회 찾기(루-왼-오)
    static void makePre(int is, int ie, int ps, int pe) {
        // 맨 마지막 친구
        if (ie < is || pe < ps) return;

        int root = postorder[pe];
        int rootIdx = inorderIdx[root];
        int leftSize = rootIdx - is;
        sb.append(root + " ");

        makePre(is, rootIdx - 1, ps, ps + leftSize - 1);
        makePre(rootIdx + 1, ie, ps + leftSize, pe- 1);
    }

    public static void main(String[] args) throws  IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());

        st = new StringTokenizer(br.readLine());
        inorder = new int[N + 1];
        for (int i = 1; i < N + 1; i++) {
            inorder[i] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        postorder = new int[N + 1];
        for (int i = 1; i < N + 1; i++) {
            postorder[i] = Integer.parseInt(st.nextToken());
        }

        inorderIdx = new int[N + 1];
        for (int i = 1; i < N + 1; i++) {
            inorderIdx[inorder[i]] = i;
        }

        makePre(1, N, 1, N);

        bw.write(String.valueOf(sb));
        bw.flush();
        bw.close();
        br.close();
    }
}