http://boj.kr/7a4cd7062f27488eb2b897aae623f48e위와 같이 재귀로 모든 경우를 탐색하돼 백트래킹을 넣어 어차피 더 해봤자 의미 없는 경우는 제외를 해줬는데 메모리 초과가 나왔습니다.위처럼 재귀로 해결하면서 따로 백트래킹으로 예외 처리를 해주는 것 보다 bfs를 쓰는 것이 더 효율적인가요? 아니면 재귀와 bfs의 차이는 크지 않지만 예외 처리를 visited로 안해줘서 생기는 차이인가요? 어디서 차이가 나는 것인지 궁금합니다 큰돌 선생님!!+ visited 배열로 예외처리를 하면 효율적으로 이미 간 곳은 못 가게 되니 속도가 빨라지는 것까지 알겠습니다! 하지만 이렇게 되면 '다른 경로로 같은 이동 횟수를 가지면서 같은 지점에 도착한 경우'에는 visited 조건 문에서 제외가 되는 걸로 알고 있습니다. 이러면 최솟값이 나온 경우가 몇가지인지 알 수가 없죠.그래서 큰돌 선생님께서 위의 코드를 통해 그 수를 세어주신 것 같은데 어떻게 세어주는 개념인지 잘 이해가 가지 않습니다.위 그림처럼 이미 못가는 곳이 저렇다고 가정하면위 그림처럼 이전의 값들을 참고, 참고, 참고... 이렇게 참고 해가면서 현재의 경우의 수까지 나오는 것이라고 보면 될까요?

