테스트 케이스는 다 맞고 코드도 틀린부분이 어딘지 모르겠습니다 ㅠㅠ #include <iostream> #include<string.h> using namespace std; const int MAX = 51; const int dy[4] = { -1,1,0,0 }; const int dx[4] = { 0,0,-1,1 }; int T, N, M, K, cnt; int adj[MAX][MAX]; bool visited[MAX][MAX]; void dfs(int y, int x) { visited[y][x] = true; for (int i = 0; i < 4; i++) { int ny = y + dy[i]; int nx = x + dx[i]; if (ny < 0 || ny >= N || nx < 0 || ny >= M) continue; if (adj[ny][nx] == 0) continue; if (visited[ny][nx]) continue; dfs(ny, nx); } return; } int main() { cin >> T; for (int i = 0; i < T; i++) { cin >> M >> N >> K; cnt = 0; memset(visited, false, sizeof(visited)); memset(adj, 0, sizeof(adj)); for (int j = 0; j < K; j++) { int y, x; cin >> x >> y; adj[y][x] = 1; } for (int y = 0; y < N; y++) for (int x = 0; x < M; x++) { if (visited[y][x]) continue; if (adj[y][x] == 1) { dfs(y, x); cnt++; } } cout << cnt << '\n'; } return 0; }
안녕하세요 선생님 수업 듣는 중에 의문점이 생겨서 질문드립니다. 6-D(7795) 번 문제 같은 경우에는 입력값의 범위가 1~20000까지로 완전 탐색으로 풀게 된다면 n^2의 시간복잡도를 가져 시간 초과가 날 줄 알았습니다. 하지만 그렇게 풀어보니 시간 초과가 나지 않고 정상적으로 통과가 되네요 어떤 이유 때문인지 궁금합니다! #include<bits/stdc++.h> using namespace std; int T, N, M, num; vector<int> A; vector<int> B; int main() { cin >> T; while (T--) { cin >> N >> M; A = vector<int>(N); B = vector<int>(M); for (int i = 0; i < N; i++) cin >> A[i]; for (int i = 0; i < M; i++) cin >> B[i]; sort(A.begin(), A.end()); sort(B.begin(), B.end()); int cnt = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (A[i] > B[j]) { cnt++; } else break; } } cout << cnt << "\n"; } return 0; }
안녕하세요 큰돌님 코드 질문은 아니고 경우의 수 질문인데요 x, head1, head2 -> 3가지 x, eye -> 2가지 x, patns1, pant2 -> 3가지 아무것도 입지않는 경우의 수 1을 빼주는 것이 알몸인 상태인 경우를 빼주는 것이니 무조건 위의 경우에도 무조건 1만 빼줘서 3 x 2 x 3 -1 = 11 로 생각하는게 맞는건가요? 듣다보니 헷갈려서 질문 드려봅니다
http://boj.kr/4dc8f27d6a09443a916061fc1ac7800c 반례가 궁금합니다. dfs와 비트마스킹을 함께 사용해서 구현했고 테스트케이스 및 질문게시판의 반례도 다 통과했습니다만 1%대에서 바로 오답이 나옵니다. p.s. 비트마스킹 챕터에 있는 문제라 비트마스킹을 써봤는데, 굳이 이런 문제에 비트마스킹을 쓸 필요가 없었을까요? 앞으로 코테를 풀 때 메모리가 부족할 만큼 수의 범위가 크면 비트마스킹만 쓰면 될까요? 이 문제도 노드가 최대 1000개에 엣지가 1000000개 까지 가능하니 비트마스킹을 써야겠다고 생각습니다.
안녕하세요 큰돌선생님 매번 좋은 강의 감사합니다.. 문제를 풀다가 못풀어서 선생님 코드를 보고 강의를 시청하였는데요, rpg함수는 dp배열을 갱신하는 재귀함수인데 기저사례가 없는 이유가 궁금합니다. 아직 제가 코드를 완전히 이해하지 못하는것 같은데, 제 생각으로는 선생님코드 for(int p = 0; p <= pnt; p++){ int nextSTR = min(1000, STR + p); int nextINT = min(1000, INT + pnt - p); ret = max(ret, rpg(nextSTR, nextINT)); } 이 부분에서 pnt가 0이더라도 계속 rpg() 함수를 호출할것 같은데 제가 어느부분을 이해하지 못하는 건가요??
https://www.acmicpc.net/source/share/c705165d9da648cab807897686bcb320 논리로직은 이해를 한거같은데 아직도 이분탐색에서 left와 right를 체크하는부분에서 mid값을 걸러내는부분이 잘 이해가가지않네요 right에서 mid값을 가지고오나 left를 체크할떄 가지고오나 결과는 같을거라고 생각했는데 아직도 이부분이 잘 이해가가지않습니다 ㅜㅜ
강의를 듣기에 앞서 계단오르기 문제를 DFS로 풀었습니다. 아래와 같이 문제를 풀어도 문제가 없을까요? // 계단 오르기 function solution(target){ const count = [1,2]; const answerArr = [] const set = [] let answer = 0; function dfs(n){ if(n>target) return if(n === target){ answer+=1 answerArr.push([...set]) return } for(let el of count){ set.push(el) dfs(n+el) set.pop() } } dfs(0) console.log(answerArr) return answer }; console.log(solution(7)) console.log(solution(8)) console.log(solution(4))
제가 작성한 코드 http://boj.kr/7e8f78a1feb2433fa70b2a847a23cfff 첫 번째 질문 제가 작성한 코드는 반례처리를 하지 않았는데 통과됐습니다. 이 문제는 시작점과 도착점이 같은 경우에도 반례처리가 필요하지 않은 문제 아닌가요? 두 번째 질문 방문하지 않은 정점을 방문할 때, cnt[there] += cnt[here] 인 이유가 무엇인가요? 저는 cnt[there] = cnt[here] 라고 생각합니다.
import java.util.*; import java.io.*; public class Main { static int[][] graph; static boolean[][] visited; static int N; static int[] answer; static int real; public static void solution(int y, int x) { // y : 학생, x : 학년 visited[y][y] = true; // 자신을 카운팅하지 않기 위한 방법 for (int i = 1; i <= N; i++) { //세로 비교 (반 같은지 비교) if (graph[i][x] == graph[y][x] && !visited[y][i]) { answer[y]++; visited[y][i] = true; } } int max = Integer.MIN_VALUE; // answer 배열에서 최댓값 찾기 for (int i = 0; i < answer.length; i++) { if (answer[i] > max) { max = answer[i]; real = i; } } } public static void main(String args[]) throws IOException{ // 0. 입출력 구현 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); graph = new int[N+1][6]; visited = new boolean[N+1][6]; answer = new int[N+1]; for (int i = 1; i <= N ; i++) { String[] str = br.readLine().split(" "); for (int j = 1; j <= 5; j++) { graph[i][j] = Integer.parseInt(str[j - 1]); } } for (int i = 1; i <= N; i++) { for (int j = 1; j <= 5; j++) { solution(i ,j); } } bw.write(String.valueOf(real)); bw.close(); br.close(); } } 피드백 요청합니다..!
안녕하세요, 시간초과로 통과하지 못해서 질문드립니다. http://boj.kr/c89e043975f349bbb7a4066422235fc0 이전에 단순히 dfs만 써서 풀었을 때와 로직은 동일합니다. 다만 이번엔 visited를 2차원 벡터가 아닌 int형 변수 하나로 처리했고 방문하는 경우엔 | 연산으로 비트를 켜줬고 방문을 마치고 나선 & ~(1<<idx) 와 같이 비트를 꺼줬습니다. 선생님의 코드와 제 코드의 함수 호출을 비교해보니 예제의 경우에선 함수 호출 횟수도 동일했습니다. 그런데 시간초과가 생기는 이유는 무엇일까요?
http://boj.kr/3aa1410045524133b6e2b5ea6da1bcce 현재 해당코드를 통해서 정답은 맞췄는데 제가생각했던건 MID-1, MID+1로 조건탐색을하고 left <= right 조건을 통해서 left가 조건탐색이 끝났을때 기준으로 left가 정답이라고 생각하고 이때 left가 max조건을 넘겨버리면 체크하는걸로 해결했는데 설명코드에서 mid를 ret으로 체크되는부분이 잘 이해가가지않아 질문을남깁니다 항상감사합니다
감사합니다. function solution(question) { let answer = 0; for (const x of question) { if (x === x.toUpperCase()) answer++; } return answer; } console.log(solution("KoreaTimeGood"));
감사합니다. function solution2(question, word) { let i = 0; for (const x of question) { if (x === word) i++; } return i; } function solution(question, word) { return question.split(word).length - 1; } console.log(solution("COMPUTERPROGRAMMING", "R")); console.log(solution2("COMPUTERPROGRAMMING", "R"));
