173만명의 커뮤니티!! 함께 토론해봐요.
해결됨
코딩테스트 [ ALL IN ONE ]
two_sum 문제에서 input으로 주어지는 nums에는 중복 원소가 없다고 가정하나요? 문제에 '같은 원소를 두 번 사용할 수 없습니다.'라는 조건이 있는데, 예를 들어, nums = [4,1,9,7,8,2], target=14인 경우에는 False를 출력해야 하는 반면, nums = [4,1,9,7,7,2], target=14인 경우에는 True를 출력해야 하니까 원소 중복 가능 여부를 여쭤보게 되었습니다!
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
큰돌님 안녕하세요. 강의 정말 잘듣고 있습니다!! 옛날부터 궁금한 점이 있었는데, 항상 헷갈리는 부분이 있어서 이렇게 질문 남기게 되었습니다. 보통 숫자 데이터를 다룰 때, C++에서 int형과 long long형 타입 두 개를 보통 사용하는 것으로 알고 있습니다. 데이터 범위에 따라서 두 개를 각각 나눠쓰면 되는 부분인데... 제가 궁금한 점은... 두 개가 그렇게 큰 차이가 없다면 숫자는 모든 걸 int형 말고, long long으로 다 선언하면 되지 않나? 라는 궁금증입니다!! 제가 혼자 공부를 해보니.. 32bit컴퓨터라면 int로 선언할때와 long long으로 선언할때 실행속도에서 차이가 생겼는데, 64bit로 넘어오면서 이 실행속도 차이도 없어졌다고 합니다. 시간복잡도(실행속도) 측면에서도 별로 그렇게 차이도 없고, long long으로 모든 숫자 타입을 지정하면 int형에서 발생하는 오버플로우 문제 등 장점들이 더 많다고 생각이 됩니다. 가장 큰 차이라고 생각이 드는 부분이 공간복잡도면인데, 코딩 테스트에서 공간복잡도는 크게 다루지 않으니.. 굳이 long long말고 int형을 쓰는 이유를 모르겠습니다. 정리: 숫자 데이터 타입을 구분할 때, 모든 걸 long long 타입으로 하면 안되나요?? long long타입으로 할 때, 안 좋은 면이 있나요?
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
d[i] = d[ stk.top ()]= 1; 여기서 stk.top () 은 ')'을 리턴하는데, 어떻게 i-1 같은 역할을 할 수 있는 건가요..?
미해결
자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
강의에는 포함되지 않는 문제인데 마땅한 방법이 떠오르지 않는 문제가 있어 질문 드립니다. 마땅히 여쭤볼 분이 안 계셔서 여기 질문 드리는데, 바쁘시면 답변하지 않으셔도 괜찮습니다. 문제는 프로그래머스 - 평행 이라는 문제입니다! 제가 푼 코드는 아래와 같습니다. import java.util.List; import java.util.ArrayList; class Solution { public int solution(int[][] dots) { double slope1; double slope2; slope1 = calculateSlope(dots[0], dots[1]); slope2 = calculateSlope(dots[2], dots[3]); if(Double.compare(slope1, slope2) == 0) { return 1; } slope1 = calculateSlope(dots[0], dots[2]); slope2 = calculateSlope(dots[1], dots[3]); if(Double.compare(slope1, slope2) == 0) { return 1; } slope1 = calculateSlope(dots[0], dots[3]); slope2 = calculateSlope(dots[1], dots[2]); if(Double.compare(slope1, slope2) == 0) { return 1; } return 0; } private double calculateSlope(int[] dot1, int[] dot2) { return (double) (dot1[1] - dot2[1]) / (dot1[0] - dot2[0]); } } 하지만 점이 4개일 때가 아닌, 다른 경우에도 적용이 가능한 메소드를 만들고 싶은데 잘 되지 않는 것 같습니다. 여유가 되신다면 부디 부탁 드립니다. 코딩테스트 연습 - 평행 | 프로그래머스 스쿨 (programmers.co.kr)
미해결
JavaScript 알고리즘 베스트 10
7번 강의에서 github 레포에서 확인하라고 주소는 주셨지만 정작 private이라서 접근이 불가능 하네요!
미해결
파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)
1~9까지 입력을 받았는데, 어째서 이것이 45가 최대가 되는건가요? 문제에서 한 곡당 용량이 최대 5라고 나와있는건가요? 어디 부분에 의해 45라는 rt 값이 나왔는지 알 수가 없어서 질문합니다.. 보니까 1~9까지 다 더하면 45가 나오는 것 같은데, 9번 노래의 용량은 9가 되는거고 8번 노래의 용량은 8이 되는건가요?
해결됨
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
큰돌님 안녕하십니까? 지난밤에 3-J 14497 주난의 난 3-K 3197 백조의 호수 해당 문제 DFS로 풀면 어떠나는 질문 남겨서 제 코드가 비효율적이라는 조언 감사히 받았습니다. https://www.inflearn.com/questions/1064823/%EC%9D%B4-%EB%AC%B8%EC%A0%9C-dfs-%ED%92%80%EC%9D%B4%EB%8A%94-%EC%96%B4%EB%96%A4%EA%B0%80%EC%9A%94 결론이 시간 복잡도를 고려하면 플루이드 워셜로 풀어야 효과적이라는 말씀같은데, 해당 문제인 2-Q 치즈 문제도 BFS 플루이드 워셜로 풀면 좀더 효율적인 풀이가 될까요? 2-Q는 DFS로 풀이해주셨는데, 플루이드 워셜 쓰면 더 효과적일지 아이디어 레밸에서 궁금해서 질문 올립니다. 답변 미리 감사합니다.
미해결
자바스크립트 알고리즘 문제풀이 입문(코딩테스트 대비)
감사합니다 // 내코드 function solution(length, ...rest) { let answer = []; for (const key in rest) { if (rest.indexOf(rest[key]) === Number(key)) answer.push(rest[key]); } return answer.join(","); } console.log(solution(5, "good", "time", "good", "time", "student"));
미해결
자바스크립트 알고리즘 문제풀이 입문(코딩테스트 대비)
function solution(arr) { // 7난쟁이가 아닌 9명이 있는상황 // 전체 난쟁이의 키는 100 const length = arr.length; const sum = arr.reduce((acc, value) => acc + value); const target = sum - 100; // 2중 반복분 종료 시 // 종료하고자하는 외부 for문에 label 지정 // break 뒤에 라벨명 명시 // >> 해당 스코프 종료 first: for (let i = 0; i < length - 1; i++) { const matchValue = target - arr[i]; for (let j = i + 1; j < length; j++) { if (matchValue === arr[j]) { arr.splice(j, 1); arr.splice(i, 1); break first; } } } return arr; } console.log(solution([20, 7, 23, 19, 10, 15, 25, 8, 13]));
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
안녕하세요. 제 나름대로 풀어봤는데 자꾸 시간초과가 걸려서 해설 코드 보고 제 코드를 조금 수정했거든요. 원래 제 코드에서 dfs알고리즘은 동일하고 해킹된 컴퓨터 수 계산해서 출력하는 것만 바꿨는데 맞네요. 그런데 제가 보기엔 별 차이 없을 것 같은데 어디서 차이가 발생하는지 궁금합니다. 원래 코드 http://boj.kr/5ff0dc6ee81c41e5acf41f41a2b3e857 수정한 코드 http://boj.kr/be9244a19d774c2ab6ce08343e52c94c
해결됨
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 안녕하세요. 큰돌 강사님 문제를 보면 "사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다." 라는 조건이 있는데, 선생님이 제공해주신 풀이에서 어떻게 순서가 같은지 체크가 되는건지 이해가 되지 않아서요. 혹시 설명해주실 수 있나요??
해결됨
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
큰돌님 안녕하십니까? 해당 문제 2636 치즈 문제가 떠올라서 DFS로 풀이를 해서 통과했는데요, 해설에는 BFS 하셔서 질문 올립니다. 해당 문제 DFS풀이는 어떻다고 생각하시나요? 왜냐하면 이 다음 문제인 3-K 3197 백조의 호수는 이래 풀면 시간 초과 뜨더라구요! 제가 짠 코드는 2636 치즈 참고해서 아래와 같습니다. http://boj.kr/cc3ec76201724d44a5c35f955a9e41cc #include <bits/stdc++.h> using namespace std; ////////////bfs dfs 용////////// char a[302][302]; int visited[302][302]; int m,n; int aa,bb; int c,d; string oneline; const int dy[] = {-1, 0, 1, 0}; const int dx[] = {0, 1, 0, -1}; vector<pair<int,int>> temp; int ret; bool dfs(int y, int x) { bool tempbool=false; visited[y][x]=1; for(int i = 0; i< 4;i++) { int ny = y + dy[i]; int nx = x + dx[i]; if( ny<0|| ny>=m || nx < 0 ||nx>=n) continue; if(visited[ny][nx]==1) continue; if(a[ny][nx]=='#') { return true; } if(a[ny][nx]== '1') { temp.push_back({ny,nx}); continue; } else { tempbool = dfs(ny,nx); if(tempbool) return tempbool; } } return tempbool; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cin>>m>>n; cin>>aa>>bb>>c>>d; for(int i = 0 ; i< m ; i++) { cin>>oneline; for(int j=0; j<n;j++) { a[i][j]= oneline[j]; } } while(true) { ret++; fill(&visited[0][0], &visited[0][0]+302*302,0); bool tempbool= dfs(aa-1,bb-1); if(tempbool) break; while(temp.size()) { pair<int,int> aaa = temp[temp.size()-1]; temp.pop_back(); a[aaa.first][aaa.second] = '0' ; } } cout<<ret; return 0; } 답변 미리 감사합니다.
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
안녕하세요. 요즘 프로그래머스에서 대부분 코딩 테스트를 제출하더라고요. 이 문제는 프로그래머스에서 어떻게 풀어야 하는지 모르겠어서 질문드립니다. int dfs(int y, int x) { if (y < 0 || x < 0 || y >= n || x >= m || a[y][x] == -1) return 0; if (visited[y][x]) { cout << -1 << "\n"; exit(0); } int &ret = dp[y][x]; if (ret) return ret; visited[y][x] = 1; for (int i = 0; i < 4; i++) { int ny = y + dy[i] * a[y][x]; int nx = x + dx[i] * a[y][x]; ret = max(ret, dfs(ny, nx) + 1); } visited[y][x] = 0; return ret; } 이 풀이에서, visited[y][x]를 확인 한 후 답을 출력하는데, 프로그래머스에서 exit(0)을 실행하면 program terminated unexpectedly 가 뜹니다. 어떻게 풀이해야 하나요??
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
재귀부분에서 질문이 있습니다 제가 이해하기론결국 for문에서 N번을 원래 브루트포스를 통해서 탐색하는 기본로직적인 측면은 같으나 반복문에 진입하기전에 메모이제이션기법인 dp[MaxN][1<<MaxN]배열을 이용해 for문을 돌지 않음으로써 최악의 시간복잡도인 N^N을 회피하면서 최적해를 찾는방식이되는걸까요? 제가이해한게맞을런지요?
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
#include <bits/stdc++.h> using namespace std; int N; map<int, vector<int>> mp; int tmp, d, ret; void removeAll(int key){ // if not leaf node -> recursive remove if(!mp[key].empty()) { for(int c: mp[key]) removeAll(c); } // erase itself mp.erase(key); } int main(){ cin >> N; // make graph for(int i = 0; i < N; i++){ mp[i]; cin >> tmp; if (tmp != -1) mp[tmp].push_back(i); } // input node to be deleted cin >> d; removeAll(d); if (mp.size() == 1) ret = 1; else if (mp.size() == 0) ret = 0; else { // for all key in map for(auto it: mp) { int key = it.first; // if the remaining value empty => plus if (mp[key].empty()) ret++; } } cout << ret; } 다음과 같이 map과 재귀를 풀어서 1068번 트리 문제를 풀었는데, 어디가 오답인지 감이 안옵니다.
해결됨
자바스크립트 알고리즘 문제풀이 입문(코딩테스트 대비)
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 안녕하세요. 강의를 듣기 전 풀어봤는데, 설명해주신 방법도 숙지하겠습니다. function solution(s) { let answer = ''; let stack = []; let contain = false for (let ele of s) { if (ele === '(') { contain = true stack.push(ele) } if (!contain) { answer += ele } if (ele === ')') { stack.pop() if (stack.length === 0) contain = false } } return answer }
미해결
자바스크립트 알고리즘 문제풀이 입문(코딩테스트 대비)
항상 감사합니다 function solution(question) { let answer = ""; if (question.length > 100) return; const oddNumber = question.length % 2 === 1 ? true : false; const MiddleLength = Math.floor(question.length / 2); let count = 0; for (const z of question) { if (oddNumber) { if (MiddleLength === count) { answer += z; } } else { if (MiddleLength - 1 === count || MiddleLength === count) { answer += z; } } count++; } return answer; } console.log(solution("study")); //"u"
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
안녕하세요 큰돌님 큰돌님 로드맵영상 보고 참고해서 공부중입니다 ㅎㅎ 제가 지금 c++개념강의만 한번 듣고 이제 큰돌님 코테강의 들으려고하는데 프로그래머스 lv0같은 거 풀고나서 강의를 듣는게 나을까요? 코테강의 공부를 시작하는게 나을까요??
미해결
코딩테스트 실전 모의고사(with C++) : 대기업 대비
선생님 BFS함수 코드 중에서 영희가 기사를 지나쳐가는 경우는 고려안했는데도 정답인 이유가 있나요? -> ['영희는 산딸기가 없이는 기사를 지나쳐 갈 수 없다.'] 2 - 0 - 3 - 4 이런 식의 행이 있으면 문제되지 않을까 싶어서요
해결됨
코딩테스트 [ ALL IN ONE ]
class Solution(object): def lowestCommonAncestor(self, root, p, q): if root is None: # check whether Node is empty return if root is p or root is q: return root # root 노드가 p 또는 q가 아니면 순회하도록 재귀함수 호출 l = self.lowestCommonAncestor(root.left, p, q) # code 1 r = self.lowestCommonAncestor(root.right, p, q) # code 2 # p와 q 조건 검사를 마친 후(모든 노드를 순회하는 것은 아님) if l and r: return root elif l: return l else: return r 먼저 LCA함수를 호출하면 root가 가리키는 노드가 있는지 체크한 다음에 계속해서 p 또는 q 노드가 맞는지 확인을 합니다. 만약 p 또는 q 노드가 아니면 재귀함수를 호출해서 자식 노드로 더 깊이 순회하도록 만듭니다. 역시 자식 노드들도 p 또는 q 노드가 맞는지 검사한 후 맞으면 l 또는 r에 그 노드를 저장합니다. 여기서 궁금한 점은, 자기 자신이 공통 조상이 될 때인데요. 이렇게 되면 더 깊이까지 탐색하지 않아도 elif l: return l 에 의해서 왼쪽만 탐색했으니까 시간복잡도가 O(logN)인가요? 아니면 다른 케이스들도 고려해서 최악의 경우 모든 노드를 탐색해야되니까 O(N)이 되는건가요?
