새싹프로그래머의 이야기

*알고리즘 이론은 복습 용도로 작성되었습니다. 간략하게 작성되어 있을 수 있으며 해당 알고리즘을 어느정도 알고있다는 전제하에 작성되었습니다.

1. 플로이드 워셜 알고리즘이란?

최단 경로 알고리즘 중 하나로, 모든 노드에서 모든 노드까지의 최단 경로를 모두 구하는 알고리즘 입니다.

플로이드 워셜 알고리즘은 거리 정보를 계산할 때, 점화식을 활용한다는 점에서 다이나믹 프로그래밍이 적용되어 있다고 할 수 있습니다.

점화식은 다음과 같습니다.

$$D_{ab} = min(D_{ab}, D_{ak} + D_{kb})$$

동작과정은 다음과 같습니다.

1. 초기 값 입력. 

각 간선(edge)에 대한 cost가 주어진다고 가정하였을 때, 이차원 배열에 해당 cost를 갱신 시킵니다.

자기 자신에 대한 cost는 0이며, 갈 수 없는 노드는 INF로 초기화 합니다.

2. 각 노드를 순회하며, 해당 노드를 거쳐갈 수 있는 경로 확인 및 갱신

예를 들어, 모든 1번 노드에 대해서 거쳐갈 수 있는 경로는 다음과 같습니다.

$$D_{23} = min(D_{23}, \, D_{21}+D_{13}) \qquad =>min(2,7+4) == 2$$

$$D_{24} = min(D_{24}, \, D_{21}+D_{14}) \qquad =>min(2,7+INF) == 2$$

$$D_{32} = min(D_{32}, \, D_{31}+D_{12}) \qquad =>min(INF,5+1) == 6$$

↑update

$$D_{34} = min(D_{34}, \, D_{31}+D_{14}) \qquad =>min(3,5+INF) ==3$$

$$D_{42} = min(D_{42}, \, D_{41}+D_{12}) \qquad =>min(INF,1+1) == 2$$

↑update

$$D_{43} = min(D_{43}, \, D_{41}+D_{13}) \qquad =>min(INF,1+4)==5$$

↑update

이와 같이 거쳐가는 경로를 계산하여, 기존 담겨있는 cost보다 더 낮은 cost가 든다면 table을 갱신하여 줍니다.

이 과정을 모든 노드에 대하여 반복하여 줍니다.

2. 코드구현

코드는 백준 알고리즘 11404번을 기반으로 작성되었습니다.

• 이차원 배열(= 거리 테이블)에 대하여, 자신한테로의 경로를 0으로 초기화 해줍니다.
• 간선와 cost에 대한 정보를 입력받아 거리 테이블에 갱신하여 줍니다.
• 3중 for문을 통해, 각 노드별로 거쳐가는 경로(점화식 기반)를 모두 탐색하고 거리 테이블을 갱신합니다. 

import sys

INF = sys.maxsize

n = int(input())    # number of city
m = int(input())    # number of bus

