월 15,400원
5개월 할부 시다른 수강생들이 자주 물어보는 질문이 궁금하신가요?
- 미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
8.수열 추측하기
이 문제에서 N이 만약 5일 경우, 더한 결과값이 값에 각각 4C0 4C1 4C2 4C3 4C4 를 곱해서 더한것과 같다고 하셨는데 왜 그런지 이유를 모르겠습니다..!!ㅜㅜ
- 미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
9_6 친구인가(서로소문제)
안녕하세요 교수님, 질문이있어서 글 남깁니다.교수님과 살짝 다른풀이로 풀었는데, 채점하는 사이트에서 계속 첫번째 케이스에서 runtime error가 나서요ㅠㅠ다른 테스트케이스들은 잘돌아가는데 첫번째만 안돌아갑니다ㅜㅜ자바 이클립스에서도 문제없이 예제테스트케이스 (첫번째 테스트케이스) 돌아갑니다.... // 서로소 집합 (유니온파인드) import java.util.*; class Main { static int n,m=0; //n:학생수, m:순서쌍개수static int[] parent; public static int find(int x) {if(x==parent[x]) return x;elsereturn parent[x]=find(parent[x]); //최상위 부모 누구인지 } public static void main(String[] args) {Main tree=new Main();Scanner scanner=new Scanner(System.in);n=scanner.nextInt();m=scanner.nextInt();parent=new int[n+1]; //배열 초기화 해야됨 - 자기자신이 부모가 되도록 초기화for(int i=1; i<=n; i++) {parent[i]=i;} //입력받아서 배열만들기for(int i=1; i<=m; i++) {int par=scanner.nextInt();int son=scanner.nextInt();parent[son]=par;} int a=scanner.nextInt();int b=scanner.nextInt(); if( (tree.find(a)) != (tree.find(b)) ){ System.out.print("NO"); } else System.out.print("YES"); } }
- 미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
DFS, BFS 풀이 차이점
import java.util.*; import java.io.*; /* 다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다. 입력 : 첫 번째 줄에는 동전의 종류개수 N(1<=N<=12)이 주어진다. 두 번째 줄에는 N개의 동전의 종류가 주어지고, 그 다음줄에 거슬러 줄 금액 M(1<=M<=500)이 주어진다.각 동전의 종류는 100원을 넘지 않는다. 출력 : 첫 번째 줄에 거슬러 줄 동전의 최소개수를 출력한다. ex. 3 1 2 5 15 -> 3 ( 출력 설명 : 5 5 5 동전 3개로 거슬러 줄 수 있다. ) */ public class P05_동전교환 { static int N, total, answer; static Integer[] coins; public static void main(String[] args) throws Exception { // 초기 세팅 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); N = Integer.parseInt(br.readLine()); coins = new Integer[N]; StringTokenizer st = new StringTokenizer(br.readLine()); for (int i=0; i<N; i++) { coins[i] = Integer.parseInt(st.nextToken()); } total = Integer.parseInt(br.readLine()); // 로직 Arrays.sort(coins, Collections.reverseOrder()); // coins 내림차순 정렬 (int[] 배열이 아닌 Integer[] 배열이여야 함 !!) // 방법1. BFS // BFS(); // 방법2. DFS answer = total; DFS(0, 0); // 출력 System.out.println(answer); } public static void BFS() { Queue<Integer> q = new LinkedList<>(); for (int i=0; i<N; i++) { q.offer(coins[i]); } int count = 1; while (true) { int size = q.size(); for (int i=0; i<size; i++) { int tmp = q.poll(); for (int j=0; j<N; j++) { int next = tmp + coins[j]; if (next == total) { answer = count + 1; return; } q.offer(next); } } count++; } } public static void DFS(int count, int sum) { if (sum > total || count >= answer) { return; } if (sum == total) { answer = Math.min(answer, count); } else { for (int i=0; i<N; i++) { DFS(count+1, sum+coins[i]); } } } } 처음에 혼자 풀 때 BFS 문제인 것 같아 BFS로 풀었고, 강의보고 나서 다시 DFS로 풀어봤는데DFS와 BFS 풀이 방법 중 어느 것이 더 좋은 방법인가요 ?성능면에서 DFS와 BFS 중 어떤 것이 더 좋은지 궁금합니다 .. !
- 미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
return; 유무
public static void DFS(int index, int sum) { if (sum > C) { return; } if (index == N) { answer = Math.max(answer, sum); return; } else { DFS(index+1, sum+arr[index]); DFS(index+1, sum); } }if(index == N) {} << 여기에서 강사님은 return;을 따로 쓰지 않으셨던데 return; 을 쓰거나 쓰지 않는 기준이 따로 있는건가요 ?? 어차피 저쪽으로 가게된다면 맨 마지막 줄이기 때문에 따로 return; 을 작성하지 않으신건가요 ?
- 미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
missing return statement 관련 질문 드립니다.
강사님이 강의에서 짜주신 코드처럼while (!q.isEmpty())로 하면 강의에서 보여주신 것처럼 return 이 따로 없을경우 에러가 나는데 (그래서 강의에서는 따로 return 0; 해주셨어요)while (true)로 하면 따로 return 이 없어도 에러가 안납니당 ,,혹시 while (true) 일때는 return 이 강의에서처럼 따로 없어도 에러가 안나는 이유가 있나요 ..? BFS 함수만 첨부하면 다음과 같습니닷// 방법3. BFS 상태트리탐색 (최단거리 BFS) - (2) : 로직 자체는 방법2와 동일, 배열 사용 및 코드 리팩토링 ! public static int BFS2(int S, int E) { Queue<Integer> q = new LinkedList<>(); int[] check = new int[10001]; int[] go = {-1, 1, 5}; // = 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다. // 0번째 세팅 q.offer(S); check[S] = 1; int level = 0; // while (!q.isEmpty()) { while (true) { int size = q.size(); for (int i=0; i<size; i++) { int tmp = q.poll(); // if (tmp == E) { // return level; // } for (int j=0; j<go.length; j++) { int nx = tmp + go[j]; if (nx == E) { return level + 1; } if (check[nx]==0 && 1<=nx && nx<=10000) { q.offer(nx); check[nx] = 1; } } } level++; } }
- 미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
boolean에만 static이 안 붙는 이유가 있나요 ?
강사님이 작성하신 코드에서DFS 함수 위에 나머지는 다 앞에 static 붙여서 정적변수로 해놓으셨는데boolean flag = false; 만 static이 안 붙여져있더라구여boolean 형에만 static을 안 붙이신 이유가 있으신가여?DFS 함수 내에서만 사용되기 때문에 안 붙이신 건가요 ?
- 미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
챕터8 - P01_합이같은부분집합_DFS_아마존인터뷰 관련 질문입니다.
강의 듣기 전, 혼자 풀어볼 때 코드를 이렇게 짰는데 이것도 맞는 풀이일까요 ...?import java.util.*; import java.io.*; /* N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력하는 프로그램을 작성하세요. 둘로 나뉘는 두 부분집합은 서로소 집합이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어 합니다. 예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다. ex. 6 1 3 5 6 7 10 -> YES */ public class P01_합이같은부분집합_DFS_아마존인터뷰 { static int total; static int[] arr; static String answer; static int index; static int sum; static int N; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); N = Integer.parseInt(br.readLine()); arr = new int[N]; StringTokenizer st = new StringTokenizer(br.readLine()); total = 0; for (int i=0; i<N; i++) { arr[i] = Integer.parseInt(st.nextToken()); total += arr[i]; } index = 0; sum = 0; answer = "NO"; DFS(index); System.out.println(answer); } public static void DFS(int index) { if (sum*2 > total || index==N) { return; } else { sum += arr[index]; if (sum*2 == total) { answer = "YES"; return; } DFS(index+1); sum -= arr[index]; DFS(index+1); } } } 채점 사이트에서 통과하기는 하는데 이 풀이가 맞아서 통과한건지 아님 운좋게(?) 테스트 케이스 5개가 다 맞아서 통과한건지 뭔가 풀이에 대한 확신이 없어서요 .. !
- 미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
동전교환문제 dfs 질문이있습니다
실행하였을 때 생각나는 테스트케이스 모두 통과되는데 오답이라고 나오는 반례가 어떤 게 있을까요?....import java.util.*; class Main{ static int number, result; static boolean check = false; boolean flag=false; public void DFS(int L,int sum, int[] arr){ if(sum>result || check) return; if(sum==result){ System.out.println(L); check = true; } else{ for(int i=0; i<number; i++) { DFS(L + 1, sum+arr[i], arr); } } } public static void main(String[] args){ Main T = new Main(); Scanner kb = new Scanner(System.in); number =kb.nextInt(); int[] arr = new int[number]; for(int i=0; i<number; i++){ arr[i] = kb.nextInt(); } Arrays.sort(arr); int first = 0; int last = arr.length-1; while(first<last){ int ch = arr[first]; arr[first++] = arr[last]; arr[last--] = ch; } result = kb.nextInt(); T.DFS( 0 , 0,arr); } }
- 미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
DFS -1번문제(아마존)
안녕하세요 교수님질문은 아래 코드와 함께 표시해 두었습니다.import java.util.*; class Main { static int n;static int[] graph; //전체집합static int total=0; public String DFS(int val, int s) { //graph[0]부터 시작if(val==n) {if((total-s) == s)return "YES"; //이부분에서 RETURN이 제대로 이루어 지지 않는 이유가 궁금합니다. } else { DFS(val+1,s+graph[val]); DFS(val+1,s); } return "NO";} public static void main(String[] args) {Main tree=new Main();Scanner scanner=new Scanner(System.in);n=scanner.nextInt();graph=new int[n]; for(int i=0; i<n; i++) {graph[i]=scanner.nextInt();total+=graph[i];} System.out.print(tree.DFS(0,graph[0])); //graph[0]부터 시작 } }
- 미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
친구인가?(Union&Find) 첫 case1에서 타임리밋뜨는 이유
채점 결과 태스트 케이스2~5까지는 정답으로 나옵니다.4개 모두 200ms안에 끝납니다반면에 가장 테스트 케이스 크기가 작을 case1에서는 타임리밋이 뜹니다이유는 무엇이고 해결책은 무엇일까요?import java.util.*; public class Main { static String answer = "NO"; static int N,M; static int[] ch,dis; public void BFS(int t1, int t2, ArrayList<ArrayList<Integer>> arr) { Queue<Integer> Q = new LinkedList<>(); Loop:for(int i = 1;i<=N;i++) { if(ch[i] == 0) { Q.offer(i); while(!Q.isEmpty()) { int tmp = Q.poll(); ch[tmp] = 1; dis[tmp] = 1; if(dis[t1] == 1 && dis[t2]==1) { answer = "YES"; break Loop; } int len = arr.get(tmp).size(); for(int j = 0;j<len;j++) { int n = arr.get(tmp).get(j); Q.offer(n); } } Arrays.fill(dis, 0); } } } public static void main(String[] args){ Scanner in=new Scanner(System.in); N = in.nextInt(); M = in.nextInt(); ch = new int[N+1]; dis = new int[N+1]; ArrayList<ArrayList<Integer>> arr = new ArrayList<>(); for(int i = 0;i<=N;i++) { arr.add(new ArrayList<Integer>()); } for(int i = 0;i<M;i++) { int a = in.nextInt(); int b= in.nextInt(); arr.get(a).add(b); } int t1 = in.nextInt(); int t2 = in.nextInt(); Main T = new Main(); T.BFS(t1, t2, arr); System.out.print(answer); } }
- 해결됨자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
타임 리밋이 일어나는 이유를 모르겠습니다.
혼자 풀어봤을 때, 다음과 같은 코드를 작성하였는데요.타임리밋이 일어날 만한 곳이 while문밖에 없는거같아서 계속 보는데 이유를 모르겠습니다.첫 요소가 K만큼 들어왔으면 그 다음부터는 1번씩만 put하니까 괜찮을 것이라 생각했는데 어떠한 이유로 타임리밋이 뜨는걸까요 ㅠㅠ?public static String solution(int n,int k,int[] arr) { String answer =""; HashMap<Integer,Integer> map = new HashMap<>(); // 매출의 종류 => HashMap & Sliding Window int lt=0; for(int rt = 0;rt<=(n-k);rt++) { while(lt-rt<k&<<n) { map.put(arr[lt], map.getOrDefault(arr[lt],0)+1); lt++; } answer += map.size()+" "; if(map.get(arr[rt])>1) { map.put(arr[rt], map.get(arr[rt])-1); }else { map.remove(arr[rt]); } } return answer; }
- 미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
채점 오류
package main;import java.util.Scanner; class Main{ public String solution(String str) { String answer=""; char [] charArray = str.toCharArray(); for( int i=0 ; i<charArray.length; i ++) { if(Character.isUpperCase(charArray[i])) { answer+=Character.toLowerCase(charArray[i]); }else { answer +=Character.toUpperCase(charArray[i]); } } return answer; } public static void main(String[] args) { Main T = new Main(); Scanner sc = new Scanner(System.in); String str = sc.nextLine(); System.out.print(T.solution(str)); } } 대소문자 바꾸기 부분에서 , 이클립스에서는 잘 돌아가는데 자꾸 런타임 에러가 뜹니다
- 미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
마구간 정하기 문제 질문드립니다.
강사님 마구간 문제에서, mid = 5 경우에 9번 마구간에 말을 배치하지 못한다고 말씀하셨는데, 그 이유는 문제에 어떤 부분에 포함되어있는 걸까요??각각의 말이 위치한 거리가 5를 넘어야 되는건가요????
- 미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
왜 오답인지 정말 모르겠습니다...
임시반장 정하기 문제에서import java.util.Scanner; public class Main { private static void solution (int num, int[][] arr){ int[][] test_arr = new int[num][5]; int[] result = new int[num]; for (int i = 0; i < 5; i++) { for (int j = 0; j < num-1; j++) { for (int k = j+1; k < num; k++) { if (arr[j][i] == arr[k][i]){ test_arr[j][i] = 1; test_arr[k][i] = 1; } } } } int result_index =0; int max = 0; for (int i = 0; i < num; i++) { for (int j = 0; j < num; j++) { if(test_arr[i][j] != 0){ result[i] += test_arr[i][j]; } } if (result[i] > max){ max = result[i]; result_index = i+1; } } System.out.println(result_index); } public static void main(String[] args) { Main T = new Main(); Scanner sc = new Scanner(System.in); int num = Integer.parseInt(sc.nextLine()); int[][] arr = new int[num][5]; for (int i = 0; i < num; i++) { String[] temp = sc.nextLine().split(" "); for (int j = 0; j < 5; j++) { arr[i][j] = Integer.parseInt(temp[j]); } } T.solution(num, arr); } }이런식으로 3개의 for문을 써서 해결했는데요 테스트케이스들은 다 통과하는데이라고 뜨네요 왜인지 이유를 모르겠습니다...
- 미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
시간초과 이유 해결
import java.util.ArrayList; import java.util.Collections; import java.util.Scanner; public class Inflearn26 { public ArrayList<Integer> solution(int N, int[] A, int M, int[] B) { ArrayList<Integer> answer = new ArrayList<>(); for(int i=0; i<A.length; i++) { for(int j=0; j<B.length; j++) { if(A[i] == B[j]) { answer.add(A[i]); break; // 원소 중복을 허용하지 않음으로 공통원소를 찾으면 반복문 종료 } } } Collections.sort(answer); // Arrays.sort() 는 '배열'의 오름차순 정렬 return answer; } public static void main(String[] args) { Inflearn26 inflearn26 = new Inflearn26(); Scanner scanner = new Scanner(System.in); int N = scanner.nextInt(); int[] A = new int[N]; for(int i=0; i<N; i++) { A[i] = scanner.nextInt(); } int M = scanner.nextInt(); int[] B = new int[M]; for(int i=0; i<N; i++) { B[i] = scanner.nextInt(); } for(int x : inflearn26.solution(N,A,M,B)) { System.out.print(x + " "); // 공통 원소 출력 // 이 방법은 시간초과 걸림 } } }로 풀었는데 시간초과 오류가 뜹니다.어떤식으로 풀어야 해결이 가능한지 궁금합니다 .
- 미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
리미트 타임에러
소수 개수 구하기 문제언어 : 파이썬내용: 제가 작성한 하위 코드 for문 두 개 돌렸을뿐인데 리미트 타임에러가 뜹니다..구글링 해서 emurate함수 써서 푼 문제는 정답이라고 뜹니다.난이도 초급에 emurate함수 방식으로 써서 풀라는 의도는 아니라고 판단되어 문의 드립니다. 아래 코드가 에러인지, 제가 잘 못하고 있는지 궁금합니다.(입사 전에는 자바로 면접 보고 들어갔는데 입사 한 회사에서 사용하는 언어는 파이썬이라서 파이썬으로 코테 풀고 있는점도 참고해서 피드백 부탁드립니다) received_data = int(input()) list = [] for i in range(2,received_data+1): list.append(0) for i in range(2,received_data+1): if list[i-2]==0: for j in range(2,received_data+1): if j>i and j%i==0: list[j-2]=1 print(list.count(0))
- 미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
ch = new int[10001]; BFS 메서드 안에다가 생성하는 이유
안녕하세요!혹시 ch배열을 전역에서 크기를 할당하여 사용하면 안될까요?BFS메서드 안에서 크기를 할당해주는 이유가 궁금합니다! (제가 모르는 이유가 있을까 하여 질문드립니다!)
- 미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
DFS static변수 선언할떄 flag엔 static을 붙이지 않은 이유가 있나요?
어차피 정적변수나 전역변수나 쓰임이 비슷한거같기는 한데.... 딱 flag만 정적변수로 안하시더라구요 혹시 이유가있을까요??
- 미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
손코딩 이후 IDE에 코드 작성하는 방법
안녕하세요! 강의 잘 듣고 있는 학생입니다.선생님 저 같은 경우 코딩 테스트 문제를 풀때, 컴퓨터(IDE)에 바로 작성하지 않고 노트에 solution 부분의 코드를 전부 손코딩으로 작성 해본 뒤에 컴퓨터로 작성합니다. 이런 방식이 코딩테스트 시험 볼때는 시간제한이 있으니,, 비효율적인지 궁금합니다. (현재는 코드가 짧아서 상관 없다고 생각하지만, 어려운 문제들.. 즉, 코드가 길어 지는 문제들을 풀때 문제가 되지 않을까? 생각하여 이렇게 질문을 남깁니다) 이렇게 하게 된 이유는, 펜으로 작성해보지 않고 바로 코드를 타이핑 하려니 생각이 잘 떠오르지 않아 이렇게 하게 되었습니다.
- 미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
큐 사용시 add(), remove()
Queue에 add() 메서드와 remove() 메서드를 사용할 수 있던데, 이걸 사용해도 되는지 궁금합니다.