P11438 문제 교재 코드 그대로 쳤는데 시간초과가 발생하네요 ㅜ 어딜 고쳐야 할까요 ㅠ import java.util.*; import java.io.*; public class Main { static ArrayList<Integer>[] tree; static int[] depth; static int kmax; static int[][] parent; static boolean[] visited; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); // 노드의 수 tree = new ArrayList[N + 1]; for(int i = 1; i <= N; i++) { tree[i] = new ArrayList<Integer>(); } StringTokenizer st; // 1. 인접리스트에 그래프 데이터 저장하기 for(int i = 0; i < N - 1; i++) { st = new StringTokenizer(br.readLine()); int s = Integer.parseInt(st.nextToken()); int e = Integer.parseInt(st.nextToken()); tree[s].add(e); tree[e].add(s); } depth = new int[N+1]; visited = new boolean[N + 1]; int temp = 1; kmax = 0; while (temp <= N) { // 최대 가능 depth 구하기 temp <<= 1; kmax++; } parent = new int[kmax + 1][N + 1]; // 2. depth와 바로 윗 부모 bfs로 구하기 bfs(1); // 3. 2^k 부모 구하기 for(int k = 1; k <= kmax; k++) { for(int n = 1; n <= N; n++) { parent[k][n] = parent[k - 1][parent[k - 1][n]]; } } int M = Integer.parseInt(br.readLine()); // 4. 질의 수행하기 for(int i = 0; i < M; i++) { st = new StringTokenizer(br.readLine()); int a = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken()); int LCA = excuteLCA(a, b); System.out.println(LCA); } } static int excuteLCA(int a, int b) { // 더 깊은 depth가 뒤에 오도록 변경 if (depth[a] > depth[b]) { int temp = a; a = b; b = temp; } for(int k = kmax; k >= 0; k--) { // 높이 빠르게 맞추기 if(Math.pow(2, k) <= depth[b] - depth[a]) { if(depth[a] <= depth[parent[k][b]]) { b = parent[k][b]; } } } for(int k = kmax; k >=0; k--) { // 조상 빠르게 찾기 // 최대 위로 올라가서 같은 부모를 가리키면 k를 1씩 감소하며 다른 지점을 찾음 if(parent[k][a] != parent[k][b]) { a = parent[k][a]; b = parent[k][b]; } } // 여기 온 것은 k = 0일때 고려 // case 1. k=0, 둘이 같은 노드를 가리킴 -> 그곳이 최소 공통 조상 // case 2. k=0, 둘이 다른 노드를 가리킴 -> 바로 위에가 최초 공통 조상 -> 2^0 위에 보기 int LCA = a; if(a != b) { LCA = parent[0][LCA]; } return LCA; } // bfs 구현 private static void bfs(int node) { Queue<Integer> queue = new LinkedList<>(); queue.add(node); visited[node] = true; int level = 1; int now_size = 1; int count = 0; while(!queue.isEmpty()) { int now_node = queue.poll(); for(int next : tree[now_node]) { if(!visited[next]) { visited[next] = true; queue.add(next); parent[0][next] = now_node; // 부모 노드 저장하기 depth[next] = level; // 노드 depth 저장하기 } } count++; // 자식 노드 모두 검사했는지 확인 if(count == now_size) { count = 0; now_size = queue.size(); level++; } } } }
def insert(self, idx, value): new_node = Node(value) if idx == 0: new_node.next = self.head self.head = new_node else: current = self.head for _ in range(idx-1): current = current.next new_node.next = current.next current.next = new_node def remove(self, idx): if idx == 0: self.head = self.head.next # garbage collector가 알아서 처리해준다. else: current = self.head for _ in range(idx-1): current = current.next current.next = current.next.next def insert의 if문에서 self.head.prev=new_node 이렇게 연결지어주지 않아도 괜찮나요? def insert의 else문에서 new_node.prev=current current.next .prev=new_node 이 부분을 추가 안해도 괜찮나요? def remove의 if문에서 garbage collector가 알아서 처리해주신다고 했는데 1->2->3 이렇게 연결되어있고 인덱스 0인 1을 삭제한다고 했을 때 위의 코드대로 하면 head는 2를 가리킨 상태여도 1이랑 2는 아직 연결되어있는데 알아서 삭제가 되나요? 그래서 self.head.prev=None 이 코드를 추가해야된다고 생각했는데 맞을까요? def remove의 else문에서 마찬가지로 current.next .prev=current 문을 추가하지 않아도 괜찮나요?
이 영상 문제풀이에서 def __init__(self, homepage): self.head=self.current=ListNode(val=homepage) 이렇게 초기화를 해주셨는데 self.head=ListNode(val=homepage) self.current=ListNode(val=homepage) 이거와의 차이점이 뭔가요?
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. [코테 적용] 영상에 나오는 노션글들은 어디에서 볼 수 있나요? 올려주신 pdf파일에는 없는것같아서요!
선생님 강의 잘보고있습니다 강의에선 없지만 숙제로 있던 고냥이 문제를 풀어보다가 도저히 제코드의 문제를 모르겠어서 질문드립니다. 올려주신 정답코드와 비교해보면 arr.pop 을 하냐 안하냐 차인데 왜 센세처럼 마지막 원소를 빼줘야 하는지 잘 모르겠습니다 ㅠㅠㅠ 어떤 반례가 있는지 잘모르겠어서 의도를 이해못했습니다ㅠㅠ
안녕하세요. 선생님! 에러는 아니고, 프로그램 완성도 측면에서 버그 발견하여 혹시몰라서 공유드립니다. 프로젝트이름: 05_adtFileIO 소스파일: singleList.c 함수명: AddNewNode, SearchListByName New(유저추가) > Search > offset 0의 유저로만 찾아지는 버그 수정방안 새로운 유저 추가 시, g_listCount로 offset 셋팅 검색 시, 캐싱된 데이터 조회(파일에 아직 저장 안한상황 대응)
안녕하세요. 수업을 듣다 질문 사항이 생겨서 이렇게 문의 남깁니다. doubly linked list로 구성된 ''' from collections import deque # deque 선언 q = deque() ''' 에서 'enqueue ' , 'dequeue '의 시간 복잡도가 O(1)인데, 중간에 데이터가 삽입되고 삭제 되는 경우도 시간 복잡도가 O(1)인가요?
강의내용의 코드가 헷갈려서 아래내용대로 수정해보았는데 이렇게 해도 될까요 ? public static void main(String[] args) { Scanner sc = new Scanner(System. in ); int N = sc.nextInt(); // 수열의 개수 int A[] = new int[N]; // 수열을 저장할 배열 // 데이터 입력 for (int i = 0; i < N; i++) { A[i] = sc.nextInt(); } Stack<Integer> stack = new Stack<>(); StringBuffer bf = new StringBuffer(); // 연산 출력 저장 int num = 1; for (int i = 0; i < N; i++) { int su = A[i]; while (su >= num) { // 현재 수가 스택의 수와 같거나 큰 경우 stack.push(num++); bf.append("+\n"); } if (stack.isEmpty() || stack.peek() != su) { System. out .println("NO"); return; } stack.pop(); bf.append("-\n"); } System. out .println(bf.toString()); // 결과 출력 } }
선생님, 안녕하세요 다름이아니라 6강까지 꾸역꾸역 이해했다고 생각했는데 7강에서 막히네요 문제 1에서는 for문으로 변경할때 역순으로 dp를 채워주었는데 왜 문제 2냅색은 앞방향으로 for문을 도는건가요? 저는 6강에서 이해하기를 문제1, 문제2 모두 recursion을 통해 결국 맨 마지막 까지 도달한뒤 base condition을 통해 계산하면서 => 뒤에서 부터 계산하면서 dp를 채워준다고 생각했습니다 그리고 7강에서 recursion 대신에 for문을 통해 dp를 채워준다고 이해하고 강의를 보았는데요 문제1에 대해서는 for문을 역순으로 도는데 왜 문제2는 역순으로 돌지 않는지 잘 이해가 안갑니다. 둘의 차이가 뭔가요? 차이가 있다면 왜 6강에서는 둘다 똑같은 틀로 문제를 푼건가요? 정말 이해하고싶은데 어렵네요 ㅠㅠ
안녕하세요 정말 강의 잘 듣고 있습니다. 저는 코딩을 영어로 공부하고 있는데 지금까지 봤던 문제들 중에서 graph 를 짜는 부분에서 adjacency matrix 와 adjacency list 두 종류를 쓰셨는데 강의에서 말씀하신 부분을 보면 모든 면에서 adjacency list 가 더 낫지 않나요? 특히나 메모리를 적게 쓰는 부분과 더 짜기가 쉽다는 부분에 있어서요. adjacency marix 가 adjacency list 보다 선호되는 케이스가 혹시 있는지 궁금해서 질문 드립니다. 그리고 adjacency list 를 만드실 때 리스트 안에 리스트를 만드는 설정을 하셨는데 혹시 해시맵에 리스트를 넣어서 하는 게 더 보편적인건가요? 추가) 아 그리고 visited 는 list 에 False 로 채워넣는것 대신에 set() 으로 하는 게 더 메모리에 좋을까요?
안녕하세요! 2강 3020 백준에서 풀어보니 시간초과가 뜨더라구요 그래서 선생님 답안지랑 비교해보니 맨위에 import sys input = sys.stdin.readline 를 쓰신걸 확인하고 추가해서 통과했습니다. 찾아보니까 input보다 성능이 좋다고 하는데 그럼 모든 문제에 풀때 입력 방식으로 넣으면 좋은걸까요 ?
안녕하세요 수업 잘듣고있습니다. 궁금한 점이 있어 문의드립니다 문제는 인접한수가 서로소일수 있도록 숫자를 추가해야하는 문제로 이해했습니다. 강의에서 숫자를 하나만 넣거나 두개를 넣거나 밖에 경우의 수가 없다고하셨는데 그 이유가 궁금합니다. 저도 이유가 궁금해서 찾아보긴 했는데 연속되는 바로 옆의 수를 추가해주면 되기 때문에 최대 2개의 수만 추가하면 된다고 보았거든요. 그런데 강의 자료의 힌트를 보면 2184, 2200 사이에 2185, 2199가 아닌 2195, 2199를 넣으면 된다고 해서 정확히 이해가 안되었어요 왜 3개 4개를 넣지 않고 두개까지만 넣어도 괜찮은걸까요? 무조건 두수 사이에 하나가 아니면 두개가 들어가면 조건을 만족하는 걸 실제 코테에서 어떻게 유추해야할지 감이 안잡히네요 ㅠ
1) 이 문제는 2차월 배열에 False로 초기화한다음 입력받은값만 True로 썼는데 이 문제도 메모리 낭비를 위해 빈 리스트에 넣어서 풀려면 어떻게 해야 할까요?? 2) 재귀(1)중간에 재귀(2)타고 여기서 재귀(3)타고 재귀(4)타서 값을 찾았을때 리턴을 했는데요 리턴을 했다고 해서 1,2,3번의 반복문을 break하는건 아니더라고요 어짜피 답은 찾았으니 시간낭비 방지를 위해 반복문을 돌지 않는방법이 있나요?
