241027

Regular Kim·2024년 10월 27일
0

회고

목록 보기
65/70

10월이 거의 끝나간다. 24년도 100일이 채 남지 않았다. 곧 서른인데... ☹️ 이번 주 뭘 했나 10월의 넷째 주를 되돌아본다.

Keep 👍

  • 알고리즘 문제 풀이를 7일 연속 해냈다. 241027기준 379일 연속풀이, 790문제 해결 중이다. 이번 주에는 위상정렬과 최소스패닝 트리를 공부했다.
    - 문제집 가장 기본적은 위상정렬 문제이다. 위상정렬 기본 개념(그래프 개념은 따로 공부해야함)을 공부한 후에 바로 도전할 수 있는 문제다. indegree 가 0이 되는 순으로 출력하면 된다.
    - 게임개발 위상정렬 dp 문제다. indegree 배열 외에 소요시간을 저장하는 dp배열을 하나 더 정의하고 여기에 계산을 적용하면 된다. indegree 값이 0이 되는 노드들을 처리하면서 그 다음 건물의 건설 소요시간을 갱신하면 된다.
    - 음악프로그램 기본 위상정렬 문제와 똑같다. 다만 인풋으로 순환그래프가 주어질 수 있다. 순환그래프의 경우에는 위상정렬이 불가능하다. 이 경우를 처리하는 로직을 구현하는게 이 문제의 포인트다. indegree 가 0이되는 노드를 처리하면서 카운트값을 누적시킨다. 로직이 끝나고 카운트 값과 노드의 값을 비교, 값이 다르면 순환 그래프가 있다고 할 수 있다.
    - 최소 스패닝 트리 가장 기본적인 mst 문제이다. 크루스칼을 사용하던, 프림을 사용하던 편한 로직으로 구현하면 된다. 개인적으로 크루스칼 풀이를 좋아해서 크루스칼로만 풀이하고 있다. 프림 알고리즘은 직관적인 이해가 아직 안 돼서 사용을 지양하고 있다.
    - 네트워크 연결 가장 기본적인 mst 문제2이다. 마찬가지로 크루스칼 알고리즘을 사용해서 풀이했다.
  • 노드 + 익스프레스를 공부하고 있다. 기존 스프링과 개념이 다른 부분이 많아 많이 방황하는 중이다. 이게 뭐,,, 와 어렵다.
    - multar를 이용한 파일 업로드
    - mongoose를 사용한 연관관계 매핑 (1:N, N:1, 양방향)
  • 독서로 객체지향의 사실과 오해를 읽고 있다.

Problem 🤢

순공 시간을 길게 잡지 못하고있다. 집중력이 많이 안 좋다.

Try 🧚

  • 객체지향의 사실과 오해 마무리하기
  • 알고리즘 문제 풀이
  • 프론트 서버 구축
    - node 개념 학습
    - cors 해결하기
  • 백엔드 서버 개발
    - 인증, 인가
    - mvp 제작

독서 목록

서평 완료 목록

서평 예정 목록 (읽는 중)

  • 함께 자라기 애자일로 가는 길
  • 객체지향의 사실과 오해

독서 예정 목록

목록은 우선순위 큐이다. 상단에 있더라도 더 중요한 책이 들어온다면 순위가 뒤로 밀릴 수 있다.

  • 오브젝트
  • 파이브 라인스 오브 코드
  • HTTP 완벽 가이드
  • 자바/스프링 개발자를 위한 실용주의 프로그래밍
  • 모던 자바 인 액션
  • 자바 성능 튜닝 이야기
  • 자바 개발자와 시스템 운영자를 위한 트러블 슈팅 이야기 / scouter를 활용한 시스템 장애 진단 및 해결 노하우 자바 트러블슈팅
  • 헤드 퍼스트 서블릿
  • Hello Coding 그림으로 개념을 이해하는 알고리즘

Extras 😀

