월 33,000원
5개월 할부 시다른 수강생들이 자주 물어보는 질문이 궁금하신가요?
- 해결됨코딩테스트 [ 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 에러가 나는건 어떻게 해결해야 할까요?
- 해결됨코딩테스트 [ 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에서 시간초과가 났습니다. 왜 그런지 알 수 있을까요?
- 해결됨코딩테스트 [ 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를 다 넣지 않더라도 중간에 값이 나오면 중간에 연산을 끝낼 수 있으니까 조금더 효율적이라고 생각을 했습니다제가 생각한 방식이 맞는지 그리고 이런 작은(?)효율성이 코딩테스트에서 의미있게 다가올지가 궁금합니다!
- 해결됨코딩테스트 [ ALL IN ONE ]
2차코테 관련해서 질문드립니다
코테를 볼때 1차 2차 나눠서 보는 기업이 있더라구요 (대표적으로 카카오)근데 1차는 알고리즘이고 2차는 api 통신을 해야하는 코테로 진행한다고 봤는데 이렇게 api통신을 이용해 코테를 보는 기업이 많을까요? 제가 찾을때는 카카오만 보여서 질문드렸습니다또 sql 코테를 보는곳도있다고 들었는데 이것도 많이 보는지 여쭤보고 싶습니다
- 해결됨코딩테스트 [ ALL IN ONE ]
노션 링크 좀 보내주세요
노션 공유 요청 드리고 24시간 기다렸는데.......노션에 어떻게 들어가나요?
- 미해결코딩테스트 [ ALL IN ONE ]
o(1)과 o(n)이 헷갈려요
big o(1)은 한번의 연산만 한다는건 이해를했는데 o(n)은 정확히 어떤뜻인지 모르겠어요..
- 해결됨코딩테스트 [ ALL IN ONE ]
백트래킹 강의 언제 올라오나요?
다른 글에서 12월 1일안에 다 올라온다는 글을 봤는데 아직도 안올라와서요
- 해결됨코딩테스트 [ ALL IN ONE ]
공부 방법에 대해 질문이 있습니다.
처음에는 문제만 보고 1시간정도 고민해서 발상이 떠오르지 않았을 때만 발상 관련 강의를 보고, 그 다음에 또 1시간 동안 고민해서 발상을 코드로 옮기는 작업을 했는데도 테스트 케이스를 통과하지 못해서 마지못해 코드 구현 강의를 보았습니다. 그런데 이러한 bfs, dfs문제는 그냥 틀이므로 암기하라고 하셨을 때 허탈감이 들었습니다. 이러면 그냥 코테문제의 전형적인 틀이라고 받아들이고, 암기한 방법으로 다른 문제에 응용하면 되나요?
- 해결됨코딩테스트 [ ALL IN ONE ]
강의자료 노션 링크 언제 보내주시는 걸까요?
어제 노션 링크 요청드렸었는데, 혹시 언제 받아볼 수 있나요?
- 해결됨코딩테스트 [ ALL IN ONE ]
Hash Table 질문있습니다.
질문1. 해시테이블 (Hash Table)강의 마지막부분에서 파이썬은 딕셔너리로 잘구분되어있다고 하셨는데요. 해쉬테이블이 파이썬에서 딕셔너리인가요? 질문2. 제가 원했던 코드는 dir 라는 딕셔너리 변수에 possible 값이 있으면 그부분을 False로 적용시킬려고 했는데 왜 안되나요?질문3. 함수내부에서 print(dir)을 하면 딕셔너리가 출력이 되는데 밖에서 하면 <built-in function dir>이런식으로 출력이 됩니다. 배열은 함수 내부나 외부에서도 출력이 잘 되는데 딕셔너리는 직역변수로 인식이 되나요?질문4. for y in dir: 2번째 for문에 옆에 처럼 안하는 이유는 딕셔너리는 순번이 없어서 그런건가요?import sys sys.stdin = open("input.txt", "r") from collections import deque def two_sum(nums,target): # n=len(nums) dir={} for x in nums: dir[x]=True for y in nums: possible=target-dir[y] if possible in dir: dir[possible] = False print(dir)#{4: True, 1: True, 9: True, 7: True, 5: True, 3: True, 16: True} #제가 원했던 코드는 dir 라는 딕셔너리 변수에 possible 값이 있으면 그부분을 False로 적용시킬려고 했는데 왜 안되나요? # 아래처럼요. # {4: True, 1: True, 9: True, 7: True, 5: False, 3: True, 16: True} two_sum(nums=[4,1,9,7,5,3,16],target=14) print(dir)#<built-in function dir>
- 해결됨코딩테스트 [ ALL IN ONE ]
key + in 관련 질문입니다.
설명 감사드립니다.섹션 4 '[코테 적용] 👉 [2번 문제] key in (후반부) ' 2:45 부분을 공부중입니다.두 가지 질문이 있습니다. 1.이 내용 설명에 의하면 Big O notation에 대해for num in num_dict: => O(n)if num -1 not in num_dict: => O(1)while targer in num_dict: => O(1)이렇게 되는건가요? 2.if 또는 while + 딕셔너리 사용은 항상 Big O notation이 O(1)이 되는건가요? 아니면 상황에 따라 if 또는 while + dict의 시간복잡도가 달라질 수도 있는건가요? 감사합니다. - 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요! - 먼저 유사한 질문이 있었는지 검색해보세요. - 서로 예의를 지키며 존중하는 문화를 만들어가요. - 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
- 해결됨코딩테스트 [ ALL IN ONE ]
메모리 주소의 길이
연결리스트 (Linked List) - 1 강의 보면서 같이 디버깅해보는 중인데요강사님 화면에는 메모리 주소가 11자리로 나오는데저는 메모리 주소가 훨씬 길게 표시됩니다.이건 왜 그런 건가요?
- 해결됨코딩테스트 [ ALL IN ONE ]
백트래킹
안녕하세요!백트래킹 강의들은 언제 업로드가 완료되나요?
- 해결됨코딩테스트 [ ALL IN ONE ]
전자책 교재
교재 전자책을 어떻게 받을수 있나요?
- 해결됨코딩테스트 [ ALL IN ONE ]
이런 질문 드려서 죄송합니다.
결국 미루고 미루다 코딩테스트 예정 일자가 11.26 (토) 2주가 채 남지 않았습니다. 솔직하게 현재 파이썬 기초 문법, 기초적인 수식과 함수 구현만 할 수 있습니다. (반복문 포함) 남은 시간이 적지만, 그래도 전략적으로 준비해보고 싶습니다. 알고리즘은 체감으로 백준 가장 기초 브론즈 1문제, 실버 2문제 정도라고 합니다. 현실적으로 알고리즘 1문제 SQL 1문제 솔 목표를 두고 있습니다. 어떤 걸 집중적으로 공부하는 게 좋을까요? 아래는 작년 유형 및 난이도입니다. 알고리즘 1번. 문자 치환 (가장 기초 브론즈)1->92->8..9->10->0a->z..A->B..예시로 123abcABC => 987zyxBCD 이렇게 변환하는 함수 만들기알고리즘 2번. 대리출석한 사람 수 (실버3)[1,2][1,2][1,2] =>2본인 제외 대출이라고 처리 알고리즘 3번. 분할과 정복 (실버1)정사각형 형태의 데이터를 주고자를 수 있는거 다 잘라서 그 안에서 또 정사각형을 자르고그 안에 알파벳 개수 제한 둔 것이 가능한지
- 해결됨코딩테스트 [ ALL IN ONE ]
최종 진도
안녕하세요, 혹시 최종 진도가 [섹션 9. [심화] Backtracking]까지 일까요? 아니면 다른 부분도 추가로 업데이트가 될까요?
- 해결됨코딩테스트 [ ALL IN ONE ]
bfs 코드를 공부하면서 트리에서의 levelorder 구현 방식에 대해 질문이 있습니다.
from collections import deque def levelorder(root): if root is None: return visited = [] q = deque() q.append(root) while q: cur_node = q.popleft() visited.append(cur_node.val) if cur_node.left: q.append(cur_node.left) if cur_node.right: q.append(cur_node.right) return visitedlevelorder 코드는 위와 같은데요. 여기서 q.append(root) 를 bfs 코드와 같이 사전에 queue = deque(root)로 미리 넣어줘도 되지 않나요? 이렇게하면 오히려 q.append(root)를 하는데 걸리는 런타임을 더 줄일 수 있을 것 같아서요
- 해결됨코딩테스트 [ ALL IN ONE ]
강의자료 부탁드립니다.
노션 이메일 : sooin03@naver.com좋은 강의 잘 듣겠습니다.