묻고 답해요
141만명의 커뮤니티!! 함께 토론해봐요.
인프런 TOP Writers
-
해결됨10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
2%만 맞고 틀리네요..
https://www.acmicpc.net/source/67720015제 알고리즘에 강사님코드를 추가했습니다.bfs를 main에서 사용할 생각을 처음엔 못하고 불의위치만 bfs코드를 따로 떼어내서 구현한 것 빼고는비슷합니다..
-
해결됨2주만에 통과하는 알고리즘 코딩테스트 (2024년)
백준 2503 숫자야구 문제 어떤 부분이 잘 못되었는지 모르겠습니다
강의를 본 후에 아래와 같이 코드를 작성한 후백준에 제출했는데 왜 틀렸는지 이유를 모르겠습니다 N= int(input()) hint = [list(map(int,input().split())) for _ in range(N)] answer =0 for a in range(1,10): for b in range(10): for c in range(10): if(a==b or b==c or a==c): continue cnt =0 for arr in hint: number = list(str(arr[0])) ball = arr[1] strike = arr[2] ball_count = 0 strike_count =0 if(a== int(number[0])): strike_count+=1 if(b== int(number[1])): strike_count+=1 if(c== int(number[2])): strike_count+=1 if(a== int(number[1]) or a == int(number[2])): ball_count+=1 if(b== int(number[0]) or b == int(number[2])): ball_count+=1 if(c== int(number[1]) or c == int(number[0])): ball_count+=1 if ball_count == ball and strike_count == strike: cnt += 1 if cnt == N: answer=+1 print(answer)
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
4-E 반례 질문드립니다.
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. http://boj.kr/39c15e9338ad4585955d4d9f7453c741 나름의 방법대로 구현해봤는데, 반례를 찾기 어려워 질문드립니다. 좋은 강의 감사드립니다!
-
미해결자바스크립트 알고리즘 문제풀이 입문(코딩테스트 대비)
삼항연산자를 이용해서 풀어 보았습니다
삼항 연산자를 이용하여 가장 큰 수 를 구하고, 전체 수를 더한값을 뺀 후 나머지 2개의 숫자의 합을 구해서 비교하여 "YES"와"NON"를 구해 보았습니다.<!-- 삼각형 판별하기 --> <html> <head> <meta charset="UTF-8" /> <title>출력결과</title> </head> <body> <script> function solution(a, b, c) { let answer; const longLine = a > b ? (a > c ? a : c) : b > c ? b : c; const totalLine = a + b + c; const remainder = totalLine - longLine; answer = longLine < remainder ? "YES" : "NO"; return answer; } console.log(solution(7, 5, 2)); </script> </body> </html>
-
해결됨[파이썬/Python] 문과생도 이해하는 DFS 알고리즘! - 입문편
백준 11724 연결 요소의 개수 문제
선생님 안녕하세요일단 너무 만족스러운 강의 준비해주셔서 감사하고 정말 돈이 하나도 아깝지 않은 강의입니다. DFS 강의 말고도 다른 알고리즘 강의도 준비해주시면 너무 좋을것 같아요 ㅠㅠ 아무튼 질문은요,선생님 강의를 듣고 아래처럼 제가 코드를 짰는데선생님 코드랑 몇번을 비교해도 다른 점이 보이질 않는데 백준에서 제출했을 때 계속 메모리 초과라고 나옵니다.혹시나 제가 바보같은 실수를 했을 수 있으니 미리 사과드립니다 ㅠㅠ!! 감사합니다 import sys sys.setrecursionlimit(10**6) N, M = map(int, sys.stdin.readline().split()) MAX = 1000 + 10 graph = [[False] * MAX for _ in range(MAX)] visited = [False] * MAX answer = 0 for _ in range(M): u, v = map(int, sys.stdin.readline().split()) graph[u][v] = True graph[v][u] = True def dfs(idx): visited[idx] = True for i in range(1, N + 1): if not visited[i] and graph[idx][i]: dfs(i) for i in range(1, N + 1): if not visited[i]: dfs(i) answer += 1 print(answer)
-
해결됨2주만에 통과하는 알고리즘 코딩테스트 (2024년)
[완전탐색] 1090번 문제 문의
안녕하세요. 강사님!완전탐색적방법으로 접근하는 방법을 익히고싶은데 이해하고 있는게 맞는지 궁금해서 질문남겼습니다!24:10분쪽 내용을 보면서 궁금한 내용이 있습니다! 만약에 x축[] 짱구:5, 철수:7 , 맹구:9 일때 문제 조건에 제시된 1 - 1_000_000까지 전체 순회를 하면서 1번 위치일때 짱구: 1 - 5, 철수 : 1 - 7, 맹구: 1 -9 2번 위치일떄 짱구: 2 - 5, 철수 : 2 - 7, 맹구: 2 -9 x[] 원소를 기준으로 쭉 1_000_000까지 모든경우의수를 다구하는게 맞는지 궁금합니다. 최적화 아이디어를 하기전 완전탐색적인 방법을 제대로 이해하고있는지 체크하기 위함입니다! 감사합니다!
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
4-D 매개변수로 넘기면 왜 안빼도 되는거죠?
ㅠㅠ
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
1-N 곱셈 모듈러 관련 문의드립니다.
안녕하세요:)본 문제의 재귀 함수(go 함수) 안에서, b가 홀수인 경우 ret = ret * a % c; 가 되어야 하는 부분에 대해 한번 더 %c 연산을 하지 않아도 되는지 문의드립니다. 예를 들어 (a^5)%c의 경우, [{(a^4)%c}{a%c}]%c 와 같다고 이해했습니다. 이때 b=5 이므로 if(b%2) 에 걸리는데, ret가 (a^4)%c 인 상황에서 (a%c)%c 만큼 추가로 곱해줘야 성립이 되는게 아닌지 궁금합니다!( 만일 (a^4)%c 에 (a%c) 만 곱한다면 그 값이 c 보다 커져서 나머지 연산을 한번 더 해야할 경우도 있지 않나요? ) 감사합니다 :)
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
1-A 일곱 난쟁이 next_permutation 코드 관련 질문드립니다
안녕하세요:)일곱난쟁이 문제에서 "결과값을 오름차순으로 출력" 해야하는 부분과 관련하여 문의드립니다.next_permutation을 활용하여 경우의 수를 뽑는 경우에, 앞에서 부터 7개 순열을 잘라서 보면 어떤 것은 오름차순으로 되어있지 않은데 혹시 만일 그러한 순열이 답이 되는 경우 sort로 정렬을 다시 안해줘도 되나요? 예를 들어, 본 문제 테스트케이스의 경우[ 7 8 10 13 19 20 23] 이라는 값이 딱 sum이 100인 경우여서 오름차순 그대로 값이 출력이 되지만.. 만약 [7 8 10 13 15 25 19] 가 답이었다고 가정한다면 .. 오름차순이 안되는게 아닌지 해서요! 감사합니다:)
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
3-Q 이렇게 하면 안되는 이유가 뭘까요
http://boj.kr/48d6be65693f4801bc29d65346739e1a
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
3-L 이렇게 풀면 왜 안될까요?
ㅠㅠhttp://boj.kr/4d01aaf298574b598ed3f4d4412788fc
-
해결됨10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
7-H 문제 다른방식 풀이 질문
안녕하세요 큰돌선생님. 해당문제를 재귀dp (탑다운) 방식으로 풀어봤는데 잘 풀리지 않아 질문드립니다. 우선 해당문제 조건에 더불어 그냥 동전의 종류를 1, 2, 5로 픽스를 한다고 가정하여 문제를 풀어보았습니다. #include <bits/stdc++.h> using namespace std; int N, dp[100][100][100]; int go(int n1, int n2, int n5, int num) { if (num == N) return 1; int &ret = dp[n1][n2][n5]; if (ret) return ret; if (num + 1 <= N) ret += go(n1 + 1, n2, n5, num + 1); if (num + 2 <= N) ret += go(n1, n2 + 1, n5, num + 2); if (num + 5 <= N) ret += go(n1, n2, n5 + 1, num + 5); return ret; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> N; cout << go(0, 0, 0, 0) << '\n'; return 0; }dp배열의 원소는 1, 2, 5원 동전의 개수로 잡았고, 동전의 값이 N이 되었을때 return 1을 해주고 경우의수 문제라서 더해주는 방식으로 문제를 풀어보았습니다. 혹시 어떤 부분이 잘못되었나요? 이전 7-E 문제와 유사한 방식으로 풀어보았습니다. 또한 추가로 만약 1, 2, 5원을 픽스하지 않고 해당 문제의 조건 그대로 문제를 해결한다면 선생님께서는 어떻게 문제를 해결하실지 궁금합니다.
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
정답코드 40번째 줄 지도 업데이트 시점에 대한 질문입니다!
http://boj.kr/5d7d83e1069547288f02236c01cc8d5a위는 정답 코드입니다! 40번째 라인에서 a(인구 지도)를 업데이트 하는 위치가 이중 for문을 벗어난 다음이 되어야 하는 것이 아닌지 문의 드립니다. 이중 for 문 안에서 지도를 업데이트 하게 된다면, 원래라면 이동이 불가능한 지역간의 이동이 가능하게 될것 같습니다. 예를 들어3 10 110 50 4040 20 300 0 0 위와같이 진행한다고 한다면dfs가 한번돌고 나면 지도가 다음과 같을것 같습니다0 35 3540 35 350 0 0 이 상태에서 다음 dfs를 돈다면0 36 3636 36 360 0 0이 되면서 하루만에 전부 통합되는 상태가 되지 않을까 싶습니다! 실제로 코드를 돌려보면3 10 110 50 40 40 20 30 0 0 01다음과 같이 나옵니다! 정답은 2여야 하지 않을까 싶어서 질문합니다!
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
3-D 불! 메모리 초과 질문 있습니다.
안녕하세요 큰돌님, 다름이 아니라 제가 영상에 나왔던 코드를 읽기 편하게 bfs 함수를 따로 함수를 만들어서 예제 입력을 받으면 프로그램이 잘 실행되는데, 제출을 하면 메모리 초과가 뜨네요, 혹시 어떻게 된 경우인지 여쭤보고 싶습니다. 미리 감사합니다!https://www.acmicpc.net/source/share/91f2eb33d6904a5ab55d7d851f317595
-
해결됨자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
오답처리 원인
import java.util.ArrayList; import java.util.Scanner; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] nums = new int[n]; Maininf = new Main(); ArrayList<Integer> answerList = inf.solution(nums); for (int i : answerList) { System.out.print(i + " "); } } public ArrayList<Integer> solution(int[] nums) { ArrayList<Integer> answerList = new ArrayList<>(); answerList.add(nums[0]); for (int i = 1; i < nums.length; i++) { if(nums[i] > nums[i-1]) { answerList.add(nums[i]); } } return answerList; } }위는 제 코드인데.. IDE에서는 결과가 잘 리턴되는데, 채점 사이트에서 리턴이 자꾸 0으로 나온다고 오답처리합니다..! 문제가 뭔지 모르겠습니다
-
미해결파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)
1.가장 큰 수 질문드립니다
안녕하세요 교수님강의 중 질문이 있어 글 작성드립니다.마지막에 m이 0보다 클 경우 뒤에서 자르셨는데 stack에 저장되는 값이 1번 예제 7823처럼 항상 내림차순은 아니라 다른 방법으로 풀이해야하지 않나요?
-
해결됨10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
메모리 초과 관련 문제
안녕하세요, 메모리 초과 관련 문제가 생겨서 질문드립니다.제가 생각한 알고리즘을 설명드리자면2중 벡터 fire의 경로를 구합니다. (bfs)2중 벡터 player의 경로를 구합니다. (bfs)fire와 player의 각 요소를 비교하여 player의 요소가 작은 경우엔 유지, 아닌 경우엔 -1로 값을 덮어씌웁니다.최종적으로 vector<vector<int>> player는 다음과 같은 값을 갖습니다.-1 -1 -1 2-1 -1 -1 1-1 -1 1 0-1 -1 -1 -1해당 player를 다시 bfs로 순회합니다. (시작점은 player의 초기 위치인 0 지점) -> 이걸 하는 이유는 혹여나 player의 길이 fire에 의해 끊기는 경우가 존재할 수 있으므로 입니다. (하지만 이런 경우는 발생하지 않는 것 같습니다.)마지막으로 player가 갈 수 있는 최종 길만 남게되고, 가장자리의 4변에서 -1이 아닌 최소값을 찾습니다.이런 알고리즘을 시행했는데 메모리 초과가 뜹니다. 메모리 초과와 관련해서는 visual studio에서 어떻게 디버깅을 해야할지 잘 모르겠습니다. 단순히 생각해보면 각 2차원 벡터는 최대 1000*1000*4byte(int)=4MB의 크기를 갖고, deque는 아마 최대로 해도 4MB 이하의 크기를 갖을 것 같은데 문제의 256MB가 왜 초과가 되는지. 모르겠습니다.아래는 해당 코드의 링크입니다.http://boj.kr/6145ffa1c073417ab06e3a7e86afe533 강의를 듣고나서는 코드를 수정하여 player의 경로를 구할 때, 미리 구해둔 fire의 경로와 비교하여 fire가 선점한 경우엔 갈 수 없는 경로로 표시하고, 순서 5의 과정을 삭제했습니다. 이러니 해결이 되긴하는데.. 이게 왜 되는건지는 모르겠습니다. 해당 코드는 메모리 10872KB를 썼다고 나옵니다.
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
5-B erase(), substr() 시간복잡도 질문드립니다.
안녕하세요 선생님.선생님께서 푸신 코드가 시간복잡도가 통과되지 않을 것이라 생각하였는데 통과하여 질문드립니다.제가 알기로는 substr(), erase() 함수 모두 자르고 당기는 작업이 들어가서 O(n)의 시간복잡도가 걸린다고 알고 있는데, 반례로 문자열이 100만이 모두 같은 알파벳으로 aaa...라고 하고 폭발 문자열이 a라고 한다면 반복문을 100만번 돌면서 매번 substr()과 erase()를 해주게 되어 100만 * (O(n) + O(n)) 이 되어 시간복잡도가 넘어가는 것 아닌가요? 이 경우에 substr()과 erase()가 둘다 한개의 문자(a)만 체크하기 때문에 상수시간으로 취급하여 최대 200만이 되어 문제가 안 생기는 것 같기는 한데 뭔가 시간복잡도를 빡세게 잡는 문제가 나온다면 이러한 접근으로 erase()와 substr()을 사용한다면 시간초과가 날 수도 있지 않을까 하는 고민이 생겨서 질문드립니다! substr()과 erase()를 사용해도 시간복잡도 고려에 문제가 없을까요? 이 코드는 제가 find()와 erase()를 사용하여 푼 경우입니다. 이 경우에도 반복문을 돌리고 매번 find()와 erase()를 쓰는데, find()도 동일하게 O(n)이 걸리니까 로직이 선생님께서 푼 것과 동일하다고 판단하였는데, 아래 로직은 시간초과가 떴습니다.#include<bits/stdc++.h> using namespace std; string s, a; int main(){ cin >> s >> a; while(true){ if(!s.size()){cout << "FRULA" << '\n'; return 0;} int flag = s.find(a); if(flag != string::npos){ s.erase(flag, a.size()); } else break; } cout << s << '\n'; }
-
미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
씨름 O(n)으로 풀었는데 런타임 에러가 떠요
package GreedyAlgorithm;import java.util.*;public class SsireumSelection {static Scanner sc = new Scanner(System.in); static ArrayList<Body> athlete = new ArrayList<>(); static int n = sc.nextInt(); static int answer; static int maxWeight=Integer.MIN_VALUE; public static void main(String[] args) {for (int i = 0; i < n; i++) {athlete.add(new Body(sc.nextInt(), sc.nextInt())); }Collections.sort(athlete); for (Body b : athlete) {if (b.weight > maxWeight) {answer++; maxWeight=b.weight; }}System.out.println(answer); }public static class Body implements Comparable<Body> {public int height; public int weight; public Body(int height, int weight) {this.height = height; this.weight = weight; }@Override public int compareTo(Body o) {return o.height - this.height; }}}90ms~126ms, 26mb 나옵니다
-
해결됨10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
7-E 수업질문
안녕하세요 큰돌 선생님 좋은강의 항상 감사합니다. dp문제를 계속 풀고있는데, 아직까지 문제를 처음 보았을때 메모이제이션을 어떻게 걸어야 하는지, 무슨값을 반환해야하는지 등에 대해서 많이 헷갈려서 질문드립니다. 해당 7-E번 문제를 그냥 완탐으로는 풀 수 있겠는데 어떻게 메모이제이션을 해야하는지 잘 모르겠습니다. '메모이제이션을 건다' 의 정확한 의미가 무엇인가요? 또한 그냥 완탐으로 풀었을때 시간복잡도가 너무 크면 메모이제이션을 걸어서 시간복잡도를 줄인다는 큰 틀은 알겠는데, 좀더 자세한 생각의 흐름이 궁금합니다. 어떤 매개변수를 dp배열의 인자로 가져야 하는지 등이 헷갈립니다. 다음 아래는 해당 문제를 완탐으로 푼 코드입니다. 이렇게 완탐으로는 해결하겠는데 그 다음 이 코드에 메모이제이션을 적용하는 세세하고 자세한 흐름이 궁금합니다. #include <bits/stdc++.h> using namespace std; int N, ret; void go(int whole, int not_whole) { if (whole == 0 && not_whole == 0) { ret++; return; } if (whole > 0) go(whole - 1, not_whole + 1); if (not_whole > 0) go(whole, not_whole - 1); } int main() { cin >> N; go(N, 0); cout << ret << '\n'; return 0; }