union 메소드 구현할 때 저는 find(a)와 find(b) 중 더 작은 수로 통일하기 위해 static void union(int a, int b) { int a_rep = find(a); // a의 대표값 int b_rep = find(b); // b의 대표값 int min = a_rep<b_rep ? a_rep:b_rep; parent[a] = min; parent[b] = min; } 이렇게 코드를 짰는데요.이렇게 하니 에러가 나는데 이유를 모르겠습니다 ㅠㅠ 늘 좋은 강의 감사합니다.

if(nx>=0 && nx<n && ny>=0 && ny<n && arr[nx][ny]>=arr[i][j]) 여기서 nx >= 0, ny >= 0은 이해가 되는데, nx < n 과 ny<n 은 왜 해야하는지 잘 모르겠습니다. 예전에 한참 알고리즘 공부할때는 이해가 됐었는데,, 오랜만에 하니까 이해가 안되네요...  

http://boj.kr/be195db38890481b9ca7ef38e786651e 선생님의 코드와 다른 부분은 스택을 매번 재선언하지 않고 재활용 할 수 있게 비워둔다는 점 뿐인 것 같습니다. gcc로 컴파일 했을 때, 2회 이상의 입력에서 2회차 반복 시에 아무런 출력도 하지 않고 그대로 프로그램이 강제 종료됩니다. 백준에는 런타임 에러라고 뜨는데, 입력과 관련된 문제일까요? 아니면 스택을 재선언 하지 않고 매번 비워두는 코드에서 런타임 에러가 발생한 것일까요..? 조언이 필요합니다. 감사합니다.

안녕하세요! 강의를 다 듣고, 블로그에 남겨주신 문제들을 풀어보고 있습니다.'백준 1325 효율적인 해킹 문제'인데, 시간 초과가 나는 기준을 이해하지 못해서 질문드립니다!import java.io.*; import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.StringTokenizer; public class Main { private static int N, M; private static List<List<Integer>> graph; private static boolean[] visited; private static int dfs(int idx) { visited[idx] = true; int count = 1; for (int next : graph.get(idx)) { if (!visited[next]) { count += dfs(next); } } return count; } public static void main(String[] args) throws IOException { 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()); M = Integer.parseInt(st.nextToken()); graph = new ArrayList<>(N + 1); for (int i = 0; i <= N; i++) { graph.add(new ArrayList<>()); } for (int i = 0; i < M; i++) { st = new StringTokenizer(br.readLine()); int a = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken()); graph.get(b).add(a); } int max = -1; List<Integer> answer = new ArrayList<>(); for (int i = 1; i <= N; i++) { visited = new boolean[N + 1]; int count = dfs(i); if (max < count) { answer.clear(); answer.add(i); max = count; } else if (max == count) { answer.add(i); } } Collections.sort(answer); StringBuilder sb = new StringBuilder(); for (int n : answer) { sb.append(n); sb.append(" "); } bw.write(sb.toString()); br.close(); bw.close(); } } 이렇게 작성을 하니 자꾸 시간 초과가 나와서 chat gpt에 질문해보니 메모이제이션을 사용하면 해결할 수 있다는 답변이 나왔습니다. 이미 visited를 사용해 이미 방문한 노드를 다시 방문하지 않는데, 메모이제이션을 사용하는게 의미가 있을까 싶었지만 일단 코드를 변경해봤습니다.import java.io.*; import java.util.*; public class Main { private static int N, M; private static List<List<Integer>> graph; private static boolean[] visited; private static int[] memo; private static int dfs(int idx) { if (memo[idx] != -1) { return memo[idx]; } visited[idx] = true; int count = 1; for (int next : graph.get(idx)) { if (!visited[next]) { count += dfs(next); } } memo[idx] = count; return count; } public static void main(String[] args) throws IOException { 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()); M = Integer.parseInt(st.nextToken()); graph = new ArrayList<>(N + 1); for (int i = 0; i <= N; i++) { graph.add(new ArrayList<>()); } for (int i = 0; i < M; i++) { st = new StringTokenizer(br.readLine()); int a = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken()); graph.get(b).add(a); } int max = -1; List<Integer> answer = new ArrayList<>(); for (int i = 1; i <= N; i++) { visited = new boolean[N + 1]; memo = new int[N + 1]; Arrays.fill(memo, -1); int count = dfs(i); if (max < count) { answer.clear(); answer.add(i); max = count; } else if (max == count) { answer.add(i); } } Collections.sort(answer); StringBuilder sb = new StringBuilder(); for (int n : answer) { sb.append(n); sb.append(" "); } bw.write(sb.toString()); br.close(); bw.close(); } } 이렇게 작성하니까 시간 초과가 나지는 않는데, 어느 테스트 케이스에서 memo 배열에 저장된 값을 사용하는건지 알 수 있을까요?그리고 혹시 강사님은 이 문제를 이것과 다르게 푸셨을까요?? ++ 추가로 배열 대신 HashMap을 사용해도 시간 초과가 납니다... ㅠimport java.io.*; import java.util.*; public class Main { private static int N, M; private static List<List<Integer>> graph; private static boolean[] visited; private static Map<Integer, Integer> map; private static int dfs(int idx) { if (map.get(idx) != null) { return map.get(idx); } visited[idx] = true; int count = 1; for (int next : graph.get(idx)) { if (!visited[next]) { count += dfs(next); } } map.put(idx, count); return count; } public static void main(String[] args) throws IOException { 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()); M = Integer.parseInt(st.nextToken()); graph = new ArrayList<>(N + 1); for (int i = 0; i <= N; i++) { graph.add(new ArrayList<>()); } for (int i = 0; i < M; i++) { st = new StringTokenizer(br.readLine()); int a = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken()); graph.get(b).add(a); } int max = -1; List<Integer> answer = new ArrayList<>(); for (int i = 1; i <= N; i++) { visited = new boolean[N + 1]; map = new HashMap<>(); int count = dfs(i); if (max < count) { answer.clear(); answer.add(i); max = count; } else if (max == count) { answer.add(i); } } Collections.sort(answer); StringBuilder sb = new StringBuilder(); for (int n : answer) { sb.append(n); sb.append(" "); } bw.write(sb.toString()); br.close(); bw.close(); } }

#include <iostream>using namespace std;int a[9][9];int b[9];int main(){ freopen("input.txt","rt",stdin); int i,j,max,rev=0,tmp=2147000000; float x=0.0,sum=0.0; int c[9]; for(i=0;i<9;i++){ for(j=0;j<9;j++){ cin>>a[i][j]; sum+=a[i][j]; } b[i]=(sum/9.0)+0.5; sum=0.0; } for(i=0;i<9;i++){ for(j=0;j<9;j++){ tmp=a[i][j]-b[i]; if(tmp<0){ tmp*=-1; } if(tmp<max){ max=tmp; rev=a[i][j]; } if(max==tmp){ if(rev<a[i][j]){ rev=a[i][j]; } } } c[i]=rev; max=2147000000; } for(i=0;i<9;i++){ cout<<b[i]<<' '<<c[i]<<endl; } return 0;}이렇게 짰을때 출력창에서 나머지는 다 똑같이 나오는데 첫번째 행의 평균과 가장 가까운수가 0이 나옵니다. 혹시 왜 이렇게 나오는지 알려주실 수 있나요...?

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. https://www.acmicpc.net/source/64767474안녕하세요. dfs를 안쓰고, 연결하는거 체크를 해보았는데..예제는 전부 통과하는데 오답이 나오네요.. 이유가뭘까요??

