Minimum Spanning Tree(MST) 문제는 그래프에서 모든 정점을 연결해주는 최소 간선의 집합 중 가중치의 합이 가장 작은 간선의 집합을 찾는 문제입니다. MST를 구하는 방법은 크게 2가지가 있습니다. Prim algorithm과 Kruskal algorithm이죠. Prim과 Kruskal의 기본적인 아이디어는 다음과 같습니다. Prim algorithm은 각 정점을 방문하며 그 정점에 연결된 가장 가중치가 작은 간선들을 선택하여 MST를 구합니다. Kruskal algorithm은 각 간선들을 탐색하여 가장 가중치가 작은 간선들을 택하면서 MST를 구합니다. 지금부터, 아래와 같은 그래프를 가지고 Prim algorithm과 Kruskal algorithm의 동작과정을 알아보고 각 알고..

Floyd-Warshall(플로이드-워샬 알고리즘)은 그래프에서 모든 정점 사이의 최단거리를 구하는 알고리즘입니다. 시간 복잡도는 O(V^3)을 가지죠. 이 알고리즘은 음의 사이클이 없는 그래프에 대해서 모든 정점 사이의 최단거리를 구하는 것이 가능합니다. 그래프의 간선 중 음의 가중치가 존재해도 잘 실행되죠. 모든 정점에 대한 경로를 계산하므로 거리를 저장할 자료구조는 2차원 배열이 됩니다. 이 2차원 배열을 이용하여 플로이드-워셜 알고리즘은 동적계획법으로 최적의 값을 계산합니다. 이 알고리즘의 기본 컨셉은 정점 i, j사이 모든 경유지를 탐색해서 그 중 최단 경로를 찾아내는 것입니다. 그래프의 정점이 1~V까지이면, 경유지 K는 이 모든 정점들을 경유지로 하는 경로를 탐색합니다. dp[i][j] = ..

Bellman-Ford(벨만포드) 알고리즘은 음수 가중치가 있는 그래프에서 특정 시작점 Vs에서 다른 나머지 정점(Vi, i=1, N)까지의 최단거리를 구할 수 있는 알고리즘입니다. 이 벨만포드 알고리즘을 그래프의 음수 사이클의 존재 여부도 알 수 있죠. 1. 음수 가중치가 있는 그래프에서 시작점에서 다른 정점까지의 최단거리를 구할 수 있다. 2. 음수 사이클 존재 여부를 알 수 있다. Bellman-Ford 알고리즘의 동작과정은 각 정점들을 차례로 돌아 가면서 해당 정점의 간선들을 탐색합니다, 단 맨 처음은 시작점부터 탐색합니다. 그리고 그 간선의 가중치와 시작점에서 정점까지의 거리의 합이 해당 간선이 도달하고자 하는 정점의 기존 거리보다 작으면 업데이트합니다. 식으로 나타내면 다음과 같습니다. d[T]

LCS(Longest Common Subsequence)는 문자열 A,B가 있을 시, 가장 길이가 긴 공통 부분 문자열을 찾는 알고리즘입니다. 여기서 부분 문자열이라는 것은 연속된 문자열이 아닌 부분 문자열을 뜻합니다. 예로들어, 'HAYOUNG'과 'AONG'이라는 문자열이 있을 시, 공통된 부분문자열은, {A}, {A,O}, {A,N}, {A,G}, .. ,{A,O.N,G} 가 있죠. 그리고 여기서 가장 긴 부분 문자열은 'AONG'입니다. LCS를 푸는 알고리즘은 Dynamic Programming을 이용하며 O(mn), (m = len(A), n = len(B)) 의 시간복잡도를 가지고 해결할 수 있습니다. 푸는 절차는 다음과 같습니다. 먼저, Dynamic Programming을 적용하기 위해 ..

알고리즘에서의 네트워크 유량(Network Flow) 문제는 그래프에서 각 노드들 간의 용량(Capacity)이 정의되어 있을 시, 시작점(source)에서 끝점(target)까지 흐를 수 있는 최대 유량을 구하는 문제입니다. 이 네트워크 유량 문제를 해결하는 일반적으로 많이 쓰이는 방안으로는 크게 두 가지가 있습니다. 첫 번째는 DFS로 구현하는 포드 폴커슨 알고리즘(Ford-Fulkerson Algorithm), 두 번재는 BFS로 구현하는 에드몬드 카프 알고리즘(Edmonds-Karp Algorithm)이 있습니다. 여기서는 에드몬드 카프 알고리즘으로 네트워크 유량 문제를 푸는 방식과 구현 코드를 설명하도록 하겠습니다. 위와 같이 용량에 대한 정보가 명시된 그래프에서, 1(source)에서 7(si..

소수란 1과 자기 자신만으로 나눠 떨어지는 수를 말합니다. 그리고 그 소수를 구하는 가장 간단한 방식은 에라토스테네스의 체라는 알고리즘을 이용하는 것입니다. 알고리즘은 다음과 같습니다. 1. 0,1은 소수가 아님 2. 2는 소수임, 그리고 2의 배수가 되는 수들 (2,4,6,8,10,12 ...) 목록에서 제외 3. 3은 소수임, 그리고 3의 배수가 되는 수들 (9,15,21....) 목록에서 제외 *(6, 12, 18 ... 등은 이미 제외) 4. 4는 이미 제외됨 ... 다음은 이 알고리즘을 구현한 코드입니다. 각 숫자를 표현하는 데 있어서 비트마스크를 이용한 것과 2가지 최적화 방법이 적용되 있는 걸 눈여겨 보세요. 첫 번째 최적화는 어떤 N이 소수인지 판별하는 데 있어서 N까지의 모든 수를 따지는..