본문 바로가기

분류 전체보기147

[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.
[LeetCode] 17. Letter Combinations of a Phone Number [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (전화 번호 문자 조합) 2~9까지 숫자가 주어졌을 때 전화 번호로 조합 가능한 모든 문자를 출력하라. 2. 풀이 DFS를 이용한 풀이 3. 코드 class Solution: def letterCombinations(self, digits: str) -> List[str]: def dfs(idx, path): if idx == leng: ret.append(path) return for c in dic[digits[idx]]: dfs(idx + 1, path + c) if not digits: return [] dic = { "2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6".. 2021. 11. 24.
[LeetCode] 23. Merge k Sorted Lists [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (k개 정렬 리스트 병합) k개의 정렬된 리스트를 1개의 정렬된 리스트로 병합하라. 2. 풀이 우선순위 큐를 이용한 풀이 heapq 이용 heapq.heappush(heap, (node.val, node))를 할 경우 node.val가 같을 경우 TypeError: ' ListNode: root = ret = ListNode(None) heap = [] # 각 연결 리스트의 루트를 힙에 저장 for idx, node in enumerate(lists): if node: # heapq.heappush(heap, (node.val, node)) # 중복 오류 발생 heapq.heappush(heap, (node... 2021. 11. 24.

티스토리툴바