월 15,400원
5개월 할부 시다른 수강생들이 자주 물어보는 질문이 궁금하신가요?
- 미해결코딩테스트 실전 모의고사(with C++) : 대기업 대비
코드 한번 봐주시면 감사하겠습니다!
#include <iostream> #include <algorithm> #include <vector> #include <cmath> using namespace std; int main() { double n, cnt = 1, res = INT_MIN; int answer = 0; cin >> n; vector<int> arr(n); for (int i = 0; i < n; i++) { cin >> arr[i]; if (arr[i] == 0) cnt++; else { cnt /= 2; res = max(cnt, res); cnt = 0; } } if (cnt >res)answer = ceil(cnt); else answer = ceil(res); cout << answer; return 0; } 이런식으로 코드를 짜봤는데 테스트를 돌렸을 때 다 맞긴 합니다만 혹시 시간 효율성으로 봤을 때 좋지 않은 코드인가요?
- 미해결코딩테스트 실전 모의고사(with C++) : 대기업 대비
시작점의 ch
안녕하세요. While문 이전에 Q.push(s)를 통해 시작점을 Q에 넣는데, 시작점 s의 ch[s]=1은 필요 없는지요? for문 안에서 ch[nx]가 5일 때 skip 할 수 있어 보여서 문의 드립니다.
- 미해결코딩테스트 실전 모의고사(with C++) : 대기업 대비
vector에서 질문이 있습니다~!
문득 든 생각인데요 vector<int> arr[n]과 vector<int> arr(n)이 무슨 차이가 있는 건가요? arr[1]안에 배열을 넣을 수 있고 arr(1)안엔 배열을 넣을 수 없음의 차이인가요????
- 미해결코딩테스트 실전 모의고사(with C++) : 대기업 대비
그대로 따라했는데 시간 초과가 나왔습니다
그대로 따라서 했는데 4번 5번 테스트케이스에서 시간초과가 나왔습니다,,, 3번 확인해도 똑같이 따라 코딩했는데 왜 그런걸까요...? #include <iostream> #include <queue> using namespace std; int dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 }; int board[1001][1001], dis[2][1001][1001]; queue<pair<int, int>> Q; int w, h; void BFS(int idx) {//idx = 2부터 시작했니, 3부터 시작했니 판가름할 변수 while (!Q.empty()) { 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 >= 0 && nx < h&&ny >= 0 && ny < w&&dis[idx][nx][ny]==0) {//경계선 if (board[nx][ny] != 1) { dis[idx][nx][ny] = dis[idx][x][y] + 1; Q.push(make_pair(nx, ny)); } } } } } int main() { cin.tie(NULL); // 입력빨리하기 위해 cin >> w >> h; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) cin >> board[i][j]; } int j; for (int i = 0; i < h; i++) { for (j = 0; j < w; j++) { if (board[i][j] == 2) { //영희의 위치찾기 dis[0][i][j] = 1;//영희로부터의 거리를 1부터 출발 Q.push(make_pair(i, j)); BFS(0); break; } } if (j < w)break; } for (int i = 0; i < h; i++) { for (j = 0; j < w; j++) { if (board[i][j] == 3) { dis[1][i][j] = 1; Q.push(make_pair(i, j)); BFS(1); break; } } if (j < w)break; } int min = 2147000000; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { if (board[i][j] == 4 && dis[0][i][j] > 0 && dis[1][i][j] > 0) { int res = dis[0][i][j] + dis[1][i][j]; if (res < min)min = res; } } } cout << min - 2; return 0; }
- 미해결코딩테스트 실전 모의고사(with C++) : 대기업 대비
2회 모의고사 4번 숲속의 기사 코드 질문이 있습니다.
#include <bits/stdc++.h>using namespace std;struct Data { int x, y, day; Data(int a, int b, int c) { x = a; y = b; day = c; }};int w, h;int my_map[1001][1001], ch[2][1001][1001], res_me[1001][1001], res_knight[1001][1001], res_min = INT_MAX;int dx[4] = {0, 1, 0, -1};int dy[4] = {1, 0, -1, 0};Data me(0, 0, 0), knight(0, 0, 0);queue<Data> Q;vector<Data> straw_pos;void Find(string m_or_n) { int ch_; if (m_or_n == "m") { ch_ = 0; } else { ch_ = 1; } while(!Q.empty()) { Data a = Q.front(); int x = a.x; int y = a.y; int day = a.day; ch[ch_][x][y] = 1; Q.pop(); if(my_map[x][y] == 4) { if(m_or_n == "m") { if(res_me[x][y] == 0) res_me[x][y] = day; } else if(m_or_n == "n") { if(res_knight[x][y] == 0) res_knight[x][y] = day; } } for(int i=0; i<=3; i++) { int xx = x + dx[i]; int yy = y + dy[i]; if(xx >=1 && xx <= h && yy>=1 && yy <=w) { if(my_map[xx][yy] != 1 && ch[ch_][xx][yy] != 1) { Q.push(Data(xx, yy, day+1)); } } } }}int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); freopen("input.txt", "rt", stdin); cin >> w >> h; for(int i=1; i<=h; i++) { for(int j=1; j<=w; j++) { cin >> my_map[i][j]; if (my_map[i][j] == 2) me = Data(i, j, 0); if (my_map[i][j] == 3) knight = Data(i, j, 0); else if(my_map[i][j] == 4) straw_pos.push_back(Data(i, j, 0)); } } Q.push(me); ch[0][me.x][me.y] = 1; Find("m"); // me Q.push(knight); ch[1][knight.x][knight.y] = 1; Find("n"); // knight for(int i=0; i<straw_pos.size(); i++) { int x = straw_pos[i].x; int y = straw_pos[i].y; int sum = res_me[x][y] + res_knight[x][y]; if(sum == 0) sum = INT_MAX; res_min = min(sum, res_min); } cout << res_min; return 0;} 강의는 다들었습니다. 로직 자체는 같은 것 같습니다. 다만 저는 영히의 위치, 기사의 위치, 딸기의 위치를 배열에 저장하고 진행하였습니다. 4, 5번 테스트 케이스에서 타임리밋이 나오는데 이유를 잘 모르겠습니다..... 답변해주시면 감사하겠습니다.
- 미해결코딩테스트 실전 모의고사(with C++) : 대기업 대비
질문있습니다.
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. //Kruskal #include <bits/stdc++.h> using namespace std; int unf[1001]; struct Hotel{ int number; int x; int y; Hotel(int number, int x, int y){ this->number = number; this->x = x; this->y = y; } }; struct Road{ int st; int et; double val; Road(int st, int et, double val){ this->st = st; this->et =et; this->val =val; } bool operator<(const Road &ref)const{ //kruskal MST는 간선을 정렬함 return val < ref.val; } }; int Find(int v){ if(v==unf[v]) return v; else return unf[v] = Find(unf[v]); } void Union(int a, int b){ a = Find(a); b = Find(b); if(a!=b) unf[a] = b; } double DistanceCalculator(Hotel st, Hotel et){ double res = ((et.x - st.x) * (et.x - st.x) + (et.y - st.y) * (et.y - st.y)); return sqrt(res); } int main(int argc, const char * argv[]) { //ios_base::sync_with_stdio(false); int N,M; cin >> N >> M; vector<Hotel> node; vector<Road> edge; int x,y; for(int i = 1; i <= N; i++) unf[i] = i; for(int i = 0; i < N; i++){ cin >> x >> y; node.push_back(Hotel(x,y)); } for(int i=0; i<=N; i++){ for(int j=i+1; j<=N; j++){ if(i != j){ edge.push_back(Road(node[i].number, node[j].number, DistanceCalculator(node[node[i].number-1],node[node[j].number-1]))); } } } int st,et; for(int i = 0; i < M; i++){ cin >> st >> et; Union(st, et); //연결함. 이미 연결했기 때문에 나중에 고려 안함. } sort(edge.begin(), edge.end()); double res = 0; for (int i = 0; i < edge.size(); i++) { int fa = Find(edge[i].st);//해당 노드의 집합 번호 int fb = Find(edge[i].et); if(fa != fb){ // 같지 않으면 Cycle이 돌지 않으므로 res += edge[i].val; // 최소비용에 누적 Union(edge[i].st,edge[i].et); //집합 연결시켜주기 } } printf("%0.2f",res); return 0; }
- 미해결코딩테스트 실전 모의고사(with C++) : 대기업 대비
이렇게 풀면 반례가 어떻게되나요?
#include <bits/stdc++.h> using namespace std; int LCSubstr(string x, string y){ int n = x.size(), m=y.size(); vector<vector<int>> dy(n+1,vector<int>(m+1,0)); for(int i=1; i<=n; i++){ for(int j=1; j<=m; j++){ if(x[i-1] == y[j-1]) dy[i][j] = dy[i-1][j-1] + 1; else dy[i][j] = max(dy[i-1][j], dy[i][j-1]); } } return dy[n][m]; } int main(int argc, const char * argv[]) { ios_base::sync_with_stdio(false); int n1,n2,n3; string A,B; cin >> n1 >> n2 >> n3; cin >> A >> B; int LCSLength = LCSubstr(A, B); int SpaceLength = abs(int(A.size() - B.size())); int strLength = max(A.size(),B.size()); int N1Score = LCSLength * n1; //최대공통부분 문자열 길이 * 점수 int N2Score = SpaceLength * n2;//공백갯수 * 점수 int N3Score = (strLength - LCSLength - SpaceLength) * n3;//(전체길이 - 공백갯수 - 최대공통부분 문자열 길이) * 점수 cout << N1Score + N2Score + N3Score; return 0; }
- 미해결코딩테스트 실전 모의고사(with C++) : 대기업 대비
1회 1번 공통 문자열 문제 설명 보충하시면 더 좋을 것 같습니다!
1회 1번 공통 문자열 문제에서 N개의 모든 문자열에서 같은 부분 문자열을 가지고 있다는 설명이 없어서 아래와 같이 unordered_map으로 어렵게 풀이하였습니다. 출제 의도에 맞게 N개의 모든 문자열에서 같은 부분 문자열이 있다고 적혀있으면 더 좋을 것 같아요! #include <iostream> #include <string> #include <unordered_map> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); freopen("input.txt", "rt", stdin); unordered_map<string, int> uM; string str, answer; int t, max = 0; cin >> t; while (t--) { cin >> str; string temp; for (int i = 0; i < str.size(); i++) { temp += str[i]; uM[temp]++; } } for (auto iter = uM.begin(); iter != uM.end(); iter++) { if (max < iter->second) max = iter->second; } for (auto iter = uM.begin(); iter != uM.end(); iter++) { if (iter->second == max && (answer.size() < (iter->first).size())) answer = iter->first; } cout << answer; return 0; }
- 미해결코딩테스트 실전 모의고사(with C++) : 대기업 대비
이 문제를 굳이 분류하자면...
안녕하세요, 선생님. 이 문제를 다이나믹 기초 문제로 볼수 있을까요? 한번 구해놓은 오른쪽 방향 자료를 바탕으로 왼쪽 방향 자료를 업데이트 해나가니까요. 그런데 자료가 한번씩 밖에 쓰이지 않기에 다이나믹이라고 하기도 좀 그렇고, 굳이 분류를 하자면 이 문제는 어디에 속할까요?
- 미해결코딩테스트 실전 모의고사(with C++) : 대기업 대비
a.find 함수 대신 string a를 for 루프로 탐색해도 시간복잡도가 괜찮을까요?
안녕하세요, 선생님! 오늘도 강의를 잘 듣고 있습니다. 다름이 아니오라 이 문제를 a.find 함수 대신 string a를 for루프로 캐릭터 탐색해서 문제를 풀었는데요. 시간복잡도에 큰 차이는 없을까요? 면접시 find 함수가 생각이 안나면 이렇게라도 풀어 제출해야 될것 같아서요. 아니면 find함수가 생각이 안날때 대체할수 있는 다른 좋은 방법이 있을까요? 감사합니다!
- 미해결코딩테스트 실전 모의고사(with C++) : 대기업 대비
해당 문제를 다익스트라로 풀었습니다.
안녕하세요. 너무나 잘듣고 있습니다. 해당문제를 다익스트라 알고리즘을 활용해서 풀었습니다. 다익스트라의 for-loop안에서 이런 조건을 넣었습니다. if (갱신할값 (dist[next])< min(지금까지의 최솟값, 현재 간선의 값)) { dist[next] = min(지금까지의 최솟값, 현재 간선의 값) ..... } 우선순위 큐는 맥스힙으로 현재까지의 최솟값의 최댓값을 항상 맨위로 보냈습니다. 혹시 다익스트라를 사용하면 안되는 이유가 있나요? (코드가 조금 더 간편해보여서 질문드립니다. 그 전 강의에서 다익스트라를 강의 해주셔서 알고 사용했습니다. )통과를 받기는 했습니다. 감사합니다.
- 미해결코딩테스트 실전 모의고사(with C++) : 대기업 대비
해당 문제가 일방통행인지 양방향 통행인지 나와있지 않습니다.
안녕하십니까. 해당문제의 조건에 양방통행 도로라는 조건을 추가해주시면 좋겠습니다. 감사합니다.
- 미해결코딩테스트 실전 모의고사(with C++) : 대기업 대비
문제 조건 관련해서 건의 사항이 있습니다.
안녕하세요. 송아지가 웅덩이에 있는것이 테스트케이스에 있는거 같습니다. 해당내용을 문제의 조건에 추가해주십시오. 감사합니다.
- 해결됨코딩테스트 실전 모의고사(with C++) : 대기업 대비
질문드립니다.
자바로 코딩테스트를 준비하고 있는데 문제 알고리즘만 강의를 통해 학습하고 문제는 사이트에서 자바로 풀어도 진행하는데 무리가 없는지 궁금합니다.
- 미해결코딩테스트 실전 모의고사(with C++) : 대기업 대비
강의 난이도가 어느정도 되나요? 강의 문제와 비슷한 수준의 문제들을 대부분 풀 수 있으면 대다수의 it 대기업 코딩테스트 통과할 정도인가요?
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
- 해결됨코딩테스트 실전 모의고사(with C++) : 대기업 대비
선생님, 질문이 있습니다.
별 내용은 아닌데 사실 선생님 아이디어와 동일하게 코드 구성을 하였는데요 DFS재귀 매개변수에 string a를 넣는데 다음 트리로 넘어갈 때 저는 DFS(s+1,e,a+='(') DFS(s,e+1,a+=')') 이렇게 += 연산자를 활용해보았는데요 당연히 구상할 때 부터 문자열을 더해나가야만 종착점에 도달하였을 때 매개변수로 넘어온 a를 출력한다고 생각했는데 그게 아니라 a+'(' a+')'인 이유가 무엇인지 궁금합니다ㅜㅜㅜ 그리고 string 자료형에서 push_back이 파이썬에서의 append와 개념상 동일한 기능을 한다고 봐도 되나요? 감사합니다.
- 미해결코딩테스트 실전 모의고사(with C++) : 대기업 대비
선생님 질문이있습니다.
테스트 케이스 전부 돌아가는데.. 제 코드를 돌려보면 런타임 에러가 나옵니다. 제 코드 한번만 봐주실ㅇ 수 있을까요? #include<iostream> #include<vector> #include<stdio.h> #include<algorithm> using namespace std; int N; int arr[101]; int ans[101]; int main() { cin >> N; for (int i = 1; i <= N; i++) { cin >> arr[i]; } for (int i = 1; i <= N; i++) { int cur = i; if (arr[cur] == 1) { ans[cur] = -1; } if (cur >= 1 && cur <= N&&arr[cur]==1) { int left = cur - 1; int right = cur + 1; ans[left] = 1; ans[right] = 1; } } for (int i = 1; i <= N; i++) { int cur; int answer = 0; if (i == 1&&ans[i]==0) { cur = i; while (ans[cur] != -1) { answer++; cur++; } ans[i] = answer; } if (i == N&&ans[i]==0) { cur = i; while (ans[cur] != -1) { answer++; cur--; } ans[i] = answer; } if(i>1&&i<N&&ans[i]==0){ cur = i; int tmp = cur; int left = 0; int right = 0; while (ans[cur] != -1) { left++; cur--; } while (ans[tmp] != -1) { right++; tmp++; } answer = min(left, right); ans[i] = answer; } } int maxi = -2; for (int i = 1; i <= N; i++) { if (maxi < ans[i]) { maxi = ans[i]; } } printf("%d", maxi); }
- 미해결코딩테스트 실전 모의고사(with C++) : 대기업 대비
exe로 확인할 수 있는 자료는 어디에 있나요?
실행파일(exe)로 정답 여부를 체크할 수 있는 자료가 있는 것으로 알고 있습니다. 어디에 링크가 되어 있는지 모르겠습니다. 강의자료에는 없는 것 같아서요.
- 미해결코딩테스트 실전 모의고사(with C++) : 대기업 대비
코드 체크 부탁 드리겠습니다.
바둑 문제인데요, 주어진 테스트 케이스는 통괗하는데, 오답이 나옵니다. 리뷰 가능하실까요? 아니면 테스트 케이스 공유가 가능할까요? #include <bits/stdc++.h> using namespace std; class Go { public: int white, black; Go(int white, int black) { this->white = white; this->black = black; } }; int N, R, minv=INT_MAX; int whitesum, blacksum; int choice[6]; vector<Go> player; void dfs(int l, int s) { if (l >= R) { int white = 0, black = 0; for (int i=0; i<R; i++) { white += player[choice[i]].white; black += player[choice[i]].black; } black = blacksum - black; minv = min(minv, abs(white - black)); return; } for (int i=s; i<N; i++) { choice[l] = i; dfs(l+1, i+1); } } int main(void) { freopen("input.txt", "rt", stdin); cin >> N; R = N/2; for (int i=0; i<N; i++) { int white, black; cin >> white >> black; whitesum += white; blacksum += black; player.push_back(Go(white, black)); } dfs(0, 0); cout << minv; return 0; }
- 미해결코딩테스트 실전 모의고사(with C++) : 대기업 대비
선생님, 질문이 있습니다.
선생님 강의 잘 듣고 있습니다! 선생님 3차원 배열을 통해 공주 -> 산딸기 <- 기사 산딸기를 기점으로 최소거리를 합하는 방식으로 접근하셨군요 저는 그런데 다르게 풀어봤는데 어떤 점이 부족한지 잘 모르겠습니다. 예제는 통과하는데 일단 답은 틀립니다!! 주석을 달아두었으니 보시는데 불편하지 않을 거라 생각합니다.. <저의 방식> 저는 일단 BFS를 2번 돌렸습니다. BFS1 BFS2 BFS1 : 공주의 위치에서 산딸기의 위치 정보를 모두 저장하기 위한 BFS BFS2 : 산딸기의 위치에서 기사의 위치에 도달하기 위한 BFS 공주의 위치에서 산딸기의 위치에 도달하였을 때의 정보(x,y좌표, 이동 횟수)를 모두 배열에 저장합니다. (기사를 지나치는 것에 제한을 두지 않고) 한번 BFS를 돌면 큐가 모두 비어있게 되니까 배열에 저장되었던 모든 산딸기의 위치를 큐에 일괄적으로 넣고 다시 한 번 BFS를 돌려서 기사를 최초로 만나는 시점에 바로 bfs를 종료하도록 만들었습니다!! #include<iostream> #include<stdio.h> #include<vector> #include<queue> #define MAX 1001 using namespace std; typedef struct node { int x; int y; int cnt = 0; }Node; int map[MAX][MAX]; bool visited[MAX][MAX]; int dx[4] = { 1,-1,0,0 }; int dy[4] = { 0,0,1,-1 }; queue<Node> Q; int strcnt = 0; //vector<Node>strb[MAX]; Node strb[MAX]; int W, H; Node start; void BFS1() { Node current; while (!Q.empty()) { current.x = Q.front().x; current.y = Q.front().y; current.cnt = Q.front().cnt; Q.pop(); // printf("current // x : %d y : %d cnt : %d\n\n", current.x, current.y, current.cnt); if (map[current.x][current.y] == 4) { //printf("4 found!! // x :%d y : %d cnt : %d\n\n", current.x, current.y, current.cnt); strb[strcnt++] = current; } for (int i = 0; i < 4; i++) { int x = current.x + dx[i]; int y = current.y + dy[i]; if (x<1 || y<1 || x>H || y>W) { continue; } if (visited[x][y]) { continue; } if (map[x][y] == 1) { continue; } if ((!visited[x][y] && map[x][y] == 0) || (!visited[x][y] && map[x][y] == 3)||(!visited[x][y]&&map[x][y]==4)) { visited[x][y] = true; Node next; next.x = x; next.y = y; int nextcnt = current.cnt + 1; next.cnt = nextcnt; //printf("next // x : %d y : %d cnt : %d\n\n", next.x, next.y, next.cnt); Q.push(next); } } } } int mini = 100000; void BFS2() { Node current; while (!Q.empty()) { current.x = Q.front().x; current.y = Q.front().y; current.cnt = Q.front().cnt; Q.pop(); //printf("current // x : %d y : %d cnt : %d\n\n", current.x, current.y, current.cnt); if (map[current.x][current.y] == 3) { if (mini > current.cnt) { mini = current.cnt; } } for (int i = 0; i < 4; i++) { int x = current.x + dx[i]; int y = current.y + dy[i]; if (x<1 || y<1 || x>H || y>W) { continue; } if (visited[x][y]) { continue; } if (map[x][y] == 1) { continue; } if ((!visited[x][y] && map[x][y] == 0)||(!visited[x][y]&&map[x][y]==3)) { visited[x][y] = true; Node next; next.x = x; next.y = y; int nextcnt = current.cnt + 1; next.cnt = nextcnt; //printf("next // x : %d y : %d cnt : %d\n\n", next.x, next.y, next.cnt); Q.push(next); } } } } int main() { cin >> W >> H; for (int i = 1; i <= H; i++) { for (int j = 1; j <= W; j++) { int input; cin >> input; map[i][j]=input; if (input == 2) { start.x = i; start.y = j; start.cnt = 0; } } } Q.push(start); //printf("start // x : %d y : %d cnt : %d \n\n", start.x, start.y, start.cnt); visited[start.x][start.y] = true; BFS1(); for (int i = 1; i <= H; i++) { for (int j = 1; j <= W; j++) { visited[i][j] = false; } } for (int i = 0; i < strcnt; i++) { Q.push(strb[i]); visited[strb[i].x][strb[i].y] = true; } //printf("<<<<BFS2 start>>>>\n\n"); BFS2(); printf("%d", mini); }