Computer Science/Algorithm

[Algorithm] 크루스칼 (Kruskal) 알고리즘

Idea Kruskal Algorithm 크루스칼 알고리즘은 최소 신장 트리, MST 를 찾는 알고리즘입니다. 그래프의 간선을 하나씩 늘리면서 가중치가 최소인 간선부터 추가하는 Greedy 방식을 사용합니다. 즉, 간선을 추가하는 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택하며 MST를 만들어가는 알고리즘입니다. 동작 과정 그래프의 간선들을 가중치의 오름차순으로 정렬한다. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다. - 즉, 가장 낮은 가중치를 먼저 선택한다. - 사이클을 형성하는 간선을 제외한다. 해당 간선을 현재의 MST(최소 비용 신장 트리)의 집합에 추가한다. 각 단계에서 간선 선택을 Greedy하게 실시 하고, 이전 단계에서 만들어진 신장 트리와는 상관없..

[Algorithm] Spanning Tree와 MST (Minimum Spanning Tree)

Idea Spanning Tree Spanning tree는 그래프 내의 모든 정점을 포함하는 트리를 의미합니다. 그래프의 일부 간선을 이용해 만든 트리로서 항상 그래프의 부분집합이 됩니다. 이때 간선의 개수가 최소이어야 하며, 따라서 최소 연결 부분 그래프라고도 합니다. N개의 정점에 대해서 모든 정점을 포함하는 트리를 만들기위해서는 최소 N-1개의 간선이 필요합니다. 따라서 Spanning Tree는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결합니다. 이때 사이클을 포함해서는 안됩니다. MST (Minimum Spanning Tree) MST는 한 그래프에 대한 Spanning Tree 중에서 간선들의 가중치 합이 최소인 트리를 의미합니다. 그림에서 아래 3개의 신장 트리 중에서 ..

[Algorithm] 유니온 파인드 (Union-Find) 알고리즘

Union-Find Idea 유니온 파인드 알고리즘은 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘입니다. 노드를 합치는 Union 연산과 root 노드를 찾는 Find 연산으로 이루어집니다. 이러한 연산을 토대로 서로소 집합(공통 원소가 없는 두 집합) 자료 구조라 불리기도 합니다. 기차를 통해 출발지와 도착지를 정해서 이동이 가능한 지 판별하려고 합니다. 그래프를 통해 기차를 타고 서울에서 강릉으로 가는건 가능하지만 서울에서 부산으로 가는건 불가능하다는 것을 알 수 있습니다. 문제는 그래프가 복잡해지면 이러한 판단이 어려워 집니다. Union-Find 알고리즘을 이용하여 복잡한 그래프에서 두 노드가 연결되어 있는지 판별할 수 있습니다. 동작 과정 8개의 단절된 노드들이 있고, 이 노드들은 배열에..

[Algorithm] 플로이드 워셜 (Floyd-Warshall) 알고리즘

Floyd-Warshall Idea 플로이드-워셜 알고리즘은 모든 정점에서 다른 모던 정점까지의 최단 경로를 모두 구하는 알고리즘입니다. 모든 정점에서 다른 모든 정점까지의 최단 거리를 저장해야 하기 때문에 2차원 테이블에 최단 거리 정보를 저장합니다. 경로 계산 방식에는 아래와 같은 종류가 있습니다. 1. (One-To-One) 한 지점에서 다른 특정 지점까지의 최단경로 구하기 2. (One-To-All) 한 지점에서 다른 모든 지점까지의 최단경로 구하기 3. (All-To-All) 모든 지점에서 모든 지점까지의 최단경로 구하기 플로이드 워셜 알고리즘은 이 중 3번째 유형(All-To-All) 입니다. 플로이드 워셜 알고리즘의 점화식은 아래와 같습니다. 3중 반복문을 이용하여 위 점화식을 기준으로 테이..

[Algorithm] 벨만-포드 (Bellman-Ford) 알고리즘

