최단 경로 알고리즘그래프 상황에서 vertex 간의 최단 경로를 구하는 알고리즘이다.   문제는 위와 같이 아예 그래프로 문제 상황이 주어지거나, 혹은 위와 같이 '경로'로서 문제 상황이 주어진다. 문제를 graph, vertex, edge로 표현하여 풀면 된다. 단일 출발 최단 경로특정 하나의 노드에서 다른 모든 노드까지의 최단 경로를 구하는 문제이다.  1. 다익스트라 알고리즘음수 가중치 미포함 경우에만 사용 가능하다.방문하지 않은 정점 중, 거리가 최소인(cost가 낮은) 정점을 방문한다. 정점을 방문 처리하고, 최단 거리를 확정한다.현재 처리 중인 (최단 거리가 확정된) 노드를 거쳐서 다른 노드로 가는 비용을 계산하고 갱신한다. 특징거리가 최소인 정점을 찾는 과정에서 Heap 혹은 Priority..

플로이드-워셜(Floyd-Warchall) 알고리즘가중 그래프에서 모든 노드 쌍들에 대한 최단 경로를 구할 때 사용하는 알고리즘이다.가중치가 음/양수일 때 모두 사용 가능하다. 알고리즘 동작모든 vertex쌍 간의 최단 경로를 갱신하여야 하므로 인접 행렬을 사용한다.정점 A에서 B로 가는 경로에서 거칠 수 있는 모든 노드(K)을 확인하여 해당 노드(K)를 경유할 경우 경로 길이가 더 짧아진다면 그 값을 테이블에 갱신한다. (D[i,j] = min( D[i,j] , D[i,k]+D[k,j])3중 for문을 사용한다. (D[i,k]와 D[k,j] 에서 공통인 중간점 k를 가장 바깥 for문으로 둔다.)만일 dist[i][i] 음수 사이클이 존재한다는 의미로, 최단 거리 테이블을 확정할 수 없다.구현 방법인..

벨만-포드(Bellman-Ford) 알고리즘가중그래프에서 특정 하나의 노드에서 다른 모든 노드로의 최단 거리 정보를 알아내는 알고리즘이다. (단일 출발)모든 경우의 수를 고려하기 때문에, 다익스트라 알고리즘보다 시간복잡도가 높다.그렇지만 다익스트라 알고리즘과 달리 노드 간의 간선 가중치가 음수인 경우에도 사용할 수 있다. 알고리즘 동작 방식매 단계(cycle)마다 모든 노드(vertex)를 방문한다.하나의 노드를 방문할 때마다 이 노드와 인접한 다른 노드들을 확인하여, 최단 거리 테이블을 갱신한다. 단계는 최단 거리 테이블이 더이상 업데이트되지 않을 때까지, 최대 V-1번 반복된다. (V: vertex, 노드의 수)만일 V-1번의 단계를 거친 이후에도 최단 거리 테이블이 업데이트 된다면, 이는 음수 사이..

다익스트라(Dijkstra) 알고리즘가중그래프에서 특정 하나의 노드에서 다른 모든 노드로의 최단 거리 정보를 알아내는 알고리즘이다.음수 가중치를 갖는 간선을 포함한 그래프에서는 올바르게 동작하지 않는다. (음수 가중치가 있을 경우 최단 경로가 계속 갱신될 수 있기 때문에)구현 특징문제를 그래프로 표현하여 각 정점 연결 상황을 저장한다.정점 간 최단 거리 정보(distance)를 1차원 리스트에 저장하며 리스트를 계속해서 갱신한다.매 단계마다 아직 방문하지 않은 정점 중 최단 거리인 정점을 찾아 방문하여 최단거리를 확정하고, 이를 반복하는 방식이다.방문하지 않은 정점 중에서 최단 거리가 최소인 정점을 찾는 과정에서 Heap, Priority Queue를 이용한다.구현 방법출발 노드(s) 설정최단 거리 테이..

투포인터 알고리즘의 정의투포인터 알고리즘(Two Pointers Algorithm) 혹은 슬라이딩 윈도우(Sliding Window)라 부른다.알고리즘 문제 중 완전 탐색으로 풀면 시간초과가 나는 문제일 때, 투포인터 알고리즘을 떠올려 보아야 한다.투포인터 알고리즘에는 1차원 배열이 있고, 이 배열에서 서로 다른 두 개의 포인터를 이용해 원소에 접근하며 원하는 것을 얻는다. 원래 이중 for문으로 $O(N^2)$에 처리되는 작업을 2개의 포인터를 이용하여 $O(N)$에 해결하는 알고리즘이다.예시크기가 N인 1차원 배열 arr가 있다. 이 때 arr의 부분 배열 중 그 원소의 합이 M이 되는 경우의 수가 몇 개 인지를 구해보자.이를 완전 탐색으로 모든 경우의 수를 전부 테스트하는 것은,  $O(N^2)$의..

인접리스트로 구현된 그래프에서의 구현 package graph; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; public class ListGraph implements Graph{ int size; boolean directed; LinkedList[] adj; LinkedList[] inv; public ListGraph(int size, boolean directed) { this.size = size; // vertex의 수 this.directed = directed; // true: 방향성 그래프, false: 무방향성 그래프 adj = new ..

누적합 알고리즘의 정의 누적합 알고리즘은 말 그대로 어떠한 구간의 누적된 합을 구하는 알고리즘이다. 수열 \(A_n\)에 대하여 특정 인덱스 a에서 b까지의 구간 합을 구하는 알고리즘이라고도 볼 수 있다. 예시 [ 1,2,3,4,5 ] 로 이루어진 크기가 5인 배열 arr가 있다. 이 때 arr[1] 부터 arr[3]의 구간 합을 구해보자. (방법 1) 가장 쉬운 방법으로, 2부터 4까지 인덱스를 하나씩 증가시키며 배열을 방문하여 요소들을 더한다. 1 1+2 1+2+3 = 6 만일 배열의 처음부터 해당 인덱스까지의 합을 나타내는 배열 [ 1,2,6,10,15 ]을 구하려고 하면 어떨까? 1 1+2 1+2+3 1+2+3+4 1+2+3+4+5 위를 보면 알 수 있듯이, 0을 제외한 모든 인덱스에서 자신 이전..