173만명의 커뮤니티!! 함께 토론해봐요.
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
http://boj.kr/be195db38890481b9ca7ef38e786651e 선생님의 코드와 다른 부분은 스택을 매번 재선언하지 않고 재활용 할 수 있게 비워둔다는 점 뿐인 것 같습니다. gcc로 컴파일 했을 때, 2회 이상의 입력에서 2회차 반복 시에 아무런 출력도 하지 않고 그대로 프로그램이 강제 종료됩니다. 백준에는 런타임 에러라고 뜨는데, 입력과 관련된 문제일까요? 아니면 스택을 재선언 하지 않고 매번 비워두는 코드에서 런타임 에러가 발생한 것일까요..? 조언이 필요합니다. 감사합니다.
해결됨
[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편
안녕하세요! 강의를 다 듣고, 블로그에 남겨주신 문제들을 풀어보고 있습니다. '백준 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(); } }
미해결
it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
#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이 나옵니다. 혹시 왜 이렇게 나오는지 알려주실 수 있나요...?
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. https://www.acmicpc.net/source/64767474 안녕하세요. dfs를 안쓰고, 연결하는거 체크를 해보았는데.. 예제는 전부 통과하는데 오답이 나오네요.. 이유가뭘까요??
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
http://boj.kr/36b07be654c44bf9ac885bc8f1726452 예시 코드도 맞고, 제 생각에는 맞는 코드인 것 같은데 어느 부분에서 틀린 건지 잘 모르겠습니다. 예외 테스트케이스가 있을까요?
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
이런식으로 코드를 구성하였습니다 해당 부분에서 이전수업에서 들었던 모듈러연산은 최종결과에서 하는것과 중간에 모듈러연산이 사칙연산에 의해서 같이 계산되는게 결과가 같다고 기억하여 이런식으로 구성하였는데 맞는걸까요? 정답은 같은것같은데 테스트케이스가 따로있진 않은 예제라 혹시나하여 질문드립니다
해결됨
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
안녕하세요, 3-B가 최단거리를 구하는 문제이기에 BFS를 활용한 것까지는 이해가 됐습니다! 그런데 이 문제가 왜 완전탐색 파트로 분류되어 있는지 궁금합니다. 일반적인 BFS 문제들과 다르게 모든 경우에 대해 BFS 탐색을 하고, 매 탐색마다 원복을 해줘야 하기 때문에 완전탐색 문제로 분류된 것인가요?
해결됨
코딩테스트 [ ALL IN ONE ]
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 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보다 차수가 더 높은걸로 이해하면 될까요? 감사합니다!
해결됨
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
http://boj.kr/54cbfbf55f6946edbeb3beb93d88f6bc 안녕하세요 강사님! 여태 틀린 문제 다시 한번 풀어보고 있습니다. 백조 문제에서 메모리 초과가 나서 제가 생각하기에 의심되는 부분들 (queue에 중복 좌표를 여러번 푸시하는 경우)을 없애고도 메모리 초과가 나길래 어느 부분이 문제일지 한번 봐주시면 감사하겠습니다.. 로직 자체는 강사님 코드와 거의 비슷하게 떠올린 것 같은데 2차원 배열을 너무 많이 쓴 것이 문제인지.. 특정 케이스에서 queue가 너무 커지는 것이 문제일지 잘 감이 안 옵니다 ㅜ
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
안녕하세요! 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; }
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
http://boj.kr/44c6637eb356484a8f22139b8d4f217e 링크를 잘못올려서 다시 올립니다ㅜㅜ 답안에는 map을 이용해서 풀었는데 이 방법으로해도 크게 문제없는것 같은데 왜 틀렸다고 나오는지 알고 싶습니다! 감사합니다
미해결
입문자를 위한 코딩테스트 핵심(이론과 문제풀이) [Python]
자바 코테 이어서 파이썬 강의까지 듣고있습니다 :) 혹시 출처 남기고 블로그 및 깃에 올려서 될까요!
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
만약에 m이 3이고 치킨집이 5개면 5C1인 경우 5C2, 5C3인 경우의 조합들을 다 구해서 각각의 경우에 대한 치킨 거리를 계산한 후 최종적인 최솟값을 구하는 문제인 줄 알았습니다. 예시) 5C1 이면 m=3이니까 {0} -> 각 집들의 치킨 거리를 구한 후 더한 값 {1} 위와 같음 {2} 위와 같음 {3} 위와 같음 {4} 위와 같음 5C2 이면 {0,1} {0,2} {0,3} . . . 이렇게 전부의 경우에 대한 거리 값을 구한 후 최소를 찾는 건 줄 알았는데 위의 방법이 아니라 그냥 m=3이면 5C3의 조합들 중에서 최소가 나오는 경우를 구하면 되는 건가요?? 제가 문제를 잘 이해를 못하는 것 같아서 질문 드립니다!!
해결됨
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
안녕하세요 큰돌님 1 - M 3986 좋은 단어 문제를 deque 를 이용해 deque 이 비거나 하나만 남을 때까지 반복하면서 back 과 다음 back 이 같은 경우 두 개의 back 을 모두 제거하고 아닌 경우 첫번째 꺼낸 back 을 다시 front로 push 하는 방식으로 풀고자 했습니다!! 제 생각으로는 deque 의 최대 반복 되는 수가 처음 문자열의 크기를 넘지 않을 것 같아서 시간초과에 문제 없을 줄 알았는데 시간 초과가 나옵니다 어떠한 이유에서 시간초과가 나오게 되었는지 여쭤보고자 질문 드립니다!! 감사합니다! 코드 https://www.acmicpc.net/source/64697159
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
http://boj.kr/6fd1c581d7154d70a7523d1151aec403 제가 작성한 코드입니다. map을 이용하지 않고 풀긴했지만 답안과 크게 다른게 없다고생각하는데 틀렸다고 나옵니다 왜 틀렸는지 알고 싶습니다! 감사합니다!
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
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 부분을 추가했을때 성공이 떴습니다 1 a*aaa aaa 일때 정답이 어떻게 되는지 설명 부탁드립니다! 제가 생각했을때는 DA 같습니다!
해결됨
it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
안녕하세요 선생님! 항상 좋은 강의 감사히 잘 듣고 있습니다. 이번 문제에서 제 코드로는 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; }
해결됨
SQL 코딩테스트를 위한 첫 걸음
설명이 너무 생략되어 있어서 이해가 안됩니다. 깃헙을 처음 써보는데 중간에 생략한 부분이 많네요. 윈도우 환경에서 다시 상세히 설명 부탁드립니다.
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
제가 짠 코드가 예제출력은 맞게 나오는데 제출했을 때 틀렸다고 나옵니다. 강의 보기 전에 짠거라서 강사님과는 다른 방향으로 풀었지만 어디서 잘못됐는지 궁금합니다. #include <iostream> #include <string> using namespace std; string s; int mo[21]; int cnt; int main(){ while(true){ cin >> s; cnt=0; if(s == "end") break; //s가 높은 품질이 아니면 //1번째 조건 if(s.find('a') && s.find('e') && s.find('i') && s.find('o') && s.find('u') > 20){ cnt += 1; } //2번째 조건 fill(&mo[0], &mo[0]+21, 0); for(int i=0; i<s.size(); i++){ if(s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u'){ mo[i] = 1; } else{ mo[i] = 2; } } if(s.size()>=3){ for(int i=0; i<s.size()-2; i++){ if(mo[i] == mo[i+1] && mo[i+1] == mo[i+2]){ cnt+=1; } } } //3번째 조건 for(int i=0; i<s.size(); i++){ if((s[i] == s[i+1]) && s[i] != 'e' && s[i] != 'o'){ cnt += 1; } } //cnt가 1이라도 있으면 낮은 품질 if(cnt>=1){ cout << "<" << s << "> is not acceptable." << '\n'; } //그렇지 않으면 높은 품질 else{ cout << "<" << s << "> is acceptable." << '\n'; } } return 0; }
미해결
10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 예제는 통과되었는데 틀려서 어디가 틀렸는지 계속 찾아보았지만 못 찾아 질문 남깁니다. http://boj.kr/1e440eca5c9e4ac69c978a0f9289603b