Bellman-Ford Idea 벨만-포드 알고리즘은 한 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘입니다. 이때, 다익스트라와 달리 간선의 가중치가 음수인 경우에도 최단 거리를 구할 수 있습니다. 단, 음의 사이클이 없는 그래프에서만 벨만-포드 알고리즘을 적용할 수 있습니다. 이를 위해 한 노드에서 다른 노드까지의 최단 경로를 많아봐야 V-1개의 간선을 지난다는 가정을 세웁니다. 경로 계산 방식에는 아래와 같은 종류가 있습니다. 1. (One-To-One) 한 지점에서 다른 특정 지점까지의 최단경로 구하기 2. (One-To-All) 한 지점에서 다른 모든 지점까지의 최단경로 구하기 3. (All-To-All) 모든 지점에서 모든 지점까지의 최단경로 구하기 벨만-포드 알고리즘은 이 중 2..

[Algorithm] 다익스트라(Dijkstra) 알고리즘

Dijkstra Algorithm Idea 다익스트라 알고리즘은 그래프에서 한 정점에서 모든 다른 정점까지의 최단 경로를 구하는 알고리즘입니다. 매번 최단 경로의 정점을 선택하며 탐색을 반복함으로써 출발 정점에서 나머지 각 정점까지의 최단 경로를 모두 찾게 됩니다. 단, 모든 링크의 가중치(길이)는 양의 정수 값이어야 합니다! 이러한 최단 경로(최소 비용)을 구하는 알고리즘은 다익스트라 알고리즘 외에도 벨만-포드, 플로이드-워샬 알고리즘 등이 있습니다. 경로 계산 방식에는 아래와 같은 종류가 있습니다. 1. (One-To-One) 한 지점에서 다른 특정 지점까지의 최단경로 구하기 2. (One-To-All) 한 지점에서 다른 모든 지점까지의 최단경로 구하기 3. (All-To-All) 모든 지점에서 모든..

[Algorithm] 이진 탐색(Binary Search) 알고리즘

Binary Search Idea 이진 탐색은 정렬된 배열이 주어질 때, 리스트의 중간값과 비교하면서 반씩 제외하며 원하는 값을 찾아가는 과정입니다. 주의할 점은, 이진 탐색 알고리즘은 정렬된 배열에만 적용 가능하다는 점입니다. 따라서 정렬되어있지 않다면 성능이 우수한 퀵 정렬을 통해 약 O(nlogn)의 시간을 들여 정렬을 한 뒤 이진 탐색 알고리즘을 적용해야 합니다. 이진 탐색의 과정을 살펴보면 아래와 같습니다. 중간 인덱스(middle)를 구한다. (첫번째 인덱스 + 마지막 인덱스) / 2 찾을 값(target)이 middle보다 작은 경우, middle과 그 이후 인덱스들을 검색 범위에서 제외한다. target이 middle보다 큰 경우, middler과 그 이전 인덱스들을 검색 범위에서 제외한다..

[Algorithm] 위상 정렬(Topological sort) 알고리즘

Topological sort 위상 정렬이란, 사이클이 없는 방향 그래프(DAG)를 방향성에 거스르지 않도록 순서대로 나열하는 것입니다. 대표적인 예시로, 선수 과목을 고려해서 학습 순서를 설정하는 것이 있습니다. 일반화학, 유기화학1, 유기화학2 라는 3과목이 있을 때, 아래의 학습 순서들 중 적절한 순서는 (2)가 될 것입니다. (1) 일반화학 -> 유기화학2 -> 유기화학1 (2) 일반화학 -> 유기화학1 -> 유기화학2 우선, 비순환 방향 그래프(DAG)에 대해 정리하겠습니다. 비순환 방향 그래프 (Directed Acyclic Graph) 위와 같이 방향 그래프이면서 사이클이 없는 그래프를 DAG라고 한다. DAG와 Topological sort 위상 정렬은 이러한 비순환 방향 그래프에서 정점들..