월 33,000원
5개월 할부 시다른 수강생들이 자주 물어보는 질문이 궁금하신가요?
- 해결됨10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
map을 2개 사용하는 방식이 좋은지 이 방식이 좋은지 궁금하여 질문드립니다!
소스 코드http://boj.kr/d754f100ea9f49e6b9f3bd0c8f1ec98a저는 map을 <int, pair<int, int>>의 형식으로 사용했는데요, first에는 key, second.first에는 빈도수, second.second에는 입력 순서가 저장됩니다. 강의를 보기 전 문제를 풀어 보았는데 이러한 방식으로 구현하는 것이 map을 2개 사용하는 것보다 효율적일까요?
- 미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
2-R 질문합니다.
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.안녕하세요 큰돌님.<1번 코드>#include <iostream> #include <vector> using namespace std; int n, root, del, visited[53], cnt; vector<int> v[53]; bool isLeaf; void dfs(int n){ visited[n]= 1; isLeaf=true; for(int i : v[n]){ if(!visited[i] && i != del){ //방문하지 않았고 현재 i가 del이랑 다르면 dfs를 계속 호출해서 탐색해야 함 isLeaf = false; dfs(i); } } if(isLeaf){ cnt++; } } int main(){ cin >> n; int num; for(int i=0; i<n; i++){ cin >> num; if(num == -1){ root = i; }else{ v[num].push_back(i); } } cin >> del; if(del == root){ cout << 0 << "\n"; }else{ dfs(root); cout << cnt << "\n"; } return 0; }#include <iostream> #include <vector> using namespace std; int n, root, del, visited[53], cnt; vector<int> v[53]; void dfs(int n){ visited[n]= 1; bool isLeaf = true; //가지마다 체크해야하니까 for(int i : v[n]){ if(!visited[i] && i != del){ //방문하지 않았고 현재 i가 del이랑 다르면 dfs를 계속 호출해서 탐색해야 함 isLeaf = false; dfs(i); } } if(isLeaf){ cnt++; } } int main(){ cin >> n; int num; for(int i=0; i<n; i++){ cin >> num; if(num == -1){ root = i; }else{ v[num].push_back(i); } } cin >> del; if(del == root){ cout << 0 << "\n"; }else{ dfs(root); cout << cnt << "\n"; } return 0; } 처음에 첫번째 코드로 작성하여 리프 노드의 갯수가 제대로 출력되지 않았습니다. isLeaf라는 변수의 선언 위치에 따라 값이 달라지는데 왜 두 코드가 값이 다르게 나오는지 모르겠습니다..
- 미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
bfs 질문
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 안녕하세요 큰돌 선생님 이번 정답 코드를 보고 의문점이 생겨서 게시글을 남깁니다! 저번 G-12851 문제에서 trace만 추가된것이 이번 H-13913 문제인데 저번 G번 문제 같은 경우 bfs를 이용한 해설코드가 다음과 같았습니다.그런데 이번 H 문제에서는 이렇게 짜셨는데 G번 문제에서는 here==k 일 때 break를 걸지 않고 H문제에서는 걸어도 되는 이유는 정확히 모르겠습니다.. 혼동이 오네요 또한 G번 문제에서 H문제 처럼 here==k 라는 조건 즉, 동생을 찾았다는 조건이 없으면 동생의 위치를 찾아도 계속 bfs가 돌아서 시간적으로 더 소모가 되는게 아닌가요...?
- 미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
9996번 문제 질문입니다!
예제도 다 맞고 질문게시판에 반례들도 다 넣어서 옳게 출력된 거 같은데 런타임 에러가 납니다ㅠㅠ뭘 빼먹었을까요?http://boj.kr/e808a1c39cc74954a63f14721dc3dce3
- 미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
4-a
// Online C++ compiler to run C++ program online #include <bits/stdc++.h> using namespace std; //// 다이어트 int N,mp,mf,ms,mv; int resultSet; vector<int> resultSetVector; typedef struct food{ int v[5]; }food; food* input(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>N>>mp>>mf>>ms>>mv; food* fList = (food*) malloc(sizeof(food) * N); for(int i=0; i<N; i++){ for(int j=0; j<5; j++){ cin >> fList[i].v[j]; } } return fList; } void printBitSet(int resultSet, int N){ for(int i=0;i<N; i++){ if( resultSet & (1<<i) ) { cout << i + 1 << " "; } } } //// logic // 1. 모든 조합을 구한다. // 2. 해당 조합 중에 최소 영양소 기준을 만족하는 조합을 찾는다. // 3. 해당 조합 중 최소 비용 조합을 찾는다. void solve(){ food* fList = input(); int result = INT_MAX; for(int i=0; i<(1<<N); i++){//O(N^2) //1. int sum[5] = {0}; for(int j=0;j<N;j++){ if(i&(1<<j)){ sum[0] += fList[j].v[0];//pi sum[1] += fList[j].v[1];//fi sum[2] += fList[j].v[2];//si sum[3] += fList[j].v[3];//vi sum[4] += fList[j].v[4];//ci } } //2.mp,mf,ms,mv if(sum[0] >= mp && sum[1] >= mf && sum[2] >= ms && sum[3] >= mv){ //3. if(result >= sum[4]){ result = sum[4]; resultSet = i;//최소 비용 조합 } } } if(result == INT_MAX) cout << -1 << '\n'; else{ cout << result << "\n"; printBitSet(resultSet, N); } } int main(){ solve(); } void printBitSet(int resultSet, int N){ for(int i=0;i<N; i++){ if( resultSet & (1<<i) ) { cout << i + 1 << " "; } } ////..... //2.mp,mf,ms,mv if(sum[0] >= mp && sum[1] >= mf && sum[2] >= ms && sum[3] >= mv){ //3. if(result >= sum[4]){ result = sum[4]; resultSet = i;//최소 비용 조합 } } ////..... if(result == INT_MAX) cout << -1 << '\n'; else{ cout << result << "\n"; printBitSet(resultSet, N);//최소 비용 조합 출력 }} 안녕하세요 큰돌 님. 비트마스킹 문제 질문이 있어 여쭤봅니다. 어떤 반례가 있을지 궁금합니다. vector에 넣어주는 방식이 아니라, i 비트값을 업데이트 해서 프린트 해주는 방식으로 구현 했습니다.위 방식만 다르기 때문에 여기서 문제가 있을 거라 추측됩니다.12퍼센트 쯤에서 테케통과를 못 하더라구요ㅠ 도와주시면 정말 감사드리겠습니다. 공유 소스 보기 (acmicpc.net)
- 미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
3-d 오답 질문드립니다.
// Online C++ compiler to run C++ program online #include <bits/stdc++.h> using namespace std; // 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. typedef pair<int,int> pp; int R,C; int visited[1004][1004]; char cmap[1004][1004]; int fmap[1004][1004]; int dx[4] = {0,0,1,-1}; int dy[4] = {-1,1,0,0}; //pp start; queue<pp> q; queue<pp> fq; bool outOfBound(int y, int x){ return (y < 0 || x < 0 || y >= R || x >= C ); } bool isExit(int y, int x){//탈출구 return (y == 0 || x == 0 || y == R - 1 || x == C -1); } bool isWall(int y, int x){ return cmap[y][x] == '#'; } void input(){ // 초기화 fill(&fmap[0][0],&fmap[0][0] + 1004 * 1004 , INT_MAX ); cin >>R>>C; for(int i=0;i<R;i++) for(int j=0;j<C;j++){ cin >> cmap[i][j]; if(cmap[i][j] == 'F'){//fire then fmap[i][j] = 1; fq.push({i,j}); } if(cmap[i][j] == 'J'){//출발 지점 q.push({i,j}); visited[i][j] = 1; } } } //bfs int solution(){ int y,x; int ny,nx; //bfs fire while(!fq.empty()){ tie(y,x) = fq.front(); fq.pop(); for(int i=0; i<4; i++){ ny = y + dy[i]; nx = x + dx[i]; if( fmap[ny][nx] != INT_MAX ) continue; //visited if(isWall(ny,nx) || outOfBound(ny,nx)) continue; fq.push({ny,nx}); fmap[ny][nx] = fmap[y][x] + 1; } } //bfs person while(!q.empty()){ tie(y,x) = q.front(); q.pop(); if(isExit(y,x)){ return visited[y][x]; } for(int i=0; i<4; i++){ ny = y + dy[i]; nx = x + dx[i]; if(visited[ny][nx] || isWall(ny,nx) || outOfBound(ny,nx)) continue; if(fmap[ny][nx] <= visited[x][y] + 1) continue; //이미 불이 있는 지역 q.push({ny,nx}); visited[ny][nx] = visited[y][x] + 1; } } return -1; } //solve void solve(){ input(); int result = solution(); if(result == -1) cout << "IMPOSSIBLE"; else cout << result; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); solve(); } bool outOfBound(int y, int x){ return (y < 0 || x < 0 || y >= R || x >= C ); } bool isExit(int y, int x){//탈출구 return (y == 0 || x == 0 || y == R - 1 || x == C -1); } bool isWall(int y, int x){ return cmap[y][x] == '#'; } 2% 오답 처리가 나는데 도저히 모르겠습니다. ㅠㅠ 위로 뺀 bool 컨디션 체크에서 문제가 생겼을 수도 있을 거 같은데.. 로직 구조가 해답과 거의 유사해서 어디서 문제가 생겼는지 디버깅 해도 안 보이네요 ㅠㅠ.. 그리고 ######J#F###..##...##...# 원본 반례 찾아보다가 시험 해본 케이슨데 해설지 답에서 걸러내지 못하는 것 같습니다. 코테 너무 어려워요 ㅠㅠㅠ 4179번: 불! (acmicpc.net)
- 미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
테스트케이스는 잘 되는데 제출하면 에러
#include <bits/stdc++.h> using namespace std; int N, M; // 세로 : N int arr[8][8]; int visited[8][8]; int dx[] = { 0, 1, 0, -1 }; int dy[] = { -1, 0, 1, 0 }; int t = 1; int curVirus = 2; int cnt = 0; int maxCnt = 0; void BFS(int _y, int _x) { queue<pair<int, int>> q; q.push({ _y, _x }); int firstX = _x; int firstY = _y; while (q.size()) { tie(_y, _x) = q.front(); visited[_y][_x] = t; arr[_y][_x] = curVirus; q.pop(); for (int i = 0; i < 4; ++i) { int nx = _x + dx[i]; int ny = _y + dy[i]; if (nx < 0 || ny < 0 || nx >= M || ny >= N) continue; if (arr[ny][nx] == 0 && visited[ny][nx] != t) q.push({ ny, nx }); } } arr[firstY][firstX] = curVirus + 1; } void ClearSpreadVirus() { for (int y = 0; y < N; ++y) { for (int x = 0; x < M; ++x) { if (arr[y][x] == curVirus) arr[y][x] = 0; } } } void SpreadVirus() { for (int y = 0; y < N; ++y) { for (int x = 0; x < M; ++x) { if (arr[y][x] != curVirus) continue; if (visited[y][x] == t) continue; BFS(y, x); } } } void CountZero() { for (int y = 0; y < N; ++y) { for (int x = 0; x < M; ++x) { if (arr[y][x] == 0) ++cnt; } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> N >> M; for (int y = 0; y < N; ++y) { for (int x = 0; x < M; ++x) { cin >> arr[y][x]; } } // 1. 브루트포스로 벽을 세운다. for (int b1 = 0; b1 < N * M; ++b1) { if (arr[b1 / M][b1 % M] != 0) continue; arr[b1 / M][b1 % M] = 1; for (int b2 = b1 + 1; b2 < N * M - 1; ++b2) { if (arr[b2 / M][b2 % M] != 0) continue; arr[b2 / M][b2 % M] = 1; for (int b3 = b2 + 1; b3 < N * M - 2; ++b3) { if (arr[b3 / M][b3 % M] != 0) continue; arr[b3 / M][b3 % M] = 1; SpreadVirus(); CountZero(); ClearSpreadVirus(); ++curVirus; maxCnt = max(maxCnt, cnt); cnt = 0; ++t; arr[b3 / M][b3 % M] = 0; } arr[b2 / M][b2 % M] = 0; } arr[b1 / M][b1 % M] = 0; } cout << maxCnt; return 0; } 안녕하세요.예제케이스는 답이 잘 나오는데 제출하면 에러가 뜹니다.코드가 복잡해서 디버깅이 쉽지 않네요..어디가 문제일까요?
- 미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
구현 문제
안녕하세요! 현재 구현 문제 강의까지 들었는데 좀 더 많은 구현 문제를 풀어보고 싶어서 질문 드립니다.! 혹시 백준에서 더 풀어볼 만한 문제 추천해주실 수 있으실까요??
- 미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
7-P 질문 있습니다!
안녕하세요, 큰돌님! 7-P 관련해서 질문드립니다. bfs + 맵 으로 완탐을 구현했습니다.하지만, 계속 71%에서 틀립니다.강의 로직과 비슷하다고 생각하는데, 왜 안되는지 궁금합니다! https://www.acmicpc.net/source/72316595
- 미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
a.cpp 오류
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.a.cpp 파일을 visual studio code 에서 만들었는데 다음과 같이 오류가 발생합니다.수업 자료처럼 open in intergrated terminal을 눌러서 컴파일명령어 실행한 상태입니다.
- 미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
테스트케이스는 다 맞는데
#include <bits/stdc++.h> using namespace std; int arr[51][51]; int visited[51][51]; vector<pair<int, int>> v; int dy[] = { -1, 0, 1, 0 }; int dx[] = { 0, 1, 0, -1 }; int T, M, N, K; int x, y; int t = 1; int cnt = 0; void DFS(int _y, int _x) { visited[_y][_x] = t; for(int i=0; i<4; ++i) { int ny = _y + dy[i]; int nx = _x + dx[i]; if(nx < 0 || ny < 0 || nx >= M || ny >= N) continue; if(visited[ny][nx] == t) continue; if(arr[ny][nx] == 0) continue; DFS(ny, nx); } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> T; for(int i=0; i<T; ++i, ++t) { cnt = 0; cin >> M >> N >> K; for(int j=0; j<K; ++j) { cin >> x >> y; v.push_back({x, y}); arr[y][x] = 1; } for(int k=0; k<v.size(); ++k) { tie(x, y) = v[k]; if(visited[y][x] == t) continue; if(arr[y][x] == 0) continue; DFS(y, x); ++cnt; } v.clear(); cout << cnt << '\n'; } return 0; } 안녕하세요. 강의 안보고 한번 풀어봤는데요. 테스트 케이스는 다 맞는데 어디가 문제인지 모르겠습니다 ㅠ
- 미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
a.cpp
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. a.cpp 파일을 visual studio code로 만들면 되는걸까요?
- 미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
queue를 통해 풀순 없을까요?
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. http://boj.kr/783d87e6fdf94af598c1204fe09a8c3b 반례주시면 감사하겠습니다..왜 오답인지 모르겠습니다..
- 미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
사전순 정렬
http://boj.kr/ac9c5032616d42d3b9599642e583fdcb 더 효율적인 방법을 제시해 주셨는데이 방식도 알아내고 싶어 질문 드립니다.이 방식대로 풀어내면 정렬하는 곳에서 문제가 생기는데1 4 101 4 6이렇게 정렬되어 사전순 정렬이 불가능한데.. 백터<string>에 담긴 "1 4 10", "1 4 6" 를 정렬하려면 어떡하면 좋을까요? 뭔가.. split을 잘 사용하면 될 것 같은 느낌이 있는데과부하가 걸렸는지 사고가 안되네요 ㅎㅎㅜ
- 미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
9996문제 질문있습니다.
앞부분과 뒷부분을 비교해서 DA로 출력하는 조건문에서 조건의 뒷부분을 비교하는 조건에 대해서 이해가 되지 않습니다.string f; (ab * ab 중 앞 ab)string e; (ab * ab 중 뒤 ab) 문제로 제시된 문자열의 사이즈에서 뒷부분의 사이즈를 빼면 조건의 뒷 문자에 대한 조건이 완성되는 이유가 궁금합니다. if(f == s.substr(0,f.size()) && e == s.substr(s.size() - e.size()))
- 해결됨10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
2-I 반례를 잘 모르겠습니다!
http://boj.kr/01660705b14346a68f903e9c57b3553b처음에 설명하신 String을 접근하는 방법과 cmp를 만드는 것 까지 접근했으나 계속 틀렸다고 나옵니다 ㅠㅠ한번 살펴봐주시면 감사하겠습니다!
- 미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
1-h 문제 질문입니다.
https://www.acmicpc.net/source/72188767 sum의 값에 따라 최솟값과 비교하여 최대값이 갱신되도록 짯는데 왜 틀리는걸까요?
- 해결됨10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
인접행렬 재귀함수 이렇게 짠 것도 맞는 건가요..?
이중for문도 아니고 뭔가 이상한 것 같은데 출력은 나오고..근데 정확히 뭐가 이상한 건지 잘 모르겠어요..ㅜㅜ맞게 짠 건지 확인 및 조언 부탁드려도 될까요..?
- 미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
7-O 질문입니다!
안녕하세요, 큰돌님17837을 풀던중 문제 예제 입력 5에서 답이 나오지 않습니다.반례를 다 찾았다고 생각했는데, 대체 왜 안되는지 궁금합니다... https://www.acmicpc.net/source/72120636
- 해결됨10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
1-A 테스트 케이스는 통과하는데 틀렸다고 뜹니다 ㅠ
안녕하세요 선생님,강의 잘 보고 있습니다. http://boj.kr/af15ab332b77463faa58e47e6826ca48선생님께서 설명하신 방법과 비슷한데, 일곱 난쟁이가 아닌 두 명을 잡아내기 위해 아홉개의 입력값의 합 sum에서 일곱 난쟁이 키의 합인 100을 뺀 sum-100 을 sub라는 변수에 담아두었고, 이중for문을 이용해 두 입력값의 합이 sub와 일치하는 두 수를 찾아냈습니다. 배열은 삭제가 안되니 그냥 저 두수를 0으로 처리하고 sort를 통해 오름차순으로 정렬한 다음, 출력할 때 두번째 인덱스부터 출력하도록 코드를 짜봤습니다.(0으로 바뀐 두 수는 맨 앞인 0번째와 1번째에 위치하게 되어 2번째 인덱스부터 출력하도록 하여 출력이 안되는 것을 의도) 야매스러운 방법이긴 하지만.... 그래도 어느 부분에서 예외가 발생했는지 확실히 알고 싶어 이렇게 질문드립니다!