똥대

/*
총 numCourses개의 코스를 수강해야 하며, 각 코스는 0부터 numCourses - 1까지 번호가 매겨져 있습니다.
배열 prerequisites가 주어지는데, prerequisites[i] = [ai, bi]는 코스 ai를 
듣기 위해 먼저 코스 bi를 이수해야 함을 의미합니다.

예를 들어, [0, 1]이 주어지면 코스 0을 듣기 전에 코스 1을 먼저 수강해야 한다는 뜻입니다.

모든 코스를 이수할 수 있으면 true를, 그렇지 않으면 false를 반환하세요.
*/
class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Deque <Integer> dq = new ArrayDeque<>();
        List <List<Integer>> list = new ArrayList<>();
        for (int i = 0; i < 2000; i++) {
            list.add(new ArrayList<>());
        }
        int [] degree = new int[numCourses];

        Arrays.fill(degree, 0);

        for(int i=0; i<prerequisites.length; i++) {
            int a = prerequisites[i][0];
            int b = prerequisites[i][1];
            list.get(b).add(a);
            degree[a] ++;
        }

        // 초기값  세팅
        for(int i=0; i<degree.length; i++) {
            if(degree[i] == 0) {
                dq.addLast(i);
            }
        }

        while(!dq.isEmpty()) {
            int course = dq.pollFirst();
            for(int nextCourse : list.get(course)) {
                degree[nextCourse] --;
                if(degree[nextCourse] == 0)
                    dq.addLast(nextCourse);
            }
            list.get(course).clear();
        }

        boolean result = true;
        for(int i=0; i<degree.length; i++) {
            if(degree[i] != 0) {
                result = false;
            }
        }

        return result;
    }
}

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0. So it is possible.

순서가 있는 그래프가 주어지고 주어진 순서에 맞게 끝내는 문제이다.

이 문제를 볼때 위상정렬이 떠올라야한다.

위상정렬은 다음과 같이 진행이된다.

1.진입차수를 관리해야한다.

2.진입차수가 0인 값을 가장 먼저 큐에 넣는다.

3. 큐에 값을 뽑고 해당값과 연결되어 있는 노드를 다시 큐에 넣는다.(단 그 노드의 진입차수가 0일 경우에만)

4. 2~3 반복한다.

/*
다음은 번역된 내용입니다:

n개의 도시가 0부터 n-1까지 번호가 매겨져 있습니다. 주어진 배열 edges에서 edges[i] = [fromi, toi, weighti]는 fromi와 toi 사이에 가중치 weighti를 갖는 양방향 엣지를 나타냅니다. 또한 정수 distanceThreshold가 주어집니다.

distanceThreshold 이하의 거리를 갖는 경로를 통해 도달할 수 있는 도시가 가장 적은 도시를 반환하세요. 만약 그런 도시가 여러 개 있다면, 가장 큰 번호의 도시를 반환하세요.

경로 i와 j를 연결하는 경로의 거리는 그 경로를 따라가는 엣지들의 가중치 합입니다.
*/

class Solution {
    public int findTheCity(int n, int[][] edges, int distanceThreshold) {
        int [][] floyd = new int[n][n];

        
        for(int i=0; i<floyd.length; i++) {
            Arrays.fill(floyd[i], Integer.MAX_VALUE);
            floyd[i][i] = 0;
        }

        for(int [] edge : edges) {
            floyd[edge[0]][edge[1]] = edge[2];
            floyd[edge[1]][edge[0]] = edge[2];
        }
        // 11 12 13 21 22 23 31 32 33
        for(int i=0; i<floyd.length; i++) {
            for(int j=0; j<floyd.length; j++) {
                for(int k=0; k<floyd.length; k++) {
                    if (floyd[j][i] != Integer.MAX_VALUE && floyd[i][k] != Integer.MAX_VALUE) {
                        floyd[j][k] = Math.min(floyd[j][k], floyd[j][i]+floyd[i][k]);
                    }
                }
            }
        }

        int city = -1;
        long count = Integer.MAX_VALUE;
        for(int i=0; i<floyd.length; i++) {
            long temp = Arrays.stream(floyd[i]).filter(a -> a<=distanceThreshold).count();
            if(count >= temp) {
                city = i;
                count = temp;
            }
        }

        return city;
    }
}

Example 1:

