일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- Protocol
- 30. Substring with Concatenation of All Words
- DWG
- t1
- 시바견
- 파이썬
- 밴픽
- 109. Convert Sorted List to Binary Search Tree
- shiba
- 715. Range Module
- 43. Multiply Strings
- 프로그래머스
- Python
- data science
- kaggle
- Substring with Concatenation of All Words
- Python Implementation
- 운영체제
- Regular Expression
- 315. Count of Smaller Numbers After Self
- Decorator
- Generator
- iterator
- LeetCode
- 컴퓨터의 구조
- concurrency
- Class
- attribute
- Python Code
- Convert Sorted List to Binary Search Tree
- Today
- Total
목록Computer Science/Algorithms & Data Structures (26)
Scribbling
위상 정렬: 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록' 순서대로 나열하는 알고리즘 def topology_sort(): result = [] q = deque() """ 진입 차수가 0인 node를 queue에 삽입 """ for i in range(1, v+1): if indegree_list[i] == 0: q.append(i) while q: now = q.popleft() result.append(now) """ queue에서 꺼낸 node와 연결된 모든 node 간의 간선을 제거 후 진입 차수가 0인 node를 queue에 삽입 """ for nxt in graph[now]: indegree_list[nxt] -= 1 if indegree_list[nxt] == 0: q.append..
1. 신장 트리: 모든 node를 포함하면서 cycle이 존재하지 않는 그래프를 의미한다. 2. 최소 신장 트리: 신장 트리 중에서 최소 비용으로 만들 수 있는 트리 3. Kruskal Algorithm: 최소 신장 트리를 찾는 알고리즘 - O(vlogv) - Greedy하게 최소 비용 edge부터 차례로 연결한다. - 연결하고자 하는 node가 서로소였다면, union을 진행 - 연결하고자 하는 node가 cycle을만든다면, pass def find_parent(parent, x): if parent[x] == x: return x parent[x] = find_parent(parent, parent[x]) return parent[x] def union(parent, a, b): a = find_p..
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..
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)
최단 거리 알고리즘을 정리해보자. 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, (..