안녕하세요. 강사님 2-D 답안을 보면서 질문이 있습니다. 해설 강의에서 설명한 DFS 반환값 설정과 DFS 로직은 이미 이해한 상태에서 해당 문제를 접했는데요. 제가 답안을 보고 수정 및 작성한 코드는 아래입니다. /* 답 : http://boj.kr/9815cd371fe643f59ac17a410e0cfca4 */ #include <bits/stdc++.h> using namespace std; int M, N, K; int m[104][104]; bool visited[104][104]; vector<tuple<int, int, int, int>> c; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; int dfs(pair<int, int> node) { int count = 1; visited[node.first][node.second] = true; for(int i = 0; i < 4; i++) { int nx = node.first + dx[i]; int ny = node.second + dy[i]; if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue; if(!m[nx][ny] && !visited[nx][ny]) count += dfs({nx, ny}); } return count; } int main(void) { cin >> M >> N >> K; for(int i = 0; i < K; i++) { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; c.push_back({x1, y1, x2, y2}); } fill(&m[0][0], &m[0][0] + 104 * 104, 0); for(int i = 0; i < N; i++) for(int j = 0; j < M; j++) for(int k = 0; k < K; k++) if(get<0>(c[k]) <= i && i < get<2>(c[k]) && get<1>(c[k]) <= j && j < get<3>(c[k])) m[i][j] = 1; // for(int i = 0; i < N; i++) // { // for(int j = 0; j < M; j++) // cout << m[i][j]; // cout << '\n'; // } int component = 0; vector<int> area; for(int i = 0; i < N; i++) for(int j = 0; j < M; j++) if(!m[i][j] && !visited[i][j]) { component++; area.push_back(dfs({i, j})); } sort(area.begin(), area.end()); cout << component << '\n'; for (int i = 0; i < area.size(); i++) cout << area[i] << ' '; cout << '\n'; return 0; } 저는 강사님과 약간 다르게 코드를 작성했는데 강사님의 이해를 돕기 위해 다른 점을 살짝 설명드리면 해당 문제 예시 그림에서 시계 방향으로 90도 회전한 상태라고 가정하고 진행을 했습니다. 그래서 x, y 위치가 반대고 각 이중 for 문의 첫 for 문 내 조건문 표현식에서 N 을 사용합니다. 미리 영역 좌표를 받고 int 형 데이터 4개를 가지고 있는 튜플을 사용했는데요. 제가 안되는 부분은 바로 해당 튜플을 가지고 영역을 표시할 때 입니다. for(int i = 0; i < N; i++) for(int j = 0; j < M; j++) for(int k = 0; k < K; k++) if(get<0>(c[k]) <= i && i < get<2>(c[k]) && get<1>(c[k]) <= j && j < get<3>(c[k])) m[i][j] = 1; 중요한건 오른쪽 위 좌표에 대해서 검사를 할 때 등호를 포함시키지 않는게 답을 위한 중요한 부분이였는데요. 이 부분이 이해가 가질 않습니다.
https://www.inflearn.com/questions/773687/dev-c-%EC%9E%90%EC%B2%B4-%EC%98%A4%EB%A5%98 안녕하세요 선생님 위 링크와 같은 문제를 겪고 있는데요. 저도 마찬가지로 경로에 공백이 있는데요. 경로를 구체적으로 어떻게 설정하는지 모르겠습니다. Chat GPT와 구글링도 해봤지만 도저히 방법을 모르겠어서 질문드립니다. 단계별로 해결방법을 알려주시면 감사하겠습니다~
싱크풀려면 ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 이렇게한다고 적혀있긴한데 선생님 코드보면 가끔식 ios_base::sync_with_stdio(0); cin.tie(0); 이렇게 콘솔인만 적혀있는것도있던데 여기에 cout.tie(0);까지 적었더니 프로그램이 동작이 안되던 경우도 있더군요 어떠한 이유인지 알고싶습니다 또한 어떤것은 아규먼트값이 0일때도있고 NULL일때도있던데 이것의 차이도 알고싶습니다 미리 감사합니다
http://boj.kr/29fb43fd10d44ca584e97162656381a0 안녕하세요 선생님 제 코드 맨 밑에 반례가 안돌아가는 논리적 이유를 알 수 있을까요?? 그리고 저는 질문게시판으로 저 반례를 찾은것인데 이러한 애매한 반례는 어떻게 찾는것이 좋을까요? 예를들어 저 반례는 선생님이 설명해주신 최대 최소로 찾을 수 있는 반례가 아닌거 같습니다. 제 코드의 33- 37번째줄은 벡터인경우에만 실행이되나요? 선생님이 max값을 200000으로 설정하신 이유가 궁금합니다!
http://boj.kr/29fb43fd10d44ca584e97162656381a0 안녕하세요 선생님 제가 많은 테스트 케이스들이 돌아가는데 맨 아래에 주석으로 넣은 테케가 돌아가지 않습니다. 혹시 제 코드의 논리적 오류가 무엇인지 찾아주실 수 있으십니까? 33줄에서부터 37번째줄까지의 코드는 예전에 벡터를 활용할시 잘 돌아갔는데 큐는 저런 코드를 못사용하나요??
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 배열로 next_permutation할 때 int a[3]={1, 2, 3}; void printA(int a[]){ for(int i : a) cout << i << " "; cout << "\n"; } int main(){ do{ printA(a); }while(next_permutation(a, a+3)); } 벡터에서 한 것 처럼 이렇게 따로 printA로 함수를 빼서 만들어봤습니다. 하지만 for 줄에서 [Error] 'begin' was not declared in this scope 이런 에러가 나면서 실행이 되지 않는데 그 이유가 궁금합니다... 교안에서처럼 따로 printA함수를 빼지 않고 for~부분을 그대로 main함수에 작성하면 실행이 됩니다. 그냥 교안처럼 printA따로 안빼고 바로 작성하면 되는건가요?
안녕하세요. 선생님 항상 강의 잘 듣고 있습니다. http://boj.kr/eb569883dd084b64877cab066012fc70 3-P 문제를 1. 꽃을 심었을 때 모든 구역의 비용을 순회하며 계산하여 가격에 따른 좌표 값과 비용을 저장한다. 2. 비용을 정렬하여 비용에 따른 좌표 값을 visited배열을 통해 체크한다. 위와 같은 방식으로 풀었는데, 어떤 부분에서 틀렸는지 잘 모르겠습니다. 감사합니다.
프로그래머스 2레벨 문제에서 조금 막히고 1레벨은 그냥 수월하게 풀정도입니다. 또 백준 기준에선 실버 2까지는 그냥 풀 수 있습니다. 제가 학부생이지만 알고리즘 자료구조를 다 까먹은 상태여서 문제를 풀 때 접근 방식이나 접근법 혹은 문제가 집중이 안되서 생각이 안될 정도로 안 풀릴때가 있습니다. 이 강의에서 제가 활용을 해야 한다면 강의를 통해서 처음부터 차근차근 기초를 쌓아 올라가면 될까요?
안녕하세요. 5 - B 문제 풀이 이후 시간 초과가 나서 이것 저것 찾아봐도 어디서 시간 복잡도가 올라간 것인지 궁금해 질문 남기게 되었습니다. 기존에 split 함수를 구현했던 것에서 착안하여 erese()를 사용하며 계속해서 문자열을 재구성하는 방식으로 구현했습니다. http://boj.kr/839e5d81df42477cae93f08c8c706222
안녕하세요. 항상 강의 잘 듣고 있습니다. 5-A 문제를 map 과 pq 를 사용해서 풀이해봤습니다. 제가 생각했던 풀이는 아래와 같습니다. d 를 기준으로 받을 수 있는 p 를 내림차순하여 그룹핑했습니다. d 마다의 최대값만을 pq.top() 를 통해 받아가며 최종 값을 계산하도록 했습니다. 예제의 경우는 통과하나 최종 결과는 실패입니다 ㅠ. 제가 고민한 부분에서 어떤 오류가 있는지 궁금하여 질문드리게 되었습니다. 제 코드입니다. http://boj.kr/ca47ec856ce04d98be7c9cb6c6571304 매번 감사드립니다.
지금까지 tc 여러 개 일때 출력 값들은 따로 저장해서 마지막에 한 번에 출력했었는데요. 영상보고 이제야 눈치챘는데, 해보니깐 아래 둘다 맞더군요. 이런 건 백준 말고도 다른 사이트도 똑같나요. 아니면 상이한가요? 아래 1번 처럼해도 모두 안전한건가요. 1 입 출 입 출 2 입 입 출 출
안녕하세요 7-1 분할 컴파일 강의를 들으면서 궁금한 점이 있어 문의 남깁니다. main.cpp 상단에 아래 코드를 작성해주지 않으면 에러가 납니다. #include "fun.cpp" 에러 내용은 다음과 같습니다. && g++ -std=c+ +14 example2.cpp -o example2 && "/Users/heehmin h/Documents/C++/07_Class_and_Object/1.분할_컴파 일/"example2 Undefined symbols for architecture arm64: "display(MyStruct&)", referenced from: _main in example2-60ed22.o ld: symbol(s) not found for architecture arm64 clang: error: linker command failed with exit code 1 (use -v to see invocation)
제 기억엔 % 연산자를 배운 기억이 없어서요..! 검색해서 풀기는 했는데 %연산자 활용하지 않고도 풀 수 있는 예제인가요? 방법이 있다면 알고 싶습니다!! 30분간 머리를 싸매고 풀어내긴 했는데, 이게 의도하신 연습은 아닌 것 같아서요..! 사실상 %를 풀어쓴 게 아닌가 싶기도 하고요..ㅠ
1주차 문제들의 큰돌님 코드의 시간 복잡도 계산을 확인받고자 질문 올립니다. A 순열로 풀었을 때 for 문 -> next_permutation 그리고, 내부에 for문 -> for문으로 출력 순으로 진행했는데, next_permutation 내부에 for문이 있으므로 O(n^2) 인가요? 조합으로 풀었을 때 solve()에서 for문 중첩이므로 O(n^2)인가요? B: O(n) C: O(n) 첫 번째 시작을 중첩 for문으로 시작했지만 바깥 for문은 i < 3까지 진행하므로 3 * n으로 하여 O(n)이고, 그 뒤에 for문이 100까지 진행되므로 3n + 100 으로 O(n)이라 생각했습니다. D: O(n) reverse를 하는데 처음부터 끝까지 하므로 O(n)이고 그 이후에 if문이 존재하므로 O(n)으로 생각했습니다. E: O(n) F: O(n) G: O(n) H: O(n) I: O(n) J: 패션왕 신해빈 문제인데, while문과 그 안에 for문이 있기 때문에 O(n^2)으로 생각해야하나요? 아니면 테스트케이스로 주어진 while문 내부만 고려해서 O(n)으로 생각해야 하나요? K: O(n) L: O(n^2) M: O(n^2) N: O(long N) O: 아직 문제 이해를 잘 못해서 더 고민해보겠습니다..
안녕하세요 선생님 혼자서 해 볼려고 해도 구현이 하기가 어려워 선생님의 코드를 보면서 원리를 이해하고 있는 학생입니다. 선생님이 만드신 코드중에 for (i = 0;i < map[x].size(); i++) { if (ch[map[x][i]] == 0) { ch[map[x][i]] = 1; Q.push(map[x][i]); dis[map[x][i]] = dis[x] + 1; } i = 0;i < map[x].size(); i++이 부분 부터 이해가 잘 되질 않습니다. x가 1이면 map[1]의 개수는 2가 되고 map[1][0], map[1][1]로 돼야 할 텐데 어떻게 ch[map[1][3]=3] = 1으로 가는지 모르겠습니다.
처음 오리의 위치를 딱 정해서 오리의 처음 위치 부터 계속 탐색 시켰습니다. 이러니 시간 초과가 나오게 되었습니다. 왜 시간 초과가 나오는지 궁금합니다. https://www.acmicpc.net/source/61456336 while (true){ ans++; v.clear(); find_water(); ice_break(); if (find_duck()) break; } 이 부분에서 find_water가 O(1500*1500) 이정도 시간이 걸린다고 생각합니다. 호수의 크기가 1500x1500이고 오리가 (0,0), (1500,1500)에 있을때, 대충 bfs로 정점이 1500개, 간선이 4개니까, O(1500 + 4)정도 걸린다고 생각합니다. O(1500*1500) * O(1500)이라 시간 초과가 나는것이라고 생각하는데, 이렇게 계산하는것이 맞는지 궁금합니다. 영상에서 나온 방법은 왜 시간초과가 안 나오는지도 궁금합니다... 문제 해설과 똑같은 로직으로 코드를 짜보았습니다. https://www.acmicpc.net/source/61457241 하지만, 메모리 초과가 나와 질문합니다.. 어디가 메모리가 초과되는지 알고 싶습니다!
