유니온 파인드에는 크게 두가지의 최적화 기법이 있는데 하나는 Union by rank라는 방식이고, 나머지는 경로 압축(path compression)라는 방식이다. 상황에 맞게 골라서 최적화 하면 되는데 구현이 쉽기때문에 주로 경로 압축 방식을 주로 사용한다. 다음은 경로 압축(path compression)을 통해 최적화 된 Disjoint set의 코드이다 int find(int num) { if (parent[num] == num) return num; else return parent[num] = find(parent[num]); } void uni(int a, int b) { if (find(a) != find(b)) parent[find(b)] = find(a); } //main 안에: //..

Introduction to Algorithms 은 토머스 H. 코르먼(Thomas H. Cormen), 찰스 E. 레이서슨(Charles E. Leiserson), 로널드 라이베스트(Ronald L. Rivest) 그리고 클리포드 스타인(Clifford Stein) 네 명이 공동으로 저술한 알고리즘 입문 서적이다. 저자들의 성 네 글자를 따서 CLRS라고 부르기도 한다. 내가 구매한 Introduction to Algorithms는 2009년 9월에 출간된 3판의 번역서이다. 번역은 문병로, 심규석 그리고 이충세 교수님이 진행하였고, 한빛아카데미에서 출간하였다. 3판 원서 pdf가 있지만 나의 영어 실력이 부족한 관계로 번역서를 구입하였다. 우선 책을 받고 역자 서문과 저자 서문을 빠르게 읽어 보았다...

벨만 포드 알고리즘(Bellman-Ford algorithm)은 다익스트라 알고리즘과 마찬가지로 하나의 정점에 대한 모든 정점의 최단 거리를 찾는 문제에 적용됩니다. 다익스트라는 음수간선이 존재하면 사용할 수 없지만 벨만 포드 알고리즘은 음수간선이 존재해도 사용할 수 있습니다. 가중치의 합이 0보다 작은 싸이클을 음수 싸이클이라고 하는데, 그래프에 음수 싸이클이 존재하면 벨만 포드 알고리즘을 사용할 수 없습니다. 다음은 벨만 포드 알고리즘이 적용되는 문제입니다. https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의..

다익스트라 알고리즘(Dijkstra Algorithm)은 저명한 컴퓨터 과학자인 에르허츠 다익스트라(Edsger Wybe Dijkstra)가 고안한 간선(Edge)에 가중치가 주어진 그래프에서 정점(Vertex)간의 최단 경로를 찾는 알고리즘입니다. 최단 경로 알고리즘에는 여러 종류가 있지만, 그중에서도 다익스트라 알고리즘은 하나의 정점에 대한 모든 정점의 최단 경로를 찾는데 사용됩니다. 단, 가중치가 음수인 간선이 있으면 사용할 수 없습니다. 처음에 에르허츠 다익스트라가 고안한 다익스트라 알고리즘의 시간복잡도는 정점의 갯수를 $V$, 간선의 갯수를 $E$라고 했을 때, $O(V^2)$였으나, 우선순위 큐(Priority Queue)등을 접목해 그 비용이 $O(E+V log V)$까지 개선되었습니다. 다..