Algorithm/LeetCode8 [LeetCode] 1061. Lexicographically Smallest Equivalent String (파이썬/python) 🎈문제 https://leetcode.com/problems/lexicographically-smallest-equivalent-string/description/ 🎁어떤 알고리즘? 1. union-find 알고리즘 -> 두 번째 풀어보는 union-find문제. 이전에는 리스트의 idx에 값을 저장하여 부모 노드를 찾아줬는데, 이번 문제에서는 숫자가 아닌 str()이여서 리스트의 65번째 idx부터 활용해야하나 고민했지만 검색을 조금 해보니 dict를 활용하는 좋은 방법이 있었다. 💻코드 class Solution: def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str: def find(x): if x not in paren.. 2023. 8. 10. [LeetCode] 684. Redundant Connection (파이썬/python) 🎈문제 https://leetcode.com/problems/redundant-connection/ 🎁어떤 알고리즘? 1. union-find 알고리즘 (생각했던 코드가 동작하지 않아 검색 후 알게 된 알고리즘) -> 각각의 idx를 노드라고 설정했을 때, 연결된 가장 작은 숫자의 노드를 idx의 값으로 가지는 방식으로 연결된 그래프를 찾는 방식이다. 💻코드 class Solution: def findRedundantConnection(self, edges: List[List[int]]) -> List[int]: # 방문 표시와 부모 노드를 동시에 기록할 리스트 par = [0] * (len(edges)+1) def find(x): if par[x] == 0: # 처음 방문 return x return .. 2023. 8. 10. [LeetCode] 863. All Nodes Distance K in Binary Tree (파이썬/python) 🎈문제 All Nodes Distance K in Binary Tree - LeetCode 🎁어떤 알고리즘? 1. 단순히 거리를 이용해 판단하게 되므로, 자식 노드로부터 부모 노드를 접근할 수 있어야 한다. 따라서 기존에 트리 구조로 되어 있던 자료구조를 그래프로 바꿔줘야한다. 2. 그래프로 바꿔준 자료 구조를 BFS를 이용해 거리가 k인 노드를 모두 탐색한다. 💻코드 # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def distanceK(self, root: TreeNode, targ.. 2023. 8. 8. [LeetCode] 802. Find Eventual Safe States (파이썬/python) 🎈문제 https://leetcode.com/problems/find-eventual-safe-states/description/ 🎁어떤 알고리즘? 1. 각 node가 terminal node로 끝나는지 순환하는지를 확인해야 하므로 DFS를 이용한다. 💻코드 class Solution(object): def eventualSafeNodes(self, graph): # 2. dfs를 이용해 끝까지 타고 가서 해당 노드가 safe node인지 판별 def dfs(i): if i in safe: return safe[i] safe[i] = False for neighbor in graph[i]: if not dfs(neighbor): return False safe[i] = True return True n .. 2023. 8. 7. 이전 1 2 다음