IT-garden

크루스칼(Kruskal) 알고리즘은 간선들을 가중치가 증가하는 순서로 정렬하고 가중치가 가장 작은 간선이 사이클을 만들지 않으면 트리 간선으로 선택합니다. 다음 가중치에서도 사이클을 만들지 않으면 트리 간선으로 선택하고 이 과정을 반복해서 정점-1개의 간선을 선택하는 알고리즘입니다.

크루스칼 알고리즘은 최소신장트리(무방향 가중치 그래프에서 간선의 가중치 합이 최소인 것)를 찾는 알고리즘입니다.

크루스칼 알고리즘은 항상 욕심내서 최솟값을 선택하여 가중치의 합이 최소인 것을 찾기 때문에 그리디 알고리즘이라고 할 수 있습니다.

크루스칼 알고리즘에서 간선이 사이클을 만드는지는 union연산과 find연산을 사용합니다. 이는 Union-Find 알고리즘이라고도 부르고 서로소 집합 알고리즘이라고도 합니다. 이 알고리즘은 여러 노드가 존재할 때 두 개의 노드를 선택해 루트를 확인하고 현재 서로 같은 그래프에 속하는지 판별합니다.

상호 배타적 집합들은 1차원 리스트로 표현하며 루트의 리스트 원소에는 루트 자신이 저장되고 루트가 아닌 노드의 원소에는 부모 노드가 저장됩니다. union은 두 개의 집합을 하나의 집합으로 합치는 연산입니다. find는 find연산을 수행하면서 루트까지 올라가는 경로 상의 각 노드의 부모 노드를 루트로 갱신합니다. 이를 경로 압축이라 하는데 이를 실행하면서 수행 시간을 단축시켜 줄 수 있습니다.

find(1)이 수행되면서 1, 3, 7, 10을 거쳤는데 각 노드의 부모노드를 루트로 갱신했습니다.

다음은 크루스칼 알고리즘으로 최소신장트리를 찾는 과정입니다.

크루스칼 알고리즘에서 최소신장트리를 찾기 위해서는 먼저 그래프의 가중치를 기준으로 오름차순으로 정렬합니다.

그리고 가중치에 따른 간선들이 싸이클을 형성하는지 하나씩 확인합니다.

정점 4와 5를 이어주는 첫번째 간선을 선택합니다.

정점 5와 6을 이어주는 두번째 간선을 선택합니다.

정점 3와 5를 이어주는 세 번째 간선을 선택합니다.

정점 1와 3을 이어주는 네 번째 간선을 선택합니다.

정점 4와 6을 선택할 경우 정점 4, 5, 6이 사이클을 형성하기 때문에 선택하지 않습니다.

정점 2와 4을 이어주는 여섯 번째 간선을 선택합니다.

이를 통해 모든 정점이 연결되어 최소신장트리를 이룹니다.

간서의 가중치의 값은 1 + 2 + 3 + 5 + 9 = 20입니다.

크루스칼 알고리즘의 파이썬 코드입니다.

graph=[(1,2,13),(1,3,5),(2,4,9),(3,4,15),(3,5,3),(4,5,1),(4,6,7),(5,6,2)]
graph.sort(key = lambda x: x[2]) # 가중치로 간선 정렬 (정점1, 정점2, 가중치)

mst=[]
n=6 # 정점 개수
p=[0] # 상호배타적 집합

for i in range(1,n+1):
    p.append(i) # 각 정점 자신이 집합의 대표

def find(u):
    if u != p[u]:
        p[u] = find(p[u]) # 경로압축
    return p[u]

def union(u, v):
    root1 = find(u)
    root2 = find(v)
    p[root2] = root1 # 임의로 root2가 root1의 부모

tree_edges = 0 # 간선 개수
mst_cost = 0 # 가중치 합

while True:
    if tree_edges == n-1:
        break
    u, v, wt =graph.pop(0)
    if find(u) != find(v): # u와 v가 서로 다른 집합에 속해 있으면
        union(u, v)
        mst.append((u, v)) 
        mst_cost += wt
        tree_edges += 1

# 출력>>최소신장트리:  [(4, 5), (5, 6), (3, 5), (1, 3), (2, 4)]
print('최소신장트리: ',mst)

