S E P H ' S

연쇄행렬 최소곱셈 알고리즘 (Matrix Chain Multiplication) 주어진 행렬들의 곱을 최소의 연산으로 수행하는 최소횟수를 구하는 알고리즘이다. 행렬의 곱셈에서 결합법칙은 성립하나 순서에 따라서 계산 횟수가 달라질 수 있다. 아래와 같은 행렬로 확인해보도록 하자. 그림을 확인해보면 순서에 따라 전체 연산횟수가 달라짐을 알 수 있다. 위와 같이 행렬의 개수가 5개일때 모든 결합의 마지막 결합 형태는 다음과 같이 네 가지로 분류가 가능하다. (행렬의 개수가 n 이면 n - 1 가지로 분류가 가능하다.) (AB)(C(DE)) 는 결국 (AB)(CDE) 와 같고 (A(B(CD)))E 는 결국 (ABCD)E 와 같다. 다시 말하자면 행렬의 개수가 n 이면 최소 연산 횟수는 n - 1 가지 경우 중의..

MST(Minimum Spanning Tree) 최소 신장 트리 그래프의 모든 정점을 사이클 없이 잇는 (신장 트리) 트리에서 간선의 가중치의 합이 최소가 되는 트리를 말한다. 크루스칼 알고리즘 간선 중심으로 최소 신장 트리를 구하는 알고리즘. 간선이 적을때 프림 알고리즘보다 유리하다. 내부적으로 union-find 알고리즘을 사용 간선들을 가중치의 오름차순 정렬하여 가장 작은 간선을 선택한다. 그 간선이 지금까지 만들어진 MST와 싸이클을 형성한다면 제외하고 아니라면 MST에 추가한다. 모든 간선에 대해 반복한다. 프림 알고리즘 정점 중심으로 최소 신장 트리를 구하는 알고리즘 정점이 적을때 크루스칼 알고리즘보다 유리 임의의 정점 선택 그 정점과 인접한 정점을 잇는 간선 중 가중치가 가장 낮은 간선 선택..

최소 공통 조상 LCA(Lowest Common Ancestor) 알고리즘 LCA(Lowest Common Ancestor)는 주어진 두 노드 a, b의 최소 공통 조상을 찾는 알고리즘이다. 예를 들어 아래의 트리에서 5번과 6번의 최소 공통 조상 LCA는 2번 노드이다. 일반적인 LCA 풀이방법 1번 루트노드를 기준으로 DFS 탐색을 하면서 각 노드의 트리의 높이(h)와 부모 노드(parent)를 저장한다. LCA 를 구하기 위한 a, b 노드가 주어지면 해당 두 노드의 h를 일정하게 맞춘다. (a의 높이 == b의 높이) 높이가 맞춰졌으면 각 부모 노드가 일치할 때 까지 비교하여 구한다. (최대 LCA는 루트노드 1) LCA를 찾는 과정을 보면 탐색을 할 때 편향트리를 만나게 되면 엄청 많은 반복을 ..

다익스트라 알고리즘 (Using Priority Queue) 다익스트라 알고리즘의 기본 구성은 지난 포스트에서 다뤘다. 다익스트라는 한 노드에서 다른 노드들까지 가는 모든 최소 비용을 구하는 알고리즘이었다. 여기서 두 가지 과정을 반복적으로 수행하면서 목적을 달성하게 된다. 방문하지 않은 노드들 중에 가장 비용이 적은 노드를 다음 노드로 삼는다. (그리디 알고리즘) 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신한다. (다이나믹 프로그래밍) 여기서 방문하지 않은 노드들 중에 가장 비용이 적은 노드를 찾기 위해 최악의 경우 모든 노드를 살펴봐야 할 수도 있다는 점이 최적화할 수 있는 부분이었다. 이를 개선하기 위한 방법 중 우선순위 큐를 활용한 다익스트라를 구현해보려고 한다. 다익스트라 알고리즘 구현 (..