2022-03-05 Log
Operator Overloading #
- 연산자 오버로딩은 인스턴스 객체끼리 서로 연산을 할 수 있게 기존 연산자의 기능을 중복으로 정의하는 것
- 연산자 오버로딩의 예시
| Method | Operator | Example |
|---|---|---|
| __add__(self, other) | + (Binomial) | A + B, A += B |
| __pos__(self) | + (Unary) | +A |
| _sub__(self, other) | - (Binomial) | A - B, A -= B |
| __neg__(self) | - (Unary) | -A |
| __mul__(self, other) | * | A * B, A *= B |
| __truediv__(self, other) | / | A / B, A /= B |
| __floordiv__(self, other) | // | A // B, A //= B |
| __mod__(self, other) | % | A % B, A %= B |
| __pow__(self, other) | pow(), ** | pow(A, B), A ** B |
| __eq__(self, other) | == | A == B |
| __lt__(self, other) | < | A < B |
| __gt__(self, other) | > | A > B |
| __lshift__(self, other) | « | A « B |
| __rshift__(self, other) | » | A » B |
| __and__(self, other) | & | A & B, A &= B |
| __xor__(self, other) | ^ | A ^ B, A ^= B |
| __or__(self, other) | | | A | B, A |= B |
| __invert__(self) | ~ | ~A |
| __abs__(self) | abs() | abs(A) |
Union-Find Algorithm #
- 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘
- 노드를 합치는 Union 연산과 루트 노드를 찾는 Find 연산으로 이루어짐
- 배열에 나열된 모든 노드들은 기본적으로 자기 자신의 값을 가짐
- 노드를 합칠 때 자식 노드의 배열 값에 부모 노드의 배열 값을 넣음
간단한 구현 코드
python
def find(graph: list, x: int) -> int:
if graph[x] == x:
return x
graph[x] = find(graph, graph[x])
def union(graph: list, x: int, y: int) -> None:
x = find(graph, x)
y = find(graph, y)
if x == y:
return
graph[y] = xKruskal’s Algorithm #
- 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘 (최소 비용 신장 트리)
- 모든 간선 정보를 오름차순으로 정렬한 뒤 비용이 적은 간선부터 그래프에 포함
- Reference: https://blog.naver.com/ndb796/221230994142
간단한 구현 코드
python
class Edge:
def __init__(self, a: int, b: int, cost: int):
self.parent = a
self.child = b
self.cost = cost
def get_parent(graph: list, x: int) -> int:
if graph[x] == x:
return x
graph[x] = get_parent(graph, graph[x])
def union_parent(graph: list, a: int, b: int) -> None:
a = get_parent(graph, a)
b = get_parent(graph, b)
if a < b:
graph[b] = a
else:
graph[a] = b
def find(graph: list, a: int, b: int) -> int:
a = get_parent(graph, a)
b = get_parent(graph, b)
if a == b:
return True
else:
return False
def sort_edge(edge_list: list) -> list:
return sorted(edge_list, key=lambda x: [x.cost, x.parent, x.child])
def union_edge(graph: list, edge_list: list) -> int:
cost = 0
for edge in edge_list:
if not find(graph, edge.parent, edge.child):
cost += edge.cost
union_parent(graph, edge.parent, edge.child)
return cost