# 출력>>최소신장트리 가중치: 20
print('최소신장트리 가중치:', mst_cost)

최대공약수(GCD : Greatest Common Divisor)
최대공약수는 두 자연수의 공통된 약수 중 가장 큰 수를 의미합니다.

최소공배수(LCM : Least Common Multiple)

최소공배수는 두 자연수의 공통된 배수 중 가장 작은 수를 의미합니다.

최소공배수 = 두 자연수의 곱 / 최대공약수

유클리드 알고리즘은 자연수 2개의 최대공약수를 구하는 알고리즘입니다.
2개의 자연수 a, b(a > b)에 대해 a를 b로 나눈 나머지를 r(0 < r < b)이라 하면 a와 b의 최대공약수는 b와 r의 최대공약수와 같습니다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수입니다. 이 알고리즘은 명시적으로 기술된 가장 오래된 알고리즘으로도 알려져 있습니다.

유클리드 알고리즘은
1. a, b 두 수가 주어집니다. (a > b)
2. b가 0이면 a을 리턴합니다.
3. a가 b로 나눠 떨어지지 않으면 a를 b로, b를 a에서 b로 나눈 나머지를 대입하고 1번으로 돌아갑니다.
3. a가 b로 나눠 떨어지면 b을 리턴합니다.

유클리드 알고리즘을 이용해 54, 20의 최대공약수를 구하는 예시입니다. (%는 나머지 구하기)
54 % 20 = 14
20 % 14 = 6
14 % 6 = 2
6 % 2 = 0

6 % 2가 0이 되기 때문에 최대공약수는 2가 됩니다.

이를 이용해 54*20/2=540를 계산하면 나오면 540이 최소공배수가 됩니다.

유클리드 알고리즘을 이용해 54, 24의 최대공약수를 구하는 예시입니다.
54 % 24 = 6
24 % 6 = 0
24 % 6가 0이 되기 때문에 최대공약수는 6이 됩니다.

최대공약수(GCD)와 최소공배수(LCM) 알고리즘의 파이썬 코드입니다.

def gcd(a,b): # 최대공약수
    if b == 0:
        return a
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)

x=54
y=20

# 최대공약수(GCD)
# 출력>>2
print(gcd(x,y))

# 출력>>6
print(gcd(54,24))

# 최소공배수(LCM)
# 출력>>540
print(int(x*y/gcd(x,y)))

에라토스테네스의 체는 소수를 판별하는 알고리즘으로 많은 소수를 구하거나 특정 범위의 소수를 구할 때 유용합니다.

n=100
a=[]

for i in range(2,n+1):
    for j in range(2,i):
        if i%j == 0:
            break
    else:
        a.append(i)

# 출력>>[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
print(a)

기본적인 소수를 구하는 방법으로 특정 수보다 작은 모든 수로 나눠서 소수인지를 판단합니다.
위 방법은 정확하지만 범위의 소수를 모두 구할 때는 효율적이지 않습니다.

따라서 에라토스테네스의 체를 이용하면 시간을 줄이고 쉽게 소수를 구할 수 있습니다.

에라토스테네스의 체 알고리즘은

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열합니다.

2. 2부터 시작해서 나열된 수에서 지워지지 않은 수 중 가장 작은 2를 소수로 선택하고 2의 배수를 지웁니다.
3. 3도 지워지지 않았기 때문에 소수로 선택하고 3의 배수를 지웁니다.
4. 4는 지워졌기 때문에 넘어가고 5를 소수로 선택하고 5의 배수를 지웁니다.
5. 2, 3, 4와 같은 과정을 반복합니다.
6. 반복이 끝나면 지워지지 않은 수들을 소수로 출력합니다.

n=100
a=[True] * (n+1)
m = int(n ** 0.5)

for i in range(2,m+1):
    if a[i] == True:
        for j in range(i+i,n+1,i):
            a[j]=False

# 출력>>[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
print([i for i in range(2, n+1) if a[i] == True])