http://boj.kr/36b07be654c44bf9ac885bc8f1726452 예시 코드도 맞고, 제 생각에는 맞는 코드인 것 같은데어느 부분에서 틀린 건지 잘 모르겠습니다.예외 테스트케이스가 있을까요?

이런식으로 코드를 구성하였습니다해당 부분에서 이전수업에서 들었던 모듈러연산은 최종결과에서 하는것과 중간에 모듈러연산이 사칙연산에 의해서 같이 계산되는게 결과가 같다고 기억하여 이런식으로 구성하였는데 맞는걸까요? 정답은 같은것같은데 테스트케이스가 따로있진 않은 예제라 혹시나하여 질문드립니다

안녕하세요, 3-B가 최단거리를 구하는 문제이기에 BFS를 활용한 것까지는 이해가 됐습니다! 그런데 이 문제가 왜 완전탐색 파트로 분류되어 있는지 궁금합니다. 일반적인 BFS 문제들과 다르게 모든 경우에 대해 BFS 탐색을 하고, 매 탐색마다 원복을 해줘야 하기 때문에 완전탐색 문제로 분류된 것인가요?

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 안녕하세요!질문이 2가지 있습니다.[기본]시간복잡도 Time Complexity 강의 @4:20부분에서 1/ "이처럼 입력값 n에 대한 실행시간 함수가 있다면, 최고차항의 계수만을 표기하여 Big-O(n)을 표기할 수 있다."이렇게 설명을 하셨는데, 제가 이해하기로는 계수는 숫자와 문자의 곱에서 '숫자'를 의미하는걸로 알고 있어서요!예를 들면, 3n이라고 한다면 숫자인 3이 계수라고 알고있습니다.그러면 Big-O표기법은 '최고차항의 계수만을 표기'하는게 아니라 '최고차항'을 표기하는걸까요? 2/ @4:27부분에O(n!) > O(2^n) > O(n^2)..이렇게 시간복잡도가 높은것부터 그래프로 보여주실때 '차수가 높은 순서는 다음과 같다'라고 말씀하셨는데제가 이해하기로는 '차수'는 문자가 곱해진 횟수, 즉 n^2면 2차, n^3이면 3차. 이런게 차수인걸로 알고있습니다.그렇다면 n!이 2^n보다 차수가 더 높고, 2^n이 n^2보다 차수가 더 높은걸로 이해하면 될까요? 감사합니다! 

http://boj.kr/54cbfbf55f6946edbeb3beb93d88f6bc안녕하세요 강사님! 여태 틀린 문제 다시 한번 풀어보고 있습니다. 백조 문제에서 메모리 초과가 나서 제가 생각하기에 의심되는 부분들 (queue에 중복 좌표를 여러번 푸시하는 경우)을 없애고도 메모리 초과가 나길래 어느 부분이 문제일지 한번 봐주시면 감사하겠습니다..로직 자체는 강사님 코드와 거의 비슷하게 떠올린 것 같은데 2차원 배열을 너무 많이 쓴 것이 문제인지.. 특정 케이스에서 queue가 너무 커지는 것이 문제일지 잘 감이 안 옵니다 ㅜ  

안녕하세요!extendCCTV함수 부분에서 강의 코드와 살짝 다르게 모든 while문을 다음과 같이 작성했더니 시간 초과가 발생합니다! 내부의 조건문을 이렇게 작성했을 때 시간초과가 발생하는 이유가 궁금합니다..!while(true) { int ny = y + dy[dir]; int nx = x + dx[dir]; if(ny<0 || ny>=n || nx<0 || nx>=m || a[ny][nx]==6) break; if(a[ny][nx] == 0) { a[ny][nx] = 8; _change.push_back({ny, nx}); } y = ny; x = nx; }

http://boj.kr/44c6637eb356484a8f22139b8d4f217e 링크를 잘못올려서 다시 올립니다ㅜㅜ답안에는 map을 이용해서 풀었는데 이 방법으로해도 크게 문제없는것 같은데 왜 틀렸다고 나오는지 알고 싶습니다! 감사합니다

자바 코테 이어서 파이썬 강의까지 듣고있습니다 :)혹시 출처 남기고 블로그 및 깃에 올려서 될까요!

