http://boj.kr/d7d5278a96d845ffb969a50d47df2264안녕하세요 선생님!테스트 케이스는 모두 통과했지만 2%에서 시간초과가 발생합니다어떻게 해야 시간초과를 해결할 수 있을지 도움을 주시면 감사할 것 같아요!물을 녹이기 전에 백조끼리 서로 만날 수 있는지를 check_swan을 통해 확인하고만나지 못할 경우에 물을 녹이고 나서 ret을 증가시키고 있습니다선생님께서 말씀하시는 flood fill은 적용하지 않고 일반적인 bfs 방식을 이용해서 풀었습니다.

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.http://boj.kr/f07cde0329cb43428b1b40bb4960eb2f위와 같이 풀이를 했는데 반례를 도저히 모르겠어서 질문남깁니다.

먼저 제가 짠 시간초과 난 소스코드는 다음과 같습니다from collections import deque class Solution(object): def numIslands(self, grid): m = len(grid) # row n = len(grid[0]) # col visited = [] ans = [[False] * n for _ in range(m)] # ans의 용도가 뭐지? cnt = 0 def bfs(x, y): q = deque() # 사전 세팅 q.append((x, y)) visited.append((x,y)) dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] while q: cur_x, cur_y = q.popleft() # (0,0) for i in range(4): next_x = cur_x + dx[i] next_y = cur_y + dy[i] if next_x >= 0 and next_x < m and next_y >= 0 and next_y < n: if grid[next_x][next_y] == "1" and (next_x, next_y) not in visited: q.append((next_x, next_y)) visited.append((next_x, next_y)) ans[next_x][next_y] = True # 완전탐색 for i in range(m): for j in range(n): if grid[i][j] == "1" and (i, j) not in visited: bfs(i, j) cnt += 1 return cnt grid = [ ["1", "1", "0", "0", "0"], ["1", "1", "0", "0", "0"], ["0", "0", "1", "0", "0"], ["0", "0", "0", "1", "1"], ] sol = Solution() print(sol.numIslands(grid)) # O/P: 3발상은 비슷한 것 같은데, 기억에서는 ans를 저렇게 작성한 것 같아서 위와 같이 초기화를 했지만 ans의 용도를 몰랐고 bfs 템플릿을 참고해서 visited.append()로 방문한 정점을 추가했습니다. 그런데 이렇게하면 테스트케이스 48/49에서 시간초과가 났습니다. 왜 그런지 알 수 있을까요?

코드 질문은 아니고 시간 복잡도 관련해서 질문이 있습니다.처음 문제를 봤을 때, 저도 조합을 떠올려서 이중 for문을 사용하여 문제를 풀어볼까 했었는데, 그러면 코드의 시간 복잡도가 O(n^2)이니까, n = 15000일 경우 연산 횟수가 대략 15,000 * 15,000번 이기 때문에 시간 초과가 날 거라고 생각해서 다른 방법을 계속 생각했는데요...결국 못 풀어서 문제 해설을 보니 처음 생각했던 그 방법이여서 조금 당황스러웠습니다. O(n^2)정도 시간복잡도를 가진 알고리즘이 떠올랐을 땐, 그냥 시간 초과 신경 안 쓰고 문제 풀이를 이어나가도 되는건가요?

안녕하십니까 코딩센세 훗날 일본 개발자 취업을 희망하는 코린이 입니다.저번 시간에도 궁금한 점이 있어서 질문 드렸지만, 오늘도 어김없이 궁금한 점이 생겨서 이렇게 게시판에 글을 작성합니다.3번 문제는 숙제로 주셨지만, 컨셉만 도출하고 코드는 30분 이상 걸리도록 구현을 못하여 강의록의 솔루션 코드를 이해하고 있는 중입니다.서론은 이만하고 바로 본론으로 들어가겠습니다. 본론에 해당 부분은 질문의 내용입니다.솔루션 코드를 해석하는 중에 # 정답 합치기 부분에 질문이 있습니다. 그 부분은 바로 maxPoint[1] - maxPoint[0] + 1 코드가 왜 필요한지 입니다. 아마도 추정컨대 높은 기둥이 넓이를 구해서 더해주는 연산으로 보입니다만, 항상 밑변이 1이라는 문제의 가정이 있었는데도 answer += 1*maxHeight 또는 answer += maxHeight가 오답인 근거를 듣고 싶습니다!바쁘신 와중에도 답변에 신경써주셔서 감사드립니다.

