묻고 답해요
158만명의 커뮤니티!! 함께 토론해봐요.
인프런 TOP Writers
-
미해결자바스크립트 알고리즘 문제풀이 입문(코딩테스트 대비)
시간 복잡도
혹시 이렇게 풀면 시간 복잡도는 어떨까요 ?<html> <head> <meta charset="UTF-8" /> <title>출력결과</title> </head> <body> <script> function solution(arr1, arr2) { let answer = []; arr1.map((a, i) => { if (arr2.includes(a)) { answer.push(a); } }); return answer.sort((a, b) => a - b); } let a = [1, 3, 9, 5, 2]; let b = [3, 2, 5, 7, 8]; console.log(solution(a, b)); </script> </body> </html>
-
해결됨10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
6-E 해당문제 이분탐색은 솔루션은 어떨까요?
큰돌님 안녕하세요? 오늘은 의견 질문을 들고 왔습니다강의 에서는 map을 제시하셨지만,이분탐색 챕터라 이분탐색으로 풀었더니 공간/시간복잡도가 map보다 좋아보여 의견을 여쭈고 싶습니다. 아이디어는 lower_bound로 해당 인덱스를 찾고, 그게 A(혹은B)집합에도 있다면 차집합에 +- 하는 방식입니다.아래는 제 코드입니다.http://boj.kr/df642c7e59444b08bd8e8e654012eafa 아래는 큰돌님과 제 소스코드의 시간/공간 복잡도 비교입니다.
-
해결됨10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
1-L1111_1940 주몽
안녕하세요 큰돌님, 문제를 풀다가 테스트 코드랑 제가 직접 만든 케이스는 잘 돌아가는데 백준에 넣으면 바로 틀려버립니다..ㅎㅎ 저는 이 문제를 visited 배열로 풀었는데요, 벡터에 고유 번호를 담고 만약 m=9라면 먼저 for문을 통해 v의 원소를 하나하나 확인합니다. 먼저 9-2=7이 존재 하는지 확인하고 존재 한다면 갑옷을 만드는 경우가 있는거니까 cnt++을 했습니다. 어디서 반례가 생기는지 모르겠습니다.ㅜㅜ 별로 효율적이지 못한 코드 같긴하지만 한번 검토 부탁드립니다..ㅎㅎ http://boj.kr/2e4c75e8c7d24a1284cc02827162c36c
-
미해결자바스크립트 알고리즘 문제풀이 입문(코딩테스트 대비)
선생님 머리를 싸메고 풀어 봤습니다.
혹시 이 코드를 더 효율적으로 짤 수 있는 방법이 있을까요? /** * @param { string } str * @param { string } x * */ function solution(str, x) { const originStr = str.split(''); const indexArr = []; const result = []; for (let i = 0; i < str.length; i++) { if (originStr[i] === x) { indexArr.push(i); } }; for (let i = 0; i < originStr.length; i++) { const matchResult = []; for (let j = 0; j < indexArr.length; j++) { matchResult.push({ val : Math.abs(indexArr[j] - i), idx: j }); }; result.push(matchResult.sort((a, b) => { return a.val - b.val })[0].val); }; return result; }; console.log(solution('teachermode', 'e'));
-
미해결자바스크립트 알고리즘 문제풀이 입문(코딩테스트 대비)
챕터3의 5.문자열 압축
5.문자열 압축에서 s=s+' ' ;을 사용해서 문자열을 하나더 늘려준다는것은 이해했습니다.다만 혼자 문제를 풀당시 해당 작업을 하지않아도 값이 올바르게 나오며 오류가 나지 않았는데 왜 오류가 나지않을까요?
-
미해결자바스크립트 알고리즘 문제풀이 입문(코딩테스트 대비)
연속부분수열2(Two Pointers Algorithm)
안녕하세요. M = 5let a=[6, 3, 1, 2, 3];혹시 만약 처음부터 배열에 6이 들어가있다면 5보다 큰경우가 될텐데 그럼 rt-lt+1이 때문에 안될꺼같은데 이런경우 어떻게 될까요..?
-
미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
idle로 실행 질문
지금 인텔리제이로 실행을 해보려고 하고있는데 입력을 어떻게 받아서 써야하는지 감이 안옵니다... 이런상태입니다... 어떻게 하면 될지 알려주시면 감사하겠습니다!!!
-
해결됨10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
6 -B 모범답안의 line 6은 반례라고 보면 될까요?
큰돌님 안녕하십니까?해당문제 큰돌님과 비슷하게 접근까지하여 예제 까지는 통과 하였습니다.아래 코드는 큰돌님 모범 답안 중 일부인데요,볼드 처리 한 부분을 생각못해서 50%에서 틀린 것 같습니다.지금이야 해설과 강의를 보고 그럴 수 있겠구나 하지만, 이런 부분을 생각 못했을 때는 반례를 생각하는 부분으로 접근하는게 맞을까요?bool check(int mid){ if(mx > mid) return false; // line 6 ...이하 생략 int main(){ cin >> n >> m; for(int i = 0; i < n; i++){ cin >> a[i]; sum += a[i]; mx = max(mx, a[i]); } ...이하 생략아래는 큰돌님 모범답안 링크입니다.https://www.acmicpc.net/source/share/e575431157ef40f48ecb65d4426ffbcb
-
미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
8-11 미로의 최단거리 (BFS)
import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Main { static int[][] miro, dis; static int[] dx = {-1, 1, 0, 0}; static int[] dy = {0, 0, -1, 1}; static int min; static boolean flag; public static void main(String[] args) { Main T = new Main(); Scanner sc = new Scanner(System.in); miro = new int[9][9]; dis = new int[9][9]; min = 0; flag = false; for (int i = 0; i < 9; i++) { if (i == 0 || i == 8) { for (int j = 0; j < 9; j++) { miro[i][j] = 1; } } else { miro[i][0]=1; miro[i][8]=1; } } for (int i = 1; i <= 7; i++) { for (int j = 1; j <= 7; j++) { miro[i][j] = sc.nextInt(); } } miro[1][1]=1; dis[1][1]=0; T.BFS(new int[]{1, 1}); System.out.println(min); } void BFS(int[] loca) { Queue<int[]> Q = new LinkedList<>(); int[] cl = loca; Q.offer(cl); while (!Q.isEmpty()) { if (flag) { return; } cl = Q.poll(); for (int i = 0; i < 4; i++) { int[] nl = {cl[0] + dx[i], cl[1] + dy[i]}; if (miro[cl[0] + dx[i]][cl[1] + dy[i]] == 0) { Q.offer(nl); dis[cl[0] + dx[i]][cl[1] + dy[i]] = dis[cl[0]][cl[1]]+1; miro[cl[0] + dx[i]][cl[1] + dy[i]] = 1; if (Arrays.equals(nl,new int[]{7,7})) { min = dis[cl[0] + dx[i]][cl[1] + dy[i]]; flag = true; return; } } } } } }좌표를 클래스로 정의하지 않고 배열로 매개변수를 사용해서 BFS 구현을 하였는데 오답이 나옵니다 ㅜㅜ 출력 12는 나오는데 무엇이 문제일까요??
-
해결됨10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
안녕하세요. 5-B 문제 시간복잡도 질문 드립니다.
선생님 안녕하세요. 우선 강의 잘 듣고 있습니다. 감사합니다.다름이 아니라, 제가 5-B 문제를 선생님 풀이방법과 거의 유사하게 풀었는데 답안 제출 시 시간초과가 발생하여 질문 드리게 되었습니다.1차 for문을 돌면서 original 문자열을 1개씩 순회하며, 새로운 문자열을 만들어가며 폭탄 문자열 길이 이상이 되었을 때 뒤에서부터 폭탄 문자열과 비교하며 같으면 erase()로 제거하는 방식까지는 선생님 풀이방법과 똑같습니다. 다른 부분은 뒤에서부터 폭탄 문자열과 비교하는 부분입니다. 선생님께서는 substr을 만들어서 == 비교연산자를 통해 폭탄문자열을 찾으셨는데요. 저의 경우, 아래 링크로 공유드린 코드와 같이 check() 라는 함수를 만들었고, 거기서 폭탄문자열 길이만큼 for문을 돌며 폭탄문자열이 존재하는지 체크를 한 후, 존재하면 erase()를 하도록하였습니다. 즉, 폭탄문자열 체크하는 부분만 다르며, 선생님 풀이처럼 substr 후 == 비교연산자로 체크하는 부분으로 수정을 하면 시간초과없이 통과가 되는데, 제가 작성한 check() 함수를 사용하면 시간초과가 납니다.제가 생각했을 때는 check()도 O(N)이고, == 비교연산자도 O(N)일 것으로 생각이 드는데 왜 check() 함수를 사용하면 시간초과가 나는지 이해가 안가서 질문드립니다. == 비교연산자가 O(N)이어도 문제 상에서 폭탄 문자열의 최대길이가 36 정도이기 때문에 시간초과가 발생하지 않았다고 생각을 했었고, 따라서 O(N)인 check() 함수도 시간초과가 발생하지 않을 것으로 생각했었습니다.http://boj.kr/fa122a7d9a5e456388da1c04be04ff69 감사합니다.
-
미해결파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)
문제에서 튜플 사용하는 이유가 뭔가요?
섹션4- 5. 회의실 배정(그리디) 문제에서리스트가 아닌 튜플을 사용하는 이유가 뭔가요 ? meeting.append((s,e))
-
미해결입문자를 위한 코딩테스트 핵심(이론과 문제풀이) [Python]
최솟값의 위치
안녕하세요! 코딩테스트를 처음 준비하는거라 잘 모르는데..최솟값의 위치에서 그냥 min함수 이용하면 안되는 건가요...?nums = [7,10,5,3,2,15,19] min_value = min(nums) print(nums.index(min(nums)))이런 식으로 하면 금방 나올텐데원래 코딩 테스트는 순차탐색을해서 풀어야하는건가요? 잘 몰라서 여쭤봅니다!
-
해결됨10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
3-K 시간초과 질문 있습니다.
http://boj.kr/5a31400e6a0e4bea85a7f0082562729d안녕하세요 좋은 강의 잘 보고 있습니다.저는 이 문제를 보고백조가 이동해서 다른 백조에게 닿을 수 있는지 판단 => dfs1이 아닐 때, bfs로 물 녹이기반복이렇게 생각해서 풀었고, 공유 소스나 다른 분들 질문을 보고 1번에서 dfs로 풀면 불필요한 과정을 더 수행하기 때문에 틀렸다는 것 또한 이해했습니다.질문드릴 부분은제 코드에서 dfs 말고도 다른 불필요한 로직이 있었는지문제를 마주했을 때 dfs를 선택하면 안될 이유가 있었는지, 그걸 어떻게 제가 판단해야 할지=> 저는 1번 생각하자마자 dfs를 떠올렸고 시간초과를 띄우고 나서야 틀린걸 알았는데, 틀리기 전에 판단하려면 어떻게 해야 할까 싶어서 질문드립니다.위 두가지 입니다.감사합니다. ㅎㅎ..
-
해결됨10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
선생님, DFS 설명 예시 코드에서 n의 크기에 대해 질문이 있습니다!
안녕하세요 선생님! 4분33초부터 시작하는 DFS 예시 코드에 관련해서 질문이 있습니다.선생님이 보여주신 그래프를 보면 노드의 개수가 총 5개인데 n의 크기를 보면 6이라고 되어 있네요.처음에는 2와 4가 양방향으로 연결돼 있기 때문에 그런가 싶었는데 이걸 인접리스트로 표현하는 코드에선 n을 4로 하셔서 뭔가 제가 잘못 생각하고 있는가 싶어서 질문드립니다.n의 크기를 노드 개수대로 5로 수정해서 코드를 돌려보면 3번 노드를 탐색을 안 하는 걸 보면 n이 6이 돼야 할 거 같은데 왜 6이 되는지 이해가 잘 가지 않습니다 ㅠ
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
학습 방법에 대한 질문입니다.
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 안녕하세요 강사님.2주차까지는 어느정도 문제를 풀고 해설을 볼 수 있었는데3주차 부터는 문제 해결을 못해서 강의를 보고 있습니다.지금 계속 이런 상태라 학습을 제대로 하고 있는지 모르겠습니다. 일단 문제를 한 시간정도 보고 안풀려서 강의를 보고다시 문제를 풀어 보고있는데 강사님의 풀이를 그냥 따라치는게게 아닌가 하는 걱정이 들어서 질문합니다.
-
미해결자바스크립트 알고리즘 문제풀이 입문(코딩테스트 대비)
이렇게 작성해도 괜찮은걸까요?
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
-
미해결자바 코딩테스트 - it 대기업 유제
방향바꾸기 문제 질문드립니다.
import java.io.*; import java.util.*; class Node implements Comparable<Node>{ int x; int y; int c; Node(int x, int y, int c){ this.x=x; this.y=y; this.c=c; } @Override public int compareTo(Node o) { return this.c-o.c; } } class Main { public int solution(int[][] board) { int answer = 0; int n=board.length; int m=board[0].length; int[][] dist =new int[n][m]; int INF = (int)1e9; PriorityQueue<Node> q = new PriorityQueue<>(); q.add(new Node(0,0,0)); for(int i=0; i<n; i++) Arrays.fill(dist[i], INF); dist[0][0]=0; int[] dx = {0,0,1,-1}; int[] dy = {1,-1,0,0}; while(!q.isEmpty()) { Node tmp = q.poll(); int nowx = tmp.x; int nowy = tmp.y; int nowc=tmp.c; int dir = board[nowx][nowy]-1; if(nowc>dist[nowx][nowy]) continue; for(int i=0; i<4;i++) { int nx = nowx+dx[i]; int ny = nowy+dy[i]; if(i==dir && dist[nx][ny]>nowc) { dist[nx][ny] = nowc; if(q.add(new Node(nx,ny,dist[nx][ny]))); } else if(i!=dir && dist[nx][ny]>nowc+1) { dist[nx][ny] = nowc+1; q.add(new Node(nx,ny,dist[nx][ny])); } } } answer = dist[n-1][m-1]; return answer; } public static void main(String[] args){ Main T = new Main(); System.out.println(T.solution(new int[][]{{3, 1, 3}, {1, 4, 2}, {4, 2, 3}})); System.out.println(T.solution(new int[][]{{3, 2, 1, 3}, {1, 1, 4, 2}, {3, 4, 2, 1}, {1, 2, 2, 4}})); System.out.println(T.solution(new int[][]{{3, 2, 1, 3, 1, 2}, {2, 1, 1, 1, 4, 2}, {2, 2, 2, 1, 2, 2}, {1, 3, 3, 4, 4, 4}, {1, 2, 2, 3, 3, 4}})); System.out.println(T.solution(new int[][]{{3, 2, 1, 3, 1, 2, 2, 2}, {2, 1, 1, 1, 4, 2, 1, 1}, {2, 2, 2, 1, 2, 2, 3, 4}, {1, 3, 3, 4, 4, 4, 3, 1}, {1, 2, 2, 3, 3, 4, 3, 4}, {1, 2, 2, 3, 3, 1, 1, 1}})); System.out.println(T.solution(new int[][]{{1, 2, 3, 2, 1, 3, 1, 2, 2, 2}, {1, 2, 2, 1, 1, 1, 4, 2, 1, 1}, {3, 2, 2, 2, 2, 1, 2, 2, 3, 4}, {3, 3, 1, 3, 3, 4, 4, 4, 3, 1}, {1, 1, 1, 2, 2, 3, 3, 4, 3, 4}, {1, 1, 1, 2, 2, 3, 3, 1, 1, 1}})); } }이렇게 작성하니까 배열 길이가 맞지 않다고 뜹니다.어디가 잘 못된건가요???
-
해결됨10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
7-N 붙일 수 있는 최대크기의 종이를쓴다
증명 까진 안되나요 일종의 그리디 인가요
-
미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
문제 pdf
강의를 듣기 전 문제를 먼저 혼자 풀어보려고 하는데, 혹시 문제 pdf 는 어디에서 확인할수 있는건가요?? 아무리 찾아봐도 안나오네요 ㅜㅜ
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
인구 이동문제 로직 의문점
큰돌님 안녕하세요 제가 문제를 잘 못 이해한게 아닌가 싶지만 질문 드려봅니다! 문제에서는 인접한 국가 인구의 차이가 특정 범위에 해당한다면 (연합국의 인구수) / (연합국의 개수) 로 배열을 변경한다 인데그럴려면 먼저 dfs로 모든곳을 전부 순회한뒤에 구한 연합국의 인구수 / 연합국의 개수로 최종적으로 계산을 해줘야 할것같은데 정답코드 같은경우 커넥티드 컴포넌트에 해당되면 해당 컴포넌트 내에서 sum / v.size() 를 해주더군요 이렇게 되면 중간에 구해진 sum(인구수) v.size() (연합국의 개수) 로 구해지기 때문에 그다음 커넥티드 컴포넌트와 이전의 커넥티드 컴포넌트의 값이 다르게 되지 않나요?