Input: n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4
Output: 3
Explanation: The figure above describes the graph. 
The neighboring cities at a distanceThreshold = 4 for each city are:
City 0 -> [City 1, City 2] 
City 1 -> [City 0, City 2, City 3] 
City 2 -> [City 0, City 1, City 3] 
City 3 -> [City 1, City 2] 
Cities 0 and 3 have 2 neighboring cities at a distanceThreshold = 4, but we have to return city 3 since it has the greatest number.

distanceThreshold 이하의 각 도시끼리 최단 경로가 있는지 찾는 문제이다.

각 도시부터 도시까지 모든 최소 경로를 구해야하기 때문에 플로이드 와샬로 풀어야한다.

플로이드 와샬은 3중 for 문으로 구성이 되며

점화식은 다음과 같다.

i,j,k 각각 3중 포문의 변수라고 가정하면

floyd[j][k] = Math.min(floyd[j][i] + floyd[i][k], floyd[j][k])

이 뜻은 j -> k 라는 도시를 갈때 i를 거쳐가는게 빠른지, 아니면 기존에 있는 값이 빠른지 비교하여 넣어준다.

방문체크는 필요 없으며, 초기 플로이드 배열을 Integer.MAX_VALUE 로 설정했기에,

floyd[j][i] 나 floyd[i][j] 가 Integer.MAX_VALUE 가 아닐때만 값 갱신을 시도한다.

/*
n개의 노드(1부터 n까지 라벨링된)로 이루어진 네트워크가 주어집니다. 
또한, times라는 리스트가 주어지는데, 이는 방향성이 있는 간선으로, 
times[i] = (ui, vi, wi) 형식으로 나타납니다. 여기서 ui는 출발 노드, vi는 도착 노드, wi는 신호가 출발 노드에서 도착 노드로 전달되는 데 걸리는 시간을 의미합니다.

주어진 노드 k에서 신호를 보낼 때, 모든 노드가 신호를 받는 데 걸리는 최소 시간을 반환하세요. 
만약 모든 노드가 신호를 받을 수 없다면 -1을 반환하세요.
*/

class Solution {
    int [] visited = null;
    int [] dist = null;
    List<List<int[]>> graph = new ArrayList<>();    
    public int networkDelayTime(int[][] times, int n, int k) {
        visited = new int[n];
        dist = new int[n];
        Arrays.fill(visited, 0);
        Arrays.fill(dist, Integer.MAX_VALUE);

        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }

        for(int [] time : times) {
            graph.get(time[0]-1).add(new int[]{ time[1]-1, time[2] } );
        }
        
        dijkstra(k);
        
        int maxDist = Arrays.stream(dist).max().orElse(-1);
        return maxDist == Integer.MAX_VALUE ? -1 : maxDist;
    }

    public void dijkstra(int k) {
        PriorityQueue <List<Integer>> pq = new PriorityQueue<>((a,b) -> a.get(1)-b.get(1));
        pq.add(List.of(k-1, 0));
        dist[k-1] = 0;

        while(!pq.isEmpty()) {
            List <Integer> list = pq.poll();
            int node = list.get(0);

            if(visited[list.get(0)] == 1) 
                continue;

            visited[list.get(0)] = 1;

            for(int i=0; i<graph.get(node).size(); i++) {
                int[] neighbor = graph.get(node).get(i);
                int nextNode = neighbor[0];
                int time = neighbor[1];

                if(dist[node] + time < dist[nextNode]) {
                    dist[nextNode] = dist[node]+time;
                    pq.add(List.of(nextNode, dist[nextNode]));
                }
            }
        }
    }
}

Example 1:

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2

k 에서 신호를 보낼대 각각의 노드까지 모두 도착하는 최솟출력이다.

그러면 여기서 2->1, 2->3, 2->4 가는 최소경로 값중에 최댓값을 고르면 된다.

육안으로 봐도 2->4 로 가는 경로가 2로 값이 출력이 될 것이다.

최소 경로 알고리즘은 많다. 다익스트라, 벨만포드, 플로와샬

여기서는 다익스트라를 채택했다. 2에서 출발하는 것을 지정할 수 있고, 간선은 양수이다. 그렇기때문에 다익스트라를 사용해도 무방하다.

다익스트라는 기본적으로 우선순위 큐를 지정한다. 

여기서 우선순위큐는 time(거리)가 가장낮은 값을 앞에 두고 뽑을수 있도록한다.

그렇게 되면 node, time 이 들어올대마다 time 이 가장 낮은 아이가 먼저 뽑히므로 다익스트라에서 가장 최소거리를 뽑을 수 있게된다.

다익스트라는 이렇게 구성된다.

