본문 바로가기
반응형

Coding Test/LeetCode57

[LeetCode] 226. Invert Binary Tree [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (이진 트리 반전) 중앙을 기준으로 트리를 반전하라. 2. 풀이 python의 특징을 이용한 풀이 BFS를 이용한 풀이 3. 코드 # 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 invertTree(self, root: TreeNode) -> TreeNode: # Python # if root: # root.left, root.right =.. 2021. 11. 24.
[LeetCode] 543. Diameter of Binary Tree [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (이진 트리의 직경) 이진 트리에서 두 노드 간 가장 긴 경로의 길이를 출력하라. 예를 들어, 위와 같은 트리는 4-2-1-3 or 5-2-1-3 으로 답은 3이다. 2. 풀이 DFS를 이용한 풀이 중첩 함수에서 숫자나 문자와 같은 불변 객체를 재할당하면 참조ID가 변경되므로 클래스 변수를 사용해야 한다! 3. 코드 # 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 .. 2021. 11. 24.
[LeetCode] 104. Maximum Depth of Binary Tree [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (이진 트리의 최대 깊이) 이진 트리의 최대 깊이를 구하라. 2. 풀이 BFS를 이용한 풀이 3. 코드 # 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 maxDepth(self, root: TreeNode) -> int: if root is None: return 0 q = collections.deque([root]) depth = 0 w.. 2021. 11. 24.
[LeetCode] 787. Cheapest Flights Within K Stops [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (K경유지 내 가장 저렴한 항공권) 시작점에서 도착점까지의 가장 저렴한 가격을 계산하되, K개의 경유지 이내에 도착하는 가격을 리턴하라. 경로가 존재하지 않을 경우 -1을 리턴한다. 2. 풀이 다익스트라 알고리즘을 이용한 풀이 collections.defaultdict(lambda : float('inf')) : 딕셔너리에 int의 최대값을 기본값으로 설정 3. 코드 import collections class Solution: def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int: .. 2021. 11. 24.
[LeetCode] 743. Network Delay Time [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (네트워크 딜레이 타임) k부터 출발해 모든 노드가 신호를 받을 수 있는 시간을 계산하라. 불가능할 경우 -1을 리턴한다. 입력값 (x,y,z)는 각각 출발지, 도착지, 소요 시간으로 구성되며, 전체 노드의 개수는 n으로 입력받는다. 2. 풀이 다익스트라 알고리즘을 이용한 풀이 3. 코드 from collections import defaultdict import heapq class Solution: def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int: graph = defaultdict(list) for x, y, w in times.. 2021. 11. 24.
[LeetCode] 207. Course Schedule [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (코스 스케줄) [0, 1]로 구성된 스케줄로 0을 수강하기 위해서는 1을 선수강해야하는 n개의 코스가 있다. 코스 개수 n과 이 쌍들을 입력으로 받았을 때 모든 코스가 완료 가능한지 판별하라. 2. 풀이 DFS를 이용한 풀이 3. 코드 from collections import defaultdict class Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool: graph = defaultdict(list) traced, visited = set(), set() for x, y in prerequisites: g.. 2021. 11. 24.
[LeetCode] 332. Reconstruct Itinerary [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (일정 재구성) [from, to]로 구성된 항공권 목록을 이용해 JFK에서 출발하는 여행 일정을 구하여라. 여러 일정이 있는 경우 사전 어휘 순으로 방문한다. 2. 풀이 DFS를 이용한 풀이 3. 코드 from collections import defaultdict class Solution: def findItinerary(self, tickets: List[List[str]]) -> List[str]: def dfs(city): while graph[city]: dfs(graph[city].pop(0)) ret.append(city) ret = [] graph = defaultdict(list) for a, b.. 2021. 11. 24.
[LeetCode] 78. Subsets [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (부분 집합) 모든 부분 집합을 리턴하라. 2. 풀이 DFS를 이용한 풀이 3. 코드 class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: def dfs(idx, arr): ret.append(arr[:]) for i in range(idx, len(nums)): dfs(i + 1, arr + [nums[i]]) ret = [] dfs(0, []) return ret 결과 : 방식 Status Runtime Memory Language 그래프 (DFS) [Accepted] 32 ms 14.3 MB python3 References 🏋🏻 개인적으.. 2021. 11. 24.
[LeetCode] 200. Number of Islands [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (섬의 개수) 주어진 맵에서 1을 육지, 0을 물로 가정하였을 때, 섬의 개수를 구하여라. 2. 풀이 DFS를 이용한 풀이 3. 코드 class Solution: def numIslands(self, grid: List[List[str]]) -> int: dx = [0, 0, -1, 1] dy = [-1, 1, 0, 0] def dfs(i, j): if i = len(grid) or j = len(grid[0]) or grid[i][j] != '1': return grid[i][j] = '0' for x in range(4): dfs(i+dx[x], j.. 2021. 11. 24.
반응형

티스토리툴바