월 15,400원
5개월 할부 시다른 수강생들이 자주 물어보는 질문이 궁금하신가요?
- 미해결코딩테스트 실전 모의고사(with C++) : 대기업 대비
BFS 참고하세요
#include <iostream> #include <vector> #include <queue> using namespace std; int n, m, k; int dx[4] = { 1, -1, 0, 0 }; int dy[4] = { 0, 0, 1, -1 }; int main() { cin >> n >> m >> k; vector<vector<int>> Map(n + 1, vector<int>(m + 1, 0)); vector<vector<bool>> visited(n + 1, vector<bool>(m + 1, false)); vector<pair<int, int>> flooded; for (int i = 0; i < k; i++) { int x, y; cin >> x >> y; Map[x][y] = 1; flooded.push_back({ x, y }); } int max_size = 0; for (auto& start : flooded) { if (visited[start.first][start.second]) continue; int size = 0; queue<pair<int, int>> Q; Q.push(start); visited[start.first][start.second] = true; while (!Q.empty()) { size++; int x = Q.front().first; int y = Q.front().second; Q.pop(); for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && Map[nx][ny] == 1 && !visited[nx][ny]) { Q.push({ nx, ny }); visited[nx][ny] = true; } } } max_size = max(max_size, size); } cout << max_size << endl; return 0; } DFS가 아닌 BFS 사용해도 문제는 풀립니다.공부중이라 어느게 더 효율적인지는 모르겠습니다만, 혹시 BFS로 접근하실 분들 참고하라고 올려봅니다~
- 미해결코딩테스트 실전 모의고사(with C++) : 대기업 대비
#include<bits/stdc++.h>
안녕하세요.제목과 같은#include<bits/stdc++.h>이 헤더를 썼을때, visual studio 나 DevC++ 에서 실행이 되지 않고 있는데요.해결 방법이 있나요?#include <iostream>을 사용해서 실행은 되고 있습니다.그리고, 실제 코딩테스트에서는 제목의 헤더나백터, 큐 같은 라이브러리 함수를 사용하지 못하도록 되어 있는데, 예를 들면#include <stdio.h> 또는#include <iostream> 이 두가지만 허용이 됩니다.벡터, 큐, max, min, abs 등과 같이 직접 만들어야 하는 함수에 대해서 부가 설명이 있으면 좋을 것 같습니다.그리고, ios ... 등등 이전 학습을 완료해야 알 수 있는 것들에 대해서도 물론 이 강의를 수강하는 정도의 레벨이라면 알고 있는 수강생들이 많겠지만, 짤막하게라도 설명이나 찾아볼 수 있는 곳이 있으면 좋겠습니다. (별도 네이버나 구글링을 통해서 찾아보려고 생각 중 입니다.) 저는 이전 강의를 미수강하고, 바로 이 과목을 선택 했거든요. 그리고, C언어에서는 안 돌아갔었던 것 같은데, 레인지 베이스드 포문도 C++에서만 되는 건지 궁금합니다. 감사합니다.
- 해결됨코딩테스트 실전 모의고사(with C++) : 대기업 대비
잔디 문제 해설 c로 바꿔서 출력할 때
안녕하세요.궁금한 점이 있어서 질문드립니다!c++로 된 코드를 c로 바꿔서 작성하려고 하는데#include<string.h> 선언 후에 string으로 넘겨서 출력하면 값이 이상하게 떠서요. 혹시 c로 바꿔서 출력하려고 하면 어떻게 코드를 짜야할까요..??
- 미해결코딩테스트 실전 모의고사(with C++) : 대기업 대비
조합을 구할때 algorithm 함수 next_permutation 사용 가능 여부
제목 그대로 조합을 구할때 next_permutation 을 사용 해도 되는지 궁금합니다
- 미해결코딩테스트 실전 모의고사(with C++) : 대기업 대비
최악의 경우 연산 질문이 있습니다.
강의를 수강하고 있는 학생입니다. 다만 최악의 경우를 따지는 데에서 조합의 수 x n(학생의수) 의 최악의 경우15C7 x 30000인데 이경우 6435x30000=193,050,000가 도출됩니다.이러면 계산이 2억번 가까이 되어서 1000ms에 풀수 있는지 여쭤 볼 수 있을 까요?
- 미해결코딩테스트 실전 모의고사(with C++) : 대기업 대비
로컬 환경과 다르게 오답이라고 나와서 문의 드립니다.
안녕하세요!우선 수업 굉장히 잘 듣고 있습니다! 도움이 많이 되네요!금일 문제를 풀고 있는데 제 로컬 환경에서는 아웃풋이 잘 나오는데 채점 사이트에서 답이 제대로 안나와서요..채점 사이트에 문제가 있는걸까요~?어제까지는 결과가 잘 나왔었어서 로컬 환경은 바뀐게 없습니다..아래 문제 목록 및 현상입니다. 도움 부탁 드립니다문제 : 5. 톰과 제리(BFS)해당 ID : d7a123cc4487문제 현상 : 채점 결과에 리턴값이 몇백줄 공란으로 나온 다음에 결과값이 프린트 되고 있습니다. 문제 : 4. 스도쿠(DFS 활용)해당 ID : ce811046b640문제현상 : 채점결과가 아예 나오지 않고 있습니다.
- 미해결코딩테스트 실전 모의고사(with C++) : 대기업 대비
6강 3번 정사각형 그리키 코드 질문 드립니다.
안녕하세요 선생님의 코드 설명을 듣고 6강 3번 코드를 구현했습니다. 그리고 제가 코드를 구현한 것에 선생님의 코드를 참고하여 코드를 조금 수정했습니다.visual studio에서는 정상적으로 정답이 출력이 되는데, 채점 사이트에서는 계속 오류가 출력됩니다. 그래서 제가 모든 테스트를 visual studio에서 돌려봤는데, 모두 정답이 출력됨에도 채점 사이트에서는 예상치 못한 오답이 출력되거나, 아예 답이 출력되지 않는 문제가 생깁니다. 띄어쓰기가 없는 입력을 한글자씩 숫자로 받기 위해서 scanf("%1d", &board[i][j]) 를 사용했습니다. 제 생각에는 scanf를 사용해서 이런 문제가 발생한 것 같은데, 아무리 찾아봐도 이유를 모르겠습니다ㅠㅠ 왜 그런지 알 수 있을까요? 답변 부탁드립니다! 감사합니다. 아래는 제가 구현한 코드입니다. #include <bits/stdc++.h>using namespace std;int main() {ios_base::sync_with_stdio(false);freopen("input.txt", "rt", stdin);int n, m;cin >> n >> m;vector < vector <int> > board(n, vector <int>(m, 0));vector < vector <int> > dy(n, vector <int>(m, 0));vector <int> answer(min(n, m) + 5, 0); // 0번부터 사용, 0 만나면 break;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {scanf("%1d", &board[i][j]);if (board[i][j] == 0) continue; // 0이면 그냥 넘기기if (i >= 1 && j >= 1) { // 경계선 밖으로 나가지 않고, board[i][j]==1이라면dy[i][j] = min(dy[i - 1][j - 1], min(dy[i - 1][j], dy[i][j - 1])) + 1;}else { // i가 0이거나 j가 0일때는 i-1, j-1이 경계에서 벗어나므로 그대로 입력dy[i][j] = board[i][j];}}}for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {for (int k = 1; k <= dy[i][j]; k++) { // k크기 이하인 정사각형 개수 세기answer[k]++;}}}for (int i = 1;; i++) {if (answer[i] == 0) break;cout << i << " " << answer[i] << endl;}return 0;}
- 미해결코딩테스트 실전 모의고사(with C++) : 대기업 대비
1-5 효율적인 공부 dy를 시간(N)으로 하는 풀이 질문
안녕하세요. 결론부터 말하자면 1-5문제 오답인데요선생님께서 푸신 풀이와는 좀 다른 방식으로 풀었습니다.저는 구간이 아니라 쌩으로 전체 시간 (N)을 dy로 놓고 풀었습니다. = (time_)=> dy는 해당 시간까지의 최대효율값을 넣고있습니다. [1] 일들을 끝나는 시간으로 정렬해서 그 순서대로 진행하는건 동일하구요.[2] dy 배열에서 해당 일의 시작 시간 - R (쉬는시간) 부터 0번째 시간까지 한 일 중에 가장 큰 값에다 해당 일의 효율을 더하는 식으로 진행했습니다.#include <iostream> #include <vector> #include <algorithm> using namespace std; int time_[1000001]; //dy*** struct my{ int a,b,c; my(int a, int b, int c){ this->a=a; //시작 시간 this->b=b; //끝나는 시간 this->c=c; //효율 } bool operator<(const my& other)const{ return b<other.b; } }; int main() { int max_=0; int N,M,R; //총 시간, 일 개수, 휴식시간 vector<my> arr; ... //DP sort(arr.begin(), arr.end()); for(int i=0; i< arr.size(); i++){ //일의 갯수 int val; if(arr[i].a - R >=1){ //time의 1번째부터 arr[i].a - R번째까지 수 중에... //가장 큰 값을 찾아서 더하여 넣음 int maxtmp=0; for(int j=0; j<=arr[i].a-R; j++){ if(maxtmp < time_[j]) maxtmp = time_[j]; } val = maxtmp + arr[i].c; } else{ val = arr[i].c; } //할 수 있는 일이 없으므로 //다음 일정이 끝나기 전 까지 같은 값 넣기 int j = arr[i].b; time_[j]=val; while( i+1!=arr.size() && j<arr[i+1].b){ time_[j]=val; j++; } //최대값 찾기 if(val > max_) max_ = val; } cout<<max_; return 0; } 이렇게 풀다가 오답이 나왔습니다. 결과는 케이스 1만 오답이고 나머지 2345는 정답인데정답은 83인데 제 코드는 81이 나옵니다큰 입력에 대해서는 정답인게 케이스 1에 뭔가 반례가 있어서 틀린 것 같은데 모르겠습니다...이전 단계 강의에서 늘상 하던 방식으로 걸리는 시간을 배열로 놓은거라 방법 자체는 맞는 것 같은데 이유를 모르겠습니다. 도와주세요
- 미해결코딩테스트 실전 모의고사(with C++) : 대기업 대비
반복수와 시간초 계산을 어떻게 하나요??
1-2 오렌지 나무에서100 (x좌표) 100 (y좌표) 100 (영지최대크기) ⇒ 1,000,000번의 반복 => 1초 안에 연산 끝남 ...이런 식으로반복문의 수로 미루어 보아서 시간이 리미트될지 아닐지 예상하셨는데반복문 수에 따라서 몇초가 걸릴지 어떻게 예상하나요???
- 미해결코딩테스트 실전 모의고사(with C++) : 대기업 대비
왜 DP로 풀어야하는지 궁금합니다
DFS 풀이는 시간초과가 발생하는 이유가 궁금합니다.DFS 풀이는 시간초과가 발생하기 때문에 DP로 풀어야하는건가요?이에 대한 설명은 없어서 질문드립니다. DFS 시간초과 코드는 다음과 같았습니다.struct Work { int s, e; int score; }; int n, m, r; vector<Work> schedule; int result = 0; bool compare(Work a, Work b) { return a.s < b.s; } void dfs(int now, int start, int score) { if (now >= n) { result = max(result, score); return; } result = max(result, score); for (int i = start; i < m; i++) { if (schedule[i].s < now) continue; dfs(schedule[i].e + r, i + 1, score + schedule[i].score); } } int main() { cin >> n >> m >> r; for (int i = 0; i < m; i++) { int s, e, score; cin >> s >> e >> score; schedule.push_back({ s,e,score }); } sort(schedule.begin(), schedule.end(), compare); dfs(0, 0, 0); cout << result; return 0; }
- 미해결코딩테스트 실전 모의고사(with C++) : 대기업 대비
선생님 안녕하세요. 다른 풀이에 대한 질문이 있습니다.
안녕하세요. 항상 좋은 강의 감사드립니다. 문제에서는 vector<pair<int, int>>를 쓰셨는데, 저는 2차원 배열을 이용해서 풀어보았습니다. #include <bits/stdc++.h> using namespace std; int board[10001][10001]; int n, m, s, e; int can(int w) { queue<int> Q; int ch[10001]; for (int i = 0; i < 10; i++) cout << ch[i] << " "; cout << endl; ch[s] = 1; cout << "앞부분 ch[e] : " << ch[e] << endl; Q.push(s); while(!Q.empty()) { int v = Q.front(); Q.pop(); for(int i = 0; i < 10; i++) { if(board[v][i] >= w && ch[i] == 0) { cout << "여기 옴" << endl; cout << v << " " << i << endl; ch[i] = 1; Q.push(i); } } } cout << "ch[e] : " << ch[e] << endl; return ch[e]; } int main() { ios_base::sync_with_stdio(false); freopen("input.txt", "rt", stdin); int lt = 1, rt = 1000000000, mid, res; cin >> n >> m; for(int i = 1; i <= m; i++) { int a, b, c; cin >> a >> b >> c; board[a][b] = c; } cin >> s >> e; while(lt <= rt) { mid = (lt + rt) / 2; if(can(mid)) { cout << "mid : " << mid << endl; res = mid; lt = mid + 1; } else { cout << "else mid : " << mid << endl; rt = mid - 1; } } cout << res; return 0; } 실행해보시면 답이 6이 나오는데, ch 배열이 새로 선언되어도 그 전의 값을 그대로 가지고 있는 것 같네요. 이 현상의 원인에 대해 질문드리고 싶습니다! 실행
- 미해결코딩테스트 실전 모의고사(with C++) : 대기업 대비
문제 해결방법에 대한 질문이 있습니다.
안녕하세요! 이 문제를 처음에 풀 때 vector,pair를 써서 DFS알고리즘(인접 리스트)으로 풀어보려고 고민했습니다. 근데, 도저히 시작값을 어떻게 넣어야 할지 모르겠어서 막혀버렸습니다. 근데 LIS알고리즘을 사용해서 푸시는걸 보고 두 가지 궁금증이 생겼습니다. 이 문제도 일단 DFS로 접근이 가능할까요? 그리고 이 문제를 보고 LIS알고리즘으로 풀어야겠다고 생각하신 것은 코딩 문제들을 많이 접해보시고 풀어보셔서 그런건지 궁금합니다. 저번 버전의 수업에서는 목차가 정해져 있어서 알고리즘을 고르는 데에 어려움이 없었는데, 이번 강좌는 진짜 시험문제처럼 나오다 보니 어떤 알고리즘을 사용해야 할지 더 고민되는 것 같습니다. 이것은 많이 풀어보고 접해야하는 부분인가요? 감사합니다.
- 미해결코딩테스트 실전 모의고사(with C++) : 대기업 대비
바둑대회 코딩 질문
#include<iostream> #include<vector> #include<math.h> #include<string> #include<deque> #include<stack> #include<queue> #include<algorithm> using namespace std; int N; vector<pair<int, int>> vec; vector<int> check(N+1, 0); int m = 2147000000; void DFS(int k, int cnt) { if(cnt == N/2) { int sum1 = 0; int sum2 = 0; for(int i = 1; i <= N; i++) { if(check[i] == 1) { sum1 += vec[i].first; } else { sum2 += vec[i].second; } } m = min(abs(sum1-sum2) , m); } else { for(int i = k; i <= N; i++) { if(check[i] == 0) { check[i] = 1; DFS(i + 1, cnt + 1); check[i] = 0; } } } } int main() { ios_base::sync_with_stdio(false); cin >> N; vec.push_back({0,0}); for(int i = 0; i < N; i++) { int a, b; cin >> a >> b; vec.push_back({a, b}); } DFS(1, 0); cout << m; return 0; }
- 미해결코딩테스트 실전 모의고사(with C++) : 대기업 대비
6분 11초에서 dis [0][][]3차원 격자판이있는데요. 격자판안에 숫자는 문제에 없던데 어떻게 구해지는건가요?
6분 11초에서 dis [0][][]3차원 격자판이있는데요. 격자판안에 숫자는 문제에 없던데 어떻게 구해지는건가요? 캡쳐해서 보여드리고 싶은데 캡쳐방지가 걸려져있어 글자로 풀어서 질문합니다.
- 미해결코딩테스트 실전 모의고사(with C++) : 대기업 대비
실전모의고사 5회 1번 패턴찾기 질문있습니다.
안녕하세요 강사님 실전모의고사 5회 1번 패턴찾기에 질문있습니다. 만약 패턴이 2012201255/2012201255 이런식으로 들어온다면 강사님의 코드로는 틀린코드가 됩니다. 스트링을 임시로 정한 패턴길이만큼만 한번만 검사하는게아니라 첫 줄은 길이가 50을 넘지않고, 패턴이 발견될 정도의 정보를 준다고 했으니 패턴스트링의 길이는 최소 3 최대 25이니, 임시로 정한 패턴길이만큼을 50길이만큼을 반복 검사해야될 것 같습니다. 혹시 제가 어딘가 잘못이해하고있는것인가요?
- 미해결코딩테스트 실전 모의고사(with C++) : 대기업 대비
전역변수관련 질문입니다.
안녕하세요 강사님. 해당 문제관련 질문은 아니지만 그래도 어느정도 관련이 있어 여기다가 질문글 올립니다. 전역변수관련 질문이 있습니다. 요즘 코딩테스트에는 입력값받는 코드는 안 써도 되게 함수를 주고 인자값에 입력값이 다들어있는상태에서 함수 안에서 코드를 작성하라고 되어있는 경우가 많더라구요. 저는 코딩테스트를 강사님의 '대기업대비' 전의 '코딩테스트 대비' 를 처음으로 연습을 해와서 DFS나 BFS등 이외에도 많은 문제들을 전역 변수로 활용해서 푸는게 습관이 되었습니다. 하지만 위와같이 함수안을 구현하라는 문제가 나올때 전역변수를 쓴다면 당장 문제를 맞출 수는 있겠지만 함수구현인데 전역변수를 쓴다는 것 자체가 프로그래밍 관점으로 보았을 때, 보안문제 등 의도에 어긋난 것 같다는 느낌이 들었습니다. 예를 들면 DFS구현 문제인데 함수에서는 인자로 학생의 데이터가 들어간 벡터를 넘겨주는데 강사님처럼 함수안에 DFS()로 하고 외부에 DFS함수구현을 하자니 벡터의 생명주기때문에 외부에서는 쓸수 없게 됩니다. 그래서 전역벡터변수를 하나 만들고 거기다가 함수인자값을 복사해주어서 전역변수로 문제를 풀었습니다. 아니면 원래 전역변수로 선언하던 벡터 등을 함수(DFS)에 인자로 계속 넘겨주자니 이것도 공간, 효율성에 문제가 있어보입니다. 그래서 이런 방식으로 문제를 풀었다고 해도 기업에서 보고 탈락시킬거라는 생각이들고 나중에 면접때도 왜 이렇게 풀었냐는 답변에는 답변을 잘 못할거라는 생각이 듭니다. 이런경우는 어떤식으로 보통 해결하나요? 긴 글 읽어주셔서 감사합니다
- 미해결코딩테스트 실전 모의고사(with C++) : 대기업 대비
5-1 패턴찾기 문제 질문드립니다.
5-1 패턴찾기 문제에서 강의에서 설명해주신 방법으로 문제를 풀게되면 패턴안에 반복되는 문자열이 있을 때 원하는 결과값을 얻지 못하지 않나요? 예를 들자면, 철수가 패턴을 "1231234"로 설정한 경우를 예시로 n이 14로 주어진다면, 강사님이 풀어주신 방법으로 문제를 풀면 패턴은 "123"이 되어 결과값 27이 반환되나 실제기댓값은 패턴이 "1231234"가 되어 결과값 32가 반환되어야 옳은 결과값이라고 생각됩니다. 저는 find함수를 통해 문제를 구현했습니다. 코드 확인도 같이 부탁드립니다. #include <iostream> #include <string> using namespace std; int main(){ string s; int n; cin >> s >> n; int cnt= 1; string pattern = s.substr(0,cnt); while(s.find(pattern,cnt+1)!=string ::npos){ pattern = s.substr(0,++cnt); } int pattern_len= pattern.size(); int res = 0; int len = pattern.size(); for(int i=0; i<len; i++){ res += pattern[i] - '0'; } res = (n/len) * res; for(int i=0; i< n%len; i++){ res += pattern[i] - '0'; } cout << res << endl; return 0; }
- 미해결코딩테스트 실전 모의고사(with C++) : 대기업 대비
오렌지 나무 문제 질문드립니다
안녕하세요. 선생님 질문드립니다. 아래와 같이 검사 범위를 지정하면 반드시 우리가 원하는 모든 영역을 다 검사할 수 있다는 것은 직관적으로 이해해야하는 것인가요? 혹시 우리가 원하는 모든 영역을 다 검사한다는 것을 좀 더 쉽게 이해할 수 있을까요? 제 경우 더 어려운 방법이긴 하지만, 모든 점을 순회하며 각 점을 기준으로 아래와 같이 4개의 영역을 S범위로 하여 검사하면 될 거라 직관적으로 생각했습니다. (빨간 점은 모든 나무 중 하나의 나무)
- 미해결코딩테스트 실전 모의고사(with C++) : 대기업 대비
코드 한번 봐주시면 감사하겠습니다!
제가 적은 코드가 시간 초과가 떠서 강사님께서 올려주신 코드로 채점해봤는데도 시간 초과가 나옵니다... 한번 봐주시면 감사하겠습니다~! #include <iostream> #include <vector> #include <algorithm> #include <string> using namespace std; int main() { ios_base::sync_with_stdio(false); int n, m; cin >> n >> m; vector<vector<int> > dy(n, vector<int>(m, 0)); vector<string> board; vector<int> answer(min(n, m) + 2); for (int i = 0; i < n; i++) { string tmp; cin >> tmp; board.push_back(tmp); } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (board[i][j] == '0') continue; int a = 0, b = 0, c = 0; if (i - 1 >= 0) a = dy[i - 1][j]; if (j - 1 >= 0) b = dy[i][j - 1]; if (i - 1 >= 0 && j - 1 >= 0) c = dy[i - 1][j - 1]; int m = min(a, min(b, c)); dy[i][j] = m + 1; } } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { for (int k = 1; k <= dy[i][j]; k++) { answer[k]++; } } } for (int i = 1; ; i++) { if (answer[i] == 0) break; cout << i << " " << answer[i] << endl; } return 0; } 어디가 문제인지 잘 모르겠습니다 :(
- 미해결코딩테스트 실전 모의고사(with C++) : 대기업 대비
코드 한번 봐주시면 감사하겠습니다!
#include <iostream> #include <vector> #include <string> using namespace std; int main() { bool flag = false; int cnt = 0; string s,res,tmp,scnt="0"; cin >> s; for (int i = 0; i < s.size(); i++) { if (flag) { while (s.at(i) != ')') { tmp += s.at(i); i++; } } if (s.at(i) == '(') { cnt = stoi(scnt); flag = true; if (cnt == 0) cnt = 1; } else if (s.at(i) == ')') { for (int j = 0; j < cnt; j++) { res += tmp; } tmp = '\0'; scnt = '0'; flag = false; cnt = 0; } else scnt += s.at(i); } cout << res; return 0; } 테스트케이스로 확인해보면 다 정답이랑 같게 나오는데 wrong answer이라고 나오고 채점 페이지를 이용하면 계속 로딩화면만 나옵니다,,,,