딥러닝 공부방

이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다. 출처 : 파이썬 알고리즘 인터뷰 코드 출처 : 파이썬 알고리즘 인터뷰 깃허브 39. 코스 스케줄 leetcode 207. Course Schdule 문제입니다. leetcode.com/problems/course-schedule/ 풀이 코스를 그래프로 만들고, 그래프가 순환 그래프인지 판단하는 풀이입니다. def canFinish(self, numCourses,prerequisites): graph = collections.defaultdict(list) # 그래프 구성 for x, y in prerequisites: graph[x].append(y) traced = set() visited = set() def dfs(i): # 순환 ..

이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다. 출처 : 파이썬 알고리즘 인터뷰 코드 출처 : 파이썬 알고리즘 인터뷰 깃허브 35. 조합 leetcode 77. Combiantion 문제입니다. leetcode.com/problems/combinations/ 풀이 1. 제가 푼 풀이 def combine(self, n, k): result = [] def dfs(index, path): if len(path) == k: result.append(path) return for i in range(index, n+1): dfs(i+1, path + [i]) dfs(1, []) return result 2. 책에 나와있는 풀이 def combine(n,k): results = [] def ..

이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다. 출처 : 파이썬 알고리즘 인터뷰 코드 출처 : 파이썬 알고리즘 인터뷰 깃허브 38. 일정 재구성 leetcode 332. Reconstruct Itinerary 문제입니다. leetcode.com/problems/reconstruct-itinerary/ 풀이 여행 일정을 그래프로 구성해서 dfs로 푸는 풀이입니다. # 반복 dfs 풀이 def itinerary(self, ticket): graph = collections.defaultdict(list) for a, b in sorted(ticket): graph[a].append(b) route, stack = [], ['JFK'] while stack: while graph[stack..

이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다. 출처 : 파이썬 알고리즘 인터뷰 코드 출처 : 파이썬 알고리즘 인터뷰 깃허브 37. 부분 집합 leetcode 78. Subsets 문제입니다. leetcode.com/problems/subsets/ 풀이 def subsets(self, nums): result = [] def dfs(index, path): result.append(path) for i in range(index, len(nums)): dfs(i+1,path+[nums[i]]) dfs(0, []) return result

이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다. 출처 : 파이썬 알고리즘 인터뷰 코드 출처 : 파이썬 알고리즘 인터뷰 깃허브 36. 조합의 합 leetcode 39. Combination Sum 문제입니다. leetcode.com/problems/combination-sum/ 풀이 dfs와 백트래킹을 활용한 풀이법입니다. def combinationSum(self, candidates,target): result=[] def dfs(csum, index, path): # 종료 조건 if csum < 0: return if csum == 0: result.append(path) return # 자신 부터 하위 원소 까지의 나열 재귀 호출 for i in range(index, len(c..

이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다. 출처 : 파이썬 알고리즘 인터뷰 코드 출처 : 파이썬 알고리즘 인터뷰 깃허브 34. 순열 leetcode 46. Permutations 문제입니다. leetcode.com/problems/permutations/ 풀이 dfs를 활용해서 순열을 생성하는 풀이입니다. def permute(self, nums): results = [] prev_elements = [] def dfs(elements): # 리프 노드일 때 결과 추가 if len(elements) == 0: results.append(prev_elements[:]) # 순열 생성 재귀 호출 for e in elements: next_elements = elements[:] ne..

이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다. 출처 : 파이썬 알고리즘 인터뷰 코드 출처 : 파이썬 알고리즘 인터뷰 깃허브 33. 전화 번호 문자 조합 leetcode 17. Letter Combinations of a Phone Number 문제입니다. leetcode.com/problems/letter-combinations-of-a-phone-number/ 풀이 def letterCombinations(self, digits): def dfs(index, path): # 끝까지 탐색하면 백트래킹 if len(path) == len(digits): result.append(path) return # 입력값 자릿수 단위 반복 for i in range(index, len(digit..

이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다. 출처 : 파이썬 알고리즘 인터뷰 코드 출처 : 파이썬 알고리즘 인터뷰 깃허브 32. 섬의 개수 leetcode 200. Number of Islands 문제입니다. leetcode.com/problems/number-of-islands/ 풀이 1은 섬을 의미합니다. grid에서 섬인 인덱스를 찾으면, dfs로 확장해 나갑니다. def numIslands(self, grid): if not grid: return 0 def dfs(i, j): # 더 이상 땅이 아닌 경우 종료 if i = len(grid) or \ j = len(grid[0]) or \ grid[i][j] != '1': return gr..

그래프 순회(Graph Traversals) 그래프 순회란 그래프 탐색이라고도 불리우며 그래프의 각 정점을 방문하는 과정을 말합니다. 그래프의 각 정점을 방문하는 그래프 순회(Graph Traversals)는 크게 깊이 우선 탐색(DFS, Depth-First Search)와 너비 우선 탐색(BFS, Breadth-First Search)의 2가지 알고리즘이 있습니다. DFS가 일반적으로 BFS에 비해 더 널리 쓰입니다. DFS는 주로 스택으로 구현하거나 재귀로 구현하며 백트래킹을 통해 뛰어난 효용을 보입니다. 반면 BFS는 주로 큐로 구현하며, 그래프의 최단 경로를 구하는 문제 등에 사용됩니다. 그래프 순회 알고리즘인 DFS와 BFS를 파이썬으로 구현해보도록 하겠습니다. 그래프를 우선 정의합니다. 그래..

이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다. 출처 : 파이썬 알고리즘 인터뷰 코드 출처 : 파이썬 알고리즘 인터뷰 깃허브 31. 상위 K 빈도 요소 leetcode 346. Top K Frequent Elements 문제입니다. leetcode.com/problems/top-k-frequent-elements/ 풀이 1. 우선순위 큐 이용 파이썬에서 우선순위 큐는 heapq 모듈을 사용합니다. nums의 빈도수를 Counter 모듈로 저장한뒤에, heapq에 빈도수를 음수로 저장합니다. heapq는 최소합을 제공하므로 음수로 저장해야 합니다. k번 반복하여 heapq를 pop하면 빈도수가 많은 요소순대로 추출이 됩니다. def topKFrequent(self, nums, k): f..