만약에 m이 3이고 치킨집이 5개면5C1인 경우 5C2, 5C3인 경우의 조합들을 다 구해서각각의 경우에 대한 치킨 거리를 계산한 후 최종적인 최솟값을 구하는 문제인 줄 알았습니다.예시)5C1 이면 m=3이니까 {0} -> 각 집들의 치킨 거리를 구한 후 더한 값{1} 위와 같음{2} 위와 같음{3} 위와 같음{4} 위와 같음5C2 이면{0,1}{0,2}{0,3}...이렇게 전부의 경우에 대한 거리 값을 구한 후 최소를 찾는 건 줄 알았는데위의 방법이 아니라 그냥 m=3이면5C3의 조합들 중에서 최소가 나오는 경우를 구하면 되는 건가요?? 제가 문제를 잘 이해를 못하는 것 같아서 질문 드립니다!!

안녕하세요 큰돌님1 - M 3986 좋은 단어 문제를 deque 를 이용해deque 이 비거나 하나만 남을 때까지 반복하면서back 과 다음 back 이 같은 경우 두 개의 back 을 모두제거하고 아닌 경우 첫번째 꺼낸 back 을 다시 front로push 하는 방식으로 풀고자 했습니다!! 제 생각으로는 deque 의 최대 반복 되는 수가 처음 문자열의 크기를 넘지 않을 것 같아서 시간초과에 문제 없을 줄 알았는데 시간 초과가 나옵니다  어떠한 이유에서 시간초과가 나오게 되었는지 여쭤보고자 질문 드립니다!!  감사합니다! 코드https://www.acmicpc.net/source/64697159

http://boj.kr/6fd1c581d7154d70a7523d1151aec403제가 작성한 코드입니다. map을 이용하지 않고 풀긴했지만 답안과 크게 다른게 없다고생각하는데 틀렸다고 나옵니다왜 틀렸는지 알고 싶습니다! 감사합니다!

9996번 문제입니다#include <iostream> #include <vector> using namespace std; int N; string strPattern; vector<string> v; string input; int main() { cin >> N; cin >> strPattern; string left = ""; string right = ""; int index = 0; while (strPattern[index] != '*') { left += strPattern[index]; ++index; } index = strPattern.find('*') + 1; right = strPattern.erase(0, index); for (int i = 0; i < N; ++i) { cin >> input; v.push_back(input); } for (int i = 0; i < v.size(); ++i) { // +ADD if (left.size() + right.size() > v[i].size()) { cout << "NE" << endl; continue; } // string leftcopy = v[i]; string rightcopy = v[i]; if (left.size() <= leftcopy.size()) leftcopy = leftcopy.erase(left.size(), leftcopy.size() - 1); if (right.size() <= rightcopy.size()) rightcopy = rightcopy.erase(0, rightcopy.size() - right.size()); if (leftcopy == left && rightcopy == right) cout << "DA" << '\n'; else cout << "NE" << '\n'; } return 0; }코드를 이렇게 작성하고 저쪽 주석 +ADD 부분이 없을때는 65% 에서 Fail 뜨고 저 ADD 부분을 추가했을때 성공이 떴습니다1a*aaaaaa일때 정답이 어떻게 되는지 설명 부탁드립니다!제가 생각했을때는 DA 같습니다!   

안녕하세요 선생님!항상 좋은 강의 감사히 잘 듣고 있습니다.이번 문제에서 제 코드로는 4번 문제가 계속 틀렸다고 나와서 선생님 코드 그대로 따라했는데도 4번 문제가 틀렸다고 되더라구요... 채점기 output이 잘못된건지 제가 짠 코드가 잘못된건지 확인 부탁드립니다...! 제 코드#include <stdio.h> #include <cmath> int n; int a[11]; int b[100]; int c[1025]; int sum; int idx = 1; void DFS(int x) { if(x == n+1) { sum = 0; for(int i = 1; i <= n; i++) if(b[a[i]] == 1) sum += a[i]; c[idx++] = sum; } else { b[a[x]] = 1; DFS(x+1); b[a[x]] = 0; DFS(x+1); } } int main() { scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); DFS(1); for(int i = 1; i <= pow(2, n); i++) { int temp = c[i]; if(temp == 0) continue; for(int j = 1; j <= pow(2, n); j++) { if(i == j) continue; if(temp == c[j]) { printf("YES"); return 0; } } } printf("NO"); return 0; }선생님 코드#include <stdio.h> int n; int a[11]; int total = 0; bool flag = false; void DFS(int x, int sum) { if(sum > (total/2)) return; if(flag) return; if(x == n+1) { if(sum == (total/2)) { flag = true; } } else { DFS(x+1, sum+a[x]); DFS(x+1, sum); } } int main() { scanf("%d", &n); for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); total += a[i]; } DFS(1, 0); if(flag) printf("YES"); else printf("NO"); return 0; }