http://boj.kr/480d56cedce24b1887732ad80aad6c12 선생님, 안녕하세요~ 이번 문제를 풀때 누적곱을 이용했는데요. 제일 앞부분에 1을 넣어놓고, n+1번째에 누적곱을 넣은 누적곱의 배열을 만들었습니다. 그리고, 이중 반복문을 진행하면서 a[i]를 a[j]로 나눠보며 최대값을 구해봤는데요. (a[0]는 1이라서, a[i]를 a[0]로 나누면 i번째 까지의 누적곱, 그 이후부터는 연속된 앞부분으로 나눈 것) 이중반복문으로 했다보니 시간초과가 나면 그렇구나 할텐데, 답이 틀렸다고 하니, 어디가 틀렸는지 잘 모르겠습니다. 처음부터 잘못 생각한 걸까요? 아니면 코드를 어딘가 잘못짠 부분이 있는걸까요?
큰돌님 안녕하십니까 커뮤니티 찾아보니까 insert 함수 첫 번째 인자는 이터레이터 값이 들어가야 해서 begin() + '넣어줘야 할 위치' 가 들어가야 오류가 안 나고 정상 작동한다고 봤는데 http://boj.kr/9fc8f9dd8de44b04b979a877da3962fd 이렇게 해도 백준에서 맞다고 합니다. 또 Programiz(c++ online Compiler)로 코딩하는데 오류 안 나고 잘 작동해서 해서 질문드립니다.
http://boj.kr/9bb703b0a79748328575376a22d93db1 안녕하세요 선생님 강의 잘 듣고 있습니다. 강의 에서는 if문에 if문을 적용하여 풀이를 하였는데, 공유드린 소스처럼 26의 나머지 값을 사용하여 풀어도 괜찮을까요? 결과는 동일 한데 어떤 방식으로 접근하는게 더 효율적인 접근방식인지 궁금합니다.
import java.util.*; class Main { static String answer = "NO"; static int n, total = 0; boolean flag = false; public void dfs(int L, int sum, int[] arr) { if(flag) return; if(sum > total/2) return; if(L == n){ if(total/2 == sum){ answer = "YES"; flag = true; } }else{ dfs(L + 1, sum + arr[L], arr); dfs(L + 1, sum, arr); } } public void main(String[] args) { Main T = new Main(); Scanner sc = new Scanner(System.in); n = sc.nextInt(); int[] arr = new int[n]; for(int i = 0; i < n; i++){ arr[i] = sc.nextInt(); total += arr[i]; } T.dfs(0, 0, arr); System.out.println(answer); } } 복습 차원에서 똑같이 코드를 실행하는데 런타임에러가 자꾸 발생하는 이유를 모르겠습니다.
정답의 경우 아래와 같이 되어있습니다. public int solution(int[] nums){ int answer = 0; HashSet<Integer> set = new HashSet<>(); for(int x : nums) set.add(x); for(int x : set){ if(set.contains(x - 1)) continue; int cnt = 0; while(set.contains(x)){ cnt++; x++; } answer = Math.max(answer, cnt); } return answer; } 제가 푼 방식 : set으로 중복되지 않은수만 우선순위 큐(pQ)에 넣어 계산. 물론 풀이에서의 코드가 간결하고 사용하는 자료형도 적으니 좋은 코드같습니다만은 이렇게 풀었을때 시간 복잡도 면에서도 많이 불리한지 피드백 부탁드립니다. public int solution(int[] nums){ int answer = 1 , cnt=1; PriorityQueue<Integer> pQ= new PriorityQueue<>(); HashSet<Integer> set = new HashSet<>(); for(int i : nums){ if(!set.contains(i)) pQ.offer(i);// set.add(i); } int N = pQ.poll(); while ( !pQ.isEmpty() ){ int nextN = pQ.poll(); if( N+1 == nextN ){ cnt++; N = nextN; } else if( N+1 != nextN ) { cnt = 1; N = nextN; } answer=Math.max(answer,cnt); } return answer; }
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 아래와 같이 작성하니까 예제 4번부터 틀렸다고 나옵니다. 어디가 잘못 된건지 궁금합니다. import java.io.*; import java.util.*; class Node implements Comparable<Node>{ int v1; int v2; double c; Node(int v1, int v2, double c) { this.v1=v1; this.v2=v2; this.c=c; } @Override public int compareTo(Node o) { //double형은 이렇게 한다. return Double.compare(this.c, o.c); } } public class Main { public static int n,m; public static int[] unf; public static ArrayList<Node> graph = new ArrayList<>(); public static ArrayList<Integer> x = new ArrayList<>(); public static ArrayList<Integer> y = new ArrayList<>(); public static int find(int v) { if(v==unf[v]) return v; else return unf[v] = find(unf[v]); } public static void union(int a, int b) { int fa = find(a); int fb = find(b); if(fa!=fb) unf[fa] = fb; } public static void main(String[] argvs) { Scanner sc = new Scanner(System.in); n=sc.nextInt(); m=sc.nextInt(); unf = new int[n]; for(int i=0; i<n; i++) unf[i] = i; for(int i=0; i<n; i++) { int a=sc.nextInt()-1; int b=sc.nextInt()-1; x.add(a); y.add(b); } for(int i=0; i<n; i++) { //점과 점 사이의 거리를 구하는 구문 for(int j=i+1; j<n; j++) { double dis = Math.sqrt((x.get(j)-x.get(i)) *(x.get(j)-x.get(i)) + (y.get(j)-y.get(i)) * (y.get(j)-y.get(i))); graph.add(new Node(i,j,dis)); } } for(int i=0; i<m; i++) { //이미 연결되어 있는 점들은 union해준다 int a=sc.nextInt(); int b=sc.nextInt(); union(a-1,b-1); } Collections.sort(graph); double answer=0; for(int i=0; i<graph.size(); i++) { //크루스칼 int fa = find(graph.get(i).v1); int fb = find(graph.get(i).v2); double cost = graph.get(i).c; if(fa!=fb) { //union(fa, fb); unf[fa] = fb; answer+=cost; } } System.out.format("%.2f", answer); //소수점 출력은 System.out.format으로 } }
그리디 알고리즘과 coin change 은강의에 없던데 디스코드 문제 목록에coin change 문제가 있어 의아해서 질문 드립니다 수업에는 따로 진행을 안하지만 별개로 디코에 문제를 올려주신건가요 ? 강의 주차와 디코 주차가 일치하지않아제목보고 하나하나 찾아가야 해서 정리가 되지 않은 느낌이 들고 심지어 누락된 것도 있어서 헷갈려서 질문드려요
시간관련 질문 --> 모든 칸을 뒤지면서 속도만큼 for문을 돌린다고 했을 때 최대값으로 계산을 하면 100 * 100 * 1000 =1000만이 나오는데 시간초과가 나온다고 하셨는데 그 이유가 무엇일까요 ? 제가 짠 로직을 테스트케이스와 찾아본 모든 반례를 넣어도 통과가 되는데 틀렸다고 나오는데 이유를 알고싶습니다. http://boj.kr/22beb014767543189300a4a0fb48b227
안녕하세요 fill 초기화 관련해서 질문이 있어 문의드립니다. http://boj.kr/00d897247c6444c892367e2aba528316) http://boj.kr/bd2af7cba0de4b399e84dd0b74e5cc08 1번은 실패, 2번은 성공인데 fill 함수 초기화하는 부분을 제외하면 둘 다 같은데 1번을 제출하면 런타임에 러(OutOfBounds)가 발생하는데 원인이 궁금합니다. 감사합니다.
https://blog.naver.com/aratino5165/223431323815 설명 다적혀있는 구현문제라 쉬울줄 알았는데 테스트 케이스가 맞는게 거의 없습니다. 문자열을 L, R로 쪼개고 L을 규칙에 맞게 수정 R로 위에것 반복 으로 이해했는데 큰돌님 코드를 보니 string c부터 이해가 안됩니다.
if day > N: return -999999999999 해당 부분을 -2 혹은 -99 등으로 조건을 바꾸면 왜 통과가 안되는지 궁금합니다. -999까지는 통과가 되더라고요 import sys N = int(sys.stdin.readline()) answer = 0 plan = [] for _ in range(N): plan.append(list(map(int, sys.stdin.readline().split()))) #dp[day]를 계산하는 함수 def rec(day): if day > N: return -999999999999 if day == N: return 0 #dp[day]가 한번이라도 계산된적 있다면 두번 할 필요없음 if dp[day] != -1: return dp[day] dp[day] = max(rec(day + plan[day][0]) + plan[day][1], rec(day + 1)) return dp[day] dp = [-1 for _ in range(N + 1)] rec(0) print(dp[0]) #dp[0]은 첫째날 선택했는지 아닌지까지 포함한 최대값
import java.util.*; import java.io.*; class Main { final static int MAX = 100000 + 10; static ArrayList<Integer>[] graph; static boolean[] visited; static int N, M, R; static int[] answer; static int order; public static void dfs(int idx){ visited[idx] = true; answer[idx] = order; order++; for(int i = 0; i < graph[idx].size(); i++){ int next = graph[idx].get(i); if(visited[next] == false) dfs(next); } } public static void main(String[] args) throws IOException{ // 0. 입력 및 초기화 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()); R = Integer.parseInt(st.nextToken()); // 1. graph에 연결 정보 채우기 graph = new ArrayList[MAX]; for(int i = 1; i <= N; i++) graph[i] = new ArrayList<>(); visited = new boolean[MAX]; answer = new int[MAX]; order = 1; for(int i = 0; i < M ;i++){ st = new StringTokenizer(br.readLine()); int x = Integer.parseInt(st.nextToken()); int y = Integer.parseInt(st.nextToken()); graph[x].add(y); graph[y].add(x); } // 2. 오름차순 정렬 for(int i = 1; i <= N; i++) Collections.sort(graph[i], Collections.reverseOrder()); // 3. dfs(재귀함수 호출) dfs(R); // 4. 출력 for(int i = 1; i <=N; i++){ bw.write(String.valueOf(answer[i])); bw.newLine(); } bw.close(); br.close(); } } 위 제공 답안 코드에서 Collections.reverseOrder() 위 처럼 revserOrder()를 걸어주신게 잘못 작성된 내용 같은데 혹시 제가 잘못 확인한걸까요? 일단 해당 코드로 그대로 백준에 올리면 안되고 있는 상태입니다! 그리고 answer나 visited에 MAX를 넣으시는 이유가 궁급합니다! 방문정보나 answer의 경우 N+1로도 초기화가 가능하지 않나요? 혹시 더 복잡한 문제등에서 풀이의 간결성을 위해 필요한 방법일까요?? -- 강의 너무 잘 보고 있습니다! 훌륭한 강의 찍어주셔서 감사합니다!
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. import java.util.Arrays; import java.util.Scanner; public class lecture27 { public static void main(String[] args) { Scanner scanner=new Scanner(System.in); int n=scanner.nextInt(); int m=scanner.nextInt(); int []arr=new int[n]; for (int i = 0; i <n ; i++) { arr[i]=scanner.nextInt(); } int count=0; for (int i = 0; i <n ; i++) { int sum=arr[i]; for (int j = i+1; j <n ; j++) { sum=sum+arr[j]; if(sum==m) { count++; } else if(sum>=m) { break; } } } System.out.println(count); } } 이 코드로 정답입니다는 받았는데 , 제 생각에는 O(n^2)이라 시간 초과가 나야할것 같은데 이중 for문이니까 시간 초과가 나지 않아서 어떤 부분에서 잘못 생각한건지 궁금합니다.
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. https://www.acmicpc.net/board/view/141897
