Trie
leetcode.com/problems/implement-trie-prefix-tree/ ['app', 'apple', 'appear', 'ape', 'boat', 'bear', 'korea', 'korean'] 위와 같은 문자열들의 배열이 있다고 해보자. 위 문자열 안에 특정 문자열, 예를 들면 'ape'가 있는지 찾아보려면 어떻게 해야 할까? 배열 자료구조를 그대로 쓴다면, 처음부터 하나하나 비교해보는 방법밖에 없을 것이다. 전체 문자열의 갯수를 n, 타겟이 되는 특정 문자열의 길이를 m이라 한다면 시간 복잡도는 O(nm)이 된다. 하지만 이보다 명백하게 나은 방법이 있다. 사람이 저 위의 문자열들 중에서 'ape'가 있는지 찾는다면, 우선 'a'로 시작하는 문자들만을 찾을 것이고, 그 다음은 'p'..
1. Insertion 일단 search로 insert해야 할 노드의 위치를 찾아본다. 이 노드가 어떤 상태냐에 따라 다음의 세 가지 경우로 나누어 생각해 볼 수 있다. 1. 노드에 키값이 한 개일때 2. 노드에 키값이 두 개고, 그 부모 노드의 키값은 한 개일때 3. 노드에 키값이 두 개고, 그 부모 노드의 키값도 두 개일때 ❗️노드가 루트고 키값이 두개인 경우, '노드에 키값이 두 개고, 그 부모 노드의 키값이 0개일때' 라고 할 수 있으나 이런 경우는 발생하지 않는다. 1. 노드에 키값이 한 개일때 이 경우에는 그냥 그 노드에 넣어주면 끝난다. 예를 들어, 30 / \ 10 35 에 40을 넣으면 30 / \ 10 35,40 이 되고 끝난다. 2. 노드에 키값이 두 개고, 그 부모 노드의 키값은 한..
binary search tree를 다른 곳에 저장했다가, 원할때 다시 불러와야 하는 상황을 상상해보자. 예를 들면... 노트북에 랜섬웨어가 들어와서 공장초기화를 해야 하는데 이 binary search tree는 남겨두고 싶어서 usb에 넣어놨다가 복원 후 가져와야 한다든지.. 아무튼 그런 상황에서 binary search tree를 저장하고 불러오는 방법은 두 가지로 생각해볼 수 있다. 1. binary search tree의 형태 그대로 저장한 후 원본 그대로 복원 2. binary serach tree내 키들을 정렬된 상태로 저장한 후 더 balanced된 상태로 복원 각각을 자세히 살펴보자. 1. binary search tree의 형태 그대로 저장한 후 원본 그대로 복원 형태 그대로 저장한다는..
leetcode.com/problems/merge-two-binary-trees/ 풀이 1) class Solution: def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode: if not root1: return root2 if not root2: return root1 def dfs(node1, node2): node1.val += node2.val if node1.left and not node2.left: node2.left = TreeNode() if node2.left and not node1.left: node1.left = TreeNode() if node1.right and not node2.right: node2.righ..
class Solution: def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int: graph = collections.defaultdict(list) for x, y, w in times: graph[x].append((y, w)) dist = {} Q = [(0, k)] while Q: time, node = heapq.heappop(Q) if node not in dist: dist[node] = time for v, w in graph[node]: alt = time + w heapq.heappush(Q, (alt, v)) max = 0 for i in range(n): if i + 1 not in dist: retur..
leetCode - Subsets
leetcode.com/problems/subsets/ 1. 시간 복잡도 높은 풀이 class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: def DFS(level, node, subset): subset.append(node) if level == len(nums): subsets.append([num for num in subset if num != None]) subset.pop() return for child in [None, nums[level - 1]]: DFS(level + 1, child, subset) subset.pop() subsets = [] DFS(0, None, []) return subsets 수학에서 부..
leetcode.com/problems/combination-sum class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: def DFS(node, combination, summation): combination.append(node) summation += node if summation == target: combinations.append(combination[:]) summation -= combination.pop() return for child in [child for child in deq_candidates if child >= node and child + summat..
leetCode - Combinations
leetcode.com/problems/combinations class Solution: def combine(self, n: int, k: int) -> List[List[int]]: def DFS(level, node, combination): combination.append(node) # for leaf if level == k - 1: combinations.append(combination[:]) combination.pop() return for next_node in range(node + 1, n - k + level + 3): DFS(level + 1, next_node, combination) # for every backtracking except backtracking at le..
leetcode.com/problems/permutations/ class Solution: def permute(self, nums: List[int]) -> List[List[int]]: permutations = [] def DFS(node, unvisited, permutation): permutation.append(node) unvisited = set(nums) - set(permutation) for next_node in unvisited: DFS(next_node, unvisited, permutation) if unvisited == set(): permutations.append(list(permutation)) # copy by value permutation.pop() for n..
leetcode.com/problems/letter-combinations-of-a-phone-number/ class Solution: def letterCombinations(self, digits: str) -> List[str]: # exception case 1: no input if not digits: return [] # mapping map = { '2': {'a', 'b', 'c'}, '3': {'d', 'e', 'f'}, '4': {'g', 'h', 'i'}, '5': {'j', 'k', 'l'}, '6': {'m', 'n', 'o'}, '7': {'p', 'q', 'r', 's'}, '8': {'t', 'u', 'v'}, '9': {'w', 'x', 'y', 'z'} } # exce..