package hash; import java.util.ArrayList; import java.util.Collection; import java.util.HashSet; import java.util.Scanner; public class TypeOfSales { static ArrayList<Integer> solution(int n, int k, int[] arr) { Collection<Integer> set = new HashSet<>(); Collection<Integer> list = new ArrayList<>(); ArrayList<Integer> result = new ArrayList<>(); int p1 = 1; for(int i = 0; i < k; i++) { list.add(arr[i]); } set.addAll(list); result.add(set.size()); while(p1 < n-k+1) { set.clear(); list.remove(arr[p1-1]); list.add(arr[p1+k-1]); set.addAll(list); result.add(set.size()); p1++; } return result; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.nextInt(); int[] arr = new int[n]; for(int i = 0; i < n; i++) { arr[i] = sc.nextInt(); } for(int x : TypeOfSales.solution(n, k, arr)) { System.out.print(x + " "); } } }시간 복잡도는 O(N)이 맞는거같은데 4번 5번 테스트 케이스에서 2초 가까이 뜨네용..

안녕하세요 큰돌님! go 재귀 함수에 대해 이해가 되지 않는 부분이 있습니다. 제가 완탐에 대한 이해가 부족해서 함수 호출에 대한 로직이 이해가 안되는 것 같습니다.질문Board d = c; 로 원본과 동일한 보드를 생성하고 d._move()하는 것 까지는 이해를 했습니다. 그런데 그 다음에 왜 d._rotate90();가 아닌 c._rotate90();를 하는지 모르겠습니다. move한 다음 rotate, 또 다시 move한 다음 rotate 과정을 반복하려면 d._rotate90();가 되어야하는 것 아닌가요..? d._move();go(d, here + 1); c._rotate90();이 과정만으로 5번 이동시키는 완탐을 진행할 수 있는지 이해가 안됩니다 ㅜㅜ 혹시 함수 호출이 어떻게 진행되는지 그림으로 설명해주실 수 있나요? 제가 생각한 완탐 방식은 아래와 같습니다. 함수 호출 순서가 go(d, here + 1); c._rotate90();인데 그러면 마지막 호출되는 함수가 return 되고 rotate과정이 진행되는게 아닌가요? rotate함수가 언제 실행되는지 잘 모르겠습니다.제가 생각하는 함수 호출 순서는 아래 그림과 같습니다.뭔가 그림이 카오스네요..큰돌님 코드void go(Board c, int here){ if(here == 5){ c.get_max(); return; } for(int i = 0; i < 4; i++){ Board d = c; // 동일한 구조체 생성 d._move(); go(d, here + 1); c._rotate90(); } return;}

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요import java.util.*; public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int cnt = sc.nextInt(); String pw = sc.next(); pw = pw.replaceAll("#","1").replaceAll("/*","0"); String answer = ""; for(int i=0 ; i<cnt*7 ; i+=7){ char target =(char)Integer.parseInt(pw.substring(i,i+7),2); answer +=target; } System.out.println("answer = " + answer); } }콘솔창 : IntellJ에서는 직접 값을 입력하면 잘 뜨는데 강사님의 채점 프로그램에서는 작동하지 않습니다... 뭐가 문제일까요

백준에서 bfs와 dfs 관련 문제를 추가적으로 풀다보니까, Python3에서는 시간 초과를 해결되지 않는 문제가, PyPy3에서는 해결되는 경우가 있습니다.이럴 때는 Python3에서도 해결 가능하도록 시간 복잡도를 줄이기 위해 노력해야 할까요?아니면 PyPy3 환경에서 정답임을 만족해야 할까요...?

강사님 안녕하세요. 좋은 강의 잘 듣고 있습니다. 임시반장 정하기 문제에서 강사님이 작성해주신 코드와 동일하게 solution 메서드를 만들었다고 보이는데 런타임 에러로 나오는거 같습니다. 혹시 원인을 알 수 있을까요? 감사합니다.  import java.util.*; public class Main { public int Solution(int n, int[][] array) { int answer=0, max=Integer.MIN_VALUE; for(int i=1; i <=n; i++) { int cnt = 0; for(int j=1; j<=n;j++) { for(int k=1; k<=5;k++) { if(array[i][k] == array[j][k]) { cnt++; break; } } } if(cnt>max) { max = cnt; answer = i; } } return answer; } public static void main(String[] args) { Scanner in=new Scanner(System.in); int n = in.nextInt(); Main T = new Main(); int[][] array = new int[n][n]; for(int i = 0; i < n ; i++) { for(int j = 0; j < n ; j++) { array[i][j] = in.nextInt(); } } System.out.println(T.Solution(n, array)); } }

