zerohertzLib.algorithm¶

Algorithm

Algorithm과 관련된 다양한 함수들

class zerohertzLib.algorithm.DisjointSet(size, compression=False)[source]¶

Bases: object

Vanilla disjoint set

Note

Time Complexity:

Without path compression:
- Worst: \(O(V)\)
- Average: \(O(V)\)
With path compression:
- Worst: \(O(\log{V})\)
- Average: \(O(\alpha(V))\)

\(V\): Node의 수
\(\alpha(V)\): Ackermann function 의 역함수 (\(O(\alpha(V))\simeq O(1)\))

Parameters:

size¶ (int) – Node의 수
compression¶ (Optional[bool]) – Path compression 여부

parent¶

Node에 따른 부모 node의 index

Type:: List[int]

Examples

>>> disjointset = zz.algorithm.DisjointSet(5)
>>> disjointset.union(0, 1)
>>> disjointset.union(2, 3)
>>> disjointset.union(1, 2)
>>> disjointset.parent
[0, 0, 0, 2, 4]
>>> disjointset = zz.algorithm.DisjointSet(5, True)
>>> disjointset.union(0, 1)
>>> disjointset.union(2, 3)
>>> disjointset.union(1, 2)
>>> disjointset.parent
[0, 0, 0, 2, 4]

find(node)[source]¶

Parameters:: node¶ (int) – 목표 node의 index
Returns:: 목표 node에 대한 root node의 index
Return type:: int

union(node1, node2)[source]¶

Parameters:

node1¶ (int) – 목표 node의 index
node2¶ (int) – 목표 node의 index

Returns:

self.parent 에 root node의 index를 update

Return type:

None

class zerohertzLib.algorithm.DisjointSetRank(size)[source]¶

Bases: DisjointSet

Disjoint set (union by rank)

Note

Time Complexity:

Worst: \(O(\log{V})\)
Average: \(O(\alpha(V))\)

\(V\): Node의 수
\(\alpha(V)\): Ackermann function 의 역함수 (\(O(\alpha(V))\simeq O(1)\))

Parameters:: size¶ (int) – Node의 수

parent¶

Node에 따른 부모 node의 index

Type:: List[int]

rank¶

Node에 따른 rank

Type:: List[int]

Examples

>>> disjointset = zz.algorithm.DisjointSetRank(5)
>>> disjointset.union(0, 1)
>>> disjointset.union(2, 3)
>>> disjointset.union(1, 2)
>>> disjointset.parent
[0, 0, 0, 2, 4]
>>> disjointset.rank
[2, 0, 1, 0, 0]

union(node1, node2)[source]¶

Parameters:

node1¶ (int) – 목표 node의 index
node2¶ (int) – 목표 node의 index

Returns:

self.parent 에 root node의 index를 update

Return type:

None

class zerohertzLib.algorithm.DisjointSetSize(size)[source]¶

Bases: DisjointSet

Disjoint set (union by size)

Note

Time Complexity:

Worst: \(O(\log{V})\)
Average: \(O(\alpha(V))\)

\(V\): Node의 수
\(\alpha(V)\): Ackermann function 의 역함수 (\(O(\alpha(V))\simeq O(1)\))

Parameters:: size¶ (int) – Node의 수

parent¶

Node에 따른 부모 node의 index

Type:: List[int]

size¶

Node에 따른 size

Type:: List[int]

Examples

>>> disjointset = zz.algorithm.DisjointSetSize(5)
>>> disjointset.union(0, 1)
>>> disjointset.union(2, 3)
>>> disjointset.union(1, 2)
>>> disjointset.parent
[0, 0, 0, 2, 4]
>>> disjointset.size
[4, 1, 2, 1, 1]
>>> [disjointset.size[disjointset.find(i)] for i in range(5)]
[4, 4, 4, 4, 1]

union(node1, node2)[source]¶

Parameters:

node1¶ (int) – 목표 node의 index
node2¶ (int) – 목표 node의 index

Returns:

self.parent 에 root node의 index를 update

Return type:

None

zerohertzLib.algorithm.bellman_ford(graph, start)[source]¶

Graph에서 시작 node로부터 모든 다른 node까지의 최단 경로 거리 계산

Note

Time Complexity: \(O(VE)\)

\(V\): Node의 수
\(E\): 간선의 수

Parameters:

graph¶ (List[List[Tuple[int, int]]]) – Index (간선의 시작 node)에 따른 간선의 도착 node와 가중치 정보
start¶ (int) – 최단 경로 거리가 계신될 시작 node

Returns:

start 에서 graph 내 모든 다른 node 까지의 최단 경로 거리 (음의 cycle을 가질 시 None return)

Return type:

List[int]

Examples