에라토스테네스의 체를 이용한 방법입니다.
에라토스테네스의 체를 구할 때는 또한 n의 약수가 sqrt(n) 이하여서 sqrt(n)까지 검사하면 시간을 더 줄일 수 있습니다.
(sqrt는 루트)

플로이드-워셜(Floyd-Warshall) 알고리즘은 모든 정점 사이의 최단 경로를 찾는 탐색 알고리즘입니다.

최단 경로는 길이 순으로 구해집니다.

플로이드 워셜 알고리즘의 과정입니다.

1. 하나의 정점에서 다른 정점으로 바로 갈 수 있으면 최소 비용을, 갈 수 없다면 INF로 배열에 값을 저장합니다.
2. 3중 for문을 통해 거쳐가는 정점을 설정한 후 해당 정점을 거쳐가서 비용이 줄어드는 경우에는 값을 바꿔줍니다.
3. 위의 과정을 반복해 모든 정점 사이의 최단 경로를 탐색합니다.

다음과 같은 단방향 그래프가 있으면 정점은 1, 2, 3, 4로 4개입니다.

간선은 1 → 2, 1 → 4, 2 → 1, 2 → 4, 3 → 1, 4 → 2, 4 → 3로 7개입니다.

플로이드-워셜 알고리즘은 각각의 점들을 거치는 경우를 생각해야 합니다.

Dist는 1부터 각 정점까지의 최단 경로를 담는 배열입니다.

시작점과 끝점이 1을 거치는 경우에 값이 기존 값보다 작은 경우 최단 경로를 Dist에 넣습니다.

3에서 2로 가는 방법이 INF였는데 3에서 1을 거쳐 2로 가는 방법이 5이기 때문에 Dist[3][2]는 5로 바꿔줍니다.
3에서 4로 가는 방법이 INF였는데 3에서 1을 거쳐 4로 가는 방법이 7이기 때문에 Dist[3][4]는 7로 바꿔줍니다.

4에서 1로 가는 방법이 INF였는데 4에서 2을 거쳐 4로 가는 방법이 4이기 때문에 Dist[4][1]는 4로 바꿔줍니다.

3을 거쳐가는 경우에는 변동이 없습니다.

1에서 3로 가는 방법이 INF였는데 1에서 4를 거쳐 3으로 가는 방법이 5이기 때문에 Dist[1][3]는 5로 바꿔줍니다.

2에서 3로 가는 방법이 INF였는데 2에서 4를 거쳐 3으로 가는 방법이 6이기 때문에 Dist[2][3]는 6로 바꿔줍니다.

플로이드-워셜 알고리즘이 끝나면 각 정점들을 거치는 경우를 계산한 것을 확인할 수 있습니다.

Dist[i][j]는 i에서 j로 가는 경우 최단 경로의 값들입니다.

위의 예시를 이용한 플로이드-워셜 알고리즘 파이썬 코드입니다.

import sys

INF = sys.maxsize

def Floyd_Warshall():
    dist = [[INF]*n for i in range(n)] # 최단 경로를 담는 배열

    for i in range(n): # 최단 경로를 담는 배열 초기화
        for j in range(n):
            dist[i][j] = a[i][j]

    for k in range(n): # 거치는 점
        for i in range(n): # 시작점
            for j in range(n): # 끝점
                # k를 거쳤을 때의 경로가 더 적은 경로
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    return dist

n = 4 # 정점 수
a = [[0, 2, INF, 4],[2, 0, INF, 5],[3, INF, 0, INF],[INF, 2, 1, 0]]

dist = Floyd_Warshall()

for i in range(n):
    for j in range(n):
        print(dist[i][j],end=' ')
    print()

다익스트라(Dijkstra) 알고리즘은 특정한 하나의 시작 정점에서 모든 다른 정점까지의 최단 경로를 찾는 탐색 알고리즘입니다.

최단 경로는 경로의 길이순으로 구해집니다.

경로는 간선으로 주어지는데 이때 간선의 가중치는 문제에서 비용, 거리, 시간 등으로 나타납니다.

다익스트라(Dijkstra) 알고리즘의 과정입니다.

1. 하나의 시작 정점을 설정하고 이를 기준으로 각 최소 비용을 배열에 저장합니다.
    바로 갈 수 없는 곳의 값은 INF로 합니다.