문제집


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) {
        new Main().run();
    }
    
    private void run() {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

            Solution s = new Solution();
            System.out.println(s.solution(readInput(br)));

        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }
    
    private List<List<Integer>> readInput(BufferedReader br) throws IOException {
        String[] tokens = br.readLine().split(" ");
        int numOfNodes = Integer.parseInt(tokens[0]);
        int numOfLinks = Integer.parseInt(tokens[1]);

        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < numOfNodes + 1; i++) {
            result.add(new ArrayList<>());
        }
        for (int i = 0; i < numOfLinks; i++) {
            tokens = br.readLine().split(" ");
            int from = Integer.parseInt(tokens[0]);
            int to = Integer.parseInt(tokens[1]);
            result.get(from).add(to);
        }
        return result;
    }
}

class Solution {

    public String solution(List<List<Integer>> graph) {
        StringBuilder answer = new StringBuilder();
        int[] indegree = getIndegree(graph);

        PriorityQueue<Integer> q = new PriorityQueue<>();
        for (int i = 1; i < indegree.length; i++) {
            if(indegree[i] == 0) q.offer(i);
        }

        while (!q.isEmpty()) {
            int cur = q.poll();

            answer.append(cur).append(" ");

            for (Integer next : graph.get(cur)) {
                indegree[next]--;
                if(indegree[next] == 0) q.offer(next);
            }
        }
        return answer.toString();
    }

    private int[] getIndegree(List<List<Integer>> graph) {
        int len = graph.size();
        int[] indegree = new int[len];
        for (int i = 1; i < len; i++) {
            List<Integer> node = graph.get(i);
            for (Integer next : node) {
                indegree[next]++;
            }
        }
        return indegree;
    }
}

게임개발


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) {
        new Main().run();
    }

    private void run() {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

            Input ip = readInput(br);
            Solution s = new Solution();
            System.out.println(s.solution(ip.costs, ip.graph));

        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    private Input readInput(BufferedReader br) throws IOException {
        int len = Integer.parseInt(br.readLine());
        int[] costs = new int[len + 1];
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < len + 1; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < len; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int cost = Integer.parseInt(st.nextToken());
            costs[i + 1] = cost;

            while (st.hasMoreTokens()) {
                int value = Integer.parseInt(st.nextToken());
                if(value == -1) break;
                graph.get(value).add(i + 1);
            }
        }
        return new Input(costs, graph);
    }

    private static class Input {
        private final int[] costs;
        private final List<List<Integer>> graph;

        public Input(int[] costs, List<List<Integer>> graph) {
            this.costs = costs;
            this.graph = graph;
        }
    }
}

class Solution {

    public String solution(int[] costs, List<List<Integer>> graph) {
        int[] indegree = getIndegree(graph);
        int[] dp = Arrays.copyOfRange(costs, 0, costs.length);

        Queue<Integer> q = new ArrayDeque<>();
        for (int i = 1; i < indegree.length; i++) {
            if(indegree[i] == 0) q.offer(i);
        }

        while (!q.isEmpty()) {
            int cur = q.poll();

            for (Integer next : graph.get(cur)) {
                if (dp[next] < dp[cur] + costs[next]) {
                    dp[next] = dp[cur] + costs[next];
                }
                indegree[next]--;
                if(indegree[next] == 0) q.offer(next);
            }
        }

        return getAnswer(dp);
    }

    private int[] getIndegree(List<List<Integer>> graph) {
        int len = graph.size();
        int[] indegree = new int[len];
        for (int i = 1; i < len; i++) {
            List<Integer> node = graph.get(i);
            for (Integer next : node) {
                indegree[next]++;
            }
        }
        return indegree;
    }

    private String getAnswer(int[] dp) {
        StringBuilder answer = new StringBuilder();
        for (int i = 1; i < dp.length; i++) {
            answer.append(dp[i]).append("\n");
        }
        return answer.toString();
    }
}