graph = [[INF] * (n+1) for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(1, n+1):
        if i == j:
            graph[i][j] = 0  # path to self = 0

for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    graph[a][b] = min(graph[a][b],c)    # update array about initial path

# D_ab = D_ak + D_kb
for k in range(1,n+1):
    for a in range(1,n+1):
        for b in range(1, n+1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

for i in range(1,n+1):
    for j in range(1, n+1):
        if graph[i][j] == INF:
            graph[i][j] = 0
for i in range(1, n+1):
    print(*graph[i][1:])
    # print(' '.join(map(str,graph[i][1:])))

• Reference

https://freedeveloper.tistory.com/385

*알고리즘 이론은 복습 용도로 작성되었습니다. 간략하게 작성되어 있을 수 있으며 해당 알고리즘을 어느정도 알고있다는 전제하에 작성되었습니다.

다익스트라(dijkstra) 알고리즘은 최단 경로를 구하는 알고리즘 중 하나입니다.

1. 최단 경로(Shortest Path) 알고리즘이란?

Path와 cost가 주어졌을 때, cost가 제일 적게 드는 경로를 찾는 알고리즘 입니다.

특히, 다익스트라 알고리즘은 한 지점에서 특정 지점까지의 최단 경로를 구하는 알고리즘으로 시작점과 끝점을 필요로 합니다.

자료구조로는 graph를 사용하며, 지점을 그래프의 node로 표현하고 경로를 그래프의 edge로 표현합니다.

2. 다익스트라 알고리즘

1. 시작 노드가 1이라고 했을 때, 알고리즘이 동작하는 원리는 다음과 같습니다.
2. 1에서 cost가 가장 가까운 노드 3에 대한 distance를 업데이트 합니다
3. 1에서 가장 가까운 노드를 모두 업데이트 합니다. 즉, 1에 대해서 1 -> 3, 1 -> 2, 1 -> 5 의 cost가 업데이트 됩니다.
4. 코스트가 낮은 3으로 이동하지만 연결된 노드가 없으므로, 2로 이동합니다.
5. 2 -> 5의 cost = 1이므로, 1 -> 5 의 최소 cost는 6 입니다. 따라서, 기존의 cost 9 짜리 1 -> 5 경로는 폐기되고 6으로 새로 업데이트 됩니다.

*다익스트라 알고리즘은 모든 cost가 음의 정수가 아니어야만 동작 가능합니다. 음의 정수가 포함되어 있을 경우, 최단거리를 구하는 알고리즘은 Bellman-Ford 알고리즘으로 향후 포스팅 하도록 하겠습니다.

*시간복잡도는 우선순위 큐를 사용할 경우, O($ElogV$)입니다.

3. 코드구현

• 노드에 대한 정보를 담을 때는, graph를 활용합니다.
• 우선순위 큐와 거리 정보를 담을 list를 사용합니다.
• 반복문을 통해, 출발 노드 부터 최소거리 순으로 거리 정보를 업데이트 해줍니다.
• 위 그림의 1 -> 2 -> 5와 같이 거쳐서 가는 경로에 대한 거리 정보도 업데이트 해줍니다.
• 거리정보 업데이트가 완료되면, 수행을 종료합니다.

코드는 백준 알고리즘 1753번 문제 풀이를 통해 작성하였습니다.(https://www.acmicpc.net/problem/1753)

import sys
import heapq

INF = 1E10

v, e = map(int, sys.stdin.readline().split())
k = int(input())

graph = [[]for _ in range(v+1)]
heap_q = [(0, k)]
distance = [INF] * (v+1)
distance[k] = 0

for _ in range(e):
    start, end, cost = map(int, sys.stdin.readline().split())
    graph[start].append((cost,end))


def dijkstra():
    while heap_q:
        nowCost, node = heapq.heappop(heap_q)

        if distance[node] < nowCost:    # if distance is updated
            continue

        for newCost, newNode in graph[node]:    # check adjacent node
            dist = distance[node] + newCost
            if distance[newNode] > dist:    # update lower cost
                distance[newNode] = dist
                heapq.heappush(heap_q, (dist, newNode))

dijkstra()

for i in range(1,v+1):
    if distance[i] == INF:
        print('INF')
    else:
        print(distance[i])

Reference

https://jaemunbro.medium.com/algorithm-%EC%B5%9C%EB%8B%A8-%EA%B2%BD%EB%A1%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-with-python-20f061fdc8f1

*알고리즘 이론은 복습 용도로 작성되었습니다. 간략하게 작성되어 있을 수 있으며 해당 알고리즘을 어느정도 알고있다는 전제하에 작성되었습니다.

1. BFS란?

그래프를 탐색하는 알고리즘의 한 종류로, leaf 노드에 도달할 때 까지 깊이 우선 탐색을 하는 DFS와 달리 인접한 노드부터 탐색하는 방법입니다. 그래프의 각 깊이 별로 탐색을 하게 되므로, 넓이 우선 탐색이라고 부릅니다.

*시간복잡도는 DFS와 마찬가지로 인접리스트 방식은 모든 노드(n)와 간선(e)을 탐색하므로, O(n+e) 입니다.

구체적으로 단계를 설명해보자면 다음 그림과 같습니다.

2. 구현 방법

• queue를 통해 인접한 배열을 담아가며 탐색합니다.
• visited 배열을 통해 방문 여부를 확인합니다.
• 인접한 노드를 우선적으로 탐색하며, 방문하지 않은 노드만 탐색합니다.

백준알고리즘 1260번을 기반으로 구현한 코드입니다.(https://www.acmicpc.net/problem/1260)

import sys
from collections import deque

n,m,v = map(int, sys.stdin.readline().split())

graph = [[] for _ in range(n+1)]

for i in range(m):
    node1, node2 = map(int, sys.stdin.readline().split())
    graph[node1].append(node2)
    graph[node2].append(node1)

for i in range(1,n+1):
    graph[i].sort()

visited_bfs = [False]*(n+1)

def bfs(n):
    q = deque([n])
    visited_bfs[n] = True

    while q:
        node = q.popleft()
        print(node, end=' ')

        for new_node in graph[node]:
            if visited_bfs[new_node]:
                continue
            q.append(new_node)
            visited_bfs[new_node] = True

bfs(v)

*알고리즘 이론은 복습 용도로 작성되었습니다. 간략하게 작성되어 있을 수 있으며 해당 알고리즘을 어느정도 알고있다는 전제하에 작성되었습니다.

1. DFS란? 

그래프를 탐색하는 알고리즘의 한 종류로, leaf node(자식이 없는 노드)에 도달할 때까지 한 방향으로 탐색하는 기법입니다.

*시간 복잡도는 인접리스트 방식의 DFS는 모든 노드(n)와 모든 간선(e)을 탐색했다고 할 수 있으므로, O(n+e)의 복잡도를 가집니다.

구체적으로 보자면, 다음과 같은 탐색과정을 거칩니다.

2. 코드 구현

• 재귀적 구현을 통하여 구현합니다.
• visited 배열을 통해 방문 여부를 확인하여야 합니다.
• 노드를 방문할 경우 방문처리를 해주며, 방문하지 않은 노드만 방문합니다.
• 방문하는 방향으로 leaf node에 도달할 때 까지 탐색을 진행합니다.
• 위, 과정을 모든 leaf node를 방문할 때 까지 반복합니다.

백준 알고리즘 1260번을 통하여 구현한 코드입니다.(https://www.acmicpc.net/problem/1260)

import sys
from collections import deque

n,m,v = map(int, sys.stdin.readline().split())

graph = [[] for _ in range(n+1)]

for i in range(m):
    node1, node2 = map(int, sys.stdin.readline().split())
    graph[node1].append(node2)
    graph[node2].append(node1)

for i in range(1,n+1):
    graph[i].sort()

visited_dfs = [False]*(n+1)

def dfs(n):
    print(n, end=' ')
    visited_dfs[n] = True

    for node in graph[n]:
        if visited_dfs[node]:
            continue
        dfs(node)
dfs(v)

*알고리즘 이론은 복습 용도로 작성되었습니다. 간략하게 작성되어 있을 수 있으며 해당 알고리즘을 어느정도 알고있다는 전제하에 작성되었습니다.

1. 이진 탐색(Binary Search)이란?

오름차순으로 정렬된 배열에서 찾고자하는 element를 탐색하는 알고리즘 입니다.

데이터를 반으로 나눠가며 탐색을 진행합니다.

시간 복잡도는 O( log N ) 입니다.

 2. 구현 방법

• 배열에서 중간 값을 찾고자하는 target 값이랑 비교한다
• 중간 값 < target 이라면, 중간 값보다 오른쪽에 있는 배열로 범주를 좁혀 과정을 반복한다
• 중간 값 > target 이라면, 중간 값보다 왼쪽에 있는 배열로 범주를 좁혀 과정을 반복한다

3. 코드

백준 알고리즘 10815번을 기준으로 작성하였습니다.

myCard - 오름차순으로 정렬 되어 있는 배열

Binary Search - 반복문

def binarySearch(target):
    start = 0
    end = len(myCard) - 1

    while start <= end:
        mid = (start + end) // 2
        if myCard[mid] == target:
            return 1
        elif myCard[mid] < target:
            start = mid + 1
        else:
            end = mid - 1

    return 0

Binary Search - 재귀

def binarySearch(target,start,end):
    mid = (start+end)//2

    if start > end:
        return 0
    if myCard[mid] == target:
        return 1
    elif myCard[mid] < target:
        start = mid + 1
    else:
        end = mid -1

    return binarySearch(target,start,end)