기존코드def two_sum(nums, target): memo = {} for v in nums: memo[v] = 1 for v in nums: needed_number = target - v if needed_number in memo: return True return False기존 코드에서 첫번째 for문은 O(n)이고두번째 for문은 O(1)이 n번 실행되니까 최종적으로는 O(n)이 되어서 해당 알고리즘의 시간복잡도는 O(n)이되는데처음에 문제를 설명해주실때의 순서대로라면 4를 먼저넣고 target이 14니까 10이 있는지 확인해보고 없으니까 1을 넣고 13이없는지 확인해보고 없으니까 9를 넣고 5가 없으니까 7을 넣고 7이 없으니까 5를 넣고 9가 있으니까 true를 반환 이라고 생각을 했고 그렇게 로직을 짜면 아래와 같은 코드가 될것같습니다(제가 파이썬을 잘 몰라서 정확한지는 모르겠네요 ㅠㅠ)def two_sum(nums, target): memo = {} for v in nums: memo[v] = 1 needed_number = target - v if needed_number in memo: return True return False해당 코드에서는 첫번째 for문 내부의 시간복잡도가 전부다 O(1)이고 그걸 n번 반복하는것이니 O(n)이라는 최종적인 시간복잡도라고 생각을 하는게 맞을까요??만약에 아래에 짠 로직이 올바른 로직이라면위에 로직은 n번 연산하면서 dictionary에 넣고 후에 요소를 돌면서 답을 찾고아래로직은(코드가 맞다면) dictionary를 다 넣지 않더라도 중간에 값이 나오면 중간에 연산을 끝낼 수 있으니까 조금더 효율적이라고 생각을 했습니다제가 생각한 방식이 맞는지 그리고 이런 작은(?)효율성이 코딩테스트에서 의미있게 다가올지가 궁금합니다!

안녕하세요?강사님께서 영상에서는 deque 자료형으로 바로바로 pop 하는 방식으로 코드를 짜셨는데요강의 내용:arr.sort() arr = deque(arr) cnt = 0 while arr: if len(arr)==1: cnt += 1 break if arr[0]+arr[-1] > limit: arr.pop() cnt += 1 else: arr.popleft() arr.pop() cnt += 1 print(cnt) 그런데 비슷하다고 생각한 인덱스 이동 방식은 오답인 거 같습니다 arr.sort() lt = 0 rt = n - 1 while lt <= rt: if len(arr) == 1: cnt += 1 break sum = arr[lt] + arr[rt] if sum <= limit: cnt += 1 lt += 1 rt -= 1 else: cnt += 1 rt -= 1 # 맨 끝 가장 큰 수 pop print(cnt) 테스트 케이스는 강사님께서 댓글에 알려주신 8 14971 72 73 74 75 76 77 78 149로 돌려보니, 강의 내용은 5가 나오고 두번째 방식은 4가 나오네요? 근데 제가 이해가 딸려서 그런지 인덱스 이동하는 방식과 pop 방식의 차이가 잘 머리로 들어오지 않습니다..  

