플로이드-워셜(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차원 배열이 있고, 이 배열에서 서로 다른 두 개의 포인터를 이용해 원소에 접근하며 원하는 것을 얻는다. 예시크기가 N인 1차원 배열 arr가 있다. 이 때 arr의 부분 배열 중 그 원소의 합이 M이 되는 경우의 수가 몇 개 인지를 구해보자.이를 완전 탐색으로 모든 경우의 수를 전부 테스트하는 것은,  $O(N^2)$의 시간복잡도를 가진다.이를 투포인터 알고리즘으로 풀기 위해서1. 포인터 s(start)와 포인터 e(end)..

인접리스트로 구현된 그래프에서의 구현 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을 제외한 모든 인덱스에서 자신 이전..

Big O : OBig O describes an upper bound on the time.학문적으로, Big O는 시간의 상한선을 의미한다.사람은 모두 최대 100살까지 산다고 가정하고, 이 때 사람의 나이를 x라고 하자.이 때 x따라서 사람의 나이를 Big O로는 O(N), O(N^2), O(N^3) 모두로 나타낼 수 있다.이를 다시 알고리즘 관점으로 가져오면 실제 런타임 속도는 Big O로 표현한 속도보다 작거나 같다는 것을 의미한다. Big Omega : ΩBig omega is the equivalent concept but for lower bound.학문적으로, Big Omega는 시간의 하한선을 의미한다.다시 사람의 나이 비유를 빌려오자면, Big omega로는 Ω(N..