묻고 답해요
141만명의 커뮤니티!! 함께 토론해봐요.
인프런 TOP Writers
-
미해결자바스크립트 알고리즘 문제풀이 입문(코딩테스트 대비)
섹션2 공통원소 구하기 정렬 없이 해봤는데 괜찮을까요??
<html> <body> <script> function solution(arr1, arr2) { const answer = []; const n = arr1.length; const m = arr2.length; let p1 = (p2 = 0); while (p1 < n) { if (arr1[p1] === arr2[p2]) { answer.push(arr1[p1++]); p2++; } else { p1++; } } p1--; while (p2 < m && p1 >= 0) { if (arr2[p2] === arr1[p1]) { answer.push(arr2[p2++]); p1--; } else { p1--; } } return answer.sort((a, b) => a - b); } const arr1 = [1, 3, 9, 5, 2]; const arr2 = [3, 2, 5, 7, 8]; console.log(solution(arr1, arr2)); </script> </body> </html>위와 같이 p1먼저 돌고 그 다음에 p2돌면서 p1을 뒤에서부터 찾았는데 이렇게 하는건 별로 일까요...?
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
7-V 질문 있습니다
안녕하세요, 큰돌님 7-v 질문 드립니다.첫번째 풀이가 큰돌님의 답 코드와 비슷한 로직을 사용한다고 생각하는데,왜 시간 초과가 나는지 모르겠습니다.https://www.acmicpc.net/source/73255801백트래킹 풀이 (시간초과)https://www.acmicpc.net/source/73256688dp 배열 + 반복문 (맞았습니다!)
-
해결됨10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
이터레이터 질문
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. - 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.현재 교안으로 1회독중에 이터레이터 부분에서 막혀 질문드립니다. cout << &*lower_bound(a.begin(), a.end(), 3) << endl; cout << &*a.begin(); cout << &*lower_bound(a.begin(), a.end(), 3) - &*a.begin() << endl;각각의 주소값이0x139e05e580x139e05e50 임을 가정했을때0x139e05e58 - 0x139e05e50 연산이 왜 8이 아니라 2가 되는지 모르겠습니다.
-
해결됨2주만에 통과하는 알고리즘 코딩테스트 (2024년)
[3강 누적합>이모스1법> 백준 17611] 런타임에러 질문드립니다!
import sys sys.stdin = open('BackJoon/3강_누적합/5_17611.txt','r') input = sys.stdin.readline n = int(input()) vertex = [list(map(int, input().split())) for _ in range(n)] ######## (x_min, y_min) -> (0, 0)으로 이동 x_min, x_max = 500000, -500000 y_min, y_max = 500000, -500000 for x,y in vertex: x_min = min(x, x_min) x_max = max(x, x_max) y_min = min(y, y_min) y_max = max(y, y_max) x_diff = 0 - x_min y_diff = 0 - y_min for i in range(n): vertex[i][0] = vertex[i][0] + x_diff vertex[i][1] = vertex[i][1] + y_diff ##### 수평선 조사 (강의에서와 같이 왼쪽으로 돌려서 봄) vertex_x_incre = sorted(vertex, key = lambda x: (x[0], x[1])) # y_range = y_max-y_min+1 x_range = x_max-x_min+1 x_sum_list = [0] * (y_range+1) # x축 방향으로 [1, 0, 0, ..., -1] 더함 for i in range(0,n,2): # 선분은 2개의 꼭지점으로 이루어짐 v1 = vertex_x_incre[i] v2 = vertex_x_incre[i+1] if v1[0] != v2[0]: # 디버깅 print('x point does not match!!')#만약 선분이 직선이 아니라면(혹은 sort가 잘못됨) break if v1[1] >= v2[1]: print('y point does not align!!')#sort가 잘못됨 print('v1:', v1) print('v2:', v2) break x_sum_list[v1[1]] += 1 x_sum_list[v2[1]] -= 1 x_sum_list = x_sum_list[:-1] #범위밖의 맨 마지막 -1 자리 버림 prefix = [0]*(y_range+1) for i in range(y_range): prefix[i+1] = prefix[i] + x_sum_list[i] prefix = prefix[1:] h = max(prefix) ##### y축 방향으로 조사 (수직선 조사) vertex_y_incre = sorted(vertex, key = lambda x: (-x[1], x[0])) y_sum_list = [0] * (x_range+1) # y축 방향으로 [1, 0, 0, ..., -1] 더함 for i in range(0,n,2): v1 = vertex_y_incre[i] v2 = vertex_y_incre[i+1] if v1[1] != v2[1]: print('y point does not match!!') break if v1[0] >= v2[0]: print('x point does not align!!') print('v1:', v1) print('v2:', v2) break y_sum_list[v1[0]] += 1 y_sum_list[v2[0]] -= 1 y_sum_list = y_sum_list[:-1] prefix = [0]*(x_range+1) for i in range(x_range): prefix[i+1] = prefix[i] + y_sum_list[i] prefix = prefix[1:] v= max(prefix) print(max(h,v))
-
미해결비전공자의 전공자 따라잡기 - 자료구조(with JavaScript)
let current = this.head 질문 있습니다!
this.head 대신 let current = this.head 처럼 current변수에 할당하여 사용하는 이유가 무엇일까요?ㅠ변수에 할당하여 사용하지 않았을 때 값을 보니 값이 다르게 나와 문의드립니다. li.add(3)이 실행될때 첫번째 노드가 사라짐 정상출력
-
해결됨10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
3-D 문제 시간초과
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 안녕하세요.강의 잘 듣고 있습니다.!! 혼자 풀어보는 중인데, 시간초과가 나서 오랫동안 고민하다 질문드립니다. 제 생각에는 Fire를 전파하는 부분에서 비효율이 있는듯한데,이를 개선할 방법이 딱히 떠오르지 않아서요, 질문드립니다. ㅠ #include <bits/stdc++.h> using namespace std; int R, C; vector<vector<char>> maze; pair<int, int> jihun; vector<pair<int, int>> fire; vector<vector<int>> delta = {{0,-1},{1,0},{0,1},{-1,0}}; vector<vector<int>> visited; set<int> ret; void dfs(pair<int, int>J, int step){ step+=1; // cout << "DEBUG: " << step << ", (" << J.first <<"," << J.second << ")" << endl; // for(int i = 0 ; i < R ; ++i){ // for(int j = 0 ; j < C ; ++j){ // if (i ==J.first && j == J.second) cout << "J"; // else cout << maze[i][j]; // } // cout << endl; // } // cout << endl; if (J.first == 0 || J.second == 0 || J.first == R-1 || J.second == C-1){ ret.insert(step); return; } // 1. 맵 업데이트 int cnt = 0; int s = fire.size(); for(int q = 0 ; q < s ; ++q ){ for(int p = 0 ; p < 4 ; ++p){ int nextF_i = fire[q].first + delta[p][0]; int nextF_j = fire[q].second+ delta[p][1]; if (nextF_i >=0 && nextF_j >=0 && nextF_i < R && nextF_j < C){ if (maze[nextF_i][nextF_j] == '.' || maze[nextF_i][nextF_j] == 'J'){ maze[nextF_i][nextF_j] = 'F'; fire.push_back({nextF_i, nextF_j}); cnt ++; } } } } // 2. dfs 호출 propagation for(auto d : delta){ int next_i = J.first + d[0]; int next_j = J.second+ d[1]; if (next_i >= 0 && next_j >= 0 && next_i < R && next_j < C){ if (visited[next_i][next_j] == 0 && maze[next_i][next_j] == '.'){ visited[next_i][next_j] = 1; // 방문 처리 dfs({next_i, next_j}, step); visited[next_i][next_j] = 0; // 방문 원복 } } } // 3. 맵 원복 while(cnt>0){ pair<int, int> b = fire.back(); fire.pop_back(); maze[b.first][b.second] = '.'; cnt--; } } int main(){ cin >> R >> C; maze = vector<vector<char>>(R, vector<char>(C)); visited = vector<vector<int>>(R, vector<int>(C, 0)); string s; for(int i = 0 ; i <R ; ++i){ cin >> s; for(int j = 0 ; j < C ; ++j){ maze[i][j] = s[j]; if (maze[i][j] == 'J') jihun = {i,j}; else if (maze[i][j] == 'F') fire.push_back({i,j}); } } visited[jihun.first][jihun.second] = 1; dfs(jihun, 0); if (!ret.empty()){ cout << *ret.begin(); } else cout <<"IMPOSSIBLE"; return 0; }
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
2-H 질문있습니다
모음이나 자음이 3개가 연속으로 올 때 비밀번호로 적절하지 않다는 조건을 for문 밖으로 빼면 틀리는 이유가 알고 싶습니다!이렇게 짰을 땐 틀렸다고 나오는데 조건을 어느 부분에서 만족하지 않는지 궁금합니다#include<bits/stdc++.h> using namespace std; string str; bool mo(char c){ if(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'){ return 1; } return 0; } int main(){ while(true){ cin >> str; if(str == "end"){ break; } bool moum = 0; bool same = 0; int cnt1 = 0; int cnt2 = 0; for(int i = 0; i < str.length(); i++){ if(mo(str[i])){ moum = 1; cnt1++; cnt2 = 0; }else{ cnt2++; cnt1 = 0; } if(i >= 1 && (str[i-1] == str[i]) && str[i] != 'e' && str[i] != 'o'){ same = 1; } } if(cnt1 >= 3 || cnt2 >= 3 || moum == 0 || same == 1){ cout << "<" << str << "> is not acceptable.\n"; }else{ cout << "<" << str << "> is acceptable.\n"; } } return 0; }
-
미해결Do it! 알고리즘 코딩테스트 with C++
백준11505, 교재 73번
#include <iostream> #include <vector> #include <cmath> using namespace std; static vector<long> tree; static int n, m, k,mod = 1000000007; void tree_set(int a); void change_val(int index, long val); long gugan(int s, int e); int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> m >> k; int q = n; int l = 0; while (q != 0) { q = q / 2; l++; } int tree_size = int(pow(2, l+1)); int left_index = pow(2, l); tree.resize(tree_size); fill(tree.begin(), tree.end(), 1); for (int i = left_index; i < n+left_index; i++) { cin >> tree[i]; } tree_set(tree_size-1); for (int i = 0; i < m + k; i++) { long a, s, e; cin >> a >> s >> e; if (a == 1) { change_val(s + left_index - 1, e); } else if (a == 2) { long start = s + left_index - 1; long end = e + left_index - 1; long result = gugan(start, end); cout<<result<<'\n'; } } } long gugan(int s, int e) { long part_sum = 1; while (s <= e) { if (s % 2 == 1) { part_sum *= tree[s]%mod; } if (e % 2 == 0) { part_sum *= tree[e]%mod; } s = (s + 1) / 2; e = (e - 1) / 2; } return part_sum; } void change_val(int index, long val) { tree[index] = val; while (index > 1) { index = index / 2; tree[index] = tree[index*2]%mod*tree[index*2+1]%mod; } } void tree_set(int a) { while (a != 1) { tree[a / 2] *= tree[a]%mod; a--; } } 위의 방법으로 코드를짜서 제출했더니 출력초과가 발생합니다. 왜 이런오류가 발생하는지 모르겠습니다..
-
해결됨10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
교안 81p 예제코드 질문드립니다.
안녕하세요 큰돌님교안 81p 예제 코드를 그대로 복사하였는데 에러가 떠서요. 짧은 코드라서 캡쳐본으로 올리겠습니다.위에서 전역변수로 초기화하는 것까지 똑같이 했는데 왜 이런 오류가 뜨는 것인지 궁금합니다.
-
해결됨10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
교안 79p vector 초기화 질문드립니다.
안녕하세요 큰돌님강의를 듣고 천천히 따라가고 있는데요, 강의 설명도 너무 이해되게 잘해주시고 교안도 잘 보고 있습니다.그런데 몇 가지 아쉬운 부분들이 있어서요..ㅠㅠc++을 처음 접하는데 가끔 예시코드를 봤을 때 설명 않고 넘어가시는 부분이 있기에 이해가 안될 때가 종종 있습니다.. ㅜㅜ 예를 들어 교안 79p에서vector<int> v{1, 2, 3};이 코드에서 지금 vector가 초기화가 어떻게 된 것인지 주석이라도 간략하게 달아주셨으면 좋겠는데 따로 찾아봐도 이거랑 비슷한 방식의 초기화를 잘 못찾겠어서요.. 제가 코드를 더 작성해서 저렇게 초기화된 건 v = {1, 2, 3}과 같다고 유추하였는데 맞을까요..?아직 교안 전부를 본 것은 아니라 뒤에 설명을 해주실지는 모르지만, 당장의 예제 코드를 이해하기 위해서 추가적으로 구글링하고 하는 부분들이 조금 시간이 소요되는 것 같습니다 그리고 다른 부분에서도, 교안에서 처음 push_back()이 언급됐을 때 문자하나씩밖에 더하지 못한다고 설명해주셨는데, split() 강의에서는 string 단위로 push_back(token) 해서 문자열이 추가되는 거 보고 혼란스럽기도 했습니다..ㅜㅜ 다르게 이해될 소지 없이 분명하게 설명해주셨으면 좋겠습니다..TrivallyCopyable도 그렇고,이런 UB같은 것도 그렇고 이미 알고 있을 거라고 생각하시고 넘어가시는 부분들에, 물론 중요한 설명을 빠뜨리신 것은 절대 아니지만 이런 작은 부분들이 모여서 제가 교안 외에 따로 검색을 하거나 찾는 부분이 잦게되다 보니, 시간도 걸리고 자꾸 흐름이 끊겨서요..시간이 걸리더라도 이러한 부분들에 대해서 간단한 주석이라도 설명해주시면 예제코드를 보았을 때 바로 이해하기가 더 좋을 것 같다는 생각이 들었습니다..! 큰돌님 유튜브도 잘 보고있고 이미 충분히 질 좋은 강의와 빠른 피드백으로 감사함이 참 많은데.. c++을 처음 접하는 사람들도 들을 수 있다고 하셔서, 이 강의 하나로 c++을 빠르게 공부할 목적으로 구매한 것이라 제 욕심이지만 말씀드립니다..ㅠㅠ
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
2-R 질문있습니다!
#include <bits/stdc++.h> using namespace std; int n,a[52],k,ret; vector<int> adj[52]; bool b[52]; void cut(int node){ b[node] = false; for(int s : adj[node]){ cut(s); } } int main(){ //입력 받기 cin >> n; for(int i = 0; i < n; i++){ cin >> a[i]; if(a[i]!=-1) adj[a[i]].push_back(i); b[i] = true; } cin >> k; // 노드 삭제 cut(k); for(int i = 0; i < n; i++){ if(adj[i].size() == 0 && b[i] == true) ret++; } cout << ret; } //테스트 케이스 통과 but 틀림..제 코드에서 놓친게 무엇일까요..!현재 노드에서 이어진 것이 없고, 잘리지 않았다면 리프노드로 판단해서 수를 카운트 해주었는데 오답입니다
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
2-O 질문있습니다!
#include <bits/stdc++.h> using namespace std; int main(){ string s; while(true){ getline(cin, s); if (s == ".") break; stack<char> stk = {}; for (char c : s) { if (c == ')' && stk.size() && stk.top() == '(') { stk.pop(); } else if (c == ']' && stk.size() && stk.top() == '[') { stk.pop(); } else if (c == '(' || c == '[') { stk.push(c); } else { continue; } } if (stk.empty()) { cout << "yes" << '\n'; } else { cout << "no" << '\n'; } } } 이 코드가 틀린 이유가 뭘까요..ㅠ 도저히 모르겠네요.그리고, 정답 풀이에서 check bool 변수가 하는 역할이 무엇일까요? 제 코드와의 차이가 check 플래그 변수가 없다는 것이 가장 큰 차이인 거 같은데 왜인지 모르겠습니다..
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
2-L 질문 있습니다.
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 선생님의 소스코드를 보면 int changeToInt(string a){ return atoi(a.substr(0, 2).c_str()) * 60 + atoi(a.substr(3, 2).c_str());}이렇게 되어 있는데 stoi()함수를 쓰면 c_str()을 안써도 되는 것으로 알고 있는데 atoi를 사용하는 이유가 있을까요??아니면 제가 잘못 알고 있는 걸까요...
-
해결됨10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
6-L 질문있습니다.
안녕하세요 강사님, 강의 잘 듣고 있습니다.강사님의 코드를 보면서 궁금한 점이 있습니다.강사님 코드에 아래의 두 케이스를 대입했습니다. 490.10.10.1 40.10.10.19문제에서는 '한 개 이상의 연속된 수의 곱' 이니 위와 아래 케이스 다 9가 나와야 하는 것 같은데, 케이스 1은 0.9가 나오고 케이스 2는 9가 나왔습니다. 제가 문제를 잘못 이해한 것인가요?#include <bits/stdc++.h> using namespace std; int n; double psum[10001], a[10001], ret, b; // a[i] > b*a[i] 일 경우, 이전까지의 곱 b를 버리고 a[i]에서 곱셈을 시작한다. int main(){ cin >> n; for(int i = 0; i < n; i++) cin >> a[i]; double b = a[0]; for(int i = 1; i < n; i++){ cout<<"a["<<i<<"] = "<<a[i]<<" b = "<<b*a[i]<<"\n"; if(a[i] > b * a[i])b = a[i]; else b *= a[i]; ret = max(b, ret); } ret = round(ret*1000)/1000; printf("%.3lf", ret); return 0; }
-
해결됨독하게 C를 배운 사람을 위한 선형 자료구조
자료 자체와 정렬된 인덱스 분리 (인덱스 정렬) - 인덱스 범위 코드에 버그가 있어서 질문 드립니다.
강사님 다름이 아니라 인덱스 검색의 SearchByIndexAgeRange에서 작은 버그가 있어서 해당 내용 공유 드립니다.검색 조건을 리스트에서 작은 값의 범위로 지정을 했을 시 아래 해당 코드에서 length 가 최소 값이 1이 되므로 항상 리스트의 작은 값이 출력이 되는 버그가 있습니다.동작에 대한 예시 화면입니다. 따라서 length 를 구한 다음 리스트에서 해당 USERDATA의 age 값을 max 값과 비교를 해서 max 값보다 작을 경우에만 해당 코드들이 동작하게 되어야 하는 것이 맞는 것 같습니다. 다음과 같이 코드 수정 시 동작 화면입니다.
-
해결됨10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
dfs 시간복잡도 질문
안녕하세요 큰돌님, 강의 잘 듣고 있습니다.간선리스트로 구현된 그래프에 dfs를 적용할 경우,시간복잡도는 O(|V|+|E|)로 알고 있습니다.만약, 주어진 그래프에서 각 노드가 4방향으로 간선이 뻗어있을 경우, 아래와 같은 방식으로 탐색을 이어나갑니다.int mv[4][2]={{0,1},{0,-1},{1,0},{-1,0}} for(int i=0; i<4; i++;) { int ny = y+mv[i][0] int nx = x+mv[i][1] }이때, 노드 개수를 V개면, 간선의 개수는 각 노드 별로 4개니까, |E|=|V|*4로 계산해서, 시간복잡도는 O(|V|*5) 인가요?
-
해결됨10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
백트래킹을 사용하는 경우 질문
안녕하세요 강사님, 강의 잘 듣고 있습니다.백트래킹은 완전탐색시 탐색하지 않아도 되는 부분은 건너뛰는 기능을 한다고 알고 있습니다.백트래킹은 기본적으로 완전탐색의 연산량을 줄여주는 역할을 한다는 것인데, 완전탐색으로 풀면 시간초과가 나는 문제를, 백트래킹을 적용해서 풀면 시간초과가 나지 않는 건 어떻게 판단할 수 있나요?완전탐색에 백트래킹을 적용해도 시간초과가 나는 경우에는 지체없이 다른 풀이법을 찾아야 하나요?
-
해결됨10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
4-L 시간복잡도 질문
안녕하세요 강사님, 강의 잘 듣고 있습니다.AC처럼 테스트케이스가 여러 개 주어질 경우, 제한 시간은 어떻게 고려해야 하는지 질문드리고 싶습니다.예를 들어, 주어진 문제의 제한 시간이 1초라면,테스트 케이스를 다 합해서 1초 안에 처리해야 하는 건지,아니면, 각 케이스를 1초 안에 처리해야 하는 건지 궁금합니다.
-
해결됨10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
조합 시간복잡도 질문
안녕하세요 강사님, 강의 잘 듣고 있습니다.조합을 구하는 함수의 시간복잡도에 대해 질문 드리고 싶습니다.// Online C++ compiler to run C++ program online #include <iostream> #include <vector> using namespace std; int r=0; vector<int> t; int cnt=0; int forcount=0; void combi(int idx) { if(t.size()==r) { cnt++; return; } for(int i=idx; i<=10; i++) { forcount++; t.push_back(i); func(i+1); t.pop_back(); } } int main() { // Write C++ code here while(true){ cnt=0; forcount=0; cin>>r; func(1); cout<<"cnt = "<<cnt<<"\n"; cout<<"forcount = "<<forcount; } return 0; }조합 함수의 시간복잡도는 O(nCr), 위의 함수에서는 cnt의 값이라고 알고 있습니다.그런데, 시간복잡도는 주어진 입력의 크기에 대한 연산의 총합이라고 알고 있습니다.그러면, combi 함수의 for문 연산의 수인 forcount도 고려해야 하지 않나요?왜? cnt만 고려해도 되는지 궁금합니다.
-
미해결파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)
격자판 최대합 질문있습니다.
이렇게 for문안에 모두 넣었습니다. 예제 답으로는 154가 뜨지만 채점 시 100점으로 뜨네요. 혹시 문제없는 코드일까요?
