묻고 답해요
131만명의 커뮤니티!! 함께 토론해봐요.
인프런 TOP Writers
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
1-E질문입니다!
안녕하세요 강사님!질문이 많은데도 항상 답글 달아주셔서 감사합니다.http://boj.kr/db4f11ea95744e9598cedb54483b9800 // s.substr(0, 1)은 11행에 있습니다.저는 입력한 string형 s에서 첫번째 문자를 추출하고 싶을때, s[0]이 아닌 s.substr(0, 1)을 사용하고 싶었습니다.그러하였더니 타입이 맞지 않는다고 컴파일 에러가 떠서 int(s.substr(0, 1))로 바꾸어서 실행시켜봤지만 타입이 맞지 않는다고 컴파일 에러가 다시 떴습니다.s.substr(0, 1)은 char형인데 이것을 정수형으로 바꾸고 싶을때는 int(s.substr(0, 1)) 로 하는게 맞는건가요?s.substr(0, 1)을 이 문제에서 사용하지 못하는 이유가 있다면 이유가 무엇일까요?
-
해결됨코딩테스트 [ ALL IN ONE ]
self
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.노드를 구현할때, 함수의 변수안에 self가 있는데 이게 어떤 역할을 하는지 궁금합니다.
-
미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
DFS -1번문제(아마존)
안녕하세요 교수님질문은 아래 코드와 함께 표시해 두었습니다.import java.util.*; class Main { static int n;static int[] graph; //전체집합static int total=0; public String DFS(int val, int s) { //graph[0]부터 시작if(val==n) {if((total-s) == s)return "YES"; //이부분에서 RETURN이 제대로 이루어 지지 않는 이유가 궁금합니다. } else { DFS(val+1,s+graph[val]); DFS(val+1,s); } return "NO";} public static void main(String[] args) {Main tree=new Main();Scanner scanner=new Scanner(System.in);n=scanner.nextInt();graph=new int[n]; for(int i=0; i<n; i++) {graph[i]=scanner.nextInt();total+=graph[i];} System.out.print(tree.DFS(0,graph[0])); //graph[0]부터 시작 } }
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
3-L 틀린 부분 피드백 부탁드립니다.
안녕하세요 큰돌님!강의 잘 보고 있습니다! 3-L 문제를 혼자 해내려고 했다가 문제가 생겨서 이렇게 질문글을 드립니다.https://www.acmicpc.net/submit/1987/56715364 int 형의 dfs함수, go()를 짜보려고 노력했습니다.그런데 테스트 케이스에 대한 예제 결과는 잘 나오지만, 자꾸 문제 제출 결과는 틀렸다고 나옵니다. 어디서 잘 못 꼬인 것인지 로직 오류 같은데, 제 머리로는 이해가 되지 않아서 이렇게 피드백 부탁드립니다..! <참고>ret으로 노드마다 방문하였을 때 1씩 쌓이도록 ret+=go(ny, nx)했구요.continue 조건으로 alpha에서 겹치는 노드는 아예 배제하도록 하여서 한방에 찾고 싶었습니다..
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
1-A문제 순열재귀함수 질문입니다.
안녕하세요 강사님!일곱난쟁이문제를 순열로 풀 때 순열의 방법으로 do-while permutation와 재귀함수가 있습니다.이 중, 일곱난쟁이문제를 순열의 재귀함수를 통해서 푸는 방법으로 풀고 싶어서 풀다가 어느 코드의 구현이 잘못 된지를 몰라서 질문 드립니다.http://boj.kr/ad5d9ed01b4c433cadf0e458aad20a09
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
17071번 메모리 초과
안녕하세요 큰돌 선생님! 궁금한게 있어 문의 드립니다.https://www.acmicpc.net/source/56686984선생님 코드와 같게 작성했지만 visited 배열의 turn 부분을 다르게 작성했습니다.선생님의 코드는 아래와 같고요visited[turn%2][nx]= visited[(turn+1)%2][x]+1;제가 작성한 코드는 아래와 같습니다.visited[(turn+1)%2][nx]= visited[turn%2][x]+1;현재 시간의 위치는 x이고, nx로 갈때의 시간은 +1 증가할 것이므로 이렇게 작성했는데 왜 메모리 초과가 났는지 알 수 있을까요?항상 좋은 답변 감사드립니다!
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
6-J 놀이공원 문제 질문
안녕하세요 강사님.풀이관련해서 질문인데요. 이분탐색으로 최소 시간을 구하는 것까지 이해했는데요.(ret - 1)에 대해서 다시 구하는게 잘 이해가 안되서요 ㅜ.N명이 모두 탈 수 있는 최소 시간이 ret이고,그보다 1분 전시간에 탈 수 있는 인원을 구해서 N번 아이가 탈 때의 놀이기구 번호를 구하는 거로 이해하면 될까요?
-
미해결자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
친구인가?(Union&Find) 첫 case1에서 타임리밋뜨는 이유
채점 결과 태스트 케이스2~5까지는 정답으로 나옵니다.4개 모두 200ms안에 끝납니다반면에 가장 테스트 케이스 크기가 작을 case1에서는 타임리밋이 뜹니다이유는 무엇이고 해결책은 무엇일까요?import java.util.*; public class Main { static String answer = "NO"; static int N,M; static int[] ch,dis; public void BFS(int t1, int t2, ArrayList<ArrayList<Integer>> arr) { Queue<Integer> Q = new LinkedList<>(); Loop:for(int i = 1;i<=N;i++) { if(ch[i] == 0) { Q.offer(i); while(!Q.isEmpty()) { int tmp = Q.poll(); ch[tmp] = 1; dis[tmp] = 1; if(dis[t1] == 1 && dis[t2]==1) { answer = "YES"; break Loop; } int len = arr.get(tmp).size(); for(int j = 0;j<len;j++) { int n = arr.get(tmp).get(j); Q.offer(n); } } Arrays.fill(dis, 0); } } } public static void main(String[] args){ Scanner in=new Scanner(System.in); N = in.nextInt(); M = in.nextInt(); ch = new int[N+1]; dis = new int[N+1]; ArrayList<ArrayList<Integer>> arr = new ArrayList<>(); for(int i = 0;i<=N;i++) { arr.add(new ArrayList<Integer>()); } for(int i = 0;i<M;i++) { int a = in.nextInt(); int b= in.nextInt(); arr.get(a).add(b); } int t1 = in.nextInt(); int t2 = in.nextInt(); Main T = new Main(); T.BFS(t1, t2, arr); System.out.print(answer); } }
-
해결됨자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비
타임 리밋이 일어나는 이유를 모르겠습니다.
혼자 풀어봤을 때, 다음과 같은 코드를 작성하였는데요.타임리밋이 일어날 만한 곳이 while문밖에 없는거같아서 계속 보는데 이유를 모르겠습니다.첫 요소가 K만큼 들어왔으면 그 다음부터는 1번씩만 put하니까 괜찮을 것이라 생각했는데 어떠한 이유로 타임리밋이 뜨는걸까요 ㅠㅠ?public static String solution(int n,int k,int[] arr) { String answer =""; HashMap<Integer,Integer> map = new HashMap<>(); // 매출의 종류 => HashMap & Sliding Window int lt=0; for(int rt = 0;rt<=(n-k);rt++) { while(lt-rt<k&<<n) { map.put(arr[lt], map.getOrDefault(arr[lt],0)+1); lt++; } answer += map.size()+" "; if(map.get(arr[rt])>1) { map.put(arr[rt], map.get(arr[rt])-1); }else { map.remove(arr[rt]); } } return answer; }
-
해결됨it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비
테스트 케이스 질문
#include <iostream> #include <vector> using namespace std; int main() { freopen("input.txt", "rt", stdin); int s, n, i, j, tmp, idx; scanf("%d%d", &s, &n); vector<int> a(n); for (i = 0; i < n; i++) { scanf("%d", &tmp); if(i < s) a[s-1-i] = tmp; else { idx = s; for (j = 0; j < s; j++) { if(a[j] == tmp) { idx = j; break; } } for (j = idx - 1; j >= 0; j--) a[j+1] = a[j]; a[j+1] = tmp; } } for (i = 0; i < s; i++) printf("%d ", a[i]); return 0; }이렇게 작성했는데 채점 폴더 전부 통과하는데 만약 입력이 5 51 2 2 3 4 이 들어왔다면 출력이4 3 2 2 1로 출력 되니까 위의 코드는 틀린 코드 같은데 맞나요???
-
미해결파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)
섹션 4 -> 그리디 , 결정문제 질문
안녕하세요! 강의 정말 잘 듣고 있습니다.섹션 4를 풀다가, 어떤 문제를 그리디를 쓰고, 어떤문제를 결정알고리즘을 써야하는지 감이 잡히지 않아서 질문 드립니다. 답변해주시면 정말 감사하겠습니다!
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
3-G번 질문있습니다.
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 3-G 문제에서 정점에 이미 방문한 경우(현 정점 거리 +1 == 다음 정점 거리) 인 경우만 체크해주는데(현 정점 거리 +1 < 다음 정점 거리) 인 경우는 존재하지 않아서 체크하지 않는 건가요??궁금해서 질문드립니다. 감사합니다.
-
미해결파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)
이 문제에서 궁금한게있습니다.
ch[i] != 0라서 if문을 탐색하지않는다면 L에 해당하는 dfs함수는 뭘 반환하는건가요?? 반환하는게 안보일때는 return이 생략됐다고 생각하는건가요?
-
해결됨10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
비트마스킹 연산자 "1의 보수" 영문 표기법
안녕하세요,비트마스킹 개념 #2-4 비트연산자의 기초에서1의 보수 영문 표기가 one's completion 이라고 하셨는데one's complement 가 맞는 표현인 것 같습니다 ㅎㅎ
-
미해결10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
3-O go 함수 질문 드립니다.
안녕하세요 강사님풀이 해주신 코드 기준 go 함수의 이중 for loop 에서, 변수 i 가 가로선의 index 를 나타내는 것으로 이해하고있는데for loop 에서 변수 i 의 시작이 왜 here 부터 시작해야하는지 이해가 잘 되지 않아서요.cnt = 0 에서 가로선 1개를 놓고, cnt = 1 에서 또 가로선을 1개 더 놓게 되는 상황에서cnt = 0 에서 놓았던 가로선 보다 같거나 아래 위치에 가로선을 놓아야한다는 조건이 어떻게 도출된 것인지 궁금합니다.(가로선을 놓을 때 접하거나 연속되지 않아야 한다는 조건은이중 for loop 안에 if 문에서 걸러지는 것으로 이해하고 있습니다) (변수 i 의 시작을 0 으로 고정하면 시간 초과가 되는 것은 확인했습니다..)
-
미해결파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)
안녕하세요. 다른 풀이도 풀었는데 괜찮을까요?
정답은 제대로 나오긴 했는데 시간 초과라던가 하는 문제가 없을까요?4중 for문은 생각지도 못했네요..ㅠㅠ sudoku = [list(map(int, input().split())) for _ in range(9)] def solution(sudoku): length = len(sudoku) a, b, c, = list(), list(), list() # 행열 검사 for i in range(length): row, col = list(), list() for j in range(length): row.append(sudoku[i][j]) col.append(sudoku[j][i]) if len(set(row)) != 9 or len(set(col)) != 9: return "NO" # 3x3 격자판 검사 a.extend(row[0:3]) b.extend(row[3:6]) c.extend(row[6:]) if i == 2 or i == 5 or i == 8: if len(set(a)) != 9 or len(set(b)) != 9 or len(set(c)) != 9: return "NO" a, b, c, = list(), list(), list() return "YES" print(solution(sudoku))
-
미해결파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)
1068번: 트리
제가 다음과 같이 코드를 작성했는데,100%까지 가다가 틀립니다.. 어떤게 문제일까요? 반례를 제시해주실 수 있나요?감사합니다. https://www.acmicpc.net/problem/1068 import sys input = sys.stdin.readline n = int(input()) g = list(map(int, input().split())) m = int(input()) cnt = 0 def DFS(x): g[x] = -1 for i in range(n): if g[i] == x: DFS(i) DFS(m) for i in range(n): if g[i] != -1 and i not in g: cnt += 1 print(cnt)
-
미해결파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)
안녕하세요 리뷰복습하다가, 발견했습니다
최근에 다시 자바스크립트로 돌리면서, 기존에 파이썬으로 했던 것들 다시 모두 자바스크립트로 풀어보면서 문제 풀어보니, 발견했습니다.이거 첫번째 가정을, 그리디로 접근하면 해결 안되는 문제인것같습니다. 이후 가정들은 당연히 그리디 관념으로 최적값 찾을 수 있는데, 첫번째 가정부터 그리디로 접근하면 해결되는 문제가 아니라서 어긋나기때문에, 그리디관념이 통하지 않는 문제인것같습니다.완전탐색해버리거나, 시간 더 줄이려면 백트래킹 가지치기 해야하는 문제인것같습니다. 입력입니다!7172 67183 65179 61178 62177 63170 72181 60 기존 풀이(무조건 183선발) 가 내주는 답 : 3감독 현수가 원할 것 같은 답 : 6그리디로 가장 키 큰 사람 무조건 선발하는 과정이 풀이에서 오류인것같습니다.183 선발 가정하고 cnt 값 구하고,그다음 181 선발 가정하고 cnt값 구하고,쭉 다음 순으로 선발 가정하고 cnt값 구하는데,만약 어떤 사람 선발 가정하고 cnt값 구하는데남은 사람 수 다 합해도 기존 Max cnt보다 적을 경우,백트레킹 가지치기로 break 혹은 return 끊어버리는게 맞는것같습니다. 풀이1. 이중포문const input = require("fs") .readFileSync("input.txt") .toString() .trim() .split("\n"); const n = parseInt(input[0]); const arr = Array.from(Array(5), () => []); for (let i = 0; i < n; i++) { arr[i] = Array.from(input[i + 1].trim().split(" ")).map((v) => parseInt(v)); } function solution(n, arr) { arr.sort((a, b) => b[0] - a[0]); let cnt = 0; let largest = 0; let res = 0; for (let i = 0; i < n; i++) { largest = arr[i][1]; cnt += 1; if (res >= n - i) { break; } for (let j = i + 1; j < n; j++) { if (arr[j][1] > largest) { largest = arr[j][1]; cnt += 1; } } res = Math.max(res, cnt); cnt = 0; } console.log(res); } solution(n, arr); 풀이2. DFSconst input = require("fs") .readFileSync("input.txt") .toString() .trim() .split("\n"); const n = parseInt(input[0]); const arr = Array.from(Array(5), () => []); for (let i = 0; i < n; i++) { arr[i] = Array.from(input[i + 1].trim().split(" ")).map((v) => parseInt(v)); } let cnt = 0; let res = 0; //const list = []; function DFS(s, weight) { if (s < 0) return; if (cnt + n - s <= res) { cnt -= 1; s -= 1; return; } for (let i = s; i < n; i++) { if (arr[i][1] > weight) { cnt += 1; //list.push(arr[i][1]); DFS(i + 1, arr[i][1]); //list.pop(); } } res = Math.max(res, cnt); //console.log(list); cnt -= 1; } function solution(n, arr) { arr.sort((a, b) => b[0] - a[0]); DFS(0, 0); console.log(res); } solution(n, arr);
-
해결됨파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)
봉우리 - 가장자리 0으로 채우기
이렇게 (N+2)*(N+2) list를 만들고 안에다가복사해서 붙여넣어버리는 방법은 별로인가요? N = int(input()) input_list = [list(map(int, input().split())) for _ in range(N)] n_list = [[0] * (N + 2) for _ in range(N + 2)] for i in range(N): for j in range(N): n_list[i + 1][j + 1] = input_list[i][j]
-
해결됨10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트
인접리스트 시간 복잡도가 잘 이해가 가지 않습니다.
선생님 안녕하세요.수업 열심히 들으면서 코테 준비중인 취준생입니다.인접리스트의 공간복잡도와 모든 간선찾기의 설명을 들으면서 약간 의문이 들어 질문드립니다.예를 들어,vector<int> v1[V] 만큼의 배열을 생성하고 나서, 각 배열에 연결할 정점들을 다 카운트 했을 때 E개라서 공간복잡도가 O(V + E) 이라고 이해해도 될까요?E = E * push_back(i); 와 같은 코드로 이해했습니다.재미있고 수준높은 강의 잘 듣고 있습니다!