음악프로그램


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) {
        new Main().run();
    }

    private void run() {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

            Solution s = new Solution();
            System.out.println(s.solution(readInput(br)));

        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    private List<List<Integer>> readInput(BufferedReader br) throws IOException {
        String[] tokens = br.readLine().split(" ");
        int numOfNodes = Integer.parseInt(tokens[0]);
        int repeat = Integer.parseInt(tokens[1]);

        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < numOfNodes + 1; i++) {
            result.add(new ArrayList<>());
        }

        for (int i = 0; i < repeat; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            st.nextToken();
            int from = 0;
            int value = 0;
            while (st.hasMoreTokens()) {
                if (from == 0) {
                    from = Integer.parseInt(st.nextToken());
                    value = Integer.parseInt(st.nextToken());
                } else {
                    value = Integer.parseInt(st.nextToken());
                }
                result.get(from).add(value);
                from = value;
            }
        }
        return result;
    }
}

class Solution {

    public String solution(List<List<Integer>> graph) {
        StringBuilder answer = new StringBuilder();
        int[] indegree = getIndegree(graph);

        Queue<Integer> q = new ArrayDeque<>();
        for (int i = 1; i < indegree.length; i++) {
            if(indegree[i] == 0) q.offer(i);
        }

        int cnt = 0;
        while (!q.isEmpty()) {
            int cur = q.poll();
            cnt++;

            answer.append(cur).append("\n");

            for (Integer next : graph.get(cur)) {
                indegree[next]--;
                if(indegree[next] == 0) q.offer(next);
            }
        }

        if (cnt == graph.size() - 1) {
            return answer.toString();
        }
        return "0";
    }

    private int[] getIndegree(List<List<Integer>> graph) {
        int len = graph.size();
        int[] indegree = new int[len];

        for (int i = 1; i < len; i++) {
            for (Integer next : graph.get(i)) {
                indegree[next]++;
            }
        }
        return indegree;
    }
}

네트워크 연결


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) {
        new Main().run();
    }

    private void run() {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

            Input ip = readInput(br);
            Solution s = new Solution();
            System.out.println(s.solution(ip.numOfComputers, ip.wires));
            
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    private Input readInput(BufferedReader br) throws IOException {
        int numOfComputers = Integer.parseInt(br.readLine());
        int numOfWires = Integer.parseInt(br.readLine());

        int[][] wires = new int[numOfWires][3];
        for (int i = 0; i < numOfWires; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            wires[i][0] = from;
            wires[i][1] = to;
            wires[i][2] = cost;
        }
        return new Input(numOfComputers, wires);
    }

    private static class Input{
        private final int numOfComputers;
        private final int[][] wires;

        public Input(int numOfComputers, int[][] wires) {
            this.numOfComputers = numOfComputers;
            this.wires = wires;
        }
    }
}

class Solution {

    public int solution(int numOfComputers, int[][] wires) {
        Arrays.sort(wires, Comparator.comparing(a -> a[2]));
        int[] group = initGroup(numOfComputers);

        int cnt = 0;
        int sumOfCosts = 0;

        for (int[] wire : wires) {
            if(cnt == numOfComputers - 1) break;
            int from = wire[0];
            int to = wire[1];
            if(isSameGroup(group, from, to)) continue;

            connect(group, from, to);
            sumOfCosts += wire[2];
        }

        return sumOfCosts;
    }

    private int[] initGroup(int numOfComputers) {
        int[] result = new int[numOfComputers + 1];
        for (int i = 0; i < numOfComputers + 1; i++) {
            result[i] = i;
        }
        return result;
    }

    private boolean isSameGroup(int[] group, int target1, int target2) {
        return getGroup(group, target1) == getGroup(group, target2);
    }

    private int getGroup(int[] group, int target) {
        if(target != group[target]) group[target] = getGroup(group, group[target]);
        return group[target];
    }

    private void connect(int[] group, int target1, int target2) {
        int group1 = getGroup(group, target1);
        int group2 = getGroup(group, target2);
        group[Math.max(group1, group2)] = Math.min(group1, group2);
    }
}
profile
What doesn't kill you, makes you stronger

0개의 댓글