일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- concurrency
- 43. Multiply Strings
- kaggle
- 315. Count of Smaller Numbers After Self
- Python
- Generator
- 밴픽
- Decorator
- 운영체제
- 시바견
- Convert Sorted List to Binary Search Tree
- 715. Range Module
- 프로그래머스
- Class
- iterator
- Protocol
- DWG
- 파이썬
- shiba
- data science
- attribute
- 109. Convert Sorted List to Binary Search Tree
- t1
- Regular Expression
- Python Code
- 컴퓨터의 구조
- LeetCode
- 30. Substring with Concatenation of All Words
- Substring with Concatenation of All Words
- Python Implementation
- Today
- Total
목록전체 글 (382)
Scribbling
1. 무향 그래프 내 Cycle 판별 - 서로소 집합 알고리즘을 사용한다. - 모든 edge에 대해 두 node의 부모가 같다면, cycle이 존재. 두 node의 부모가 다르다면, union 진행. v, e = map(int, input().split()) edges = [] for _ in range(e): edges.append(list(map(int, input().split()))) parent = [0] * (v+1) for i in range(v+1): parent[i] = i def find_parent(parent, a): if parent[a] == a: return a else: parent[a] = find_parent(parent, parent[a]) return parent[a]..
v, e = map(int, input().split()) edges = [] for _ in range(e): edges.append(list(map(int, input().split()))) parent = [0] * (v+1) for i in range(v+1): parent[i] = i def find_parent(parent, a): if parent[a] == a: return a else: parent[a] = find_parent(parent, parent[a]) return parent[a] def union(parent, a, b): a = find_parent(parent, a) b = find_parent(parent, b) if a < b: parent[b] = a else: pa..
src로부터 특정 dst까지의 최단 거리를 묻는 문제로, 다익스트라 알고리즘을 먼저 떠올릴 수 있다. 기본적인 형태의 다익스트라 알고리즘은, priority queue에 "최단 거리가 갱신되는 경우"를 추가한다. 하지만 이 문제는 "이동 횟수 제한"이 있으므로, 이를 수정해야한다. 즉, priority queue에 "최단 거리가 갱신되는 경우"를 추가하는 것이 아니라, "추가적으로 이동 가능한 경우"를 모두 추가할 필요가 있다. 이를 코드로 구현하면 아래와 같다. import heapq class Solution: def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int: INF = int..
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: char_set = set() l = 0 max_len = 0 for r in range(len(s)): if s[r] in char_set: while s[r] in char_set: char_set.remove(s[l]) l += 1 char_set.add(s[r]) max_len = max(max_len, r - l + 1) return max_len
Set 자료형: 중복을 제거해준다. mySet = set([1, 2, 3]) 1) 데이터 추가 mySet.add(3) mySet.update([4, 5, 6]) 2) 데이터 삭제 mySet.remove(3): set에 3이 없으면 error mySet.discard(3): set에 3이 없어도 no error 3) Set에 데이터 추가/삭제는 O(1)
class Solution: def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int: INF = int(1e9) distance = [[INF] * (n) for _ in range(n)] for i in range(n): distance[i][i] = 0 for edge in edges: u = edge[0] v = edge[1] w = edge[2] distance[u][v] = w distance[v][u] = w for k in range(n): for a in range(n): for b in range(n): distance[a][b] = min(distance[a][b], distance[a][k..
최단 거리 알고리즘을 정리해보자. 1. 다익스트라 알고리즘 - 하나의 node로부터 다른 모든 node까지의 최단거리를 계산 가능 - 음의 간선이 없는 경우에만 유효 - O(VlogV) import heapq def dijkstra(start): pq = [] heapq.heappush(pq, (0, start)) distance[start] = 0 while pq: dist_u, u = heapq.heappop(pq) # node u가 이미 처리된 경우 if distance[u] dist_uv + dist_u: distance[v] = dist_uv + dist_u heapq.heappush(pq, (..
다익스트라 알고리즘을 활용하여 푼다. import heapq class Solution: def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int: INF = int(1e9) graph = [[] for _ in range(n+1)] distance = [INF] * (n+1) for time in times: u = time[0] v = time[1] w = time[2] graph[u].append((w, v)) self.dijkstra(graph, distance, k) max_dist = 0 for i in range(1, n+1): max_dist = max(max_dist, distance[i]) if max_dist ..
1. 노가다성 답안 class Solution: def addTwoNumbers(self, l1, l2, up=0): if l1 != None and l2 != None: val1 = l1.val val2 = l2.val val = (val1 + val2 + up) % 10 up = (val1 + val2 + up) // 10 ret_node = ListNode(val=val) ret_node.next = self.addTwoNumbers(l1.next, l2.next, up=up) elif l1 == None and l2 != None: val2 = l2.val val = (val2 + up) % 10 up = (val2 + up) // 10 ret_node = ListNode(val=val) ret_..
XO (1) XO란? XO란 quartz crystal oscillator를 일컫는다. 이는 압력을 가하면 전기가 발생되고 반대로 전기를 가하면 진동을 하는 ‘압전효과’를 이용한다. 즉, 적절한 제어 회로를 통해 크리스탈을 초당 32768회 진동하게 만들 수 있다. 이러한 진동을 감지하여 디지털 회로의 clock 및 RF 회로 내 PLL의 reference clock으로 사용할 수 있다. 이처럼 clock generation에 crystal을 사용하는 이유는 crystal의 정확성에 있다. 특히 PLL같이 매우 정확한 frequency가 요구되는 회로에는 비교적 low frequency에서 정확한 주파수를 생성할 수 있는 기제가 필요하다. 때문에 crystal 기반의 XO는 이에 가장 적합한 것이다. 그..