LCA 코드에서 left, right 변수는 방명록 (visited) 변수와 같이 방문한 값을 저장하기 위한 용도로 사용하는 것인 가요?!

pq를 쓰지 않고, 골동품 가치를 내림차순으로 정렬하고 가방 무게를 오름차순으로 정렬해서 풀면 틀린 명제일까요??

이전강의에서 풀엇던것처럼 ch체크 배열만들고 시계방향 9,12,3,6시 방향으로만 체크해서 이렇게 만들었는데강사님이 강의 때 하셧던거에 비하면 효율이 많이 떨어지는지 궁금해서 질문 남깁니다  package section9; import java.util.ArrayList; import java.util.Scanner; public class Main13 { static int[] dx= {-1,0,1,0}; static int [] dy= {0,1,0,-1}; static int[][] ch,dir,map; static int n,answer; public static void main(String[] args) { // TODO Auto-generated method stub Scanner s=new Scanner(System.in); ArrayList<Integer> list = new ArrayList<>(); answer=0; n=s.nextInt(); map= new int[n][n]; ch= new int[n][n]; dir= new int[n][n]; for(int i=0;i<n;++i) { for(int z=0;z<n;++z) { map[i][z]=s.nextInt(); } } for(int i=0;i<7;++i) { for(int z=0;z<7;++z) { if(map[i][z]==1 && ch[i][z]==0) { DFS(i,z); if(answer>1) { list.add(answer); answer=0; } }else { answer=0; continue; } } } System.out.println(list.toString()); System.out.println(list.size()); } static void DFS(int x,int y) { if(map[x][y]==1) { answer++; } if(ch[x][y]==1) return; if(map[x][y]==0) return; if(x<0 || x>6 || y<0 || y>6) { return; }else { ch[x][y]=1; for(int i=0;i<4;++i) { int nx= x+dx[i]; int ny=y+dy[i]; if(nx>=0 && nx<7 && ny>=0 && ny<7 && ch[nx][ny]==0 && map[nx][ny]==1) { DFS(nx,ny); } } } } }

제목 그대로 union and find 알고리즘을 써서 이문제를 풀었습니다.풀이를 보니 dfs를 써서 푸는 방법도 있는거 같은데 어떤 접근법이 시간 복잡도가 더 낮은 가요?

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 안녕하시렵니까 본론부터 말씀드리자면, 해당 강의 3분 27초경에 출력되는 값을 보면 0x...0100x...0100x...0140x...014라는 것을 확인할 수 있는데, 주소 값이 4가 커졌다는 건 int 배열의 각 값들이 4 Byte이기 때문이라고 이해했습니다. 다만 이전 강의에서- int는 4바이트, double은 8바이트니까 포인터도 4, 8바이트가 되어야 하는 게 아닌가?- 포인터의 크기는 실행 OS 체제의 비트마다 달라짐- Window OS 64비트를 사용하는 경우의 포인터 사이즈 = 8 Byte- Window OS 32비트를 사용하는 경우의 포인터 사이즈 = 4 Byte 이러한 내용을 확인할 수 있었는데, int 배열을 포인터로 변환했으니, 이전과 마찬가지로 주소값이 8이 커져야 한다고 생각했는데 그렇지 않았다는 점에서 의문이 생겼습니다! int 배열을 포인터에 할당하면서 포인터로 전환되는 것이 아니라 단순히 주소를 할당했기 때문에 이런 일이 발생하는걸까요? 또한, 포인터의 크기가 8 Byte라고 했을 때, 연속되는 포인터라고 가정한다면 두 포인터의 주소값 차이는 8이 맞는지도 궁금합니다! 감사합니다.

안녕하세요 선생님.#2234 문제에 대해서 Connected Component개념으로 DFS를 소개해주셔서 문제풀이를 이해하는데 수월했습니다. 다만, 처음 문제를 저 혼자 풀 때,각 방 칸의 크기가 1이고, 방 칸의 개수에 따라 방 넓이가 결정되므로 가중치가 동일하니 BFS로도 풀 수 있지 않을까라고 생각되어 아래와 같이 풀어봤습니다.http://boj.kr/896f1a9fbf8e47628666c1c0a8c59db5 각 방을 탐색할때마다 queue를 생성하고 queue pop을 할 때마다 방 칸의 개수를 cnt++라는 변수에 담고,탐색을 더이상 진행할 수 없을 때 방 칸의 개수값 cnt를 return하도록 하여 탐색했는데요. 문제에서 주어진 예제 입력1은 통과했지만 채점에서도 어떠한 반례에 걸려 fail이 발생한 것 같습니다.BFS 탐색 코드에 어떠한 문제점이 있는지 피드백 주시면 감사드리겠습니다... 감사합니다. 

우선순위큐 크기가 가방 총 크기보다 클 때만 큐에서 빼는 로직을 작성했는데 왜 틀렸는지 궁금합니다#include<bits/stdc++.h> using namespace std; typedef long long ll; priority_queue<ll> pq; ll n,k,ret; int main(){ cin>>n>>k; pair<ll,ll> v[n]; //jewelry ll bag[k]; for (int i=0;i<n;i++){ cin>>v[i].first>>v[i].second; } for (int i=0;i<k;i++){ cin>>bag[i]; } int idx=0; //bag index sort(v,v+n); sort(bag,bag+k); int idx2=0; while (idx2<n){ while (idx<k && idx2<n){ if (bag[idx]<v[idx2].first) idx++; else{ if (pq.size()==k){ if (v[idx2].second>pq.top()){ pq.pop(); pq.push(v[idx2].second); } }else if (pq.size()<k) pq.push(v[idx2].second); } idx2++; } } while (pq.size()){ ret+=pq.top(); pq.pop(); } cout<<ret;

n이 15000이고 2초의 제한 시간이라 조합이 떠올랐지만 이중 for문으로 풀 생각을 못했습니다. 문제를 재귀로 풀고 생각해보니 최악의 경우인 15000 * 15000이 될 수 없긴 한데 그래도 N^2의 시간 복잡도인데 어떻게 통과한 것인지 궁금하고 이런 경우 대충?의 시간 복잡도를 어떻게 계산해서 -> 이중 for문으로도 풀어도 되겠다라는 생각까지 이어지는 것인지 궁금합니다.

http://boj.kr/35af496c1fb44628be4b5f27dde803d3문제 보자 마자 조합이 떠올라서 위처럼 풀었습니다.코드 자체에 대한 질문은 아니고 '재귀함수의 시간 복잡도를 어떻게 계산'하는지 궁금합니다.함수를 호출시 스택 프레임이 쌓이고 이것을 반환하고..등등의 작업 까지 생각하는 것은 아닌거같아 질문드립니다.재귀 함수의 깊이가 100이면 O(100)으로 시간 복잡도가 잡히는 것인지 궁금합니다.

안녕하세요 정답과 다르게 코드를 짜봤는데 코드 평가 해주실 수 있나요?? http://boj.kr/e426c9cd01624541b5251528546a8eae 강의 잘 보고있습니다 감사합니다

안녕하세요. 선생님.강의 교안 p.33에서cout << a << " " << "" << b << '\n';"" 빈 문자열을 넣으신 이유가 있을까요?빈 문자열을 빼도 출력 값은 동일하게 보이는데 어떤 의미로 넣으신건지 궁금합니다.혹시 cout 설명처럼 입력할 문자열을 넣을 수 있다를 설명하기 위해서 그런건가요?   

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.#include<iostream> #include<algorithm> #include<vector> #include<utility> using namespace std; int n,person[14],ret =987654321,temp,temp1,visited[14],comp[14]; string s; vector<int> adj[14]; pair<int,int> dfs(int here, int value){//인접구 개수, 인구수 반환 visited[here] =1; pair<int,int> ret = {1,person[here]}; for(int there:adj[here]){ if(comp[there] != value) continue; if(visited[there]) continue; pair<int,int> temp_ = dfs(there,value); ret.first +=temp_.first; ret.second += temp_.second; } return ret; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n; for(int i =1; i<=n;i++){ cin>>person[i]; } for(int i =1;i<=n;i++){ cin>>temp; for(int j =0; j<temp;j++){ cin>>temp1; adj[i].push_back(temp1); adj[temp1].push_back(i); } } for(int i =1;i<(1<<n)-1; i++){ fill(&comp[0],&comp[0]+14,0); fill(&visited[0],&visited[0]+14,0); int idx1=-1,idx2 =-1; for(int j =0; j<n;j++){ if(i&(1<<j)){ comp[j+1]=1; idx1 = j+1; } else idx2 = j+1; } pair<int,int> comp1 = dfs(idx1,1); pair<int,int> comp2 = dfs(idx2,0); if(comp1.first+comp2.first == n) ret = min(ret,abs(comp1.second-comp2.second)); } cout<<(ret==987654321 ? -1:ret); return 0; }저는 이렇게 백준에 제출했을때 맞았다고 나오는데 제 vscode에서는 예제에서 밑에 만큼 입력하면 -1이 출력되어 끝나 버립니다 왜 그런건가요..? 다른 문제 풀때도 정답은 맞지만 제가 실행하면 도중에 입력을 그만 받습니다.. ㅠㅠ6 5 2 3 4 1 2 2 2 4 4 1 3 6 5

c@fa$ 가 입력 되었을 때, 제 생각에는결과가 그대로 나와야 하지 않나 싶은데, (짝이 되는 알파벳이 없음) a@fc$이 나오는 이유가 궁금합니다.

http://boj.kr/b3912cd4b65448baa4a27bea951494cb안녕하세요, 큰돌님.해당 문제를 queue를 이용한 BFS로 풀었습니다.더 효율적으로 수정할 부분이 있을까요?

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 위험도가 높은 환자 순서로 우선순위 큐를 만들었습니다. 정답으로 찾아야 하는 환자의 위치의 번호를 이동해가면서 현재 치료 받는 환자가 찾아야 하는 환자인지를 체크 했고요. 우선순위 큐에서 poll한 값을 통해서 현재 대기하고 있는 환자가 현재 치료를 받아도 되는지(우선순위가 가장 높은지)를 체크 했습니다. public int solution(int[] input1, int m) { Queue<Integer> q = new LinkedList<>(); Queue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder()); int seq = m; for (int i : input1) { q.offer(i); pq.offer(i); } int cnt = 0; while (true) { Integer poll = q.poll(); seq--; if (Objects.equals(pq.peek(), poll)) { cnt++; if (seq == -1) { break; } pq.poll(); } else { q.offer(poll); if (seq == -1) { seq = q.size() - 1; } } } return cnt; }

선생님 코드에서 ret의 초기값을 -1000000 으로 주셨는데 이유가 궁금합니다.만약 n이 100000, k가 99999, 모든 temp가 -100일 때 0~99999까지 더하면 -1000000보다 작은 값이 나오게 되어 최대 값을 제대로 못찾을거같은데 어떻게 코드가 통과한 것인지 궁금합니다.

안녕하세요, 큰돌님.http://boj.kr/f7198ad0aa0740abb6a3d6f9cb33c43e2-H 에서 입력 받은 s가 "a" 같은 하나의 문자일 때 런타임 에러가 떴습니다. 계속 수정하다 보니 모음 or 자음 3개 연속 조건 부분의 코드 문제인 것 같았습니다. for(int i = 0; i < s.size() - 2; i ++)그래서 s가 하나의 문자일 때를 나눠서 계산하였습니다. // s가 문자일 때 if(s.size() == 1) 이렇게 하니 맞긴 했는데 코드가 너무 난잡해진 것 같습니다...기존 방식의 런타임 에러의 이유제 코드보다 더 좋은 해결 방안이 있을까요?

안녕하세요 큰돌님!2Q 를 풀다가 반례를 못찾겠어서 질문드립니다!https://www.acmicpc.net/source/90805248제가 제출한 코드인데, 큰돌님의 풀이보다 복잡하고 비효율적인 것은 알지만 이 풀이가 왜 틀렸는지 알고싶어서 여쭤봅니다. 

선생님의 풀이를 보고 이건 진짜 못떠올릴 것 같은데? 라는 생각이 들었습니다.배열에 마킹을 하면서 푸는 풀이는 떠올릴 수 있을 것 같은데, 스택만 이용한 풀이에서 -1을 넣어서 풀이하는 방식은 정말 감탄이 나오네요. 저도 스택만을 이용하는 비슷한 풀이를 떠올려서 '((()))'가 6이 나오게 하는 방법은 고안을 했는데 '((()))()'가 8이 되게 하는걸 처리하기가 너무 어렵더라구요. 하지만 -1을 넣어두면 전부 처리가 되네요.그리고 올바르지 않는 문자열이 오면 그 인덱스를 넣어주면 -1을 넣은 것과 동일하게 뒤의 문자열도 판별할 수 있다니...이 풀이를 보고 이런 아이디어는 정말 못 떠올릴 것 같다는 생각이 들었습니다. 이런 아이디어를 잘 떠올리기 위해서 어떻게 연습하면 좋을까요?

from copy import deepcopy def init_sort_checker(checkers): tmp_list = [] sorted_sum_list = [] for idx, chk in enumerate(checkers): for i, tgt in enumerate(checkers): if idx == i: #본인으로 가는 값은 제외 continue x_val = abs(chk[0] - tgt[0]) y_val = abs(chk[1] - tgt[1]) # price, [src, tgt] 순 정렬 tmp_list.append([x_val + y_val, [idx, i]]) tmp_list.sort(key=lambda x: x[0]) # price 값 적은 순서대로 정렬 sorted_sum_list.append(deepcopy(tmp_list)) tmp_list = [] return sorted_sum_list def sort_sum_target(sorted_sum_list, k): lowest_price = 1000000*k target_idx = -1 for idx, line in enumerate(sorted_sum_list): cnt = 0 line_price = 0 for price in line: if cnt >= k-1: break line_price = line_price + price[0] cnt += 1 if line_price < lowest_price: lowest_price = line_price target_idx = idx return target_idx def k_tgt_process(k, sorted_tgt, sorted_sum_list): tgt_line = sorted_sum_list[sorted_tgt] tgt_loc = [] for i in range(k-1): tgt_loc.append(tgt_line[i][1]) return tgt_loc def k_sorting_process(tgt_loc, checkers): tgt_list = [] for tgt in tgt_loc: tgt_list.append(tgt[0]) tgt_list.append(tgt[1]) tgt_list = list(set(tgt_list)) x_list = [] y_list = [] tgt_checkers = [] for tgt in tgt_list: x_list.append(checkers[tgt][0]) y_list.append(checkers[tgt][1]) tgt_checkers.append(checkers[tgt]) x_list.sort() y_list.sort() if len(x_list)%2 == 0: #짝수 x_chk_point = [int(len(x_list)/2-1),int(len(x_list)/2)] else: # 홀수 x_chk_point = [int(len(x_list)/2)] if len(y_list)%2 == 0: #짝수 y_chk_point = [int(len(y_list)/2-1),int(len(y_list)/2)] else: # 홀수 y_chk_point = [int(len(y_list)/2)] #모아볼 위치의 case 집합 chk_point_list = [] for x_chk in x_chk_point: for y_chk in y_chk_point: chk_point_list.append([x_chk,y_chk]) # 각 checker 위치에서 좌표로 이동하는데 드는 값 계산 ttl_price_list = [] for chk in chk_point_list: x_tgt = chk[0] y_tgt = chk[1] price_list = [] for checker in tgt_checkers: x = checker[0] y = checker[1] if x_list[x_tgt] > x: x_price = x_list[x_tgt] - x else: x_price = x - x_list[x_tgt] if y_list[y_tgt] > y: y_price = y_list[y_tgt] - y else: y_price = y - y_list[y_tgt] price = x_price + y_price price_list.append(price) price_list.sort() ttl_price_list.append(price_list) return ttl_price_list def TestCases(N): checkers = [list(map(int,input().split())) for _ in range(N)] sorted_sum_list = init_sort_checker(checkers) output_str = '0' for k in range(2, N+1): min_price = 2000000 sorted_tgt = sort_sum_target(sorted_sum_list, k) tgt_loc = k_tgt_process(k, sorted_tgt, sorted_sum_list) ttl_price_list = k_sorting_process(tgt_loc, checkers) for n_list in ttl_price_list: tmp = 0 for idx in range(k): tmp = tmp + n_list[idx] if tmp < min_price: min_price = tmp output_str = output_str + ' ' + str(min_price) tmp_str = list(map(int,output_str.split())) # print(output_str) print(*tmp_str) N = int(input()) TestCases(N) 다음과 같이 코드 작성해봤는데, sample input에 대한 답은 다 도출되지만문제 제출하면 답이 틀리다 나오네요..반례나 코드상의 오류를 도와주실 수 있을까요? [사용해본 input/output]4 1 1 2 1 4 1 13 1 0 1 3 14 4 13 13 16 14 15 18 15 30 0 4 8 24 5 3 2 6 9 3 16 14 6 17 14 0 10 17 31 47 5 3 2 6 9 6 13 13 6 17 14 0 4 14 24 40 4 15 14 15 16 14 15 16 15 0 2 3 4 2 4 7 4 7 0 0 4 1 101 2 101 200 101 201 101 0 1 199 398