묻고 답해요
130만명의 커뮤니티!! 함께 토론해봐요.
인프런 TOP Writers
-
해결됨10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
1-M 반례 질문
안녕하십니까 큰돌님정답 맞추긴 했는데 틀렸던 코드 중에서 반례가 무엇이 있는지 궁금해서 질문드립니다.http://boj.kr/72c2759cc7fc49bc81d88d5c5cdbdd17
-
해결됨코딩테스트 [ ALL IN ONE ]
bfs 시간복잡도 관련 질문입니다!
안녕하세요! 열심히 수강하다가 질문이 생겨 작성하게 되었습니다:> '''질문 : 이 함수의 시간복잡도는 O(n^3)인가?'''def bfs(graph, start_v): visited = [start_v] queue = deque(start_v) while queue: cur_v = queue.popleft() for v in graph[cur_v]: if v not in visited: visited.append(v) queue.append(v) return visited 위의 코드를 템플릿처럼 외우라고 하신 함수 시간복잡도가 궁금합니다!제가 생각하기로는 n(vertax의 수만큼 while문 실행) x n(for문) x n(리스트 in 연산자 수행) -> O(n^3) 이라고 생각하는데 이게 맞는걸까요??
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
누적곱을 이용한 풀이
http://boj.kr/480d56cedce24b1887732ad80aad6c12 선생님, 안녕하세요~ 이번 문제를 풀때 누적곱을 이용했는데요.제일 앞부분에 1을 넣어놓고, n+1번째에 누적곱을 넣은 누적곱의 배열을 만들었습니다.그리고, 이중 반복문을 진행하면서 a[i]를 a[j]로 나눠보며 최대값을 구해봤는데요. (a[0]는 1이라서, a[i]를 a[0]로 나누면 i번째 까지의 누적곱, 그 이후부터는 연속된 앞부분으로 나눈 것)이중반복문으로 했다보니 시간초과가 나면 그렇구나 할텐데, 답이 틀렸다고 하니, 어디가 틀렸는지 잘 모르겠습니다. 처음부터 잘못 생각한 걸까요? 아니면 코드를 어딘가 잘못짠 부분이 있는걸까요?
-
해결됨10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
1-K insert 질문
큰돌님 안녕하십니까커뮤니티 찾아보니까 insert 함수 첫 번째 인자는 이터레이터 값이 들어가야 해서 begin() + '넣어줘야 할 위치' 가 들어가야 오류가 안 나고 정상 작동한다고 봤는데http://boj.kr/9fc8f9dd8de44b04b979a877da3962fd이렇게 해도 백준에서 맞다고 합니다. 또 Programiz(c++ online Compiler)로 코딩하는데 오류 안 나고 잘 작동해서 해서 질문드립니다.
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
1-J 반례
안녕하십니까 큰돌님코드를 작성했었는데 틀렸다고 하는데 반례 어떤게 있을까요 ??반례와 왜 안 되는지도 설명 한 번 부탁드립니다 ㅜㅠhttp://boj.kr/4eae857b9f4243aa90c9206ce1aabd15
-
미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
왜 시간초과가 나는지 모르겠습니다.
import java.util.HashMap; import java.util.Map; import java.util.Scanner; public class 매출액의_종류 { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int n = scan.nextInt(); int k = scan.nextInt(); int[] arr = new int[n]; for(int i=0;i<n;i++){ arr[i] = scan.nextInt(); } System.out.println(mySol(n,k,arr)); } private static String mySol(int n, int k, int[] arr) { String result = ""; Map<Integer,Integer> map = new HashMap<>(); for(int i=0;i<k-1;i++){ map.put(arr[i],map.getOrDefault(arr[i],0) + 1); } int lt = 0; for(int rt=k-1;rt<n;rt++){ map.put(arr[rt],map.getOrDefault(arr[rt],0) + 1); result += map.size() + " "; map.put(arr[lt], map.get(arr[lt]) - 1); if(map.get(arr[lt]) == 0) map.remove(arr[lt]); lt++; } return result; } }
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
1-f 질문있습니다.
http://boj.kr/9bb703b0a79748328575376a22d93db1안녕하세요 선생님 강의 잘 듣고 있습니다.강의 에서는 if문에 if문을 적용하여 풀이를 하였는데,공유드린 소스처럼 26의 나머지 값을 사용하여 풀어도 괜찮을까요?결과는 동일 한데 어떤 방식으로 접근하는게 더 효율적인 접근방식인지 궁금합니다.
-
미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
똑같이 작성하고 실행하는데 런타임에러가 발생해요
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); } }복습 차원에서 똑같이 코드를 실행하는데 런타임에러가 자꾸 발생하는 이유를 모르겠습니다.
-
해결됨10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
2-L 어디가 틀린지 모르겠습니다 ㅠ
안녕하세요 문제를 풀다가 예제는 다 통과하고 질문게시판도 전부 봤는데 어디가 틀렸는 지를 찾지 못하겠어서 질문글 남깁니다! http://boj.kr/0b960e678b4a42f4b5628dd239f9f22a
-
미해결자바 코딩테스트 - it 대기업 유제
최대 길이 연속수열 질문
정답의 경우 아래와 같이 되어있습니다.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; }
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
4-H 질문있습니다
안녕하세요.마지막 출력값인 하나의 벽을 제거하였을 경우 얻을 수 있는 가장 넓은 방의 크기를 dfs를 이용해서 풀어봤는데요.계속 '틀렸습니다'가 나오는데 뭐가 문제인지 모르겠습니다.http://boj.kr/3f53f0669cec483f9a0ff04af2b9f4f9
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
큰돌님 vscode 폰트색상
안녕하세요 큰돌님! vscode 폰트색상이 맘에드는데 어떻게 적용하는지 알 수 있을까요?!?!
-
미해결코딩테스트 실전 모의고사(with C++) : 대기업 대비
호텔 연결 질문드립니다.
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 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으로 } }
-
해결됨코딩테스트 [ ALL IN ONE ]
디스코드문제
그리디 알고리즘과 coin change 은강의에 없던데 디스코드 문제 목록에coin change 문제가 있어 의아해서 질문 드립니다 수업에는 따로 진행을 안하지만 별개로 디코에 문제를 올려주신건가요 ? 강의 주차와 디코 주차가 일치하지않아제목보고 하나하나 찾아가야 해서 정리가 되지 않은 느낌이 들고 심지어 누락된 것도 있어서 헷갈려서 질문드려요
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
5-T 질문있습니다
시간관련 질문 --> 모든 칸을 뒤지면서 속도만큼 for문을 돌린다고 했을 때 최대값으로 계산을 하면 100 * 100 * 1000 =1000만이 나오는데 시간초과가 나온다고 하셨는데 그 이유가 무엇일까요 ?제가 짠 로직을 테스트케이스와 찾아본 모든 반례를 넣어도 통과가 되는데 틀렸다고 나오는데 이유를 알고싶습니다. http://boj.kr/22beb014767543189300a4a0fb48b227
-
해결됨10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
fill 초기화 관련해서 질문이 있습니다.
안녕하세요 fill 초기화 관련해서 질문이 있어 문의드립니다. http://boj.kr/00d897247c6444c892367e2aba528316)http://boj.kr/bd2af7cba0de4b399e84dd0b74e5cc08 1번은 실패, 2번은 성공인데 fill 함수 초기화하는 부분을 제외하면 둘 다 같은데 1번을 제출하면 런타임에러(OutOfBounds)가 발생하는데 원인이 궁금합니다. 감사합니다.
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
히든퀘스트2-3 질문이 있습니다.
https://blog.naver.com/aratino5165/223431323815설명 다적혀있는 구현문제라 쉬울줄 알았는데 테스트 케이스가 맞는게 거의 없습니다.문자열을 L, R로 쪼개고 L을 규칙에 맞게 수정R로 위에것 반복으로 이해했는데 큰돌님 코드를 보니 string c부터 이해가 안됩니다.
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
7-B 탑다운 vs 바텀업 질문
코드 : http://boj.kr/febf6425d0184aeb834f64197f68727b 안녕하세요. 저는 이문제를 재귀dp로 풀었봤는데요,큰돌님은 이문제는 바텀업으로 푸셨고 자두나무같은경우에 탑다운으로 푸셨던데, 두 방법중에 어떤방법으로 풀어야겠다를 선택하시는 기준이 있는지요?저같은경우는 경우의수가 잘 나눠지면 재귀(탑다운)로 풀고아니면 해보면서 관찰이 필요한경우 for문(바텀업)으로 풀려고 생각을 정했는데 이게 맞을까요?
-
해결됨2주만에 통과하는 알고리즘 코딩테스트 (2024년)
[탑다운] 상담문제
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]은 첫째날 선택했는지 아닌지까지 포함한 최대값
-
해결됨[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편
강사님 안녕하세요! 깊이 우선 탐색 2 (백준 24480)에서 제공하는 풀이 코드에서 궁금한 점이 있어서 질문 드립니다!
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로도 초기화가 가능하지 않나요? 혹시 더 복잡한 문제등에서 풀이의 간결성을 위해 필요한 방법일까요?? --강의 너무 잘 보고 있습니다! 훌륭한 강의 찍어주셔서 감사합니다!