23,100원
다른 수강생들이 자주 물어보는 질문이 궁금하신가요?
- 해결됨[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편
final 선언 이유
Main 클래스 안에서MAX 변수에 대해 굳이 final로 초기화 하는 이유가 무엇일까요?
- 해결됨[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편
이상한게 햇갈리는데요.....
저번 수업도 그렇고...반복문 작성할 때 아 이거는 i<N인가? M인가? 이게 햇갈리는데, 뭐 좋은 방법 없을까요?
- 해결됨[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편
혹시 구현문제의 대한 강의는 올라오지 않을까요?
혹시 구현문제의 대한 강의는 올라오지 않을까요?다음 예정된 강의는 어떤 종류의 알고리즘인지 궁금합니다.
- 해결됨[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편
MAX 크기가 왜 1000000인가요?
정점의 수 N은 100,000개 까지인데이를 담는 배열의 최대 크기인 MAX가 왜1,000,000로 잡았는지 궁금합니다(+ 10은 연산 때문에 그렇다고 하셨던것같고)
- 해결됨[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편
백준 1325 질문있습니다!
안녕하세요! 강의를 다 듣고, 블로그에 남겨주신 문제들을 풀어보고 있습니다.'백준 1325 효율적인 해킹 문제'인데, 시간 초과가 나는 기준을 이해하지 못해서 질문드립니다!import java.io.*; import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.StringTokenizer; public class Main { private static int N, M; private static List<List<Integer>> graph; private static boolean[] visited; private static int dfs(int idx) { visited[idx] = true; int count = 1; for (int next : graph.get(idx)) { if (!visited[next]) { count += dfs(next); } } return count; } 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 = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); graph = new ArrayList<>(N + 1); for (int i = 0; i <= N; i++) { graph.add(new ArrayList<>()); } for (int i = 0; i < M; i++) { st = new StringTokenizer(br.readLine()); int a = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken()); graph.get(b).add(a); } int max = -1; List<Integer> answer = new ArrayList<>(); for (int i = 1; i <= N; i++) { visited = new boolean[N + 1]; int count = dfs(i); if (max < count) { answer.clear(); answer.add(i); max = count; } else if (max == count) { answer.add(i); } } Collections.sort(answer); StringBuilder sb = new StringBuilder(); for (int n : answer) { sb.append(n); sb.append(" "); } bw.write(sb.toString()); br.close(); bw.close(); } } 이렇게 작성을 하니 자꾸 시간 초과가 나와서 chat gpt에 질문해보니 메모이제이션을 사용하면 해결할 수 있다는 답변이 나왔습니다. 이미 visited를 사용해 이미 방문한 노드를 다시 방문하지 않는데, 메모이제이션을 사용하는게 의미가 있을까 싶었지만 일단 코드를 변경해봤습니다.import java.io.*; import java.util.*; public class Main { private static int N, M; private static List<List<Integer>> graph; private static boolean[] visited; private static int[] memo; private static int dfs(int idx) { if (memo[idx] != -1) { return memo[idx]; } visited[idx] = true; int count = 1; for (int next : graph.get(idx)) { if (!visited[next]) { count += dfs(next); } } memo[idx] = count; return count; } 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 = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); graph = new ArrayList<>(N + 1); for (int i = 0; i <= N; i++) { graph.add(new ArrayList<>()); } for (int i = 0; i < M; i++) { st = new StringTokenizer(br.readLine()); int a = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken()); graph.get(b).add(a); } int max = -1; List<Integer> answer = new ArrayList<>(); for (int i = 1; i <= N; i++) { visited = new boolean[N + 1]; memo = new int[N + 1]; Arrays.fill(memo, -1); int count = dfs(i); if (max < count) { answer.clear(); answer.add(i); max = count; } else if (max == count) { answer.add(i); } } Collections.sort(answer); StringBuilder sb = new StringBuilder(); for (int n : answer) { sb.append(n); sb.append(" "); } bw.write(sb.toString()); br.close(); bw.close(); } } 이렇게 작성하니까 시간 초과가 나지는 않는데, 어느 테스트 케이스에서 memo 배열에 저장된 값을 사용하는건지 알 수 있을까요?그리고 혹시 강사님은 이 문제를 이것과 다르게 푸셨을까요?? ++ 추가로 배열 대신 HashMap을 사용해도 시간 초과가 납니다... ㅠimport java.io.*; import java.util.*; public class Main { private static int N, M; private static List<List<Integer>> graph; private static boolean[] visited; private static Map<Integer, Integer> map; private static int dfs(int idx) { if (map.get(idx) != null) { return map.get(idx); } visited[idx] = true; int count = 1; for (int next : graph.get(idx)) { if (!visited[next]) { count += dfs(next); } } map.put(idx, count); return count; } 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 = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); graph = new ArrayList<>(N + 1); for (int i = 0; i <= N; i++) { graph.add(new ArrayList<>()); } for (int i = 0; i < M; i++) { st = new StringTokenizer(br.readLine()); int a = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken()); graph.get(b).add(a); } int max = -1; List<Integer> answer = new ArrayList<>(); for (int i = 1; i <= N; i++) { visited = new boolean[N + 1]; map = new HashMap<>(); int count = dfs(i); if (max < count) { answer.clear(); answer.add(i); max = count; } else if (max == count) { answer.add(i); } } Collections.sort(answer); StringBuilder sb = new StringBuilder(); for (int n : answer) { sb.append(n); sb.append(" "); } bw.write(sb.toString()); br.close(); bw.close(); } }
- 해결됨[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편
촌수계산질문
안녕하세요! 선생님이 알리켜주신대로 한번 다시 하다가 저는 bfs 메소드에서 ++count로 했는데 count+1과 무슨 차이가 있을까요?? 백준에서 돌려봤더니 틀렸다고 떠요! private static void dfs(int start, int count) { visited[start]=true; if(start==end){ answer=count; return; } for(int i=1;i<=N;i++){ if(visited[i]==false&&graph[start][i]){ dfs(i,++count); } } }
- 해결됨[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편
[질문] 유기농 배추 map 정보 반영 건
안녕하세요, 강의 잘 듣고 있습니다. map 정보 반영에서 map[y+1][x+1] = true; 라고 하셨는데, map[x+1][y+1]도 true값을 넣어야 하지 않을까요?빠른 답변 부탁합니다.감사합니다.
- 해결됨[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편
(백준 1260) 큐 사용에 대해서 질문드립니다!
선생님 덕분에 회차를 거듭할수록 재귀에 대한 이해도가 높아지고 있습니다 감사합니다!기존에 계속 독학으로 하다보니 제가 아는 내용과 조금 다른 부분이 있어 오늘만 벌써 두번째 질문이네요 ㅜㅜ기존에 큐를 구현할때 Queue<Integer> q = new LinkedList<>();혹은 PriorityQueue<Integer>pq = new PriorityQueue<>();로 구현해서 사용했었습니다!근데 혹시 ArrayList로 구현하시는 이유가 있을까요?? 하나 더 여쭤보자면...dfs는 재귀함수를 호출하는게 필수인데 비해bfs는 재귀호출이 없는데그럼 bfs는 재귀가 아닌 queue를 무조건적으로 사용한다고 생각하면 될까요? 매번 훌륭한 강의 감사드립니다!!
- 해결됨[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편
(백준 24479) 강의에서 오름차순 정렬시 궁금한 점이 있습니다!
선생님 매번 감사합니다 유튜브부터 많이 도움을 받아 오늘 강의까지 결제하게 되었네요 :)for 문 안에 collections.sort를 사용하셔서 정렬하셨는데 저는 사실 그동안 Arrays.sort만 사용했었거든요프로그래머스에서 다른사람 풀이를 참고하다보면 Collections.sort 가 꽤 많이 나오더라구요합병정렬과 퀵정렬의 차이라는 이론적인 부분 외에 바꿔 사용해도 문제가 없는지, 효율적으로 다른부분이 있는지 궁금합니다! 추가적으로 궁금한게 하나 더 생겨서 수정합니다!문제에서 보면 노드의 방문순서를 출력하라고 했는데for(int i = 1; i <=N, i++) { bw.write(String.valueOf(answer[i]));로 출력해주셨습니다!리스트를 정렬해주었기에 크게 문제가 없는것인가 싶은데...조금 극단적으로 예시를answer[1] = 1answer[2] = 4answer[3] = 2answer[4] = 5answer[5] = 3이라고 했을때사용해주신 방식으로 출력하면 1,4,2,5,3 이 출력되나실제로 방문한 순서는 1,3,5,2,4로 상이하다는 생각이 들었습니다그래서 이중 for문을 사용하여for(int i = 1; i <=N; i++) { for (int j = 1; j <= N; j++) { if (i == answer[j]) 일때 j 의 값을 출력하는게순서를 출력하는게 아닌가.. 라는 의구심이 들었습니다혹시 제가 이해를 잘못하고 있는거라면 지적해주시면 감사히 듣겠습니다!
- 해결됨[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편
가중치가 1 이상일 경우~
백준 - 깊이우선탐색 강의에서 "모든 간선의 가중치가 1"이라고 되어 있는데 이게 정확히 무슨 의미 일지요? 가중치가 1 이상이면 이 가중치 정보를 그래프에 담아야 할까요??(구조체 사용)
- 해결됨[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편
Bfs 강의 도입이 시급합니다!!
강의가 너무 좋네요~~ bfs 강의도 올려주실 계획 없나요~~~ (언어는 c++ 어떨지 조심스럽게 말씀드려봅니다 ㅎㅎ)