월 15,400원
5개월 할부 시다른 수강생들이 자주 물어보는 질문이 궁금하신가요?
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
크루스칼 알고리즘 관련하여
아래가 수업도중에 배운 알고리즘인데요! ------------------------------------------ int main(void) { int v, e, city_a, city_b, cost, i, res, cnt; vector<Edge> Ed; res = cnt = 0; cin >> v >> e; for (i = 1; i <= e; i++) { unf[i] = i; } for (i = 0; i < e; i++) { cin >> city_a >> city_b >> cost; Ed.push_back(Edge(city_a, city_b, cost)); } sort(Ed.begin(), Ed.end()); for (i = 0; i < m; i++) { int fa = Find(Ed[i].v1); int fb = Find(Ed[i].v2); if (fa != fb) { res += Ed[i].cost; Union(Ed[i].v1, Ed[i].v2); } } cout << res << endl; return 0; } ------------------------------------------ 이 중에서 간선을 선택하는 for (i = 0; i < m; i++) { int fa = Find(Ed[i].v1); int fb = Find(Ed[i].v2); if (fa != fb) { res += Ed[i].cost; Union(Ed[i].v1, Ed[i].v2); } } 이 부분에 대해 궁금증이 있습니다! 크루스칼은 n개의 정점이 주어지면 n-1 개의 간선을 최소 가중치를 기준으로 선택하는 것으로 알고 있습니다. 그런데 문제에선 n-1개라는 기준을 사용하지 않았는데 그 이유가 있을까요? 선생님의 문제풀이에서 cnt 변수를 만드셨으나 사용하지 않으셨는데, 이를 체크하려다 체크하지 않으신 것 같습니다. 그 이유는 무엇인지 궁금합니다.
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
15번 질문입니다.
#define _CRT_SECURE_NO_DEPRECATE #include <stdio.h> int main() { //freopen("input.txt", "rt", stdin); int N; scanf("%d", &N); bool* isPrime = new bool[N+1]; for (int i = 0; i < N+1; ++i) isPrime[i] = true; for (int i = 2; i < N+1; ++i) for (int j = 2 * i; j < N+1; j += i) isPrime[j] = false; int cnt = 0; for (int i = 2; i < N+1; ++i) if (isPrime[i]) cnt++; printf("%d\n", cnt); if (isPrime) delete[] isPrime; return 0; } 강의시간에 보여주신 코드와 비교했을 때, Big(O)만 따져보면 뭐가 이득인지 궁금합니다. 그리고 알고리즘 문제를 풀 때, 동적할당은 피해야하는지도 궁금합니다. 감사합니다.
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
강의에 대해 질문 있습니다.
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 안녕하세요 선생님 질문있습니다. 제가 지금 C++ 에서 코딩테스트 언어를 파이썬으로 바꾸었는데, 혹시 "파이썬 알고리즘 문제풀이 (코딩테스트 대비)"와 "it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비"의 강의의 차이점이 있을까요? 내용적으로 C++강의가 더 좋아보이기는 하는데 어떤 차이점이 있는 지 궁금합니다. 별차이 없으면 파이썬으로 들으려고 합니다. 감사합니다.
- 해결됨it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
질문있습니다.
43번 뮤직비디오(이분검색 응용 : 결정 알고리즘) 관련 두가지 질문이 있습니다. 1. 직접 코드를 다음과 같이 작성해보았는데 결과값이 잘 나오지 않아 어디서 오류가 생긴 것인지 궁금하여 질문드립니다. #include<stdio.h> #include<vector> #include<algorithm> using namespace std; int main(){ freopen("input.txt", "rt", stdin); int n, m, ans, i, cnt=1, lt=1, rt=0, mid, max=-2147000000, sum; scanf("%d %d", &n, &m); vector<int> t(n); for(i=0; i<n; i++){ scanf("%d", &t[i]); rt+=t[i]; if(t[i]>max) max=t[i]; } while(lt<=rt){ mid=(lt+rt)/2; for(i=0; i<n; i++){ sum+=t[i]; if(sum>mid){ sum=0; cnt++; i--; } } if(mid>=max && cnt==m){ ans=mid; rt=mid-1; }else{ lt=mid+1; } } printf("%d\n", ans); return 0; } 2. while(lt<=rt)라는 조건을 이용하여 반복문을 실행하는데, 여기서 lt<=rt 조건을 어떻게 벗어나서 반복이 종료되는 것인지 궁금하여 질문드립니다.
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
벡터 선언할 때 a(n)으로 하면 왜 안되나요??
안녕하세요 강사님. 강의 열심히 수강하고 있습니다. 강의를 보기 전 먼저 풀어봤는데, 변수 이름만 다르고 코드내용은 거의 같은데도 아무것도 출력되지 않고 정상적으로 종료는 됩니다. 코드를 비교해보니 벡터를 선언할 때 v(n)으로 원소 개수를 정해줘서 그런것 같은데, 왜 이렇게 하면 아무것도 출력이 안되는지 알 수 있을까요..? //#42] 이분검색 (Binary Search) #include <iostream> #include <algorithm> #include <vector> using namespace std; int main(){ freopen("input.txt","rt",stdin); int n, m, start, mid, end, tmp; scanf("%d %d", &n, &m); //n=8, m=32 vector <int> v(n); for(int i=0; i<n; i++){ //scanf("%d",&v[i]); scanf("%d", &tmp); v.push_back(tmp); } sort(v.begin(), v.end()); start=0; end=n-1; while(start<=end){ mid=(start+end)/2; if(v[mid]>m){ end=mid-1; }else if(v[mid]<m){ start=mid+1; }else if(v[mid]==m){ printf("%d", mid+1); return 0; } } return 0; }
- 해결됨it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
질문있습니다.
41번 연속된 자연수의 합(단순 수리)의 코드를 i를 1부터 증가시켜서 연속되는 자연수의 합이 주어진 수를 만족하는 경우에 해당 수들을 출력하도록 코드를 짜보았는데, 이렇게 해도 되는건가요? 혹시 틀린 부분이 있다면 알려주시면 감사하겠습니다. #include<stdio.h> using namespace std; int main(){ //freopen("input.txt", "rt", stdin); int n, i, k, sum, tmp, cnt=0; scanf("%d", &n); for(i=1; i<n; i++){ sum=0; tmp=i; while(sum<n){ sum+=tmp; tmp++; } if(sum==n){ for(k=i; k<tmp-1; k++){ printf("%d + ", k); } printf("%d = %d\n", k, sum); cnt++; } } printf("%d\n", cnt); return 0; }
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
BFS와의 차이점이 궁금합니다.(64번)
안녕하세요. 64번 해당문제에서 DFS로 설명해주셨습니다. 이진트리로 DFS와 BFS를 각각 비교하면 깊이탐색, 너비탐색이 이해가 금방되는데, 이렇게 방향그래프에서 DFS와 BFS의 차이점을 잘 모르겠습니다. 해당 문제에서는 1->5로 가는 방법으로 1 2 3 4 5 1 2 5 1 3 4 2 5 1 3 4 5 1 4 2 5 1 4 5 이 순서인데, 이걸 BFS방식으로 풀면 혹시 1 2 5 1 4 5 1 3 4 5 1 4 2 5 1 2 3 4 5 1 3 4 2 5 순으로 찾게되나요? 감사합니다.
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
BFS와 다이나믹 테이블을 섞어서 풀었는데 그럼 이건 DP로 풀었다고 볼 수 없는건가요??
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중 #include <iostream> #include <queue> using namespace std; int map[21][21]; int dy[21][21]; int row[2] = {1,0}; int col[2] = {0,1}; int main() { ios_base::sync_with_stdio(false); int N; queue<pair<int,int>> q; cin >> N; for(int i = 1; i <= N; i++){ for(int j = 1; j <= N; j++){ cin >> map[i][j]; if(i == 1 && j == 1){ dy[i][j] = map[i][j]; }else{ dy[i][j] = 2147000000; } } } q.push(make_pair(1,1)); while(!q.empty()){ pair<int, int> x = q.front(); q.pop(); for(int i = 0; i < 2; i++){ int _x = x.first + row[i]; int _y = x.second + col[i]; int energy = dy[x.first][x.second] + map[_x][_y]; if(energy < dy[_x][_y]) { dy[_x][_y] = energy; q.push(make_pair(_x, _y)); } } } cout << dy[N][N]; return 0; } 하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
cin>> , scanf( ), gets( )의 차이점이 무엇인가요?
선생님 안녕하세요, cin>> , scanf( ), gets( )의 차이점이 무엇인지 모르겠습니다. 그리고 c언어에서는 scanf()나 gets()를 주로 사용했는데, C++에서 std::cin>> 함수가 쓰이는 이유도 궁금합니다. 답변 기다리겠습니다. 감사합니다.
- 해결됨it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
질문있습니다.
시간초과와 상관없이 다음과 같은 코드를 만들어보았는데 제대로 작동이 안됩니다. 어디가 잘못된 것인가요? #include<stdio.h> #include<vector> using namespace std; int main(){ freopen("input.txt", "rt", stdin); int n, m, i, k, cnt=0, tmp; scanf("%d", &n); vector<int> a(n); for(i=0; i<n; i++){ scanf("%d", &a[i]); } scanf("%d", &m); vector<int> b(m); for(i=0; i<m; i++){ scanf("%d", &b[i]); } vector<int> c(n+m); for(i=0; i<n; i++){ for(k=0; k<m; k++){ if(a[i]==b[k]){ c[i]=a[i]; cnt++; } } } for(i=0; i<cnt-1; i++){ for(k=i+1; i<cnt; i++){ if(c[i]>c[k]){ int tmp; tmp=c[i]; c[i]=c[k]; c[k]=tmp; } } } for(i=0; i<cnt; i++){ printf("%d ", c[i]); } return 0; }
- 해결됨it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
질문있습니다.
37번 Least Recently Used (삽입정렬 코드 스타일 : 카카오 문제에서 코드를 다음과 같이 작성해보았는데 제대로 작동하지 않습니다. 어디서 잘못된 것인가요? #include<stdio.h> #include<vector> using namespace std; int main(){ freopen("input.txt", "rt", stdin); int s, n, i, k, pos; scanf("%d %d", &s, &n); vector<int> c(s); vector<int> d(n); for(i=0; i<n; i++){ scanf("%d", &d[i]); } for(i=0; i<n; i++){ pos=-1; for(k=0; k<s; i++){ if(c[k]==d[i]){ pos=k; break; } } if(pos==-1){ for(k=s-1; k>=1; k--) c[k]=c[k-1]; } else{ for(k=pos; k>=1; k--) c[k]=c[k-1]; } c[k]=d[i]; } for(i=0; i<s; i++){ printf("%d ", c[i]); } return 0; }
- 해결됨it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
질문있습니다.
36번 삽입정렬 문제의 코드를 보니 앞부분에 #include<vector> #include<algorithm> using namespace std; 이게 추가되어있는데 혹시 어느 코드의 부분에서 사용되어 #include 되어 있는 것인가요?
- 해결됨it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
질문있습니다.
23번 연속 부분 증가수열 문제의 코드를 다음과 같이 작성해보았는데 채점프로그램을 돌려보니 틀린 부분이 있다고 나옵니다. 어디서 틀린건가요? #include<stdio.h> int main(){ //freopen("input.txt", "rt", stdin); int n, num[100000], max=-2147000000, cnt=1, i; scanf("%d", &n); for(i=0; i<n; i++){ scanf("%d", &num[i]); } for(i=0; i<n; i++){ if(num[i]<=num[i+1]) cnt++; else{ if(max<cnt) max=cnt; cnt=1; } } printf("%d\n", max); return 0; }
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
DFS 함수 선언
#include <iostream> #include <vector> #include <algorithm> #include <string> #include <stack> int a[101],n; int tmp[101]; using namespace std; void merge(int start, int end){ if(start >= end) return; else { int mid = (start+end)/2; merge(start,mid); merge(mid+1,end); int i = start; int j = mid+1; int k = start; while (i <= mid && j <= end){ if(a[i] <= a[j]) tmp[k++] = a[i++]; else tmp[k++] = a[j++]; } if(i <= mid) { while(i<=mid){ tmp[k++] = a[i++]; } } else if (j<= end){ while(j<= end){ tmp[k++] = a[j++]; } } for (int t = start; t <= end; t++){ a[t] = tmp[t]; } } } int main(){ int n; scanf("%d",&n); for(int i = 1; i <= n; i++){ scanf("%d",&a[i]); } merge(1,n); for (int t = 1; t <= n; t++){ printf("%d ",tmp[t]); } return 0; } 함수를 선언할 때 선생님께서는 merge(a,1,n)으로 배열까지 앞에 넣어 선언했는데 저는 merge(1,n)으로 해도 실행이 되었습니다. 앞에 배열을 넣어주는 특별한 이유가 있나요?
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
질문있습니다
int map을 전역변수가 아닌 지역변수로 선언하면 오류가 발생하는데 무엇때문인가요? 지역변수로 선언하면 초기화가 안되서 그런가요? ``` #include <iostream> #include <vector> #include <algorithm> #include <string> #include <stack> using namespace std; int main() { int map[20][20]; int n,m,a,b,c; scanf("%d %d",&n, &m); for(int i= 1; i<=m; i++){ scanf("%d %d %d",&a,&b,&c); map[a][b] = c; } for (int i = 1; i <= n; i++){ for(int j = 1; j<= n; j++){ printf("%d ", map[i][j]); } printf("\\n"); } return 0; ```
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
후속 강의 질문드립니다
선생님 안녕하세요. 코딩테스트 C++ 강의 잘 들었습니다!! 후속강좌를 올리신걸로 아는데 혹시 파이썬으로도 후속강좌 올리실 예정 있으신지 여쭙고 싶어서 질문글드립니다. 요새 파이썬을 다 지원하고, 같은 코드를 써도 간결하게 쓸 수 있어서 좀 유리하다고 생각하는데 어떻게 생각하시나요!
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
질문있습니다
61번 문제를 다르게 풀었는데 오류가 발생했습니다. 주어진 문제를 예시로 들자면 (2,4,6,8) 4개의 배열을 늘려서 (2,4,6,8,-2,-4,-6,-8) 8개로 선언한 뒤 DFS 함수를 사용했는데 답이 틀렸습니다. 스스로 디버그를 거쳤지만 오류를 발견하지 못했는데 무엇이 문제인가요?ㅠㅠ #include <iostream> #include <vector> #include <algorithm> #include <string> #include <stack> using namespace std; int cnt=0, n, m, a[22]; void DFS (int L, int sum){ if(L == n+n+1){ if(sum == m) cnt++; } else { DFS(L+1,sum + a[L]); DFS(L+1,sum); } } int main() { int n,m; scanf("%d %d",&n,&m); for(int i = 1; i<= n+n; i++){ if(i <= n) scanf("%d",&a[i]); else a[i] = -(a[i-n]); } DFS(1,0); printf("%d",cnt); return 0; }
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
질문있습니다!
#include <iostream> #include <vector> #include <algorithm> #include <string> #include <stack> using namespace std; int main() { int n; scanf("%d",&n); vector<int> a(n+2); for (int i = 1; i <= n; i++){ scanf("%d",&a[i]); } stack<int> s; vector<char> c; s.push(a[1]); c.push_back('P'); int i = 2; int j = 1; while(i<=n || j <= n ){ if(s.top() == j){ s.pop(); c.push_back('O'); j++; } else { s.push(a[i]); c.push_back('P'); i++; } } if(!s.empty()) printf("impossible"); else { for (int k = 0; k<c.size();k++) printf("%c",c[k]); // size를 이용한 for문 } return 0; } - 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 제가 짠 코드가 선생님 코드와 조금 달랐습니다. 그래서 답을 체크해봤더니 3번과 4번 문제에서 time limited이 나왔는데 스스로 디버그 하는 과정을 거쳤지만 어디가 문제인지 찾아내지 못했습니다.ㅠㅠ 어디가 문제인가요?
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
bfs를 재귀적으로 풀어봤어요..
삭제된 글입니다
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
질문있습니다
삭제된 글입니다