반응형 SWE/코테137 DFS BFS d DFS BFS Depth First Search Breadth First Search Stack / Recursive Queue Time Complexity: - 인접 리스트로 표현된 그래프 O(N+E) - 인접 행렬로 표현된 그래프 O(N^2) N is the number of nodes in the graph, E is the number of edges adjacent matrix dfs 시간 복잡도 dfs(x)는 x에 방문하는 함수이므로 정점의 개수, 즉 차수인 V번만큼 dfs(x)가 호출됩니다. 따라서 dfs(x) 시간복잡도 *V가 전체 dfs 알고리즘의 시간복잡도가 됩니다. - 인접 행렬로 표현된 그래프 모든 정점을 다 찾아봐야하기 때문에 dfs(x)의 시간복잡도는 O(N) dfs(x)가 .. 2022. 3. 28. Hashmap algorithm Hash Function best O(1), worst O(n) Load Factor : n/table size , smaller smaller is better Seperate chaining Open Addressing - Python Dictionary -> rehasing ss ListNode: def __init__(self, key=None, value=None): self.key = key self.value = value self.next = None class MyHashMap: def __init__(self): self.size = 1000 self.table = collections.defaultdict(ListNode) def put(self, key:int, value: int).. 2022. 3. 28. [Leetcode][python] 11. Container With Most Water problem: https://leetcode.com/problems/container-with-most-water/ code: brute-force time limit exceeded class Solution: def maxArea(self, height: List[int]) -> int: left = 0 right = len(height)-1 result = 0 while(left int: left = 0 right = len(height)-1 maxWater = 0 while left result maxWater = max(m.. 2022. 3. 10. [Leetcode][python3] 112. Path Sum problem: https://leetcode.com/problems/path-sum/ code : dfs recursive # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool: # recursive def _dfs(cur, curSum): # exit condition if cur == None : return .. 2022. 3. 10. 이전 1 2 3 4 5 ··· 35 다음 반응형
