월 15,400원
5개월 할부 시다른 수강생들이 자주 물어보는 질문이 궁금하신가요?
- 해결됨it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
자료구조
자료구조에 대한 학습이 안되어진 상황입니다. 자료구조에 대한 개념을 다른 강의로 잡고 이 강의를 마저 수강하는게 더 효율적일까요?
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
2번째 방법에 관한 질문입니다.
제가 먼저 풀어봣을때 말씀해주신 첫번째 방법과 같은 결과가 나왓습니다. 4번째 부터 시간초과가 걸려서 몇번을 더 고민하다가 두번째 방법을 보고 이런 방법이 있구나 하며 감탄햇는데, 문득 드는 생각이 이렇게 답만 보면 실력이 늘지를 않고 제자리 걸음이 될까봐 하는 걱정이 앞서서 이렇게 질문 남깁니다. 코딩테스트, 알고리즘은 많은 문제를 보고 풀어보고 안되면 정답을 보고 다시 이해하면 자신의 실력으로 남는걸까요? 자신감이 떨어져서 질문 남깁니다 ㅠㅠ
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
변수에 대한 질문
언제나 좋은 수업 해주셔서 감사합니다. 문제에 대해 질문이 하나 있는데, 이 문제는 조건이 "넓이" 와 "무게" 둘 뿐이기 때문에 둘중 하나를 정렬 시켜 놓고 LIS방법을 사용하면 되지만, 변수가 3개 이상이라면 이 방법은 불가능 해 보이는데 혹시 어떤 알고리즘을 사용해야 하나요? 또는 이 LIS방법에 3개 이상의 조건을 만족시켜서 동적으로 계획하는 법이 있나요?
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
제가 작성한 코드 한번 봐주실 수 있나요?
먼저 풀어봤는데, 채점은 맞았습니다만 코드가 어떤지 여쭤보고 싶어서 올립니다 #include <stdio.h> #include <stack> #include <vector> using namespace std; int main() { int i, n, idx = 0, tmp = -1; stack<int> st; scanf("%d", &n); vector<char> res; vector<int> arr(n); for (i = 0; i < n; i++) { scanf("%d", &arr[i]); } i = 0; while (i < n) { if (st.empty()) { st.push(arr[i++]); res.push_back('P'); } else { if (arr[i] < st.top()) { st.push(arr[i++]); res.push_back('P'); } else if (st.top() > tmp) { tmp = st.top(); st.pop(); res.push_back('O'); } } } while (!st.empty()) { if (st.top() < tmp) { printf("impossible"); return 0; } tmp = st.top(); st.pop(); res.push_back('O'); } for (i = 0; i<res.size(); i++) printf("%c", res[i]); } tmp 변수는 직전에 pop한 숫자를 담기 위한 용도이고, pop하기 전에 이 tmp 값보다 큰지 확인하고자 했습니다. 괜히 뺑 돌아가서 문제를 푼 것 같은데 그래도 로직이 맞는지 궁금합니다. 감사합니다!
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
안녕하세요 선생님 DFS 풀때 ch배열의 존재에 대해서 질문 드립니다.
어떤 문제 유형은 체크배열을 쓰고, 어떤 유형은 체크배열은 안쓰는 예를들어서, 부분 집합의 개수 출력이나, 미로 찾기 같은 경우에는 경우를 체크 해 나가지만 특정수 만들기나 합이 같은 부분집합에서는 체크배열을 안쓰더라구요 어떤 유형일때 체크 배열을 쓰고, 어떨때 안쓰는지 알려주시면 감사하겠습니다.
- 해결됨it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
이런 유형의 문제
강의 너무 잘 듣고있습니다. 강의를 듣다가 43번 44번 같은 유형의 문제가 제 취약점인 것을 확인했습니다. 이런 유형의 문제를 더 풀어보고 싶은데 혹시 추천해 주실만한 문제가 있는지 궁금합니다.
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
왜 오답인지 이해가 잘 가지 않습니다.
#include <iostream> #include <algorithm> #include <vector> #include <stack> using namespace std; int map[30][30], ch[30], min_sum=2147000000, n; void DFS(int v, int sum) { if(v==n) { if(sum<min_sum) min_sum=sum; } else { for(int i=1; i<=n; i++) { if(map[v][i]!=0 && ch[i]==0) { ch[i]=1; //sum += map[v][i]; DFS(i, sum+map[v][i]); ch[i]=0; } } } } int main() { freopen("input.txt", "rt", stdin); int m; scanf("%d %d", &n, &m); for(int i=1; i<=m; i++) { int a, b, v; scanf("%d %d %d", &a, &b, &v); map[a][b]=v; } ch[1]=1; DFS(1, 0); printf("%d", min_sum); return 0; } 굵게 밑줄친 부분에 대한 질문입니다. sum+=map[v][i]를 쓰고, 이어서 DFS(i, sum); 으로 넘겨주게 되면 출력이 답이 아닌 값이 나옵니다. sum+=map[v][i]를 쓰고 sum을 넘겨줄때와 DFS(i, sum+map[v][i])로 바로 넘겨줄때의 차이점이 무엇일까요... ㅠㅠㅠ 잘모르겠습니다.
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
21번 카드게임 풀이 질문입니다.
강사님, 21번 카드게임에서, 총점이 같으면 D를 출력하는 것으로 문제에 설명이 되어 있습니다. 그런데, CPS(채점폴더)에 out1,3,4,5 파일은 점수가 모두 같은데 판정은 B로 표기되어 있습니다. 이 내용이 맞는 답안인지 문의 드립니다.
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
실전에서
안녕하세요 선생님 실전에서는 문제를 딱 보고 이게 어떤 자료구조를 쓰는지 알려면 많이 연습해야 되나요?? 그리고 54번 문제에서 큐를 쓰면 안되겟죠????
- 해결됨it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
시간복잡도
문제와는 별개로 궁금합니다. 시간복잡도에 대해 잘 몰라서 질문을 드립니다. a 배열과 b 배열 선택정렬 하는 시간복잡도와 2중 반복문으로 하나씩 비교하는 시간복잡도의 차이는 어느정도 인가요? a 배열 b배열 선택정렬하는 시간복잡도가 최악의 경우라고 가정했을 때요
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
" " 와 ' ' 차이점
안녕하세요 선생님강의 너무잘듣고있습니다 printf("a") 랑 printf('a') 는 둘다 되나요? 근데 널이나 공백을 표현할때는 " "가 안되고 ' ' 만 되나요?
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
절반은 맞고 절반은 틀립니다.
안녕하세요 강사님. 방금 전 연속 부분 증가수열을 풀었던 방식으로 졸리 점퍼 문제를 풀어봤습니다. 마찬가지로 i와 i+1의 관계에 집중해서 문제를 풀어봤고, 1부터 n-1의 합과 abs(a[i + 1] - a[i]);를 비교해보았습니다. 절반은 맞고 절반은 틀립니다.. 반드시 강사님처럼 pre와 now 변수를 이용해 풀어야 하는것인가요? https://gist.github.com/k3kys/9c33f6da1b4f473cb1df5725c1105170
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
채점은 틀렸는데, 예제를 돌리면 맞습니다.
안녕하세요 강사님. 채점기에서는 틀리는데 예제를 그대로 입력하면 맞는 답이 도출됩니다. 문제 아이디어는 a[i]와 a[i+1]을 비교해서 a[i+1]이 크면 계속 cnt++, 작은것이 나오면 cnt를 1로 초기화 하는 것으로 했습니다. https://gist.github.com/k3kys/811285794e89d6ffc6f11303e549e344 한 번 검토하여 주시면 감사하겠습니다.
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
질문이 있어요 선생님!
선생님, 안녕하세요? 저는 dfs를 통해서 조합을 각각 만들어내고, (x좌표,y좌표,움직인횟수) 그 조합을 대하여 큐에 넣어준 이후 dfs를 돌렸습니다. 큐에서는 fcfs로 어차피 1을 먼저 만나게 되는 정보로 방문처리해주면 그 #include<iostream> #include<queue> #include<math.h> #include<algorithm> using namespace std; int map[51][51]; bool visited[51][51]; int N, M; int dx[4] = { 1,-1,0,0 }; int dy[4] = { 0,0,1,-1 }; typedef struct node { int x; int y; int cnt = 0; }Node; queue<Node>Q; Node piz[2501]; int pcnt = 0; int pizza[2501]; int flag = 0; int mini = 10000; void BFS() { int cres = 0; 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] == 1) { cres += current.cnt; //printf("cres : %d \n\n", cres); } else { for (int i = 0; i < 4; i++) { int x = current.x + dx[i]; int y = current.y + dy[i]; int c = current.cnt + 1; if (x >= 1 && y >= 1 && x <= N && y <= N && !visited[x][y] && map[x][y] == 1) { visited[x][y] = true; Node next; next.x = x; next.y = y; next.cnt = c; //printf("next x : %d y :%d cnt : %d\n\n", next.x, next.y, next.cnt); Q.push(next); } if (x >= 1 && y >= 1 && x <= N && y <= N && !visited[x][y] && map[x][y] == 2) { visited[x][y] = true; Node next; next.x = x; next.y = y; next.cnt = c; //printf("next x : %d y :%d cnt : %d\n\n", next.x, next.y, next.cnt); Q.push(next); } if (x >= 1 && y >= 1 && x <= N && y <= N && !visited[x][y] && map[x][y] == 0) { visited[x][y] = true; Node next; next.x = x; next.y = y; next.cnt = c; //printf("next x : %d y :%d cnt : %d\n\n", next.x, next.y, next.cnt); Q.push(next); } } } } if (mini > cres) { mini = cres; } for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { visited[i][j] = false; } } } void DFS(int start, int level) { if (level == M) { //printf("<<<start>>>\n\n"); for (int i = 0; i < M; i++) { visited[piz[pizza[i]].x][piz[pizza[i]].y] = true; //printf("x : %d y : %d \n\n", piz[pizza[i]].x, piz[pizza[i]].y); Q.push(piz[pizza[i]]); } BFS(); } else { for (int i = start; i < pcnt; i++) { pizza[level] = i; DFS(i + 1, level + 1); } } } int main() { ios_base::sync_with_stdio(false); cin >> N >> M; for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { int input; cin >> input; map[i][j] = input; if (input == 2) { Node start; start.x = i; start.y = j; start.cnt = 0; piz[pcnt++] = start; } } } DFS(0, 0); printf("%d", mini); } 이후 중복의 여지도 없을 것이라 생각했구요, 아무튼 1을 만나게 되면 그 때의 이동값을 누적하는 방식으로 해결했씁니다. 아마 이거 백준에 비슷한 문제있었던 거같은데요 이 문제에서는 3번 케이스에서 유일하게 시간 초과가 나는군요ㅜㅜㅜㅜ 어떤 점이 문제일 지 궁금합니다 선생님.ㅜㅜ!
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
질문있습니다.
선생님, 안녕하세요 선생님께서는 dp배열갱신하실 때 주어진 높이와 너비에서부터 시작을 하셨는데 저와 같은 경우는 i=1 j=1 즉 1,1시작점에서부터 시작을 하되 i+h가 H를 넘어서지 않고 j+w가 W를 넘어서지 않는 조건, 그리고 i-1>=1 j-1>W인 조건 이 두 조건을 충족하는 범위 내에서만 dp를 갱신하도록 해줬는데요 이게 선생님 방식보다 어떤 면에서 비효율인지 궁금합니다. 심지어 case 2는 틀렸다고 나오네요ㅜㅜㅜㅜ문제가 뭘까요? #include<iostream> #include<stdio.h> #include<queue> #include<vector> using namespace std; int H, W; int map[701][701]; int dp[701][701]; int dp2[701][701]; bool visited[701][701]; int h, w; int main() { cin >> H >> W; for (int i = 1; i <= H; i++) { for (int j = 1; j <= W; j++) { cin >> map[i][j]; } } cin >> h >> w; dp[1][1] = map[1][1]; for (int i = 2; i <= H; i++) { dp[i][1] = dp[i - 1][1] + map[i][1]; } for (int i = 2; i <= W; i++) { dp[1][i] = dp[1][i - 1] + map[1][i]; } /*printf("\n"); for (int i = 1; i <= H; i++) { for (int j = 1; j <= W; j++) { printf("%d ", dp[i][j]); } printf("\n"); }*/ for (int i = 2; i <= H; i++) { for (int j = 2; j <= W; j++) { dp[i][j] = map[i][j] + (dp[i][j - 1] + dp[i - 1][j]) - dp[i - 1][j - 1]; } } //printf("\n"); //for (int i = 1; i <= H; i++) { // for (int j = 1; j <= W; j++) { // printf("%d ", dp[i][j]); // } // printf("\n"); //} //printf("\n"); ////이 부분이 질문입니다!!!!!/////// int ans = -1; for (int i = 1; i <= H; i++) { for (int j = 1; j <= W; j++) { if (i + h <= H && i + w <= W && i - 1 >= 1 && j - 1 >= 1) { dp2[i][j] = dp[i + h - 1][j + w - 1] + dp[i - 1][j - 1] - dp[i - 1][j + w - 1] - dp[i + h - 1][j - 1]; if (ans < dp2[i][j]) { ans = dp2[i][j]; } } else { continue; } } } printf("%d", ans); }
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
선생님, dp문제 풀때 말입니다
선생님, 강의 항상 잘 듣고 있습니다. 다이나믹 프로그래밍 문제를 요새 연습하고 있는데 이게 점화식을 적시에 발견해내느냐 그렇지 못하느냐에 따라 쉽게 해결하기도 하고 그렇지 못한 경우도 있네요ㅜㅜ 물론 그래프나 경로 탐색 혹은 메모이제이션을 위해서는 dp가 정말 효율성 면에서 얼마나 중요한지는 알겠습니다만 그 외 다른 dp문제들은 해결을 위한 본질적인 접근이 있을까요?? 질문이 좀 추상적인데 dp문제를 풀다보면 물론 제가 부족해서 놓치는 문제도 있겠습니다만 뭔가 이건 경험이나 실력과 다소 무관한 문제들도 분명히 있다고 여겨져서 여쭤봅니다.. 감사합니다!
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
안녕하세요 48번 질문
안녕하세요 48번 문제에서 중간에 평균 구할 때 for (i = 0; i < 9; i++) { sum = 0; for (j = 0; j < 9; j++) { scanf("%d", &a[i][j]); sum += a[i][j]; } printf("%d\n", ((sum / 9.0) + 0.5)); } ave 변수에 따로 넣지 않고 바로 이렇게 출력해봤는데, 왜 이상하게 출력되는 걸까요? avg = (sum / 9.0) + 0.5; printf("%d ", avg); 이렇게 하는 것과의 차이점이 뭔가요?
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
안녕하세요. 질문입니다.
안녕하세요, 강의 잘 수강하고 있습니다. 저가 이 강좌의 문제 외에는 다른 문제를 접해 본적이 없어서요, 혹시 해당 강의의 모든 문제를 다 풀줄 아는 정도라면, 어느정도 수준일까요..? 해당강의 문제들은, 취업시 접하게 되는 알고리즘 문제와 수준차이가 큰 편일까요?
- 미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
안녕하세요 질문입니다.
제가 재귀가 너무 약해서 그런데 혹시 재귀나 DFS 할때 디버깅은 어떻게 하시는 편인가요? 이런 문제들이나 사이즈카 큰 재귀 문제들은 일일이 하기엔 너무 방대하고 복잡하던데. 재귀에서 막혀서 고민입니다. 스택 옆에 그림을 그려놓고 일일이 그려가면서 해야할까요? 다른 문제들은 디버깅 하면서 하면 이해가 가던데 재귀만 쓰면 유난히 어려운거 같습니다.
- 해결됨it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
냅색 알고리즘의 의미와 메모이제이션 활용
안녕하세요. 냅색 알고리즘에 대해 질문있습니다. 이렇게 보석을 하나씩 늘려가면서 값을 계속 갱신하는 것이 냅색 알고리즘인가요? 추가로, 이번 문제를 보면 dy[]의 값을 바꾸어주는 경우가 많은데, 여기에서 메모이제이션을 활용할수는 없는지 궁금합니다. 감사합니다.