월 15,400원
5개월 할부 시다른 수강생들이 자주 물어보는 질문이 궁금하신가요?
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
시간 초과가 나고 있습니다 선생님 어느 부분에서 효율화가 필요할까요??
선생님, 안녕하세요? 늘 좋은 강의 감사드립니다. 본 문제 코드를 bfs로 풀었는데, 4 5 예제에서 오류가 발생하고 있습니다. 제 코드 상에서 어느 부분이 효율이 떨어지고 있는지 궁금합니다. 한번 제 코드를 봐주시면 대단히 감사하겠습니다. 늘 좋은 영상 감사드립니다. #include<stdio.h> #include<stdlib.h> #include<iostream> #include<queue> #include<algorithm> #include<vector> using namespace std; int TomatoBox[1000][1000]; int visited[1000][1000]; int n, m; queue<pair < pair<int, int>, int> >Q; int dx[4] = { -1,1,0,0 }; int dy[4] = { 0,0,-1,1 }; void BFS(pair< pair<int, int>, int> vertex) { pair< pair<int, int>, int> temp; while (!Q.empty()) { temp.first.first = Q.front().first.first; temp.first.second = Q.front().first.second; temp.second = Q.front().second; //temp.second++; Q.pop(); for (int i = 0; i < 4; i++) { int x = temp.first.first + dx[i]; int y = temp.first.second + dy[i]; int v = temp.second; if (x < 0 || y < 0 || x >= n || y >= m) { continue; } if (TomatoBox[x][y] == 1 || TomatoBox[x][y] == -1) { continue; } //토마토가 익지 않았고 아직 방문을 하지 않았다면 if (visited[x][y] == 0 && TomatoBox[x][y] == 0) { v++; pair< pair<int, int>, int>next; visited[x][y] = 1; TomatoBox[x][y] = 1; next.first.first = x; next.first.second = y; next.second = v; Q.push(next); } else { return; } } } int flag = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (TomatoBox[i][j] == 0) { flag = 1; break; } else { continue; } } } if (flag == 0) { printf("%d ", temp.second); } else { printf("-1"); } } int main() { ios_base::sync_with_stdio(false); /*scanf("%d %d", &m, &n);*/ cin >> m >> n; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { //scanf("%d", &TomatoBox[i][j]); cin >> TomatoBox[i][j]; } } //시작점의 갯수를 파악합니다. int startcount = 0; //pair <pair<int, int>, int> start; vector< pair <pair<int, int>, int> > startpoint(1000); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (TomatoBox[i][j] == 1) { startcount++; //printf("현재 시작점의 개수 : %d \n", startcount); startpoint[startcount].first.first = i; //printf("해당 시작점의 x좌표 : %d \n", startpoint[startcount].first.first); startpoint[startcount].first.second = j; //printf("해당 시작점의 y좌표 : %d \n", startpoint[startcount].first.second); startpoint[startcount].second = 0; //printf("해당 시작점에서의 움직임 계수 : %d \n", startpoint[startcount].second); visited[startpoint[startcount].first.first][startpoint[startcount].first.second] = 1; startpoint[startcount]; Q.push(startpoint[startcount]); Q.push(startpoint[startcount]); } } } BFS(startpoint[1]); return 0; }
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
선생님 질문 있습니다
좋은 강의 너무 잘 듣고 있습니다. 질문이 있는데요 저는 O(n)에서 n이 대략 1억일때 1초 이렇게 생각하고 문제푸는데 이게 맞나요 ? 인터넷에서 얻은 내용이라 확인차 여쭤봅니다 ! 그리고 보통 제한시간 1초가 걸려있는 문제들은 대부분 주어진 n의 범위가 이중for문을 사용할시에 1초를 초과하도록 주어지는 것 같아요. 그래서 이중for문 말고 단일for문을 사용해 문제를 해결하도록 하는 것 같았습니다. 이 문제에서는 n이 200,000 이라고 가정할 때, 𝑛n 이 계산하면이 1억보다 작기 때문에 제한시간 내에 해결되는 것이 맞을까요? 5
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
vector<int>와 new int 차이가 궁금합니다.
vector로 배열을 선언한것과 new로 배열을 선언한 것이 어떤 차이점이 있는지 궁금합니다. vector는 추가로 계속해서 늘려줄 수 있지만, new로 동적할당을 한번 받아버리면 그 뒤로 늘려줄순 없다는 제 생각이 맞나요? 추가로 vector와 new를 같이 사용할 수 있나요? 감사합니다.
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
입력 값 질문 있습니다!
scanf로 받아올 때 "%[^\n]s"로 받아오면 안되는걸까요?
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
제가 짠 코드의 문제점이 뭘까요?
int n, cnt, i, tmp; scanf("%d", &n); for(i=2; i<=n; i++){ if(i==2||i==3||i==5) cnt++; tmp=i; if(tmp%2==0||tmp%3==0||tmp%5==0) continue; cnt++; } printf("%d", cnt); return 0; n에 200,000을 입력했을 때 다른 값이 나와서 어떤 문제점 때문인지 알고 싶습니다. 그리고 이런 방식의 코드는 비효율적일까요?
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
시간복잡도 문의
시간복잡도가... 풀이와 같이 하면 j = 1일때 n번 j = 2일때 n/2번 j = 3일때 n/3번 … j = n일때 n/n번 즉 total n * (1 + 1/2+1/3+…+1/n) 를 계산한 것이 시간복잡도가 되는것 맞나요 ? 아직 미흡해서 질문 남깁니다
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
std? vector?
선생님 이런 질문 드려서 정말 죄송합니다. 그렇지만 컴맹인 제가 기본 c언어 문법부터 선생님 강의만 믿고 따라왔습니다. 그런데 그쪽에서도 여기서도 설명해주시지 않았던 , 나오지 않던 cin?cout? std::vector 이나 #include <vector> 이런것들이 나오니 너무 당황스럽습니다. 죄송하지만 어떻게 하면 따라갈수 있을까요 ,,? 어떤 강의를 듣고 오라면 듣고 오겠습니다 ㅜㅜㅜ 따라가고 싶은데 모르는 내용에 너무 답답해서 질문 남겨봅니다 ㅜㅜ
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
선생님 질문이 있습니다ㅜㅜ
저는 코드를 다음과같이 작성을 해보았는데요, 40점이 뜨고, 문제점이 뭔지도 알고 있습니다. 일단 저는 강의를 듣기 전에 코드를 작성해보는 편입니다.제 코드는 무조건 반드시 1일차의 상담을 선택하는 상황으로 가지가 계속 뻗어나가게만 이루어져 있습니다. 그래서 1일차의 상담을 선택했을때 분기가 모두 끝나는 것도 디버깅으로 확인을 했는데 그 이후 몇시간을 고민했는데도 풀리지 않네요. N의 범위를 넘어가지 않으면서2일차 강의, 3일차 강의를 선택하는 모든 경우의 수 까지도 고려하고 싶은데 거기서 손을 쓸 수가 없습니다. 이 문제를 해결하려면 제 코드에 어디를 손봐야할까요?ㅜㅜ #include<stdio.h> #include<iostream> #include<stdlib.h> using namespace std; int* T; int* P; int N; int Tindex = 0; int Total = 0; int totalarray[100]; int cnt = 0; void DFS(int Tindex, int Total) { if (Tindex + T[Tindex] > N) { totalarray[cnt++] = Total; return; } else { DFS(Tindex + T[Tindex], Total + P[Tindex + T[Tindex]]); } } int main() { scanf("%d", &N); T = (int*)malloc(sizeof(int) * (N + 1)); P = (int*)malloc(sizeof(int) * (N + 1)); for (int i = 1; i < N+1; i++) { scanf("%d %d", &T[i], &P[i]); } T[0] = 1; P[0] = 0; DFS(0, 0); //DFS(1, 0); int max = 0; for (int i = 0; i < 100; i++) { if (max < totalarray[i]) { max = totalarray[i]; } } printf("%d", max); }
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
13번, 다른 방식으로 도전하였는데 다 틀렸다고 나와서 어디가 문제인지 알고싶습니다.
안녕하세요 선생님. 강의 재밌게 듣고 있습니다. 13번을 완전히 다른 방식으로 푼 거 같아서 이 방식으로도 풀고 싶어서 올립니다. 답은 잘 나오는 거 같은데 채점기에 돌리니 다 틀렸다고해서 어디서 틀린건지 모르겠습니다. 감사합니다. #include <iostream> using namespace std; int count[10]; int main(int argc, char** argv) { //freopen("input.txt","rt",stdin); int max = 0, n; scanf("%d", &n); while(n > 0){ count[n%10]++; n/=10; } for(int i = 1; i < 10; i++){ if(count[max] <= count[i]) max = i; } printf("%d\n", max); return 0; }
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
선생님, 제 코드에 질문이 있습니다.
#include<stdio.h> #include<iostream> #include<vector> #include<queue> using namespace std; queue<int> map; vector<int> Q[10001]; int check[10001]; int PathCost[10001]; int count = 0; int movement[3] = { 1,-1,5 }; int main() { int S, E; scanf("%d %d", &S, &E); check[S] = 1; //중복 계산을 피하기 위해. 방문 표시를 해준다. PathCost[S] = 0; map.push(S); while (!map.empty()) { int current = map.front(); //현재 5이다. //current와 연결되어 있는 것들을 모두 찾아준다. map.pop(); for (int i = 0; i < 3; i++) { int result = current + movement[i]; map.push(result); if (result == E) { printf("%d ", PathCost[result]); } if (check[result] == 0) { check[result]=1; PathCost[result] = PathCost[current] + check[result]; map.push(result); } else { continue; } } } }
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
79번, prim 알고리즘 문제 내에서 질문드립니다.
안녕하세요. 강의 잘듣고 있고 있습니다 ^^ 강의에선 main() 함수 내에서 push(),pop() 을 수행하는걸로 소스를 구현하셨는데요, 이를 별도의 함수로 만들어서 구현할 때, main에서 생성한 인접 리스트를 함수의 매개변수로 전달하는 부분에 대해서 궁금합니다. 예를 들면, int makeRoute(vector<pair<int,int> > &map[]){ ...} int main(){ vector<pair <int ,int> > map[30]; cout<<makeRoute(map); } 윗처럼 전달하면 에러가나는데, 이유를 잘 모르겠습니다. (일반 배열처럼 배열의 이름으로 넘기면 될줄 알았는데...) 항상 Java로 개발하다가 오랫만에 C++하려니까 헷갈리는 부분이 많네요. 어리석은 질문일수있지만, 도움부탁드리겠습니다~
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
선생님, 질문이 있습니다.
선생님, 안녕하세요? 일단 코드 작성했고 예제는 잘 결과가 나오는데 제가 한 방식에 확신이 없어서 질문을 드립니다. 저는 작성될 각 노드에 대한 최소비용경로를 구할 때 체크방문배열(1로 된 것)과 현재 큐에 들어온 노드까지의 경로값을 누적하는 방법으로 최단경로를 구했습니다. 해당 부분에 주석을 달아두었는데 이 방법이 다른 예제들에 대해서도 맞는지 수업을 듣기 전에 미리 먼저 물어보고 싶습니다. #include<iostream> #include<algorithm> #include<vector> #include<stdio.h> using namespace std; int Q[101]; int front = 0, back = 0; int ch[101]; int N, M; vector <int> Queue[101]; int PathCost[101]; int target = 2; int main() { scanf("%d %d", &N, &M); int SNode, TNode; for (int i = 0; i < M; i++) { scanf("%d %d", &SNode, &TNode); Queue[SNode].push_back(TNode); } /*for (int i = 0; i < N+1; i++) { for (int j = 0; j < Queue[i].size(); j++) { printf("%d ", Queue[i][j]); } printf("\n"); }*/ //최초 시작점을 설정 ch[1] = 1; Q[++back] = 1; int current; while (front < back) { current = Q[++front]; //현재 1 for (int i = 0; i < Queue[current].size(); i++) { //먼저 한 번만에 갈 수 있는 정점 판단 if (ch[Queue[current][i]] == 0) { //아직방문하지 않았다면 Q[++back] = Queue[current][i]; //뒤에 추가를 한다. ch[Queue[current][i]]=1; //그리고 방문처리를 해준다. //이게 맞는건지 궁금합니다. PathCost[Queue[current][i]] = PathCost[current] + ch[Queue[current][i]]; } } } for (int i = 2; i < N + 1; i++) { printf("%d : %d \n", i, PathCost[i]); } }
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
67번 출력 설명이 잘못되어 있습니다.
최소 비용 대신 총 가지수를 출력하라고 되어 있습니다.
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
채점할때 마지막 케이스에서 자꾸 4가 출력이 되어서 오답처리가 됩니다
확인해보니 31번째 인덱스일때 카운트가 하나 올라가는데 어떤 부분에서 잘못된건지 파악을 잘 못하겠습니다ㅠㅠㅠ // 19. 분노 유발자 #include <iostream> using namespace std; int main() { int n, arr[100] = { 0, }, cnt = 0, flag; cin >> n; for (int i = 0; i < n; i++) cin >> arr[i]; for (int i = 0; i < n - 1; i++) { flag = 0; for (int j = i + 1; j < n; j++) { if (arr[i] < arr[j]) { flag = 1; break; } } if (!flag)cnt++; } cout << cnt; }
- 해결됨it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
재귀와 반복문의 차이
삭제된 글입니다
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
67번
안녕하세요 선생님 선생님 코드에서 int i; 를 DFS 함수와 main 함수 각각 따로 선언하지 않고 전역변수로 잡았더니 답이 13이 아니라 22가 나왔습니다. 저는 어차피 둘 다 i가 나와서 한번에 전역변수로 잡자고 생각했는데 안되네요. 왜 안되는지 설명부탁드립니다. #include<stdio.h> #include<vector> #include<algorithm> using namespace std; int map[30][30], ch[30], n, cost=2147000000; int i; void DFS(int v, int sum){ if(v==n){ if(sum<cost) cost=sum; } else{ for(i=1; i<=n; i++){ if(map[v][i]>0 && ch[i]==0){ ch[i]=1; DFS(i, sum+map[v][i]); ch[i]=0; } } } } int main(){ //freopen("input.txt", "rt", stdin); int m, a, b, c; scanf("%d %d", &n, &m); for(i=1; i<=m; i++){ scanf("%d %d %d", &a, &b, &c); map[a][b]=c; } ch[1]=1; DFS(1, 0); printf("%d\n", cost); return 0; }
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
4번만 통과가 안되는데, 많이 고민해봤으나 잘모르겠네요..!
#include <stdio.h> int main() { //f9는 컴파일, f10은 실행. //채점받을때는 freopen주석처리하고 하기. //freopen("input.txt", "rt", stdin); char first_str[105], sec_str[105]; int len_first_str=0, len_sec_str=0; int flag_res=1; scanf("%s", &first_str); //printf("%s\n", first_str); scanf("%s", &sec_str); //각 길이 구하기 for(int i=0; first_str[i] != '\0'; i++) { len_first_str++; } for(int i=0; sec_str[i] != '\0'; i++) { len_sec_str++; } //printf("len_first_str : %d\n", len_first_str); //길이가 다르면 NO if(len_first_str != len_sec_str) { printf("NO"); return 0; } else { //길이가 같으면 비교해보기, 각 char이 같다면, first_str의 각자리를 0으로 치환 for(int i=0; i<len_first_str; i++) { for(int j=0; j<len_first_str; j++) { if(first_str[i] == sec_str[j]) { first_str[i] = 0; break; } } //printf("first_str is : %s\n", first_str); } // 모두 0이라면 YES, 아니면 NO for(int i=0; i<len_first_str; i++) { if(first_str[i] != 0) { flag_res = 0; break; } } if(flag_res == 1) { printf("YES"); } else if(flag_res == 0) { printf("NO"); } } return 0; }
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
37번 LRU
37번 LRU#include <iostream>#include <string>#include <vector>#include <cstdlib> using namespace std;int main(int argc, char** argv) { int s,n, wNum, hit = -1, tmp, usedSize = 0; cin >> s >> n; vector<int> v(s); cout << "s : " <<s << " " << "n : " << n << "\n"; for(int t = 0; t < n; t++) { cin >> wNum; for(int i = 0; i < v.size(); i++) { if(v[i] == wNum) { hit = i; break; } } //hit일때 if(hit != -1) { tmp = v[hit]; for(int i = hit - 1; i>=0; i--) { v[i+1] = v[i]; } } else { for(int i = s-1; i>=0; i--) { v[i+1] = v[i]; } } v[0] = wNum; hit = -1; } for(int i = 0; i < s; i++) cout << v[i] << " ";}제가 이 문제를 이렇게 풀었는데 이상하게 s값 (캐시 메모리의 크기) 가 10이 넘어가면 안되네요..ㅠㅠ 10보다 작으면 정상적으로 되는데.. 그래서 체점 해보면 1번2번은 맞는데 뒤에꺼는 틀리다고 하네요. 혹시 어떤게 문제인지 아시나요??..아무리 찾아도 못찾겠어요..ㅠㅠ
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
안녕하세요~ 동적계획법 4번 LIS 문제 질문 있습니다.
안녕하세요. 정말 감사하게 강의 잘 듣고 있습니다. 어려운 알고리즘도 너무 쉽게 설명을 잘 해주셔서 감사합니다. 추가로 계획된 알고리즘 강의도 기대됩니다. 개설하시면 바로 신청할 예정입니다. 저지사이트에 LIS 문제를 선생님이 알려주신 코드를 적용하여 잘 해결했는데요.. n<=100,000 인경우에는 O(n^2)알고리즘으로는 해결할 수 없다고 문제에 나와 있어서...시간초과가 납니다. 어떤 알고리즘을 적용하면 좋을지 조언을 구합니다. 감사합니다.~
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
선생님, 55번 기차운행 코드리뷰를 부탁드려도 될까요??
주석을 알맞게 잘 달아두어서 흐름을 보시기에는 편할 것 같습니다. 잘못된 부분이 있거나 개선해야 할 점이 있다면 조언을 해주시면 감사하겠습니다. #include<iostream> #include<stdio.h> #include<stdlib.h> #include<stack> #include<algorithm> using namespace std; int main() { int N; scanf("%d", &N); char PO[51]; int POindex = 0; int* train = (int*)malloc(sizeof(int) * N); //기차 순서 입력받습니다. for (int i = 0; i < N; i++) { scanf("%d", &train[i]); } int Intersection[51]; int top = -1; int RightSequence[51]; //index는 강의 영상에서 나온 j를 말합니다. int index = 0; //순서대로 숫자가 들어간 배열을 만듭니다. for (int i = 0; i < 51; i++) { RightSequence[i] = i; } for (int i = 0; i < N; i++) { //만일 교차로가 비었다면 if (top == -1) { Intersection[++top] = train[i]; //train에 하나 넣습니다. PO[POindex] = 'P'; //P를 기록합니다. POindex++; //그리고 다음을 계속하여 기록할 수 있도록 인덱스를 증가합니다. } //만일 교차로 안에 무언가 있다면 //정렬된 배열과 교차로 맨 위의 원소를 서로 하나씩 비교를 시작합니다. else if (Intersection[top] == RightSequence[index]) { PO[POindex] = 'O'; POindex++; //'O'를 기록한 후 PO인덱스를 증가시킵니다. Intersection[top--] = 0; //해당 top은 일치함을 확인하였으니 제거합니다. index++; // 다음 원소와의 비교를 위해 인덱스를 증가시킵니다. //그리고 교차로에 남아있는 것들을 나란히 비교합니다. for (top; top > -1; top--) { //일치한다면 빼내고 index를 증가합니다. if (Intersection[top] == RightSequence[index]) { PO[POindex] = 'O'; POindex++; Intersection[top--] = 0; index++; } //top과 일치하지 않는다면 top아래의 것들과 비교할 수 없으므로 //for문을 빠져나온다. else { break; } } } //교차로가 비어있지도 않은데, 정렬된 것과 다른 경우면 이제 새로운 것을 추가할 수 있습니다. else { Intersection[top] = RightSequence[index]; top++; PO[POindex] = 'P'; POindex++; } } if (top != -1) { printf("Impossible \n"); } else { //이제 결과를 출력하면 됩니다. for (int i = 0; i < 51; i++) { if (PO[i] != 'P' && PO[i] != 'O') { break; } else { printf("%c ", PO[i]); } } } }