WIL

최단경로 :

그래프로 표현, 각 지점은 노드, 도로는 간선

다익스트라

INF = int(1e9)


def dijkstra_naive(graph, start):
    def get_smallest_node():
        min_value = INF
        idx = 0
        for i in range(1, N):
            if dist[i] < min_value and not visited[i]:
                min_value = dist[i]
                idx = i
        return idx

    N = len(graph)
    visited = [False] * N
    dist = [INF] * N

    visited[start] = True
    dist[start] = 0

    for adj, d in graph[start]:
        dist[adj] = d

    # N개의 노드 중 첫 노드는 이미 방문했으므로,
    # N-1번 수행하면 된다.
    for _ in range(N - 1):
        # 가장 가깝고 방문 안한 녀석을 고르고,
        cur = get_smallest_node()
        visited[cur] = True
        # 최단거리를 비교, 수정한다.
        for adj, d in graph[cur]:
            cost = dist[cur] + d
            if cost < dist[adj]:
                dist[adj] = cost

    return dist

이중 for문으로 이루어져 있으므로 O(n^2)의 시간복잡도를 갖는다.
힙을 사용하면 O(nlogN) 까지 줄일 수 있다.

다익스트라(최소힙 사용)

import heapq


def dijkstra_pq(graph, start):
    N = len(graph)
    dist = [INF] * N

    q = []
    # 튜플일 경우 0번째 요소 기준으로 최소 힙 구조.
    # 첫 번째 방문 누적 비용은 0이다.
    heapq.heappush(q, (0, start))
    dist[start] = 0

    while q:
        # 누적 비용이 가장 작은 녀석을 꺼낸다.
        acc, cur = heapq.heappop(q)

        # 이미 답이 될 가망이 없다.
        if dist[cur] < acc:
            continue

        # 인접 노드를 차례대로 살펴보며 거리를 업데이트한다.
        for adj, d in graph[cur]:
            cost = acc + d
            if cost < dist[adj]:
                dist[adj] = cost
                heapq.heappush(q, (cost, adj))

    return dist

플로이드-워셜

다익스트라가 출발점이 지정되어있을때 다른 노드에 이르는 최단거리를 구하는 법이라면, 플로이드-워셜로는 모든 지점에서 다른 모든 지점까지의 최단거리를 구할 수 있다.

INF = int(1e9)


def floyd_warshall(graph):
    N = len(graph)
    dist = [[INF] * (N + 1) for _ in range(N + 1)]

    for idx in range(1, N + 1):
        dist[idx][idx] = 0

    for start, adjs in graph.items():
        for adj, d in adjs:
            dist[start][adj] = d

    for k in range(1, N + 1):
        for a in range(1, N + 1):
            for b in range(1, N + 1):
                dist[a][b] = min(dist[a][b], dist[a][k] + dist[k][b])

    return dist

동적 계획법(Dynamic Programming)

복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 수 있다. 여러 개의 하위 문제를 풀고 그 결과를 기록해 놓고 이용하여 문제를 해결할 수 있다. 재귀 알고리즘과 유사하다.
Bottom-up 방식과 Top-Down 방식으로 사용할 수도 있다.

주특기 주차를 시작했다. 알고리즘은 머리를 많이 써야해서 바빴다면, 리액트는 배울 내용이 너무 많아서 바쁘다. 부지런히 학습해야겠다. 아자자자자자!