본문 바로가기
반응형

그래프6

[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] 39. Combination Sum [Python(파이썬)] '파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀 문제 👉 1. 문제 (조합의 합) 숫자 집합 candidates를 조합하여 합이 target이 되는 원소를 나열하라. 각 원소는 중복으로 나열 가능하다. 2. 풀이 DFS를 이용한 풀이 3. 코드 class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: def dfs(csum, idx, path): if csum < 0: return if csum == 0: ret.append(path[:]) return for i in range(idx, len(candidates)): dfs(csum - candidates[i], i, path +.. 2021. 11. 23.
반응형

티스토리툴바