zerohertzLib.algorithm ¶

def bellman_ford(graph: list[list[tuple[int, int]]], start: int) -> list[int] | None:
    """Graph에서 시작 node로부터 모든 다른 node까지의 최단 경로 거리 계산

    Note:
        Time Complexity: $O(VE)$

        - $V$: Node의 수
        - $E$: 간선의 수

    Args:
        graph: Index (간선의 시작 node)에 따른 간선의 도착 node와 가중치 정보
        start: 최단 경로 거리가 계신될 시작 node

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

    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
    """
    n = len(graph)
    distance = [sys.maxsize for _ in range(n)]
    distance[start] = 0
    for cnt in range(n):
        for node in range(n):
            for node_, dist_ in graph[node]:
                if (
                    distance[node] != sys.maxsize
                    and distance[node_] > distance[node] + dist_
                ):
                    distance[node_] = distance[node] + dist_
                    if cnt == n - 1:
                        return None
    return distance

def bfs(maps: list[list[int]], start: int) -> list[int]:
    """BFS를 수행하기 위한 function

    Args:
        maps: 입력 graph
        start: Graph의 시작 지점

    Returns:
        방문 순서

    Examples:
        >>> zz.algorithm.bfs([[], [2, 3, 4], [1, 4], [1, 4], [1, 2, 3]], 1)
        [1, 2, 3, 4]
    """
    visit = [False for _ in range(len(maps))]
    results = []
    queue = deque()
    queue.append(start)
    visit[start] = True
    while queue:
        tmp = queue.popleft()
        results.append(tmp)
        for i in maps[tmp]:
            if not visit[i]:
                visit[i] = True
                queue.append(i)
    return results

def bisect_left(sorted_list: list[int | float], value: int | float) -> int:
    """Binary Search (left)

    Args:
        sorted_list: 정렬된 list
        value: 찾고자하는 값

    Returns:
        `value` 값이 `sorted_list` 에 삽입될 때 index

    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
    """
    low, high = 0, len(sorted_list)
    while low < high:
        mid = (low + high) // 2
        if sorted_list[mid] < value:
            low = mid + 1
        else:
            high = mid
    return low

def bisect_right(sorted_list: list[int | float], value: int | float) -> int:
    """Binary Search (right)

    Args:
        sorted_list: 정렬된 list
        value: 찾고자하는 값

    Returns:
        `value` 값이 `sorted_list` 에 삽입될 때 index

    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
    """
    low, high = 0, len(sorted_list)
    while low < high:
        mid = (low + high) // 2
        if value < sorted_list[mid]:
            high = mid
        else:
            low = mid + 1
    return low

