최단 경로 최단 경로 문제(shortest path problem)는 그래프에서 주어진 두 정점을 연결하는 가장 짧은 경로를 찾는 문제로, 그래프 관련 문제 중에서 최단 경로 문제가 많다. 최단 경로 문제를 해결하기 위해서는 그래프가 어떤 그래프인지 파악하고, 그에 맞는 최단 경로 알고리즘을 적용해야한다. 최단 경로 알고리즘은 최단 경로를 구성하는 정점들의 목록을 구해 주는 것이 아닌 최단 경로의 길이를 찾아줄 뿐이라는 점에 유의해야한다. 실제 경로를 계산하기 위해서는 BFS에서 그랬듯이 탐색 과정에서 별도의 정보를 저장하고, 이것으로부터 실제 경로를 찾아내야한다. 가중치가 없는 그래프에서는 BFS로 최단 경로를 구할 수 있다. 여기서의 최단 경로는 경로의 길이가 가장 짧은 경로를 말한다. 가중치가 있는..
신장 트리 (Spanning Tree) n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리, 즉 그래프의 모든 정점을 가장 적은 개수의 간선으로 연결한 그래프 최소 신장 트리 (Minimum Spanning Tree) 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 신장 트리, 최소 신장 트리를 만드는 대표적인 알고리즘에는 Prim 또는 Kruskal 알고리즘이 있다. 보통 최소 신장 트리를 줄여서 MST라고 부른다. Kruskal 알고리즘 1. 최초, 모든 간선을 가중치 순으로 오름차순 정렬 1-1. 간선 리스트를 만든다. 1-2. 만든 간선 리스트를 가중치 순으로 오름차순 정렬한다. 2. 간선을 하나씩 확인해 해당 간선이 사이클을 발생시키는지 확인 (초기..
알고리즘 증명 알고리즘을 설계했다면 알고리즘이 제대로 동작하는지 증명할 필요가 있다. 단위 테스트를 이용해 여러 개의 입력에 대해 프로그램을 실행해 보고 그 답을 점검할 수도 있지만, 이런 식으로는 이 알고리즘이 가능한 모든 입력에 대해 정확하게 동작한다는 사실을 증명할 수 없다. 이번 글에서는 알고리즘 증명을 위해 흔히 사용하는 기법들을 소개한다. 수학적 귀납법과 반복문 불변식 수학적 귀납법은 자연수 n과 관련된 명제 P(n)이 모든 자연수에 대해 성립한다는 것을 증명하는 방법이다. 증명은 아래의 두 단계로 구성된다. P(1)이 성립함을 보인다. P(n)이 성립한다 가정하에 P(n+1) 또한 성립함을 보인다. 수학적 귀납법의 원리는 도미노와 같다. 다음 2가지 사실을 보이면 모든 도미노가 쓰러진다는 걸..
BFS BFS는 시작 정점에서 가까운 정점부터 순서대로 방문하는 그래프 탐색 알고리즘이다. 이러한 탐색 방식으로 시작 정점에서 각 정점들을 최단 경로로 방문한다. 아래는 인접 행렬을 탐색하는 BFS 코드이다. static void BFS(int start, int[][] graph, boolean[] discovered) { Queue queue = new LinkedList(); discovered[start] = true; queue.add(start); while(!queue.isEmpty()) { int v = queue.remove(); for(int i=0; i
DFS 그래프의 모든 정점을 특정한 순서에 따라 방문하는 알고리즘을 그래프의 탐색 알고리즘이라 한다. 대표적인 알고리즘으로 DFS(depth-first search)와 BFS(breadth-first search)가 있다. DFS는 그래프를 더 나아갈 길이 없을 때까지 깊이 들어가 탐색하며 더 나아갈 수 없다면 되돌아가는 방식이다. 즉 현재 정점과 인접한 간선들을 하나씩 검사하다가, 아직 방문하지 않은 정점으로 향하는 간선이 있다면 그 간선을 무조건 따라가고 더 이상 갈 곳이 없는 막힌 정점에 도달하면 마지막에 따라왔던 간선을 따라 뒤로 돌아간다. 아래는 인접 행렬을 탐색하는 DFS 코드이다. static void DFS(int v, int[][] graph, boolean visit[]) { Syste..
분할 정복 문제를 더 이상 나눌 수 없을 때까지 나누고 (분할), 나누어진 부분 문제를 품으로써 (정복) 전체 문제의 답을 얻는 방식의 알고리즘 패러다임. 이진 탐색, 퀵 정렬 등이 대표적인 알고리즘이다. [동작 방식] 분할 : 문제를 더 이상 나눌 수 없을 때까지 2개 이상의 부분 문제로 나눈다. 나눠진 문제들은 서로 독립적이다. 정복 : 부분 문제를 푼다. 결합 : 정복된 답을 취합한다.
Greedy (탐욕적 알고리즘) 그리디는 재귀 호출과 같이 답을 여러 개의 조각으로 쪼개 답을 만들어간다는 점에서 완전 탐색과 DP와 같지만 모든 선택을 고려하지 않고 지금 당장 가장 좋은 선택으로 조각을 만들어간다는 점에서 이들과 다르다. 즉 그리디를 적용하면 문제의 부분 문제는 지금 당장 가장 좋은 선택만을 한다. 이로인해 성능이 뛰어나지만 최적해를 구한다고 보장할 수 없다. 그리디 정당성 증명 아래 두 가지 속성을 증명하면 그리디로 문제의 최적해를 찾아낼 수 있다는 것을 증명할 수 있다. 탐욕적 선택 속성(greedy choice property) : 모든 선택을 고려하지 않고 탐욕적으로 답의 조각을 선택해도 전체 문제의 최적해를 구할 수 있다는 속성이다. 최적 부분 구조 : 부분 문제의 최적해로 ..