1. 방문체크

2. 이웃에 이미 저장된 최솟값, 현재노드에서 이웃으로 넘어가는 값을 더한값 두개 비교해서, 기존에 있던 최솟값보다 현재노드+time 이 더 작다면 최솟값을 갱신하고, 우선순위 큐에 넣는다.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

 /*
 이진 트리의 루트 노드 root가 주어졌을 때, 트리의 레벨 순회 결과를 반환하세요.

즉, 트리의 노드들을 왼쪽에서 오른쪽으로, 레벨별로 순서대로 탐색한 결과를 반환해야 합니다.
 */
class Solution {
    List <List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        dfs(root, 0);

        return result;
    }

    public void dfs(TreeNode node, int level) {
        if(node == null) {
            return ;
        }
        
        if(result.size() > level) {
            result.get(level).add(node.val);
        } else {
            List <Integer> list = new ArrayList<>();
            list.add(node.val);
            result.add(list);
        }

        dfs(node.left, level+1);
        dfs(node.right, level+1);
    }
}

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

간단하게 해당 2진트리를 level 별로 출력하는 문제이다.

preorder 를 사용하면, 본인 -> 좌 -> 우 로 탐색을 진행할수 있어서 preorder를 사용했다.

간단하게 본인이 처음으로 해당 level 에 처음으로 들어가면 add 로 레벨을 추가해주고,

만약 level 이 이미 들어간게 있다면 간단하게 추가된 레벨에 add 만해주는 형식으로 출력하게된다.

/*
m x n 크기의 문자 격자 board와 문자열 word가 주어졌을 때, word가 해당 격자 내에 존재하면 true를 반환하세요.

word는 상하좌우로 인접한 셀들의 문자들을 순차적으로 이어 붙여 만들 수 있어야 하며,
같은 셀의 문자를 중복해서 사용할 수는 없습니다.
*/
class Solution {
    int [][] dp = null;
    boolean result = false;
    public boolean exist(char[][] board, String word) {
        dp = new int[board.length][board[0].length];
        for(int i=0; i<dp.length; i++) 
            Arrays.fill(dp[i], 0);
        

        for(int i=0; i<board.length; i++)
            for(int j=0; j<board[i].length; j++) 
                dfs(board, 0, i, j, word);
    

        return result;
    }

    public void dfs(char [][] board, int l, int y, int x, String word) {
        if(result) {
            return ;
        }

        if(board[y][x] == word.charAt(l) && dp[y][x] == 0) {
            if(l == word.length()-1) 
                result = true;

            dp[y][x] = 1;
            if(y-1 >= 0) 
                dfs(board, l+1, y-1, x, word);
            if(y+1 <= board.length-1)
                dfs(board, l+1, y+1, x, word);
            if(x-1 >= 0)
                dfs(board, l+1, y, x-1, word);
            if(x+1 <= board[0].length-1)
                dfs(board, l+1, y, x+1, word);
            dp[y][x] = 0;
        }
    }
}

가장먼저 word안에 값이 해당 배열 안에서 이어지는 값이있는지 찾는 문제이다. 

그렇기에 전체 다 탐색을 해야하며, 2중포문에서 word 의 첫번째값(예시에서는 A) 이 있는 곳이면 dfs로 진입하도록 설정한다.

dfs 진입하여, 조금이라도 시간을 줄이기 위해 값이 발견되면 그 이후 동작은 안하도록 return 설정해주었고, 

상하좌우로 위치를 옮기도록 dfs를 설정했다.

주의할점은 상하좌우 진입할때 방문체크를 하고, 다 끝나면 하위에 방문체크를 해제해주어야한다.

/*
**m x n 크기의 그리드(grid)**가 주어졌으며, 각 칸에는 0 이상의 숫자가 들어 있습니다.

왼쪽 상단 **(grid[0][0])**에서 오른쪽 하단 **(grid[m-1][n-1])**으로 이동하는 경로 중에서,
경로 상의 숫자 합이 최소가 되는 경로를 찾으세요.

📌 제한 사항:

한 번에 오른쪽 또는 아래쪽으로만 이동할 수 있습니다.
*/

class Solution {
    public int minPathSum(int[][] grid) {
        int y = grid.length;
        int x = grid[0].length;

        int [][] dp = new int[y][x];

        dp[0][0] = grid[0][0];
        for(int i=1; i<x; i++) {
            dp[0][i] = dp[0][i-1] + grid[0][i];
        }
        for(int j=1; j<y; j++) {
            dp[j][0] = dp[j-1][0] + grid[j][0];
        }

        for(int j=1; j<y; j++) {
            for(int i=1; i<x; i++) {
                dp[j][i] = Math.min(dp[j-1][i], dp[j][i-1]) + grid[j][i];
            }
        }

        return dp[y-1][x-1];
    }
}

