묻고 답해요
130만명의 커뮤니티!! 함께 토론해봐요.
인프런 TOP Writers
-
미해결Do it! 알고리즘 코딩테스트 with C++
백준 2251 C++ 질문 있습니다.
해당 강의가 없어 직접 질문 하게 되었습니다.2251번 책을 보면 이동 가능한 경로가 A -> B, A ->C, B -> A, B -> C, C -> A, C ->B 로 총 6개인것은 이해를 했습니다. 근데 최초의 물이 C에만 담겨있는데 왜sender, receiver를 6크기의 배열로 선언해주고 아래처럼 for문을 돌리고 없는 물을 처음에 6개의 경로에 따라 퍼다 나르는지 이해가 잘 가지 않습니다.for (int k = 0; k < 6; ++k){ // next[0] = a, next[1] = b, next[2] = c int next[] = { a, b, c }; next[Receiver[k]] += next[Sender[k]]; next[Sender[k]] = 0; // 대상 물통의 용량보다 물이 많아 넘칠 때 if (next[Receiver[k]] > now[Receiver[k]]) { // 초과하는 만큼 다시 이전 물통에 넣음 next[Sender[k]] = next[Receiver[k]] - now[Receiver[k]]; // 대상 물통은 최대로 채움 next[Receiver[k]] = now[Receiver[k]]; } // A와 B의 물의 양을 통하여 방문 배열 체크 if (visit[next[0]][next[1]] == false) { visit[next[0]][next[1]] = true; q.push(make_pair(next[0], next[1])); // A의 물의 양이 0일 때 C의 물의 용량을 정답 변수에 저장 if (next[0] == 0) { ret[next[2]] = true; } }}
-
해결됨실리콘밸리 엔지니어가 가르치는 파이썬 기초부터 고급까지
자식 클래스에서 __init__ 오버라이딩 하는 이유
start 메서드의 경우 부모 클래스와 다르게 출력하는 것들이 있잖아요. 그런데 '__init__'의 경우 사실 부모 클래스에서 하는 기능과 똑같은데 ElectricCar와 CombustionEngineCar에서 모두 init을 오버라이딩 해주는 건 관례 같은 건가요?replit에서 init 오버라이딩 코드를 지우고 작동해도 똑같길래 궁금해져서 질문 드립니다! 수업 너무 좋아요 잘 듣고 따라 하는 중입니다:)
-
미해결비전공자의 전공자 따라잡기 - 자료구조(with JavaScript)
퀴즈 답안
퀴즈 답안지는 따로 제공되지 않나요?
-
해결됨코딩테스트 [ ALL IN ONE ]
leetCode - Two Sum 문제 Memory Limit Exceeded 에러
class Solution(object): def twoSum(self, nums, target): def backtrack(start, curr): # base case : 2개의 합을 더해서 target과 같으면 if len(curr) == 2 and sum(nums[i] for i in curr) == target: return curr # recursion : for i in range(start, len(nums)): curr.append(i) res = backtrack(i + 1, curr) if res: return res curr.pop() return None return backtrack(0, [])https://leetcode.com/problems/two-sum/submissions/1130560186/ 이 코드로 작성해서 leet-code의 two sum 문제에 제출해봤을 때 Memory Limit Exceeded 에러가 나는건 어떻게 해결해야 할까요?
-
해결됨2주만에 통과하는 알고리즘 코딩테스트 (2024년)
3강 누적합 11660 2차원 배열 문제
안녕하세요!강의영상과 백준 문제에서 입력 순서를 x1,y1,x2,y2 형식으로 입력을 받는데 이렇게 입력할 경우 결과가 반대로 나오는거 같습니다.ex. 1,2,1,2일 경우 2,1,2,1의 결과가 출력인덱싱을 graph[y][x] 형태로 진행하여 파생된 문제 같습니다.그러므로 입력을 y1,x1,y2,x2로 변경하거나 2차원 배열 인덱싱을 graph[x][y] 형태로 변경해야할 것 같습니다.제가 이해한게 맞나요?항상 좋은 강의해주셔서 감사드립니다.
-
미해결자바 기초부터 마스터하기 with 은종쌤 (Do it 자바 프로그래밍 입문) - Part 2(마스터편)
섹션 1 - 1 equals 재정의 하면 왜 hashcode도 재정의 해야하는지..
섹션 1 - 1 강의 내용.왜 equals 재정의 했다면 왜 hascode 도 재정의 해야하는지 이해가 되지 않습니다.
-
해결됨이득우의 꼭 배워야하는 게임 알고리즘
depth 구할 때 floor로 처리하면 -1이 사라지는 과정이 잘 모르겠어요.
결국엔 log(2, x) -1 = floor ( log(2,x) ) 라는 것 같아 보이는데.. 이 수식이 잘 이해가 안 가는 것 같아요....
-
미해결이득우의 꼭 배워야하는 게임 알고리즘
GetQuads가 out of area를 체크 할 수 있는건가요??
_bounds가 노드의 영역일텐데 _bound.center와의 비교는 방향을 구하기는 하지만 영역을 완전히 넘어가는지는 체크 못하지 않나 싶어서 질문드렸습니다...
-
미해결실리콘밸리 엔지니어가 가르치는 파이썬 기초부터 고급까지
DataFrame.to_scv() 시 인덱스 컬럼이 비는 문제
문제라고 할 수는 없지만 보기가 좀 이상해서 컬럼 이름을 짓고 싶은데요.data.index.name = 'No'이렇게 하니 csv 저장시 빈쉼표가 아니라 보기 좋긴 합니다만.print(data)시에는 나머지 컬럼에 빈줄이 생기네요.큰 문제는 아닙니다만, 글 남겨봅니다.
-
미해결실리콘밸리 엔지니어가 가르치는 파이썬 기초부터 고급까지
논리 연산자 알아보기 강의 질문입니다.
7번 줄에 \는 어떤 이유로 넣으신 건가요? 역 슬레시를 무슨 이유로 사용 하신 건지 궁금합니다.
-
해결됨실리콘밸리 엔지니어가 가르치는 파이썬 기초부터 고급까지
마지막 0-10까지 출력 부분 질문입니다.
질문은 많으시면 많을수록 좋습니다. 가능한 빠른 답변 드리겠습니다.원활한 답변을 위해, 자세한 질문 사항 부탁드려요 int(random_float*10)이렇게 코드를 작성하면 0부터 9까지의 정수가 출력되는 거 아닌가요?헷갈려서 질문 남깁니다!
-
미해결Do it! 알고리즘 코딩테스트 with C++
퀵정렬 질문
퀵정렬 14:38에 32랑 15를 swap 한다고 하셨는데 그 이유를 모르겠어요. 첫번째 정렬에서는 start와 end가 만난 15가 45와 비교해서 45가 더 크기 때문에 15의 오른쪽으로 이동한다는건 알겠는데, 두번째도 똑같이 적용하면 [5, 15, 32, 24, 42]가 아닌가요??
-
해결됨코딩테스트 [ ALL IN ONE ]
DLinked List를 활용한 insert에서 메모리 할당해제관련해서 질문이 있습니다. (BrowserHistory)
class Node { let value: String var prev: Node? var next: Node? init(value: String, prev: Node? = nil, next: Node? = nil) { self.value = value self.prev = prev self.next = next } } class BrowserHistory { var head: Node? var current: Node? init(_ homepage: String) { let newNode = Node(value: homepage) self.head = newNode self.current = newNode } func visit(_ url: String) { self.current?.next = Node(value: url, prev: self.current) self.current = self.current?.next } //..생략 }강의를 듣던중 의문이 생겨서 질문남깁니다. visit시에 참조가 새로운 노드로 변경되기 때문에 그 이전에 current뒤에 존재하는 Node들은 뒤에 몇만개가 있더라도 맨앞에 있던 노드의 참조를 가르키는 곳이 없기 때문에 모두 메모리에서 가비지 컬렉터에 의해 메모리에서 지워진다라고 말씀하셨는데, 뒤에 1개의 Node가 있는 경우는 그렇지만 Doubly Linked List의 경우 그 뒤에 Node들의 prev로 그 이전 Node들을 가르키고 있어 참조하는 곳이 최소 1개 이상은 존재하게 되어 메모리에서 할당해제가 되지 않을 것이라고 생각했습니다. 따라서 visit당시에 뒤에 있는 Node들도 메모리에서 할당해제가 되게끔 리스트의 끝까지 돌면서 Node의 next만 지워주고 테스트해보자고 생각해서 아래와 같이 코드를 수정하였습니다. func visit(_ url: String) { var tmp = self.current while tmp?.next != nil { var before = tmp tmp = tmp?.next before?.next = nil } self.current?.next = Node(value: url, prev: self.current) self.current = self.current?.next }이를 LeetCode의 결과로 확인해보니 물론 속도는 5ms 줄었지만, 메모리 4MB정도 줄일 수 있었습니다.Swift의 경우 가비지 컬렉터가 아닌 ARC가 컴파일 타임에 Reference Count를 확인하기 때문에 그 동작 방식에서의 차이에서 비롯된 차이인지 궁금합니다.가비지 컬렉터에서는 실제로 위의 같은 경우에도 메모리 할당 해제가 되는건가요??
-
해결됨코딩테스트 [ ALL IN ONE ]
디코
디코를 사정이 있어 나가게 되어 다시 초대받을 수 있는지 궁금합니다.
-
해결됨코딩테스트 [ ALL IN ONE ]
num of Islands를 복습하면서 궁금한 것이 있습니다.
먼저 제가 짠 시간초과 난 소스코드는 다음과 같습니다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에서 시간초과가 났습니다. 왜 그런지 알 수 있을까요?
-
해결됨2주만에 통과하는 알고리즘 코딩테스트 (2024년)
3강 3번 문제. 텐트세우기 #2304
안녕하십니까 코딩센세 훗날 일본 개발자 취업을 희망하는 코린이 입니다.저번 시간에도 궁금한 점이 있어서 질문 드렸지만, 오늘도 어김없이 궁금한 점이 생겨서 이렇게 게시판에 글을 작성합니다.3번 문제는 숙제로 주셨지만, 컨셉만 도출하고 코드는 30분 이상 걸리도록 구현을 못하여 강의록의 솔루션 코드를 이해하고 있는 중입니다.서론은 이만하고 바로 본론으로 들어가겠습니다. 본론에 해당 부분은 질문의 내용입니다.솔루션 코드를 해석하는 중에 # 정답 합치기 부분에 질문이 있습니다. 그 부분은 바로 maxPoint[1] - maxPoint[0] + 1 코드가 왜 필요한지 입니다. 아마도 추정컨대 높은 기둥이 넓이를 구해서 더해주는 연산으로 보입니다만, 항상 밑변이 1이라는 문제의 가정이 있었는데도 answer += 1*maxHeight 또는 answer += maxHeight가 오답인 근거를 듣고 싶습니다!바쁘신 와중에도 답변에 신경써주셔서 감사드립니다.
-
해결됨그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)
유효성 검사에 대해 질문이 있습니다.
좋은 강의 만들어주셔서 감사합니다.몇몇 메서드가 실행될 때 인덱스의 유효성 검사를 진행하는데, 이 부분의 로직이 완전히 같은 상황이니 유효성 검사 메서드를 따로 생성해서 리팩토링 하는 것도 좋은 방법일까요?
-
해결됨[파이썬/Python] 문과생도 이해하는 DFS 알고리즘! - 입문편
PyPy3와 Python3
백준에서 bfs와 dfs 관련 문제를 추가적으로 풀다보니까, Python3에서는 시간 초과를 해결되지 않는 문제가, PyPy3에서는 해결되는 경우가 있습니다.이럴 때는 Python3에서도 해결 가능하도록 시간 복잡도를 줄이기 위해 노력해야 할까요?아니면 PyPy3 환경에서 정답임을 만족해야 할까요...?
-
해결됨코딩테스트 [ ALL IN ONE ]
딕셔너리를 활용한 two-sum 질문있습니다
기존코드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를 다 넣지 않더라도 중간에 값이 나오면 중간에 연산을 끝낼 수 있으니까 조금더 효율적이라고 생각을 했습니다제가 생각한 방식이 맞는지 그리고 이런 작은(?)효율성이 코딩테스트에서 의미있게 다가올지가 궁금합니다!
-
미해결비전공자의 전공자 따라잡기 - 자료구조(with JavaScript)
최소힙의 결과값과 최대힙->최소힙 결과값이 다른게 맞나요?
최소 힙 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 결과 값과 최대 힙 -> 최소 힙 결과 값은 서로 다른데 최소 힙의 조건은 아래가 크고, 위가 작다. 라고 하셨으니 결과 값은 달라도 최소 힙의 조건이 맞으니 최대 힙 -> 최소 힙 변환 코드가 맞는걸까요?