T, M, N, K를 입력받아 사용한다고 하셨는데, M과 K는 각각 세로와 가로값으로 입력받고, K는 배추의 위치라는것을 알았습니다. 근데 T는 테스크케이스 라는 언급을 하셨고 코드에서도 아래와 같이 작성되있습니다. while (T-- > 0) { StringTokenizer st = new StringTokenizer(br.readLine()); M = Integer.parseInt(br.readLine()); N = Integer.parseInt(br.readLine()); K = Integer.parseInt(br.readLine()); // map 정보 // dfs 수행 .... } 2번의 테스크케이스를 만드는 이유는 무엇인가요? 그리고 단순히 궁금해서 여쭤보는데 가로와 세로 순서로 입력받고 코드를 실행하는것이 아닌 거꾸로 세로와 가로 순으로 실행하는지 궁굼합니다. 답변 부탁드립니다. 감사합니다.
안녕하세요. 위의 코드는 제가 강의를 듣기 전에 작성한 코드입니다. 백준에서 2가지로 주어진 테스트 케이스는 통과하는데 코드를 제출하면 틀렸다고 나옵니다. 코드 어디가 잘못된지를 모르겠습니다. 그리고 강의에서는 dfs 함수에 start 변수만 넣지 않고 count 변수도 넣으셨는데 count변수를 매개변수로 넣지 않고 코드를 작성하는 방법이 있는지 궁금하고, 이러한 방법이 없다면 왜 매개변수로 count 변수를 넣어줘야 하는걸까요?
BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); N = Integer.parseInt(br.readLine()); M = Integer.parseInt(br.readLine()); graph = new boolean[N][N]; visited = new boolean[N]; int x, y; for (int i=0; i<=M; i++) { StringTokenizer tokenizer = new StringTokenizer(br.readLine()); x = Integer.parseInt(tokenizer.nextToken())-1; y = Integer.parseInt(tokenizer.nextToken())-1; graph[x][y] = true; graph[y][x] = true; } dfs(0); System.out.println(answer - 1); br.close(); } void dfs(int index) { visited[index] = true; IntStream.range(0, M).forEach(i -> { if (!visited[i] && graph[index][i]) dfs(i); }); answer++; } 위에처럼 저는 +1을하지않고(그래프에 0인덱스들은 사용을 안한다고 생각해서요.) 대신 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수를 입력받을 때 -1을해줘서 처리했는데요. 예제입력은 정상처리 되나 실제 제출해보면 런타임 에러 (ArrayIndexOutOfBounds)가 발생합니다. +1을 해줘야하는거같은데... 제가 생각한 배열사이즈, -1로 입력받기가 잘못된걸까요?
안녕하세요 저는 강사님 강의로 공부하고 파이썬으로 코테를 준비하고 있습니다. 저와 같은 상황에 계신분들과 공유하고 싶어 글을 올립니다. 파이썬 풀이에서 부족한 부분 알려주시면 수정하겠습니다.~ import sys sys.setrecursionlimit(10 ** 6) N, M = map(int, sys.stdin.readline().split()) MAX = 1000 + 10 graph = [[False for in range(MAX)] for in range(MAX)] visited = [False for in range(MAX)] for in range(M): x, y = map(int, sys.stdin.readline().split()) graph[x][y] = True graph[y][x] = True def dfs(idx): visited[idx] = True for j in range(1, N + 1): if not visited[j] and graph[idx][j]: dfs(j) cnt = 0 for i in range(1, N + 1): if not visited[i]: dfs(i) cnt += 1 print(cnt)
안녕하세요! 강의를 다 듣고, 블로그에 남겨주신 문제들을 풀어보고 있습니다. '백준 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(); } }
선생님 덕분에 회차를 거듭할수록 재귀에 대한 이해도가 높아지고 있습니다 감사합니다! 기존에 계속 독학으로 하다보니 제가 아는 내용과 조금 다른 부분이 있어 오늘만 벌써 두번째 질문이네요 ㅜㅜ 기존에 큐를 구현할때 Queue<Integer> q = new LinkedList<>(); 혹은 PriorityQueue<Integer>pq = new PriorityQueue<>(); 로 구현해서 사용했었습니다! 근데 혹시 ArrayList로 구현하시는 이유가 있을까요?? 하나 더 여쭤보자면... dfs는 재귀함수를 호출하는게 필수인데 비해 bfs는 재귀호출이 없는데 그럼 bfs는 재귀가 아닌 queue를 무조건적으로 사용한다고 생각하면 될까요? 매번 훌륭한 강의 감사드립니다!!
선생님 매번 감사합니다 유튜브부터 많이 도움을 받아 오늘 강의까지 결제하게 되었네요 :) for 문 안에 collections.sort를 사용하셔서 정렬하셨는데 저는 사실 그동안 Arrays.sort만 사용했었거든요 프로그래머스에서 다른사람 풀이를 참고하다보면 Collections.sort 가 꽤 많이 나오더라구요 합병정렬과 퀵정렬의 차이라는 이론적인 부분 외에 바꿔 사용해도 문제가 없는지, 효율적으로 다른부분이 있는지 궁금합니다! 추가적으로 궁금한게 하나 더 생겨서 수정합니다! 문제에서 보면 노드의 방문순서를 출력하라고 했는데 for(int i = 1; i <=N, i++) { bw.write(String.valueOf(answer[i])); 로 출력해주셨습니다! 리스트를 정렬해주었기에 크게 문제가 없는것인가 싶은데... 조금 극단적으로 예시를 answer[1] = 1 answer[2] = 4 answer[3] = 2 answer[4] = 5 answer[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 의 값을 출력하는게 순서를 출력하는게 아닌가.. 라는 의구심이 들었습니다 혹시 제가 이해를 잘못하고 있는거라면 지적해주시면 감사히 듣겠습니다!
안녕하세요! 바둑이 승차 문제 풀이 영상을 보고 다른 풀이로도 한번 풀어봤는데 예제 입출력대로는 제대로 나오는데 혹시 제 풀이가 맞는지 질문하고자 코드를 올립니다. C,N=map(int,input().split()) weights=[] result=[] for _ in range(N): weights.append(int(input())) def dfs(L,sum): if sum>C: return if L==N: result.append(sum) else: dfs(L+1,sum+weights[L]) dfs(L+1,sum) dfs(0,0) print(max(result))
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. dx dy가 -1 0 1 0 정해졌는데 이 설명이 9시 3시 6시 그러시는데.... 이해가 잘 안됩니다 dx dy기준 -1,0이 12시라고 그러시는데 x좌표가 -1 y좌표가 0이면 9시 아닌가요?? 어떤 방향인지 이해가 안됩니다
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 바둑이 승차 문제 질문있습니다 DFS함수 내 else구문에서 DFS(L+1, sum, arr); 의 역할과 arr은 무엇인가요? sum에 arr[L] 바둑이 더하는거까지 이해했는데 마지막 3번쨰 요소 arr이 뭔지 모르겠습니다
선생님 섹션 8의 9번 동전교환 문제를 복습하면서 풀어보니 손에 익어서 이젠 풀 수 있게 되었습니다. 여기서 문제를 변형시켜서 가장 적은 동전갯수를 반환하는게 아닌, 가장 작은 동전 갯수를 가진 동전 종류의 배열 (해당 문제의 경우 [5,5,5])를 반환하도록 문제를 풀고있는 중인데요. 간단할 거 같았는데 의외로 잘 안풀리네요 ㅠㅠ 출력해보면서 이리저리 해보는데 접근 방법과 풀이를 알려주실 수 있을지 여쭙습니다. 아래는 여태 작성한 제 코드입니다. let answer = Number.MAX_SAFE_INTEGER let len = arr.length let tmp = [] function DFS(L , sum){ if (sum > m) return if (L > answer) return if (sum === m) { answer = Math.min(answer, L) console.log(answer) console.log(tmp) tmp = [] } else { for (let i=0; i<len; i++){ DFS(L+1 , sum+arr[i]) if (!tmp.length || tmp.reduce((a,b)=>a+b) <= m) tmp.push(arr[i]) } } } DFS(0, 0) return answer } let arr=[1, 2, 5]; console.log(solution(15, arr));
