딥러닝 공부방

이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다. 출처 : 파이썬 알고리즘 인터뷰 코드 출처 : 파이썬 알고리즘 인터뷰 깃허브 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..

이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다. 출처 : 파이썬 알고리즘 인터뷰 코드 출처 : 파이썬 알고리즘 인터뷰 깃허브 30. 중복 문자 없는 가장 긴 부분 문자열 leetcode 3. Longest Substring Without Repeating Characters 문제입니다. leetcode.com/problems/longest-substring-without-repeating-characters/ 풀이 s를 enumerate로 index와 char을 하나씩 꺼냅니다. char에 해당하는 index를 dictionary에 저장하고, char가 이미 dictionary에 저장되어 있으면 중복 문자입니다. 이 경우에 start를 변경해줍니다. def lengthOfLongest..

이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다. 출처 : 파이썬 알고리즘 인터뷰 코드 출처 : 파이썬 알고리즘 인터뷰 깃허브 29. 보석과 돌 leetcode 771. Jewels and Stones 문제입니다. leetcode.com/problems/jewels-and-stones/ 풀이 1. 한줄 풀이 def numJewelsInStones(self, J, S): return sum(s in J for s in S) S에 있는 char을 하나씩 꺼내면서 J에 있는 char이면 True를 반환합니다. sum 함수로 True의 개수를 다 더합니다. 2. Counter 이용 def numJewelsInStones(self, J, S): freqs = collections.Counter(..

이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다. 출처 : 파이썬 알고리즘 인터뷰 코드 출처 : 파이썬 알고리즘 인터뷰 깃허브 25. 원형 큐 디자인 leetcode 622. Design Circular Queue 문제입니다. leetcode.com/problems/design-circular-queue/ 풀이 class MyCirculurQueue: def __init__(self, k): self.q = [None] * k self.maxlen = k self.p1 = 0 self.p2 = 0 # enQueue(): rear 포인터 이동 def enQueue(self, value): if self.q[self.p2] is None: self.q[self.p2] = value self..

이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다. 출처 : 파이썬 알고리즘 인터뷰 코드 출처 : 파이썬 알고리즘 인터뷰 깃허브 24. 스택을 이용한 큐 구현 leetcode 232. Implement Queue using Stacks 문제입니다. leetcode.com/problems/implement-queue-using-stacks/ 풀이 class MyQueue: def __init__(self): self.input = [] self.output = [] def push(self, x): self.input.append(x) def pop(self): self.peek() return self.output.pop() def peek(self): # output이 없으면 모두 재입..

이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다. 출처 : 파이썬 알고리즘 인터뷰 코드 출처 : 파이썬 알고리즘 인터뷰 깃허브 23. 큐를 이용한 스택 구현 leetcode 225. Implement Stack using Queues 문제입니다. leetcode.com/problems/implement-stack-using-queues/ 풀이 class MyStack: def __init__(self): self.q = collections.deque() def push(self, x): self.q.append(x) # 요소 삽입 후 맨 앞에 두는 상태로 재정렬 for _ in range(len(self.q) - 1): self.q.append(self.q.popleft()) def ..

이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다. 출처 : 파이썬 알고리즘 인터뷰 코드 출처 : 파이썬 알고리즘 인터뷰 깃허브 22. 일일 온도 리트코드 739. Daily Temperatures 문제입니다. leetcode.com/problems/daily-temperatures/ 풀이 stack에 인덱스를 저장하고 현재 인덱스에 해당하는 온도가 stack[-1] 인덱스에 해당하는 온도보다 크면 stack에서 값을 꺼내서 인덱스 차이를 계산합니다. def dailyTemperatures(self, T): answer = [0] * len(T) stack = [] for i, t in T: while stack and T[stack[-1]] < t: last = stack.pop() a..

이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다. 출처 : 파이썬 알고리즘 인터뷰 코드 출처 : 파이썬 알고리즘 인터뷰 깃허브 21. 중복 문자 제거 리트코드 316. Remove Duplicate Letters 문제입니다. leetcode.com/problems/remove-duplicate-letters/ 풀이 def removeDuplicateLetters(self, s): stack,seen,counts = [], set(), collections.Counter(s) for char in s: counts[char] -= 1 while stack and char 0: seen.remove(stack.pop()) se..