묻고 답해요
141만명의 커뮤니티!! 함께 토론해봐요.
인프런 TOP Writers
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
mod11 개념문제 백트래킹 질문드립니다.
큰돌님 안녕하세요.3주차 문제들을 풀던 중 의문점이 생겨서 질문드립니다.3주차 개념강의 때 합을 mod 11한 숫자 중 가장 큰 수를 구하는 예시문제가 있었습니다.이 문제를 아래와 같은 방법으로 재귀를 통해 각 숫자별로 더할지 말지로 나눠서 숫자가 {1,2,3}인 경우는 총 경우의 수가 8이 된다고말씀하셨습니다.go(idx + 1, sum + v[idx]); go(idx + 1, sum); 그런데 3주차 문제들을 풀던 도중 백트래킹을 쓰는 경우와 이렇게 재귀로 현재 위치를 하나씩 증가시켜가며 포함하는지 안하는지를 체크해가며 완전탐색을 돌리는 경우가 같은 경우가 아닌가 하는 의문점이 들었습니다(둘 다 모든 경우를 따지는 것이기 때문입니다).그래서 개념강의 예시문제를 다시 백트래킹으로 풀어보았는데 {1,2,3}인 경우에서 8번의 경우를 따져야 하는데 경우의 수를 4번만 도출해는 것을 확인하였습니다. 아래는 백트래킹으로 구현한 mod 11 문제입니다.#include<bits/stdc++.h> using namespace std; const int mod = 11; int n, temp, cnt, ret; vector<int> v; void go(int idx, int sum){ if(idx == n){ ret = max(ret, sum % mod); cnt++; return; } for(int i = idx; i < n; i++){ sum += v[i]; go(i + 1, sum); sum -= v[i]; } // 설명해주신 방식 // go(idx + 1, sum + v[idx]); // go(idx + 1, sum); } int main(){ cin >> n; for(int i = 0; i < n; i++){ cin >> temp; v.push_back(temp); } go(0, 0); cout << ret << '\n'; cout << cnt << '\n'; }코드를 하나하나 디버깅해가며 체크해보면서 왜 4번만 경우를 구하게 되는지는 알게 되었는데,개념적으로 백트래킹이라는 개념이 모든 경우의 수를 구하는 것이고, 기존에 풀었던 방법인 idx를 증가시키면서 해당 위치의 숫자를 더할지 말지를 구하는 것도 모든 경우의 수를 구하는 것이라서 두 경우의 문제 접근할 때의 사고방식이 같다고 생각하는데 왜 백트래킹은 안되는 것인가요? 두 경우의 차이점이 너무 헷갈립니다 ㅠㅠ
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
7-F void go(int here)코드 질문드립니다
void go(int here){ if(here == 0) return; printf("%d ", here); if(here % 3 == 0 && dp[here] == (dp[here / 3] + 1)) go(here / 3); if(here % 2 == 0 && dp[here] == (dp[here / 2] + 1))go(here / 2); if((here - 1 >= 0) && (dp[here] == (dp[here - 1] + 1))) go(here - 1); return;}왜 이렇게 하면 안되나요?
-
해결됨[파이썬/Python] 문과생도 이해하는 DFS 알고리즘! - 입문편
graph, visited 사이즈 관련 문의
graph, visited의 사이즈를 다음 코드와 같이 노드 개수에 맞게 (n+1)로 하면 되겠다고 생각했는데, 노드 개수의 최댓값인 1000을 이용해 사이즈를 정하신 이유가 무엇인가요??graph = [[False]*(n+1) for _ in range(n+1)] visited = [False]*(n+1)
-
미해결자바 코딩테스트 - it 대기업 유제
cpu스케쥴링 질문드립니다.
import java.io.*; import java.util.*; public class Main { public int[] solution(int[][] tasks){ int[] answer = {}; int n=tasks.length; PriorityQueue<int[]> q = new PriorityQueue<>((a,b) ->a[0]==b[0] ? a[1] - b[1] : a[0] - b[0]); LinkedList<int[]> list = new LinkedList<>(); int i=0; for(int[] x :tasks) { list.add(new int[] {x[0],x[1],i}); i++; } answer = new int[n]; list.sort((a,b) ->a[0]-b[0]); int ft=0; for(int idx=0; idx<n; idx++) { if(q.isEmpty()) ft = Math.max(ft, list.peek()[0]); while(!list.isEmpty() && list.peek()[0]<=ft) { //ft를 맨 처음 값으로 만들어주고 int[] x = list.pollFirst(); q.add(new int[] {x[1],x[2]}); //실행시간이랑 작업번호 대입 } int[] ex = q.poll(); ft+=ex[0]; answer[idx] = ex[1]; } return answer; } public static void main(String[] args){ Main T = new Main(); System.out.println(Arrays.toString(T.solution(new int[][]{{2, 3}, {1, 2}, {8, 2}, {3, 1}, {10, 2}}))); System.out.println(Arrays.toString(T.solution(new int[][]{{5, 2}, {7, 3}, {1, 3}, {1, 5}, {2, 2}, {1, 1}}))); System.out.println(Arrays.toString(T.solution(new int[][]{{1, 2}, {2, 3}, {1, 3}, {3, 3}, {8, 2}, {1, 5}, {2, 2}, {1, 1}}))); System.out.println(Arrays.toString(T.solution(new int[][]{{999, 1000}, {996, 1000}, {998, 1000}, {999, 7}}))); } }while(!list.isEpmty() || !q.isEmpty()){}이렇게 생각을 못할 거 같아서그냥 애초에 for(int idx=0; idx<n; idx++){}로 바꿨습니다.답을 똑같이 나오는데, 이렇게 작성해도 상관없는건가요??
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
안녕하세요 목차관련 궁금한점이있어서 문의합니다.
혹시 union - find, disjoint set은 어디에 나와있을까요?
-
미해결[입문편] 안드로이드를 위한 코틀린(Kotlin) 문법
when 버전으로도 알려주세요!
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. else if 문 말고 when 버전으로도 알려주시면 좋을 것 같아요
-
해결됨[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편
유기농배추에서 T는 무엇을 의미하나요?
T, M, N, K를 입력받아 사용한다고 하셨는데, M과 K는 각각 세로와 가로값으로 입력받고, K는 배추의 위치라는것을 알았습니다. 근데 T는 테스크케이스 라는 언급을 하셨고 코드에서도 아래와 같이 작성되있습니다.while (T-- > 0) { StringTokenizer st = new StringTokenizer(br.readLine()); M = Integer.parseInt(br.readLine()); N = Integer.parseInt(br.readLine()); K = Integer.parseInt(br.readLine()); // map 정보 // dfs 수행 .... }2번의 테스크케이스를 만드는 이유는 무엇인가요?그리고 단순히 궁금해서 여쭤보는데 가로와 세로 순서로 입력받고 코드를 실행하는것이 아닌 거꾸로 세로와 가로 순으로 실행하는지 궁굼합니다.답변 부탁드립니다. 감사합니다.
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
1-L 시간초과 질문
http://boj.kr/5633bd87bd1d49e28ec713fc1ed3da93재귀함수를 이용하여 풀었더니 시간초과가 납니다. nCr 에서 r이 작다면(r <= 3) 중첩 for문을 이용하는 게 더 빠른 건가요?
-
미해결자바스크립트 알고리즘 문제풀이 입문(코딩테스트 대비)
Set 자료형 사용
혹시 Set 자료형으로 중복을 제거하고 문자열로 만들어주는 방식으로 작성했는데 괜찮을까요 ?? <html> <head> <meta charset="UTF-8" /> <title>출력결과</title> </head> <body> <script> function solution(s) { let answer = ""; answer = [...new Set(s)].join(""); return answer; } console.log(solution("ksekkset")); </script> </body> </html>
-
해결됨10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
map 자료구조의 시간복잡도
블로그에서 map 자료구조의 시간복잡도가 전부 nlogn이라고 써있던데, 이게 맞나요?찾아보니 해쉬맵 종류는 전부 O(1)을 갖고 트리 맵은 logn을 갖던데, nlogn이 어떻게 나오는건지 궁금합니다.
-
해결됨[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편
촌수계산 문제 질문
안녕하세요.위의 코드는 제가 강의를 듣기 전에 작성한 코드입니다.백준에서 2가지로 주어진 테스트 케이스는 통과하는데 코드를 제출하면 틀렸다고 나옵니다.코드 어디가 잘못된지를 모르겠습니다.그리고 강의에서는 dfs 함수에 start 변수만 넣지 않고 count 변수도 넣으셨는데 count변수를 매개변수로 넣지 않고 코드를 작성하는 방법이 있는지 궁금하고, 이러한 방법이 없다면 왜 매개변수로 count 변수를 넣어줘야 하는걸까요?
-
미해결it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
20번 가위바위보 질문있습니다
처음에 아래와 같은 식으로 하드코딩 했는데, out으로 나오는 답이 메모장에 있는 답과 같은데 정답이 아니라고 떠서 질문 남깁니다.왜 틀린 건지 알 수 있을까요? #define CRTSECURE_NO_WARNINGS#include <stdio.h>int main(){ int n, input; int a[101], b[101]; scanf("%d", &n); for (int i = 0; i < n; ++i) { scanf("%d", &input); a[i] = input; } for (int i = 0; i < n; ++i) { scanf("%d", &input); b[i] = input; } for (int i = 0; i < n; ++i) { // a가 가위를 낸 경우 if (a[i] == 1) { if (b[i] == 1) { printf("D\n"); } else if (b[i] == 2) { printf("B\n"); } else { printf("A\n"); } } // a가 바위를 낸 경우 else if (a[i] == 2) { if (b[i] == 1) { printf("A\n"); } else if (b[i] == 2) { printf("D\n"); } else { printf("B\n"); } } // a가 보를 낸 경우 else if (a[i] == 3) { if (b[i] == 1) { printf("B\n"); } else if (b[i] == 2) { printf("A\n"); } else { printf("D\n"); } } } return 0;}
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
안녕하세요! 큰돌님 질문있습니다!
2-O문제에서 공백이 포함된 문자열들을 여러개 입력받을때 풀이에서는 bufferflush를 안했는데 안해도 되는 이유가 있을까요?? 궁금해서 질문드립니다!2-O 해설코드입니다!#include <bits/stdc++.h> using namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); while(true){ string s; getline(cin, s); if(s == ".") break; stack<int> stk; bool check = true; for(int i = 0; i < s.length(); i++){ if(s[i] == ')'){ if(stk.size() == 0 || stk.top() == '['){ check = false; break; }else{ stk.pop(); } } if(s[i] == ']'){ if(stk.size() == 0 || stk.top() == '('){ check = false; break; }else{ stk.pop(); } } if(s[i] == '(') stk.push(s[i]); if(s[i] == '[') stk.push(s[i]); } if(check && stk.size() == 0) cout << "yes\n"; else cout << "no\n"; } return 0;}
-
미해결자바 코딩테스트 - it 대기업 유제
백준 <수확> 코드
public class Main { public static int solution(int[] value, int N) { int[][] dynamic = new int[N + 1][N + 1]; int[] sum = new int[N + 1]; for (int i = 1; i <= N; i++) { dynamic[i][i] = value[i]; } sum[1] = 1; for (int i = 2; i <= N; i++) { sum[i] = sum[i - 1] + value[i]; } for (int i = 1; i < N ; i++) { for (int j = 1; j <= N - i; j++) { dynamic[j][j + i] = Math.max(dynamic[j + 1][j + i], dynamic[j][j + i - 1]) + (sum[j + i] - sum[j - 1]); } } return dynamic[1][N]; } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int N = Integer.parseInt(st.nextToken()); int[] value = new int[N + 1]; for (int i = 1; i <= N; i++) { value[i] = Integer.parseInt(br.readLine()); } System.out.println(solution(value, N)); } }강사님, 안녕하세요! 강의 보고 구현한 코드인데, 백준에서 채점이 틀리게 나와서 혹시 로직이 틀린건지 궁금합니다. [해결 됐습니다!]1부터 n까지 합 저장하는 배열인 sum을 초기화하면서sum[1] = value[1] 을 해야 할 것을 sum[1] = 1; 로 잘못 초기화 했네요.우연히 테스트 케이스 value[1] 값이 1이어서 해당 답만 맞았던 것 같습니다.강의 보면서 실력이 늘고 있음을 느끼고 있습니다. 감사합니다:)
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
그리디에 대해서 질문있습니다
강의를 보는데 이해가 안되는부분이 있어 질문드립니다그리디 문제의 경우는 실제로 해당경우에 대한 모든 경우의수가 대입된다면 임의의 해답논리를 이용해서 푼 경우가 진짜 정답은 아닐 수 있으나 문제에서 제시되는 테스트케이스는 해당 논리에대해서는 참 이라는 조건이 제시되는 문제로만 구성되있다고 생각하면 되는걸까요?
-
미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
뮤직비디오
안녕하세요 선생님! 다름이 아니라 저는 최소용량크기를 곡들의 분을 더한 값 M으로 나눈걸로 시작했는데 안되는 걸까요? 채점사이트에서는 성공했는데 혹시 그렇게 시작하면 안되는 이유가 있을지 궁금해서요!
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
반례 찾아주세요ㅜㅜ
안녕하세요 강사님 강의 잘 듣고 있습니다.강사님 강의를 보기 전에 제가 스스로 풀었던 내용입니다.https://www.acmicpc.net/source/66606871문제의 예시와 첫 글자 z도 다 잘 출력 되었는데 어디서 실패하는건지 모르겠어서 여쭤봅니다...!
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
lower_bound 에 교안과 다른 숫자로 변경하면
처음에는 교안과 동일한 숫자를 넣어봤다가 다르게 숫자를 넣어봤는데.. lower_bound는 그대로 2고 upper_bound는 2로 변해버립니다.. 왜그런걸까요? 그리고 주소값도 변하지가 않습니다.. 실행환경때문에 그런걸까요?그리고 typedef long long 11을 적으면 error: expected unqualified-id before numeric constant 라는 에러가 발생합니다..(그래서 아래 코드보면 안적혀있어요)그리고 제가 이해한것이 맞는지 알려주시면 감사하겠습니다. 교안기준 주소값을 기반으로 몇번째 요소인지를 뽑아낼 수 있다고 적혀있는데 그말은 곧 "0xd21518 - 0xd21510 = 8 이 나오는데, int형이니까 4바이트가 두개와 같으니 2번째 인덱스를 의미한다 " 라고 이해했습니다.. #include <bits/stdc++.h> using namespace std; int main(){ vector<int> a {1,2,5,6,7,3,3,3,4}; cout << lower_bound(a.begin(), a.end(), 3) - a.begin() << "\n"; cout << upper_bound(a.begin(), a.end(), 3) - a.begin() << "\n"; cout << &*lower_bound(a.begin(), a.end(), 3) << "\n"; cout << &*a.begin() << "\n"; cout << &*(a.begin() + 1) << "\n"; return 0; } /* 실행결과 2 2 0xe71d68 0xe71d60 0xe71d64 */
-
미해결입문자를 위한 코딩테스트 핵심(이론과 문제풀이) [Python]
이렇게 풀어도 돼나요?
안녕하세요 강사님. 수업 너무 잘 듣고 있습니다.궁금한게 있어 질문 드립니다.제가 딕셔너리를 이용해서 아래와 같이 풀었는데 강사님 코드를 보니 너무 깔끔하더라구요."from collections import defaultdictdef solution(nums, target): answer = [0]*2 dicts = defaultdict(int) for i in nums: dicts[i]=target-i for i in dicts: if i in nums and dicts[i] in nums and i!=dicts[i]: return [min(i,dicts[i]),max(i,dicts[i])] return answer"이렇게 IF문 안에 여러 조건들을 넣어서 풀어도 시간 복잡도가 O(N^2)이 안되고 O(N)이 될까요??
-
미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
중복문자 제거 질문
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.import java.util.Arrays;import java.util.List;import java.util.Scanner;public class Main { public String solution(String str) { String[] arr = str.split(""); List<String> list = Arrays.asList(arr); List<String> resultList = list.stream().distinct().toList(); StringBuilder answer = new StringBuilder(); for (String s : resultList) { answer.append(s); } return answer.toString(); } public static void main(String[] args) { Main T = new Main(); Scanner kb = new Scanner(System.in); String str = kb.nextLine(); System.out.println(T.solution(str)); }} 위 코드가 저의 개발환경에서는 돌아가는데 채점서비스에서는 컴파일에러가 뜹니다ㅜ원인을 잘 모르겠습니다.