Example 1:

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

일단 최종구역까지 어느 구간이 최단거리인지 찾는 문제이다. dp 는 2차원 배열이 필요하다.

1열과 1행은 누적된 값을 넣어준다.

해당그림에서의 dp는

1  4  5

2  0  0

6  0  0

으로 초기화가 되고 dp 순차탐색이 시작된다.

점화식은 다음과 같다.

현재 기준으로 위와 왼쪽중에 최단거리를 찾아 grid[i][j](현재값) 을 더하면 현재 위치까지의 최단 거리가 나온다.

그렇게 끝까지 진행하고 리턴하면 정답이 나온다.

최종 dp 값은 이렇다.

1  4  5

2  7  6

6  8  7

따라서 7이 정답이다.

/*

두 개의 문자열 text1과 text2가 주어졌을 때,
두 문자열의 **최장 공통 부분 수열(Longest Common Subsequence, LCS)**의 길이를 반환하세요.
만약 공통 부분 수열이 없다면 0을 반환하세요.



*/

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int length1 = text1.length();
        int length2 = text2.length();
        int [][] dp = new int[length1+1][length2+1];

        for(int i=0; i<dp.length; i++) {
            Arrays.fill(dp[i], 0);
        }
        
        for(int i=1; i<=length1; i++) {
            for(int j=1; j<=length2; j++) {
                String a = text1.substring(i-1, i);
                String b = text2.substring(j-1, j);

                if(a.equals(b)) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }

        return dp[length1][length2];
    }
}

Example 1:

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

text1 과 text2 의 공통 부분 문자열의 길이를 리턴하는 문제이다

이때 2차원 dp 배열이 필요하다.

그 크기는 dp[text1 length+1][text2 length+2] 이며,

점화식은 다음과 같다.

초기값은 다음으로 시작한다.

여기서 a 부터 시작을한다 첫번째줄부터 실행하면, 다음과 같다.

a는 a 와 같으니 1로 채워줬다. 다음줄을 다시 보자

다음과 같이 표시가 된다. 각각을 살펴보면 a는 위쪽에 1이 더 크니, 1이들어가고 c와 e는 좌측에 1이 더 크니 1이 들어간다.

각각의 칸이 의미하는 것은 a는 ab 와 공통된 최대 부분이 1이고 ac와 ab, ab ae 도 마찬가지고 1이라는 뜻이다.

모든 칸을 채워보자.

이렇게 그려질 수 있고, 마지막의 3이 최대 길이로 반환된다.

시간복잡도는 o(mn) 이다.

/*
당신은 전문 강도로, 길을 따라 있는 집들을 털 계획을 세우고 있습니다. 
각 집에는 일정한 금액의 돈이 숨겨져 있으며, 
유일한 제약은 서로 인접한 두 집을 같은 날 털면 보안 시스템이 작동하여 경찰이 자동으로 출동한다는 것입니다.

정수 배열 nums가 주어지며, 이는 각 집에 숨겨진 돈의 금액을 나타냅니다. 
경찰을 경고하지 않으면서 오늘 밤에 훔칠 수 있는 최대 금액을 반환하세요.
*/

class Solution {
    public int rob(int[] nums) {
        int [] dp = new int[nums.length];
        
        if(nums.length == 1) {
            return nums[0];
        }
        else if(nums.length == 2) {
            return Math.max(nums[0], nums[1]);
        }
        else if(nums.length == 3) {
            return Math.max(nums[1], nums[0] + nums[2]);
        }

        dp[0] = nums[0];
        dp[1] = nums[1];
        dp[2] = nums[0] + nums[2];
        for(int i=3; i<nums.length; i++) {
            dp[i] = Math.max(nums[i]+dp[i-2],nums[i]+dp[i-3]);
        }

        return Math.max(dp[nums.length-1], dp[nums.length-2]);
    }
}

Example 1:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

인접한 곳은 털수 없다는 조건이 붙어있는 전형적인 dp 문제이다.

그렇기에 전 house 를 터는게 아니라, 전전 house 나 전전전 house 까지의 값이 현재값에 영향이 온다고 볼수 있다.

점화식은 다음과 같다.