Algorithm101 [그래프] 일정 재구성 332 | Reconstruct Itinerary https://leetcode.com/problems/reconstruct-itinerary/ 작성 코드 class Solution: def findItinerary(self, tickets: List[List[str]]) -> List[str]: path = ["JFK"] def dfs(depart, next_tickets_dict): if len(path) == len(tickets) + 1: return path if not tickets_dict[depart]: return next_tickets_dict[depart].sort() while next_tickets_dict[depart]: next_tickets_dict_copy = next_ti.. 2022. 3. 3. [그래프] 부분 집합 78 | Subsets https://leetcode.com/problems/subsets/ 작성 코드 class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: res = [] prev_elements = [] def dfs(depth, cnt, elements): if depth == cnt: res.append(prev_elements[:]) return for elem in elements: next_elements = elements[elements.index(elem):] prev_elements.append(elem) next_elements.remove(elem) dfs(depth + 1, cnt, next_elements.. 2022. 3. 1. [그래프] 조합의 합 39 | Combination Sum https://leetcode.com/problems/combination-sum/ 작성 코드 class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: results = [] prev_elements = [] def dfs(cnt, elements): if len(prev_elements) == cnt: if sum(prev_elements) == target: results.append(prev_elements[:]) return for cand in elements: prev_elements.append(cand) dfs(cnt, candidates.. 2022. 2. 28. [그래프] 순열 46 | Permutations https://leetcode.com/problems/permutations/ 작성 코드 class Solution: def permute(self, nums: List[int]) -> List[List[int]]: nums.sort() stack = [] answer = [] for num in nums: need_visited = nums visited = num del need_visited[need_visited.index(num)] while need_visited: v = visited.pop() nums를 차례대로 돌면서, need_visited에 nums, visited에 num 할당 현재 num 은 이미 돈 것이니 need_visited 에서 num 삭제 .. 2022. 2. 25. 파이썬 알고리즘 인터뷰 | 그래프 DFS pg. 323 BFS에 비해 더 널리 쓰임 스택, 재귀로 구현 백트래킹을 통해 뛰어난 효용 BFS pg. 323 큐로 구현 그래프의 최단 경로 구하는 문제 재귀로 동작하지 않음 백트래킹 pg. 328 DFS를 이야기하다보면 항상 같이 나옴 주로 재귀로 구현 2022. 2. 24. [그래프] 전화 번호 문자 조합 17 | Letter Combinations of a Phone Number https://leetcode.com/problems/letter-combinations-of-a-phone-number/ 작성 코드 자릿수 만큼 for 문을 돌아야겠다는 생각은 했으나 구현 방법을 몰랐음 작성 코드 DFS 탐색 + 백트래킹 class Solution: def letterCombinations(self, digits: str) -> List[str]: def dfs(index, path): # search till the end, Backtracking if len(path) == len(digits): result.append(path) return # for statement - Number of digits.. 2022. 2. 23. 이전 1 ··· 8 9 10 11 12 13 14 ··· 17 다음 반응형
