알고리즘

플로이드-워셜 모든 노드간의 최단 경로를 구할 수 있는 알고리즘 입니다. 다익스트라는 출발 지점이 정해진 경우에 사용할 수 있지만 플로이드-워셜 알고리즘은 한번 실행으로 모든 노드간의 최단 경로를 구할 수 있습니다. 대신 $O(n^3)$ 이라는 시간 복잡도를 가지고 있습니다. 그래프내에 음의 간선이 있는 경우에도 활용 가능합니다. 해결 방법 그래프가 주어지면 각 간선을 토대로 2차원 인접행렬을 만듭니다. 알고리즘은 여러 라운드로 구성됩니다. 각 라운드마다 경유 노드를 지정하고 해당 노드를 반드시 지나는 경우와 기존의 경우를 비교하여 더 짧은 경우를 선택합니다. 모든 노드를 경유하는 경우를 고려해야 하므로 노드의 개수가 n 이라면 n개의 라운드를 반복합니다. 예시를 들어 알아봅시다. 위의 그래프를 2차원 ..

배낭 문제 N 개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지고, 해당 물건을 배낭에 넣으면 V 만큼의 가치를 얻는다. 최대 K 만큼의 무게만을 넣을 수 있는 배낭이 있을 때, 배낭에 넣을 수 있는 물건들의 가치의 최대값을 구하여라. 위의 문제가 배낭 문제 입니다. 문제의 상황이나 디테일한 부분은 달라질 수 있겠지만 대게 가중치 W 와 값 V 가 주어지고 가중치의 합이 K를 넘지 않도록 물건들을 조합하여 V의 합이 최대가 되도록 구하는 문제로 정의할 수 있습니다. Fractional Knapsack Problem 주어진 물건들이 분할 가능한 경우입니다. 물건들이 분할 가능하기 때문에 무게당 가치를 계산하여 높은 순서대로 배낭에 넣으면 K 까지 넣었을 때의 가치가 최대값 입니다. 즉, 그리디 알고..

신장 트리 신장트리(Spanngin Tree) 란, 무방향 그래프에서 그래프 내의 모든 정점을 포함하며, 최소한의 간선 개수만을 가지는 서브 그래프입니다. 최소한의 간선만을 사용해야 하므로 사이클이 발생하면 안되고, 놓치는 정점이 발생하면 안됩니다. 이는 이름에서도 알 수 있듯이 트리의 형태입니다. 따라서 간선의 개수는 (정점의 개수 - 1) 입니다. 정점의 개수가 N개라면 신장트리의 간선 개수는 N-1 이 됩니다. 최소 신장 트리 (MST) 하나의 그래프에서 여러개의 신장트리가 만들어 질 수 있습니다. 이 중에서 각 간선의 가중치 합이 최소가 되는 신장트리가 최소 신장 트리(MST) 입니다. MST는 다음과 같은 특징을 가집니다. 사이클이 존재하지 않는다. n개의 정점을 가지는 그래프에서 항상 n-1 ..

Travelling Salesman Problem 외판원 순회 알고리즘은 가중치가 주어진 그래프에서 가장 작은 가중치를 가지는 해밀턴 순환을 구하는 알고리즘입니다. 다시 말해, 간선의 가중치가 주어졌을 때 임의의 시작노드에서 출발하여 모든 노드를 탐색한 뒤 다시 시작노드로 돌아올 때의 가중치 합의 최소값을 구하는 알고리즘 입니다. 이때 마지막 노드에서 시작 노드로 돌아오는 것을 제외하고는 노드를 중복하여 탐색해서는 안됩니다. 가장 먼저 떠올릴 수 있는 방법은 완전탐색이 있습니다. 노드가 n개라면 n개의 순열을 만들어 각 경우의 가중치 합을 비교하여 최소값을 구할 수 있습니다. 하지만 이 방법은 $O(n!)$으로 n이 조금만 커져도 사용할 수 없는 알고리즘이 됩니다. DP, memoization 완전탐색에..

희소 배열 희소배열, Sparse Table 이라 불리는 기법에 대해 알아봅시다. 노드마다 단 하나의 간선만을 가지는 방향그래프가 있습니다. 위와 같은 그래프를 특별히 functional graph라고 부릅니다. 이 그래프에서 각 노드는 간선을 타고 한 칸씩 움직일 수 있습니다. 이때 만약 1번 노드에서 3칸 전진한 노드를 알고 싶다면, 1 -> 2 -> 4 -> 8 이므로 8번 노드임을 알 수 있습니다. 그렇다면 1번 노드에서 10칸 전진한 노드를 알고 싶다면? 직접 10칸을 움직여보면 알 수 있겠죠. 1 -> 2 -> 4 -> ... -> 7입니다. 1,000,000,000 칸 전진한 노드를 알고 싶다면? 1,000,000,000 번 움직여야하기 때문에 컴퓨터로 작업한다해도 시간이 꽤나 걸리게 될겁니..

세그먼트 트리 세그먼트 트리는 특정 구간의 최대값, 최소값, 합, 곱 등을 빠르고 간단하게 구할 수 있게 해주는 자료구조 입니다. 예를 들어 배열 arr = [1, 3, 2, 5, 7, 3, 5] 에서 3 ~ 7 번째 수 까지의 구간합을 구한다고 가정해봅시다. 가장 단순한 방법으로는 선형적으로 3번부터 8번까지의 수를 더하며 구할 수 있습니다. 하지만 이 방법은 $O(n)$으로 n = 1,000,000,000 처럼 크다면 상당히 부담되는 연산량입니다. 그래서 누적합을 미리 구해 구간합을 구하는 방법도 있습니다. prefixSum = [0, 1, 4, 6, 11, 18, 21, 26] 을 구한 뒤 prefixSum[7] - prefixSum[2]을 계산하여 구간합을 얻을 수 있겠죠. 문제는 배열의 값을 수..

벨만-포드 알고리즘 벨만 포드 알고리즘은 그래프에서 출발점이 주어졌을 때 최단 거리를 계산하기 위한 알고리즘입니다. 그렇다면 다익스트라 알고리즘과는 무슨 차이가 있을까요? 다익스트라 알고리즘을 수행하기 위해서는 그래프의 모든 간선이 음이 아닌 가중치를 가져야 한다는 조건이 지켜져야 합니다. 그에 반면 벨만포드 알고리즘은 그래프 내 음의 가중치를 갖는 간선이 있어도 수행가능한 알고리즘 입니다. 다익스트라 알고리즘에서 음의 가중치를 가진 간선이 존재하면 왜 수행하지 못할까요? 음수 가중치가 있으면 이전까지 계산해둔 최단거리가 최소값이라는 보장을 받을 수 없기 때문입니다. 또한 음수 사이클이 발생하면 최단거리가 무한히 줄어들게 됩니다. 그렇기 때문에 벨만 포드 알고리즘으로 더 많은 연산을 통해 음수 사이클을 ..