def bubble_sort(arr: list[int]) -> list[int]:
    """Bubble Sort Algorithm: 연속된 값들을 비교하여 가장 큰 값을 배열의 끝으로 이동시키는 방식으로 정렬

    Args:
        arr: 정렬할 정수 list

    Returns:
        오름차순으로 정렬된 list

    Examples:
        >>> zz.algorithm.bubble_sort([64, 34, 25, 12, 22, 11, 90])
        [11, 12, 22, 25, 34, 64, 90]
    """
    arr_len = len(arr)
    for i in range(arr_len):
        for j in range(0, arr_len - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

def counting_sort(arr: list[int]) -> list[int]:
    """Counting Sort Algorithm: 각 숫자의 개수를 세어 정렬

    Args:
        arr: 정렬할 정수 list

    Returns:
        오름차순으로 정렬된 list

    Examples:
        >>> zz.algorithm.counting_sort([64, 34, 25, 12, 22, 11, 90])
        [11, 12, 22, 25, 34, 64, 90]
    """
    max_val = max(arr) + 1
    count = [0] * max_val
    for arr_ in arr:
        count[arr_] += 1
    idx = 0
    for value in range(max_val):
        for _ in range(count[value]):
            arr[idx] = value
            idx += 1
    return arr

def dfs(maps: list[list[int]], start: int) -> list[int]:
    """DFS를 수행하기 위한 function

    Args:
        maps: 입력 graph
        start: Graph의 시작 지점

    Returns:
        방문 순서

    Examples:
        >>> zz.algorithm.dfs([[], [2, 3, 4], [1, 4], [1, 4], [1, 2, 3]], 1)
        [1, 2, 4, 3]
    """
    visit = [False for _ in range(len(maps))]
    results = []

    def _dfs(start):
        visit[start] = True
        results.append(start)
        for i in maps[start]:
            if not visit[i]:
                _dfs(i)

    _dfs(start)
    return results

def dijkstra(graph: list[list[tuple[int, int]]], start: int) -> list[int]:
    r"""Graph에서 시작 node로부터 모든 다른 node까지의 최단 경로 거리 계산

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

        - $V$: Node의 수
        - $E$: 간선의 수

    Args:
        graph: Index (간선의 시작 node)에 따른 간선의 도착 node와 가중치 정보
        start: 최단 경로 거리가 계신될 시작 node

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

    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]
    """
    distance = [sys.maxsize for _ in range(len(graph))]
    distance[start] = 0
    queue = [(0, start)]
    while queue:
        dist, node = heapq.heappop(queue)
        if distance[node] < dist:
            continue
        for node_, dist_ in graph[node]:
            if distance[node_] > dist + dist_:
                distance[node_] = dist + dist_
                heapq.heappush(queue, (dist + dist_, node_))
    return distance

def floyd_warshall(graph: list[list[tuple[int, int]]]) -> list[list[int]] | None:
    """Graph에서 모든 node 쌍 간의 최단 경로 거리 계산

    Note:
        Time Complexity: $O(V^3)$

        - $V$: Node의 수

    Args:
        graph: Index (간선의 시작 node)에 따른 간선의 도착 node와 가중치 정보

    Returns:
        모든 node 쌍에 대한 최단 경로 거리 (음의 cycle을 가질 시 None return)

    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]]
    """
    n = len(graph)
    distance = [[sys.maxsize for _ in range(n)] for _ in range(n)]
    for i in range(n):
        distance[i][i] = 0
        for j, dist in graph[i]:
            distance[i][j] = dist
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if (
                    distance[i][j] > distance[i][k] + distance[k][j]
                    and distance[i][k] != sys.maxsize
                    and distance[k][j] != sys.maxsize
                ):
                    distance[i][j] = distance[i][k] + distance[k][j]
    for i in range(n):
        if distance[i][i] < 0:
            return None
    return distance

def heap_sort(arr: list[int]) -> list[int]:
    """Heap Sort Algorithm: 배열 요소들을 heap으로 구성한 다음, 최대 heap 속성을 이용하여 정렬

    Args:
        arr: 정렬할 정수 list

    Returns:
        오름차순으로 정렬된 list

    Examples:
        >>> zz.algorithm.heap_sort([64, 34, 25, 12, 22, 11, 90])
        [11, 12, 22, 25, 34, 64, 90]
    """
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        _heapify(arr, n, i)
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        _heapify(arr, i, 0)
    return arr

def insertion_sort(arr: list[int]) -> list[int]:
    """Insertion Sort Algorithm: 각 값들을 이미 정렬된 부분의 올바른 위치에 삽입하는 방식으로 정렬

    Args:
        arr: 정렬할 정수 list

    Returns:
        오름차순으로 정렬된 list

    Examples:
        >>> zz.algorithm.insertion_sort([64, 34, 25, 12, 22, 11, 90])
        [11, 12, 22, 25, 34, 64, 90]
    """
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

def merge_sort(arr: list[int]) -> list[int]:
    """Merge Sort Algorithm: 분할 정복 방법을 사용하여 배열을 절반으로 나누고, 각 부분을 정렬한 다음 합치는 방식으로 정렬

    Args:
        arr: 정렬할 정수 list

    Returns:
        오름차순으로 정렬된 list

    Examples:
        >>> zz.algorithm.merge_sort([64, 34, 25, 12, 22, 11, 90])
        [11, 12, 22, 25, 34, 64, 90]
    """
    if len(arr) > 1:
        mid = len(arr) // 2
        left = arr[:mid]
        right = arr[mid:]
        merge_sort(left)
        merge_sort(right)
        i = j = k = 0
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                arr[k] = left[i]
                i += 1
            else:
                arr[k] = right[j]
                j += 1
            k += 1
        while i < len(left):
            arr[k] = left[i]
            i += 1
            k += 1
        while j < len(right):
            arr[k] = right[j]
            j += 1
            k += 1
    return arr

def quick_sort(arr: list[int]) -> list[int]:
    """Quick Sort Algorithm: Pivot을 선택하여 이보다 작은 요소는 왼쪽, 큰 요소는 오른쪽에 위치시키는 방식으로 분할 정복을 사용하여 정렬

    Args:
        arr: 정렬할 정수 list

    Returns:
        오름차순으로 정렬된 list

    Examples:
        >>> zz.algorithm.quick_sort([64, 34, 25, 12, 22, 11, 90])
        [11, 12, 22, 25, 34, 64, 90]
    """
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

def radix_sort(arr: list[int]) -> list[int]:
    """Radix Sort Algorithm: 각 자릿수에 대해 개별적으로 정렬

    Args:
        arr: 정렬할 정수 list

    Returns:
        오름차순으로 정렬된 list

    Examples:
        >>> zz.algorithm.radix_sort([64, 34, 25, 12, 22, 11, 90])
        [11, 12, 22, 25, 34, 64, 90]
    """
    max_val = max(arr)
    exp = 1
    while max_val / exp > 0:
        _counting_sort_for_radix(arr, exp)
        exp *= 10
    return arr

def selection_sort(arr: list[int]) -> list[int]:
    """Selection Sort Algorithm: 배열에서 가장 작은 값을 찾아 해당 값을 배열의 앞부분으로 이동시키는 방식으로 정렬

    Args:
        arr: 정렬할 정수 list

    Returns:
        오름차순으로 정렬된 list

    Examples:
        >>> zz.algorithm.selection_sort([64, 34, 25, 12, 22, 11, 90])
        [11, 12, 22, 25, 34, 64, 90]
    """
    for i, _ in enumerate(arr):
        min_idx = i
        for j in range(i + 1, len(arr)):
            if arr[min_idx] > arr[j]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

def soe(n_max: int) -> list[int]:
    """Sieve of Eratosthenes

    Args:
        n_max: 구하고자 하는 소수 범위의 최댓값

    Returns:
        N까지 존재하는 소수 list

    Examples:
        >>> zz.algorithm.soe(10)
        [2, 3, 5, 7]
    """
    visited = [False, False] + [True] * (n_max - 1)
    prime_numbers = []
    for i in range(2, n_max + 1):
        if visited[i]:
            prime_numbers.append(i)
            for idx in range(2 * i, n_max + 1, i):
                visited[idx] = False
    return prime_numbers