2. 방문하지 않은 점 중 가장 비용이 적은 정점을 선택합니다.
3. 해당 정점를 거쳐 특정한 정점으로 가는 경우를 고려하여 최소비용을 변경합니다.
4. 위의 과정을 반복해 최단 경로를 탐색합니다.

다음과 같은 단방향 그래프가 있으면 정점은 1, 2, 3, 4, 5, 6으로 6개입니다.

간선은 1 → 2, 1 → 3, 1 → 4, 2 → 6, 3 → 4로 5개입니다.

다익스트라 알고리즘은 시작점이 있어야 합니다. 1부터 모든 정점까지의 최단 경로를 탐색하겠습니다.

Dist는 1부터 각 정점까지의 최단 경로를 담는 배열입니다.

Dist에 1에서 1을 가는 경로는 0이기 때문에 Dist[1]은 0으로 설정해줍니다.

이 외의 값들은 아직 모르기 때문에 최대값을 넣습니다.

1에서 각 정점들의 최단 경로를 탐색에 Dist에 있는 값보다 작은 경우 최단 경로를 Dist에 넣습니다.

1에서 2로 가는 경로는 길이가 2이기 때문에 INF보다 적으니 Dist[2]는 2로 바꿔줍니다.

1에서 3로 가는 경로는 길이가 3이기 때문에 INF보다 적으니 Dist[3]는 3로 바꿔줍니다.

1에서 4로 가는 경로는 길이가 6이기 때문에 INF보다 적으니 Dist[4]는 6로 바꿔줍니다.

2에서는 1에서 2를 거쳐 6으로 가는 경로의 길이가 6이기 때문에 INF보다 적으니 Dist[6]는 6로 바꿔줍니다.

3에서는 1에서 3를 거쳐 4으로 가는 경로의 길이가 4인데 기존에 있던 6(1에서 4로 가는 경로) 보다 적으니 Dist[4]는 4로 바꿔줍니다.

4에서는 변경이 없습니다.

6에서는 변경이 없습니다.

다익스트라 알고리즘이 끝나면 정점 1, 2, 3, 4, 6을 거친 것을 알 수 있습니다.

정점 5를 연결해주는 간선은 없기 때문에 정점 5는 거치지 않았습니다.

최종적인 Dist가 1에서 각 정점까지의 최단 경로입니다.

Dist[0] 코드의 편리를 위해 만들었고 실제로는 정점도 없고 거치지 않았기 때문에 제외해야 합니다.

위의 예시를 이용한 다익스트라 알고리즘 파이썬 코드입니다.

import heapq
import sys

INF = sys.maxsize

def Dijkstra(adjacent, K):

    dist = [INF] * len(adjacent)   # source로부터의 최소 거리 배열, 무한대로 초기
    
    dist[K] = 0 #시작점에서 시작점으로의 거리는 0으로 설정

    queue = []
    heapq.heappush(queue, [0, K]) #시작점 넣기
    
    while queue:

        # 거리가 제일 작은 노드 선택
        current_dist, here = heapq.heappop(queue)

        # 인접 노드 iteration
        for there, length in adjacent[here].items():
            next_dist = dist[here] + length

            if next_dist < dist[there]:
                dist[there] = next_dist
                heapq.heappush(queue, [next_dist, there])

    return dist

# v는 정점, e는 간선, k는 시작점
V=6
E=5

adjacent=[{}, {2: 2, 3: 3, 4: 6}, {6: 4}, {4: 1}, {}, {}, {}]

dist = Dijkstra(adjacent, 1)

for d in dist[1:]:
    print(d if d != INF else "INF")

힙(heap) 큐 알고리즘을 이용한 기본 다익스트라 알고리즘 파이썬 코드입니다.

import heapq
import sys

INF = sys.maxsize

