Programming/leetcode
-
next_permutation, prev_permutationProgramming/leetcode 2022. 4. 20. 09:23
next_permutation, prev_permutation c++의 레퍼런스에는 들어있지만, python에는 구현되어있지 않아 이 기회에 정리해둘겸 적어본다. python에는 itertools을 이용하여 순열 전체를 구하는 방법은 있다 기본 원리 예를 들어, [1,2,3,4]라는 것을 순열을 만든다 가정해보자 [1, 2, 3, 4] : 오름차순 시작 [1, 2, 4, 3] [1, 3, 2, 4] [1, 3, 4, 2] [1, 4, 3, 2] [2, 1, 3, 4] [2, 1, 4, 3] [2, 3, 1, 4] [2, 3, 4, 1] [2, 4, 3, 1] [3, 2, 4, 1] [3, 4, 2, 1] [4, 3, 2, 1] : 내림차순 마무리 ===> 오름차순으로 시작하고, 내림차순으로 끝이 난다. ..
-
104. Maximum Depth of Binary TreeProgramming/leetcode 2021. 3. 17. 10:00
public int maxDepth(TreeNode root) { if (root == null) return 0; if (root.left == null && root.right == null) return 1; if (root.left != null && root.right == null) return maxDepth(root.left) + 1; if (root.left == null && root.right != null) return maxDepth(root.right) + 1; return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1; } 풀이 방법은 여러 가지가 있겠다. BFS, 재귀... 먼저 BFS로 푼 것이다. Queue에 넣고 해당..
-
743. Network Delay TimeProgramming/leetcode 2021. 3. 10. 11:23
최소 비용을 구하는 문제. 음수값이 없어 다익스트라로 해결 가능하다. def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int: graph = collections.defaultdict(list) for u, v, w in times: graph[u].append((v, w)) distances = {node:float('inf') for node in range(n+1)} distances[k] = 0 q = [(0, k)] while q: weight, vertex = heapq.heappop(q) if weight < distances[vertex]: continue for new_vertex, new_weight in gr..
-
78. SubsetsProgramming/leetcode 2021. 3. 3. 14:41
주어진 배열의 모든 부분 set을 출력하는 문제 dfs를 호출할 때, cur_lst + [num[i]]와 cur_lst.append(nums[i])가 무슨 차이가 있을까? cur_lst + [num[i]] -> 새로운 주소에 list가 만들어지고 cur_lst.append(nums[i]) -> 기존 주소에 nums[i]를 추가한다. 이해가 잘 되지 않아, 저자에게 질문을 했다. def subsets(self, nums: List[int]) -> List[List[int]]: results = [] def dfs(cur_lst, index): results.append(cur_lst) for i in range(index, len(nums)): dfs(cur_lst+[nums[i]], i+1) dfs([]..
-
39. Combination SumProgramming/leetcode 2021. 3. 3. 13:43
재귀 호출 돌리면서 target 값이 되면 result에 저장하면 되는 문제 def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: results = [] def dfs(index, cur, path): if cur < 0: return if cur == 0: results.append(path) return for i in range(index, len(candidates)): dfs(i, cur-candidates[i], path + [candidates[i]]) dfs(0, target, []) return results
-
17. Letter Combinations of a Phone NumberProgramming/leetcode 2021. 2. 24. 21:24
dfs-재귀를 이용한 문제, 전화 패드의 숫자를 돌려가면서 출력하는 문제 '2':"abc", '3':"def"가 있고 "23"이면 "ad", "ae", "af"...으로 모두 출력하는 문제 끝 조건에서 결과를 append해주면 된다. 맨처음 dfs의 조건을 어떻게 줘야하나 고민했다. 재귀를 돌리는데, 처음은 뺄수 없어서 0을 줬다. def letterCombinations(self, digits: str) -> List[str]: if not digits: return [] dic = {'2':['a','b','c'], '3':['d','e','f'], '4':['g','h','i'], '5':['j','k','l'], '6':['m','n','o'],'7':['p','q','r', 's'],'8':['..
-
200. Number of IslandsProgramming/leetcode 2021. 2. 24. 15:09
DFS(재귀)를 이용한 문제 풀이 좌표를 찾아가다가 1을 만나면 연결된 1을 0으로 만들고 상,하,좌,우에 1이 없을때까지 반복 내부함수로 구현했지만, dfs를 함수로 빼도되지만, self와 grid를 넘기기 싫어서 이렇게 구현함 def numIslands(self, grid: List[List[str]]) -> int: def dfs(x:int, y:int)->int: if x = len(grid) or y = len(grid[0]) or grid[x][y] != '1': return 0 grid[x][y] = 0 dfs(x+1, y) dfs(x-1, y) dfs(x, y+1) dfs(x, y-1) return 1 count = 0 for i in range(len(..
-
DFS, BFSProgramming/leetcode 2021. 2. 23. 22:44
그래프 순회 이론 정리 DFS - 깊이 우선 탐색, Stack과 재귀 호출로 구현되며 Back-Tracking과 같이 사용하면 뛰어난 효과 BFS - 너비 우선 탐색, 주로 Queue로 구현하며 최단 경로 문제에서 많이 사용됨(다익스트라 알고리즘) 코딩테스트에서 대부분의 그래프 탐색은 DFS로 이루어짐 DFS - Stack과 재귀 호출로 구현 ex) graph = { 1:[2,3,4], 2:[5], 3:[5], 4:[], 5:[6,7], 6:[], 7:3} 재귀 호출로 구현 graph = { 1:[2,3,4], 2:[5], 3:[5], 4:[], 5:[6,7], 6:[], 7:[3]} def recursive_dfs(v, discovered=[]): discovered.append(v) for w in ..