최소 힙 insert#reheapUp(index) { // index 0은 root if (index > 0) { // 부모 노드가 root가 아니면 계속 비교 const parentIndex = Math.floor((index - 1) / 2); if (this.arr[index] < this.arr[parentIndex]) { // 값 바꾸기 const temp = this.arr[index]; this.arr[index] = this.arr[parentIndex]; this.arr[parentIndex] = temp; this.#reheapUp(parentIndex); } } } // O (log n) insert(value) { this.arr.push(value); this.#reheapUp(this.arr.length - 1); }const heap = new MinHeap(); // insert는 큰 값부터 넣고, root가 8이 되는지 확인 heap.insert(78); heap.insert(56); heap.insert(45); heap.insert(32); heap.insert(23); heap.insert(19); heap.insert(8); // [8, 32, 19, 78, 45, 56, 23] heap; 최대 힙 insert#reheapUp(index) { // index 0은 root if (index > 0) { // 부모 노드가 root가 아니면 계속 비교 const parentIndex = Math.floor((index - 1) / 2); if (this.arr[index] > this.arr[parentIndex]) { // 값 바꾸기 const temp = this.arr[index]; this.arr[index] = this.arr[parentIndex]; this.arr[parentIndex] = temp; this.#reheapUp(parentIndex); } } } // O (log n) insert(value) { this.arr.push(value); this.#reheapUp(this.arr.length - 1); }const heap = new MaxHeap(); // insert는 작은 값부터 넣고, root가 78이 되는지 확인 heap.insert(8); heap.insert(19); heap.insert(23); heap.insert(32); heap.insert(45); heap.insert(56); heap.insert(78); // [78, 32, 56, 8, 23, 19, 45] heap; 최대 힙 -> 최소 힙// 최소 힙 유지 함수 #heapifyMin(index) { // 수정, 삭제 const leftIndex = index * 2 + 1; const rightIndex = index * 2 + 2; const smallerIndex = (this.arr[leftIndex] || 0) < (this.arr[rightIndex] || 0) ? leftIndex : rightIndex; if (this.arr[index] > this.arr[smallerIndex]) { // 값 바꾸기 const temp = this.arr[index]; this.arr[index] = this.arr[smallerIndex]; this.arr[smallerIndex] = temp; // 재귀적으로 최소 힙 유지 this.#heapifyMin(smallerIndex); } } toMinHeap() { // O(1/2n) for (let i = Math.floor(this.arr.length / 2 - 1); i >= 0; i--) { this.#heapifyMin(i); } }const heap = new MaxHeap(); // insert는 작은 값부터 넣고, root가 78이 되는지 확인 heap.insert(8); heap.insert(19); heap.insert(23); heap.insert(32); heap.insert(45); heap.insert(56); heap.insert(78); // [78, 32, 56, 8, 23, 19, 45] heap.toMinHeap(); // [8, 23, 19, 32, 78, 56, 45] heap; // 최소 힙 insert 결과 값 [8, 32, 19, 78, 45, 56, 23] // 최대 힙 insert 결과 값 [78, 32, 56, 8, 23, 19, 45] // 최대 힙 -> 최소 힙 결과 값 [8, 23, 19, 32, 78, 56, 45] 최소힙 insert 결과 값과 최대 힙 -> 최소 힙 결과 값은 서로 다른데 최소 힙의 조건은 아래가 크고, 위가 작다. 라고 하셨으니 결과 값은 달라도 최소 힙의 조건이 맞으니 최대 힙 -> 최소 힙 변환 코드가 맞는걸까요? 

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 

선생님 마지막 줄의 return True에서 else를 쓰고 안 쓰고는 왜 상관 없는 건가요?  def isPrime(x): for i in range(2, x): if x%i==0: return False return True  

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요. 아래와 같이 풀어도 될까요 ?아래와 같은 경우에 시간복잡도는 어떻게 될까요 ...?const solution = (k, arr) => { let answer = Array.from({ length: k }, () => 0); for (let i = 0; i < arr.length; i++) { if (!answer.includes(arr[i])) { answer.unshift(arr[i]); answer.pop(); } else { let tmp = answer.filter((v) => v !== arr[i]); tmp.unshift(arr[i]); answer = tmp; } } return answer; }; console.log(solution(5, [1, 2, 3, 2, 6, 2, 3, 5, 7]));

enumerate 함수에 대해 질문 있습니다.  a=[23, 12, 36, 53, 19] for x in enumerate(a): print(x)print()  for x in enumerate(a): print(x[0], x[1])print()  for index, value in enumerate(a): print(index, value)print()  똑같은 enumerate함수를 썼는데왜 첫번째 for문에서만 튜플 형태로 출력이 되고 두번째, 세번째에선 그냥 값만 출력이 되는 건가요? 

안녕하세요 선생님! 복습하다가 의문점이 생겨 질문드립니다.from collections import defaultdict N = int(input()) T = int(input()) dic = defaultdict(list) discovered = [] for _ in range(T): a, b = map(int, input().split()) dic[a].append(b) dic[b].append(a) def dfs(node): global dic, discovered discovered.append(node) for n in dic[node]: if n not in discovered: dfs(n) return dfs(1) print(len(discovered) - 1)이 코드에서 dic[b].append(a)를 지워도 문제 해결에는 영향이 없어 보이는데, 백준에 제출하면 틀린 답으로 나옵니다.즉, 그래프를 양방향이 아닌 단방향으로 설정해도 문제 없지 않나요..?

코테를 볼때 1차 2차 나눠서 보는 기업이 있더라구요 (대표적으로 카카오)근데 1차는 알고리즘이고 2차는 api 통신을 해야하는 코테로 진행한다고 봤는데 이렇게 api통신을 이용해 코테를 보는 기업이 많을까요? 제가 찾을때는 카카오만 보여서 질문드렸습니다또 sql 코테를 보는곳도있다고 들었는데 이것도 많이 보는지 여쭤보고 싶습니다

선생님 조건문에서 i+=i 는 써야 하는 위치가 정해져 있는 건가요?왠지 쓰는 위치가 애매하게 느껴집니다..print 다음으로 마지막에 쓰면 되는 건가요?