묻고 답해요
131만명의 커뮤니티!! 함께 토론해봐요.
인프런 TOP Writers
-
해결됨그림으로 쉽게 배우는 자료구조와 알고리즘 (심화편)
AVL 트리 회전 질문
안녕하세요. 선생님~[AVL트리 - 개념] 강의 - 회전 관련 질문있습니다.7:00 즈음LL회전, RR회전 펼져있는 노드 이미지가 반대로 된것 아닌지? 궁금합니다.헷갈려서 검색해보니LL이라는 용어가 회전할 기준이 되는 노드의 왼쪽 노드, 그 다음 왼쪽 노드형태에서 오른쪽으로 회전해서 균형을 맞추자!로 대체적으로 설명이 되어있는것같습니다.(이미지로는 왼쪽으로 쭉 내려가는 이미지)위키백과에는 따로 LL,RR이라는 용어설명이 없어서, 블로그 글들 참조하였습니다.뭔가 관점 차이인 부분일까요?
-
해결됨[파이썬/Python] 문과생도 이해하는 DFS 알고리즘! - 입문편
바이러스 백준 2606 dfs 종료는 어떻게 되는건가요?
def dfs(idx): global visited, graph, answer visited[idx] = True answer += 1 for i in range(1,N+1): if not visited[i] and graph[idx][i]: dfs(i)이와 같은 dfs 재귀함수에서 dfs(1)이 맨 처음에 실행되고 조건에 따라 계속 재귀되는데 마지막 dfs(7)까지 간다고 했을 때 range(1,N+1)에 범위는 넘지만 dfs(8), dfs(9), ... 이런식으로 계속 코드가 돌아버릴 수도 있는 것이 아닌가요??DFS와 재귀함수가 처음이여서 질문을 명확하게 못 작성한 것 같네요.return이라는게 필요한 것이 아닌지, 재귀함수에 종료조건이 어떻게 되는 것인지 궁금해서 여쭤봅니다.답변 기다리겠습니다. 감사합니다
-
미해결코딩테스트 [ ALL IN ONE ]
강의 듣고 난 후 어떤 문제를 풀어야 할까요
안녕하세요! 강의 잘 듣고있습니다. 강의듣고 나서 해당 알고리즘에 맞는 쉬운문제부터 차근차근 풀어보고 싶은데 추천하는 문제 리스트가 있나요? 그리고 디스코드에서 문제를 같이푸는건 어떤건가요???저는 디스코드가 안들어가집니다.
-
해결됨2주만에 통과하는 알고리즘 코딩테스트 (2024년)
1520.py
안녕하세요 ! 강의를 잘 보고있습니다 :)1520 문제를 처음 접하였을때, dp를 사용하지 않았었는데요강의를 보니 강사님께서도 처음에는 dp테이블을 사용하지 않고 푸시다가, 나중에 dp를 추가해주시더라구요 .. !이, 이유가 백준에서 시간제한이 걸리기 때문에, 이미 방문한곳은 다시 방문하지 않기위해 그러는 것 인가요 .. ?아직 들어야할 강의가 많아서, 문제가 이렇다 저렇다 말 할 수 없겠지만만약, 코테에서 위와같이 문제가 나오면, 시간제한이 걸리는지 아닌지를 확인할 방법이 없는데 항상 dp테이블을 생각하는것이 좋은 방법일지 궁금합니다 .. !
-
해결됨코딩테스트 [ ALL IN ONE ]
다익스트라 final 노드 도착후에 바로 종료하지 않는 이유가 궁금합니다.
구현하신 코드를 보니 목적지에 도착한 이후에도 우선순위 큐를 모두 비우고 나서 값을 리턴하도록 함수를 작성하셨는데요, 목적지 도달 후 바로 반환 하는 것이 시간상 더 유리할 것 같은데 혹시 다른 이유가 있는걸까요?
-
해결됨2주만에 통과하는 알고리즘 코딩테스트 (2024년)
12865 배낭문제
안녕하세요! 제 6강을 수강하고 탑다운 DP 문제 중 냅색문제를 백준에서 풀었을 때 계속 런타임에러가 나네요 ㅠ 혹시 이유를 알 수 있을까요 ? 제가 작성한 코드는 다음과 같습니다. #물건의 수 n와 배낭의 무게 k n,k = map(int,input().split()) #순서대로 배낭의 무게 w와 가치 v item = [list(map(int,input().split())) for _ in range(n)] dp = [[-1 for _ in range(10*6)] for _ in range(n)] #모든 경우의 수 생각하기 def bag(idx , weight ) : if weight > k : return -999 if idx == n : return 0 if dp[idx][weight] != -1 : return dp[idx][weight] #물건을 넣은 경우와 넣지 않은 경우를 비교해준다 dp[idx][weight] = max( bag(idx+1 , weight + item[idx][0]) + item[idx][1] , bag(idx+1 , weight)) return dp[idx][weight] ans = bag(0,0) ans
-
해결됨2주만에 통과하는 알고리즘 코딩테스트 (2024년)
12865
def recur(idx, weight): if weight > K : return -99999 if idx == N : return 0 if dp[idx][weight] != -1: return dp[idx][weight] dp[idx][weight] = max(recur(idx + 1, weight + items[idx][0]) + items[idx][1], recur(idx + 1, weight)) return dp[idx][weight] N,K = map(int,input().split()) items = [list(map(int,input().split())) for _ in range(N)] #무게를 고려해서 가치를 담는 dp테이블, 무게는 얼마든지 커질 수 있으므로 10만, 그리고 물건개수만큼 N 작성 dp = [[-1 for _ in range(100_001)] for _ in range(N)] print(recur(0,0))recur(0,0) 재귀함수를 불렀는데 dp 테이블의 최대값이 찍히는게 잘 이해되지 않습니당...!당연히 dp테이블에서 max값을 찾아 출력해야 하는 줄 알았는데, 코드를 보니 그냥 print(recur(0,0))을 하네욥..!
-
해결됨2주만에 통과하는 알고리즘 코딩테스트 (2024년)
재귀 경우의수 14501 퇴사문제
def recur(idx,money): global answer if idx == n: answer = max(answer, money) return if idx > n: return # idx 해당날에 상담 ㄱㄱ recur(idx + arr[idx][0], money + arr[idx][1]) # pass 하는날 recur(idx + 1, money) n = int(input()) arr = [[] for _ in range(n+1)] for i in range(n): t,p = map(int,input().split()) arr[i+1] = [t,p] answer = -999999 recur(1,0) print(answer)위는 제 코드입니다. 이 코드를 백준에 제출하면 오답이 나옵니다. 테스트 케이스의 경우에는 맞았는데.근데 위 코드에서 if에 해당하는 부분을 아래와 같이 고치면 정답이 나오더라고요.if idx == n+1: answer = max(answer, money) return if idx > n+1: return제가 아직 재귀에 대한 완벽한 이해가 없고, 어떤 식으로 재귀함수가 동작하는 지는 정확히 몰라서 구글링을 통해 재귀 함수는 스택방식으로 작용한다라는 내용도 공부해보고 왜 n+1은 통과고 n은 실패인지 암만 생각해봐도 모르겠네요,,도와주십시오!!
-
해결됨2주만에 통과하는 알고리즘 코딩테스트 (2024년)
투포인터 22988번 문제에서 continue와 break이 들어가는 이유
N, X = map(int,input().split()) arr = sorted(list(map(int,input().split()))) s = 0 e = N-1 remain = 0 cnt = 0 while s <= e : # s와 e가 교차되면 멈춘다! if arr[e] == X: cnt += 1 e -= 1 continue if s == e : remain += 1 break # 짜투리를 하나 추가한다! if arr[e] + arr[s] >= X/2: cnt +=1 s += 1 e -= 1 else: s += 1 # 수가 커지겠죠! remain += 1 print(cnt + remain//3 )여기에서 while문 안에 첫 번째 if 다음에 continue가 들어가는 이유와두 번째 if 문에서 break을 사용하는 이유를 모르겠습니다. 두 개 다 없어도 가능하다고 생각하는데 테스트 케이스의 경우 continue는 없어도 예제 출력을 출력했고, break은 없으면 예제출력과 결과가 다르네요!!continue와 break이 어떻게 쓰인 것인지 조금 자세히 설명해주실 수 있으실까요
-
해결됨2주만에 통과하는 알고리즘 코딩테스트 (2024년)
완전탐색 1090번 시간초과
예제 문제는 잘 풀리는데 백준에 제출하니까 시간초과가 뜹니다강의 자료랑 큰 차이는 없어 보이는데 어느 부분을 고쳐야 시간 안에 계산 가능할까요?#include <iostream> #include <cstdlib> using namespace std; int main(int argc, char **argv) { int n; int minX, minY, maxX, maxY; cin >> n; int arr[n][2]; for(int i=0; i<n; i++){ cin >> arr[i][0] >> arr[i][1]; } minX = arr[0][0]; maxX = arr[0][0]; minY = arr[0][1]; maxY = arr[0][1]; for(int i=1; i<n; i++){ if(arr[i][0]>maxX){ maxX = arr[i][0]; } else if(arr[i][0]<minX){ minX = arr[i][0]; } if(arr[i][1]>maxY){ maxY = arr[i][1]; } else if(arr[i][1]<minY){ minY = arr[i][1]; } } int arr_answer[n]; int arr_dis[n]; for(int i=minY; i<=maxY; i++){ for(int j=minX; j<= maxX; j++){ for(int l=0; l<n; l++){ int subY= 0, subX=0; subY = i-arr[l][1]; subX = j-arr[l][0]; arr_dis[l] = abs(subX) + abs(subY); } int sum = 0; for(int k=0; k<n; k++){ sum+=arr_dis[k]; if(i==minY && j ==minX){ arr_answer[k] =sum; } else if(sum < arr_answer[k]){ arr_answer[k] = sum; } } } } for(int i=0; i<n; i++){ cout << arr_answer[i] << " "; } return 0; }
-
해결됨[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편
바닥 장식 (백준 1388) 문제 질문입니당
저는 맵2차원배열을 boolean으로 사용하고싶어아래와 같이 코드를 작성해봤습니당... 예제입력1. 은 답이 잘나오는데 나머지는 왜 틀리게 나올까용... package DFS; import java.io.*; import java.util.StringTokenizer; import java.util.Vector; /* 바닥 장식 https://www.acmicpc.net/problem/1388 */ public class B1388 { final static int MAX =50+10; static boolean [][] map; static boolean [][] visited; static int M,N; static void dfs(int y, int x){ visited[y][x]=true; if (map[y][x]==true&& map[y][x+1]==true){ dfs(y, x + 1); } if(map[y][x]==false&&map[y+1][x]==false){ dfs(y+1,x ); } } 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()); map = new boolean[MAX][MAX]; visited = new boolean[MAX][MAX]; //맵정보 반영 for (int i = 1; i <= N; i++) { String str = br.readLine(); for (int j = 1; j <= M; j++) { map[i][j] = (str.charAt(j - 1) == '-' ? true : false); } } //dfs int answer=0; for (int i = 1; i <= N; i++) { for (int j = 1; j <= M; j++) { if(map[i][j]&&visited[i][j]==false){ dfs(i,j); answer++; } } } bw.write(String.valueOf(answer)); bw.flush(); bw.close(); } }
-
해결됨[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편
침투 (백준 13565) 문제중 질문입니당
아래 코드에서 왜DFS를 수행할때 MAP[1] 이 왜 고정인지 잘모르겠습니다... //맵정보 저장 for (int i = 1; i <= N; i++) { String str = br.readLine(); for (int j = 1; j <= M; j++) { map[i][j] = (str.charAt(j - 1) == '0' ? true : false); } } //dfs for (int j = 1; j <= M; j++) { if (map[1][j]) { // 왜 map[1][j] 일까요 dfs(1, j); // 또한 dfs도왜 1,j 일가요 } }
-
해결됨2주만에 통과하는 알고리즘 코딩테스트 (2024년)
최적화(정수론) 질문
21분 22초에서 176에서 177까지의 수에서 2의 제곱수로 나누어지는 약수를 모두 찾아 더하는 문제인데요.뜬금없게 느껴졌는데,176은 16으로 나누어 떨어지고, 177은 1로 나누어 떨어지니 16+1 =17이 답이다라고 하셨는데... 저는 이 전개가 전혀 이해가 되지 않습니다...어떻게 16 + 1이 나오는지 알려주시면 감사하겠습니다....
-
해결됨코딩테스트 [ ALL IN ONE ]
노션 교재가 있어야 수강 가능한가요?
안녕하세요!강의를 수강하려고 결제했는데 노션 교재를 바로 받아 볼 수 있는게 아니더라구요 ㅠㅠ구글폼 제출했는데..노션 교재가 있어야 원활한 수강이 가능한 것인지요?
-
해결됨코딩테스트 [ ALL IN ONE ]
노션 공유 부탁드리겠습니다
인프런 아이디: sonaky47노션 이메일주소: sonaky47@gmail.com
-
미해결Do it! 알고리즘 코딩테스트 with JAVA
12891_DNA비밀번호
package baekjoon; import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer; public class p12891_DNA비밀번호 {static int[] myArr;static int[] checkArr;static int checkSecret; public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));StringTokenizer st = new StringTokenizer(br.readLine());int s = Integer.parseInt(st.nextToken());int p = Integer.parseInt(st.nextToken()); int result = 0;checkArr = new int[4]; // 비밀번호 체크 배열myArr = new int[4]; // 현재 상태 배열char[] a = new char[s];checkSecret = 0; // 현재 p개 중 몇개가 비밀번호 요건에 만족하는지 a = br.readLine().toCharArray();st = new StringTokenizer(br.readLine());for (int i = 0; i < 4; i++) {checkArr[i] = Integer.parseInt(st.nextToken());if (checkArr[i] == 0) {checkSecret++; // i번째 값은 이미 완성됨.}} for (int i = 0; i < p; i++) { // 부분 문자열 처음 받을 때 세팅Add(a[i]); // 현재 상태 배열에 담음} if (checkSecret == 4) {result++;} // 슬라이딩 윈도우for (int i = p; i < s; i++) {int j = i - p; // j = 맨 왼쪽, i = 맨 오른쪽Add(a[i]); // 오른쪽에 있는 값 추가Remove(a[j]);if (checkSecret == 4) {result++;}} System.out.println(result);br.close();} private static void Remove(char c) {switch (c) {case 'A':if (myArr[0] == checkArr[0]) // 같으면 이번에 빠짐으로써 충족이 안 되는 것이니까 checkSecret 하나 줄임checkSecret--;myArr[0]--;break;case 'C':if (myArr[1] == checkArr[1])checkSecret--;myArr[1]--;break;case 'G':if (myArr[2] == checkArr[2])checkSecret--;myArr[2]--;break;case 'T':if (myArr[3] == checkArr[3])checkSecret--;myArr[3]--;break;}} private static void Add(char c) {switch (c) {case 'A':myArr[0]++;if (myArr[0] == checkArr[0])checkSecret++; // 'A'가 더 많이 들어온다고 해서 checkSecret값을 올리면 되는 게 아니므로 딱 같을 때에만 증가시킴break;case 'C':myArr[1]++;if (myArr[1] == checkArr[1])checkSecret++;break;case 'G':myArr[2]++;if (myArr[2] == checkArr[2])checkSecret++;break;case 'T':myArr[3]++;if (myArr[3] == checkArr[3])checkSecret++;break;}}}현재 백준에서 문제가 통과되지 않고 있는데 혹시 잘못된 부분이라도 있을까요?ㅠ
-
해결됨2주만에 통과하는 알고리즘 코딩테스트 (2024년)
40분쯤 gcd 관련 이해가 안됩니다.
gcd(12,8) -> gcd(8,12-8)이면gcd(a,b) -> gcd(b,a-b) 가 맞는게아닌가요?
-
미해결Do it! 알고리즘 코딩테스트 with C++
i==k일떄 i++안해도되지않나요
i==k인 경우는 a[i]에 1을 더하더라도 큰 값이 나올텐데i를 오른쪾으로 옮겨버리면 사실상 a[k]보다 더 큰 값만 나오는거 아닌가요?
-
미해결그림으로 쉽게 배우는 자료구조와 알고리즘 (심화편)
레드플랙트리의높이
닐노드기준으로 21을가려면 HEIGHT가 2아닌가요? 왜 4인가요? 가는 통로가 따로 있나요? Red-Black 트리 - 개념(제거) 10분에서Red-Black 트리 - 개념(제거)에서 15노드를 제거하면 닐이 바깥쪽 조카노드가 아니라 형제노드가 되는거 아닌가요? 21닐 30(형제노드) 25(안쪽조카노드)
-
해결됨[자바/Java] 문과생도 이해하는 DFS 알고리즘! - 입문편
Main class에 static으로 선언하는 이유
강의 영상마다 질문이 있으면 언제든 그리고 바로 질문 남겨주세요! 질문할 때 가장 정확하게 이해할 수 있습니다.해당 영상과 관련된 질문들을 해주실 때 제가 가장 정확히 답변 드릴 수 있습니다!취업 전반의 상담이나, "제 코드가 왜 틀렸는지 알려주세요"와 같이 광범위한 질문은, 질문자의 상황에 따라 답변이 달라질 수 있기 때문에, 정확한 답변을 드리기가 어렵습니다 :(이런 분들을 위해서는 멘토링 항목으로 별도 제공하고 있으니, 다음 링크를 참고해주세요!이 링크를 통해서는 본인의 코드가 왜 틀렸는지 모를 때 질문을 주셔도 좋고, 취업 전반(면접 준비, 자소서, CS 면접 등)에 관련한 질문을 주시면 답변 드리겠습니다 :)"이 질문은 해도 되나?"라는 생각이 드신다면 우선 남겨주세요! 제가 답변 드리기 어려운 건 멘토링에 올려 달라고 재요청 드리겠습니다 :) 안녕하세요!혹시 Main class에 static으로 변수를 선언하는 이유가 궁금합니다!또한, 백준에서 public static void main 에 선언했을 때와 차이가 궁금합니다..!! 감사합니다