>>> graph = [[(1, 4), (2, 2), (3, 7)], [(0, 1), (2, 5)], [(0, 2), (3, 4)], [(1, 3)]]
>>> zz.algorithm.bellman_ford(graph, 0)
[0, 4, 2, 6]
>>> zz.algorithm.bellman_ford(graph, 1)
[1, 0, 3, 7]
>>> zz.algorithm.bellman_ford(graph, 2)
[2, 6, 0, 4]
>>> zz.algorithm.bellman_ford(graph, 3)
[4, 3, 6, 0]
>>> zz.algorithm.bellman_ford([[(1, -1)], [(0, -1)]], 0) is None
True

zerohertzLib.algorithm.bfs(maps, start)[source]¶

BFS를 수행하기 위한 함수

Parameters:

maps¶ (List[List[int]]) – 입력 graph
start¶ (int) – Graph의 시작 지점

Returns:

방문 순서

Return type:

List[int]

Examples

>>> zz.algorithm.bfs([[], [2, 3, 4], [1, 4], [1, 4], [1, 2, 3]], 1)
[1, 2, 3, 4]

zerohertzLib.algorithm.bisect_left(sorted_list, value)[source]¶

Binary Search (left)

Parameters:

sorted_list¶ (List[Union[int, float]]) – 정렬된 list
value¶ (Union[int, float]) – 찾고자하는 값

Returns:

value 값이 sorted_list 에 삽입될 때 index

Return type:

int

Examples

>>> zz.algorithm.bisect_left([1, 3, 5], 2.7)
1
>>> zz.algorithm.bisect_left([1, 3, 5], 3)
1
>>> zz.algorithm.bisect_left([1, 3, 5], 3.3)
2

zerohertzLib.algorithm.bisect_right(sorted_list, value)[source]¶

Binary Search (right)

Parameters:

sorted_list¶ (List[Union[int, float]]) – 정렬된 list
value¶ (Union[int, float]) – 찾고자하는 값

Returns:

value 값이 sorted_list 에 삽입될 때 index

Return type:

int

Examples

>>> zz.algorithm.bisect_right([1, 3, 5], 2.7)
1
>>> zz.algorithm.bisect_right([1, 3, 5], 3)
2
>>> zz.algorithm.bisect_right([1, 3, 5], 3.3)
2

zerohertzLib.algorithm.bubble_sort(arr)[source]¶

Bubble Sort Algorithm: 연속된 값들을 비교하여 가장 큰 값을 배열의 끝으로 이동시키는 방식으로 정렬

Parameters:: arr¶ (List[int]) – 정렬할 정수 list
Returns:: 오름차순으로 정렬된 list
Return type:: List[int]

Examples

>>> zz.algorithm.bubble_sort([64, 34, 25, 12, 22, 11, 90])
[11, 12, 22, 25, 34, 64, 90]

zerohertzLib.algorithm.counting_sort(arr)[source]¶

Counting Sort Algorithm: 각 숫자의 개수를 세어 정렬

Parameters:: arr¶ (List[int]) – 정렬할 정수 list
Returns:: 오름차순으로 정렬된 list
Return type:: List[int]

Examples

>>> zz.algorithm.counting_sort([64, 34, 25, 12, 22, 11, 90])
[11, 12, 22, 25, 34, 64, 90]

zerohertzLib.algorithm.dfs(maps, start)[source]¶

DFS를 수행하기 위한 함수

Parameters:

maps¶ (List[List[int]]) – 입력 graph
start¶ (int) – Graph의 시작 지점

Returns:

방문 순서

Return type:

List[int]

Examples

>>> zz.algorithm.dfs([[], [2, 3, 4], [1, 4], [1, 4], [1, 2, 3]], 1)
[1, 2, 4, 3]

zerohertzLib.algorithm.dijkstra(graph, start)[source]¶

Graph에서 시작 node로부터 모든 다른 node까지의 최단 경로 거리 계산

Note

Time Complexity: \(O((V+E)\log{V})\)

\(V\): Node의 수
\(E\): 간선의 수

Parameters:

graph¶ (List[List[Tuple[int, int]]]) – Index (간선의 시작 node)에 따른 간선의 도착 node와 가중치 정보
start¶ (int) – 최단 경로 거리가 계신될 시작 node

Returns:

start 에서 graph 내 모든 다른 node 까지의 최단 경로 거리 (음의 가중치에서는 정확하지 않음)

Return type:

List[int]

Examples

>>> graph = [[(1, 4), (2, 2), (3, 7)], [(0, 1), (2, 5)], [(0, 2), (3, 4)], [(1, 3)]]
>>> zz.algorithm.dijkstra(graph, 0)
[0, 4, 2, 6]
>>> zz.algorithm.dijkstra(graph, 1)
[1, 0, 3, 7]
>>> zz.algorithm.dijkstra(graph, 2)
[2, 6, 0, 4]
>>> zz.algorithm.dijkstra(graph, 3)
[4, 3, 6, 0]

zerohertzLib.algorithm.fft(sig, inv=False)[source]¶

FFT (Fast Fourier Transform)를 수행하기 위한 함수

Parameters:

sig¶ (List[complex]) – 입력 신호 (복소수 list)
inv¶ (Optional[bool]) – 변환 방향을 지정 (False: 정방향, True: 역방향)

Returns:

변환된 결과 (복소수 list)

Return type:

List[complex]

Examples

>>> zz.algorithm.fft([1, 0, 0, 0])
[(1+0j), (1+0j), (1+0j), (1+0j)]
>>> zz.algorithm.fft([1+0j, 1+0j, 1+0j, 1+0j], True)
[(4+0j), 0j, 0j, 0j]

zerohertzLib.algorithm.floyd_warshall(graph)[source]¶

Graph에서 모든 node 쌍 간의 최단 경로 거리 계산

Note

Time Complexity: \(O(V^3)\)

\(V\): Node의 수

Parameters:: graph¶ (List[List[Tuple[int, int]]]) – Index (간선의 시작 node)에 따른 간선의 도착 node와 가중치 정보
Returns:: 모든 node 쌍에 대한 최단 경로 거리 (음의 cycle을 가질 시 None return)
Return type:: List[List[int]]

Examples

>>> graph = [[(1, 4), (2, 2), (3, 7)], [(0, 1), (2, 5)], [(0, 2), (3, 4)], [(1, 3)]]
>>> zz.algorithm.floyd_warshall(graph)
[[0, 4, 2, 6], [1, 0, 3, 7], [2, 6, 0, 4], [4, 3, 6, 0]]

zerohertzLib.algorithm.heap_sort(arr)[source]¶

Heap Sort Algorithm: 배열 요소들을 heap으로 구성한 다음, 최대 heap 속성을 이용하여 정렬

Parameters:: arr¶ (List[int]) – 정렬할 정수 list
Returns:: 오름차순으로 정렬된 list
Return type:: List[int]

Examples

>>> zz.algorithm.heap_sort([64, 34, 25, 12, 22, 11, 90])
[11, 12, 22, 25, 34, 64, 90]

zerohertzLib.algorithm.insertion_sort(arr)[source]¶

Insertion Sort Algorithm: 각 값들을 이미 정렬된 부분의 올바른 위치에 삽입하는 방식으로 정렬

Parameters:: arr¶ (List[int]) – 정렬할 정수 list
Returns:: 오름차순으로 정렬된 list
Return type:: List[int]

Examples

>>> zz.algorithm.insertion_sort([64, 34, 25, 12, 22, 11, 90])
[11, 12, 22, 25, 34, 64, 90]

zerohertzLib.algorithm.merge_sort(arr)[source]¶

Merge Sort Algorithm: 분할 정복 방법을 사용하여 배열을 절반으로 나누고, 각 부분을 정렬한 다음 합치는 방식으로 정렬

Parameters:: arr¶ (List[int]) – 정렬할 정수 list
Returns:: 오름차순으로 정렬된 list
Return type:: List[int]

Examples

>>> zz.algorithm.merge_sort([64, 34, 25, 12, 22, 11, 90])
[11, 12, 22, 25, 34, 64, 90]

zerohertzLib.algorithm.quick_sort(arr)[source]¶

Quick Sort Algorithm: Pivot을 선택하여 이보다 작은 요소는 왼쪽, 큰 요소는 오른쪽에 위치시키는 방식으로 분할 정복을 사용하여 정렬

Parameters:: arr¶ (List[int]) – 정렬할 정수 list
Returns:: 오름차순으로 정렬된 list
Return type:: List[int]

Examples

>>> zz.algorithm.quick_sort([64, 34, 25, 12, 22, 11, 90])
[11, 12, 22, 25, 34, 64, 90]

zerohertzLib.algorithm.radix_sort(arr)[source]¶

Radix Sort Algorithm: 각 자릿수에 대해 개별적으로 정렬

Parameters:: arr¶ (List[int]) – 정렬할 정수 list
Returns:: 오름차순으로 정렬된 list
Return type:: List[int]

Examples

>>> zz.algorithm.radix_sort([64, 34, 25, 12, 22, 11, 90])
[11, 12, 22, 25, 34, 64, 90]

zerohertzLib.algorithm.selection_sort(arr)[source]¶

Selection Sort Algorithm: 배열에서 가장 작은 값을 찾아 해당 값을 배열의 앞부분으로 이동시키는 방식으로 정렬

Parameters:: arr¶ (List[int]) – 정렬할 정수 list
Returns:: 오름차순으로 정렬된 list
Return type:: List[int]

Examples

>>> zz.algorithm.selection_sort([64, 34, 25, 12, 22, 11, 90])
[11, 12, 22, 25, 34, 64, 90]

zerohertzLib.algorithm.soe(n_max)[source]¶

Sieve of Eratosthenes

Parameters:: n_max¶ (int) – 구하고자 하는 소수 범위의 최댓값
Returns:: N까지 존재하는 소수 list
Return type:: List[int]

Examples

>>> zz.algorithm.soe(10)
[2, 3, 5, 7]