def Dijkstra(adjacent, K):

    prev = [-1] * len(adjacent)   # 이전에 거친 것 구하는 배열
    dist = [INF] * len(adjacent)   # K로부터의 최소 거리 배열, INF로 초기화

    dist[K] = 0 #시작점에서 시작점으로의 거리는 0으로 설정

    queue = []
    heapq.heappush(queue, [0, K]) #시작점 넣기
    
    while queue:
	# 거리가 제일 작은 노드 선택
    # current_dist: 현재까지의 거리, here : 지금 위치한 곳의 정점
        current_dist, here = heapq.heappop(queue) 

        for there, length in adjacent[here].items():
            next_dist = dist[here] + length

            if next_dist < dist[there]:
                dist[there] = next_dist
                prev[there] = here
                heapq.heappush(queue, [next_dist, there])

    return dist, prev

# V는 정점 수, E는 간선 수, K는 시작점
V, E = map(int, input().split())
K = int(input())
adjacent = [{} for _ in range(V + 1)]

for i in range(E):
    u, v, w = map(int, input().split())

    #같은 경로의 간선이 주어질 경우 적은 비용의 간선 선택
    if v in adjacent[u]:
        adjacent[u][v] = min(adjacent[u][v], w)
    else:
        adjacent[u][v] = w

dist, prev = Dijkstra(adjacent, 1)

for d in dist[1:]:
    print(d if d != INF else "INF")

이진 탐색(Binary Search)은 리스트를 반으로 나눠 검색하며 원하는 값을 찾는 알고리즘입니다.

원하는 값은 key로 주어지고 탐색의 범위는 low와 high로 주어집니다.

리스트의 중앙에 있는 값을 확인해 찾고자 하는 key 값이 리스트의 중앙에 있는 값보다 작은지 큰지에 따라 검색 범위를 반으로 줄입니다.

- key 값이 리스트의 중간 요소와 일치하면 탐색을 끝냅니다.

- key 값이 리스트의 중간 요소보다 큰 경우 중간 요소 이후의 리스트만 탐색합니다.

- key 값이 리스트의 중간 요소보다 작은 경우 중간 요소 이전의 리스트만 탐색합니다.

이진 탐색을 하기 위해서는 리스트는 반드시 정렬되어 있어야 합니다.

이진 탐색은 이분 탐색이라고도 합니다.

a=[1, 3, 5, 7, 9, 11, 13]

def Binary_Search(key, low, high):

    while low <= high:
        middle = (low + high) //2

        if key == a[middle]:
            return middle

        elif key > a[middle]:
            low = middle + 1
            
        elif key < a[middle]:
            high = middle - 1
        
    return -1
        
# 출력>>6
print(Binary_Search(13, 0, 6))

# 출력>>-1
print(Binary_Search(10, 0, 6))

# 출력>>2
print(Binary_Search(5, 0, 4))

# 출력>>-1
print(Binary_Search(6, 0, 4))

함수 Binary_Search이 이진 탐색 알고리즘입니다.

Binary_Search(13, 0, 6)

low가 0이고 high가 6입니다. 리스트 a의 인덱스 0에서 6까지에서 key가 13인 인덱스를 찾습니다.

Binary_Search(10, 0, 6)

low가 0이고 high가 6입니다. 리스트 a의 인덱스 0에서 6까지에서 key가 10인 인덱스를 찾습니다.

Binary_Search(5, 0, 4)

low가 0이고 high가 4입니다. 리스트 a의 인덱스 0에서 4까지에서 key가 5인 인덱스를 찾습니다.

Binary_Search(6, 0, 4)

low가 0이고 high가 4입니다. 리스트 a의 인덱스 0에서 4까지에서 key가 6인 인덱스를 찾습니다.

a=[1, 3, 5, 7, 9, 11, 13]

def Binary_Search(key):
    low = 0
    high = len(a) - 1

    while low <= high:
        middle = (low + high) //2

        if key == a[middle]:
            return middle

        elif key > a[middle]:
            low = middle + 1
            
        elif key < a[middle]:
            high = middle - 1
        
    return -1
        
# 출력>>6
print(Binary_Search(13))

# 출력>>-1
print(Binary_Search(10))

탐색의 범위를 low와 high로 설정하지 않고 리스트 전체에서 key를 찾는 이진 탐색 알고리즘입니다.

가장 많이 사용하는 이진 탐색 알고리즘 코드입니다.

이진 탐색 알고리즘의 시간복잡도는 O(logN)입니다.