얄루의 개발일기🥑

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님' 책을 보고 작성되었습니다. 😎문제 : https://leetcode.com/problems/merge-two-binary-trees/ 두 이진 트리를 병합하라. 중복되는 노드는 값을 합산한다. [재귀 탐색] class Solution: def mergeTrees(self, t1: Optional[TreeNode], t2: Optional[TreeNode]) -> Optional[TreeNode]: if t1 and t2: #자식노드가 모두 있을 경우 node = TreeNode(t1.val + t2.val) node.left = self.mergeTrees(t1.left, t2.left) node.right = self.mergeTrees(t1.rig..

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님' 책을 보고 작성되었습니다. 😎문제 : https://leetcode.com/problems/invert-binary-tree/submissions/ 중앙을 기준으로 이진 트리를 반전시키는 문제 [반복 구조로 BFS] import collections class Solution: def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: queue = collections.deque([root]) while queue: node = queue.popleft() if node: node.left, node.right = node.right, node.left queue.append(node..

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님' 책을 보고 작성되었습니다. 😎문제 : https://leetcode.com/problems/longest-univalue-path/ 동일한 값을 지닌 가장 긴 경로를 찾아라. [상태값 거리 계산 DFS] class Solution: result: int = 0 def longestUnivaluePath(self, root: TreeNode) -> int: def dfs(node: TreeNode): if node is None: return 0 # 존재하지 않는 노드까지 DFS 재귀 탐색 left = dfs(node.left) right = dfs(node.right) # 현재 노드가 자식 노드와 동일한 경우 거리 1 증가 if node.left an..

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님' 책을 보고 작성되었습니다. 😎문제 : https://leetcode.com/problems/diameter-of-binary-tree/ 이진 트리에서 두 노드 간 가장 긴 경로의 길이를 출력하라. [상태값 누적 트리 DFS] class Solution: longest = 0 def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int: def dfs(node:TreeNode)->int: if not node: return -1 #각 노드의 왼쪽, 오른쪽 리프노드(자식이 없는 잎 노드)까지 탐색 left = dfs(node.left) right = dfs(node.right) #가장 긴 경로 self..

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님' 책을 보고 작성되었습니다. 😎문제 : https://leetcode.com/problems/maximum-depth-of-binary-tree/submissions/ 이진 트리의 최대 깊이를 구하라 [반복 구조로 BFS 풀이] import collections class Solution: def maxDepth(self, root: Optional[TreeNode]) -> int: if root is None: return 0 q = collections.deque([root]) depth = 0 while q: depth += 1 for _ in range(len(q)): current_root = q.popleft() if current_root...

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님' 책을 보고 작성되었습니다. 😎문제 : https://leetcode.com/problems/cheapest-flights-within-k-stops/ 시작점에서 도착점까지의 가장 저렴한 가격을 계산하되. k개의 경유지 이내에 도착하는 가격을 리턴하라. 경로가 존재하지 않을 경우 -1을 리턴한다. [다익스트라 응용버전] import collections import heapq class Solution(object): def findCheapestPrice(self, n, flights, src, dst, k): graph = collections.defaultdict(list) for u,v,w in flights: graph[u].append((v,..

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님' 책을 보고 작성되었습니다. 😎문제 : https://leetcode.com/problems/network-delay-time/ k부터 출발해 모든 노드가 신호를 받을 수 있는 시간을 계산하라. 불가능할 경우 -1을 리턴한다. 입력값(u,v,w)는 각 출발지, 도착지, 소요 시간으로 구성되며, 전체 노드의 개수는 N으로 입력받는다. [다익스트라 알고리즘 구현] import collections import heapq class Solution(object): def networkDelayTime(self, times, n, k): graph = collections.defaultdict(list) #그래프 인접 리스트 구성 for u,v,w in tim..

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님' 책을 보고 작성되었습니다. 😎문제 : https://leetcode.com/problems/course-schedule/submissions/ 0을 완료하기 위해서 1을 끝내야 한다는 것을 [0,1] 쌍으로 표현하는 n개의 코스가 있다. 코스 개수 n과 이 쌍들을 입력으로 받았을 때 모든 코스가 완료 가능한지 판별하라. [DFS로 순환 구조 판별 - 시간 초과] import collections class Solution(object): def canFinish(self, numCourses, prerequisites): graph = collections.defaultdict(list) for x, y in prerequisites: graph[x]..

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님' 책을 보고 작성되었습니다. 😎문제 : https://leetcode.com/problems/reconstruct-itinerary/ [from, to]로 구성된 항공권 목록을 이용해 JFK에서 출발하는 여행 일정을 구성하라. 여러 일정이 있는 경우 사전 어휘순으로 방문한다. [DFS로 일정 그래프 구성] import collections class Solution(object): def findItinerary(self, tickets): graph = collections.defaultdict(list) for a, b in sorted(tickets): graph[a].append(b) route = [] def DFS(a): while graph..

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님' 책을 보고 작성되었습니다. 😎문제 : https://leetcode.com/problems/subsets/submissions/ 모든 부분 집합을 리턴하라 class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: result = [] def DFS(index, path): result.append(path) for i in range(index, len(nums)): DFS(i+1, path + [nums[i]]) DFS(0,[]) return result