https://www.acmicpc.net/problem/1753 1753번: 최단경로첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가www.acmicpc.net다익스트라 알고리즘을 사용하는 대표적인 문제. 다익스트라 알고리즘이란? BFS와 DP를 활용한 최단경로 탐색 알고리즘이다. 즉, 그래프에서 출발점에서 목표점까지의 최단거리를 구할 때 사용하는 알고리즘이다. 이 과정에서 도착 정점 뿐만 아니라 모든 다른 정점까지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두 찾게 된다. 매번 최단 경로의 정점을 선택해 탐색을..
Algorithm/Theory
최장 증가 부분 수열은 어떤 수열에서 만들 수 있는 부분 수열 중에서 가장 길면서 오름차순을 유지하는 수열이며, LIS라고 한다. 예시로, 수열 A = {10, 20, 10, 30, 20, 50}이 있다고 하면 해당 수열의 LIS는 {10, 20, 30, 50} 풀이 방법1. DP를 활용한 LIS2. 이진탐색을 활용한 LIS* DP는 단순하지만 시간복잡도가 O(n^2)을 가진다.* 이진탐색을 활용하면 시간복잡도를 O(nlogn)을 가진다. 1. DP로 푸는 법 int N = 13; int[] arr = new int[N]; int[] dp = new int[N]; // dp로 풀 경우 for (int i = 0; i arr[j]) { dp[i] = Math.max(dp[i], dp[j] + 1..
DP 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘이다. 먼저 작은 부분 문제들의 해들을 구하고, 이들을 이용하여 보다 큰 크기의 부분 문제들을 해결하여, 최종적으로 원래 주어진 문제를 해결하는 알고리즘 설계 기법이다. 동적 계획법의 방법 자체가 큰 문제의 최적 해를 작은 문제의 최적해들을 이용하여 구하기 때문에 만약 큰 문제의 최적해가 작은 문제들의 최적해들로 구성되지 않는다면 이 문제는 동적 계획법을 적용할 수 없다. 부분 문제들이 연관이 없으면 적용할 수 없다. 최적의 원칙이 적용되지 않는 예) 최장 경로 문제 memorization 메모리제이션은 컴퓨터 프로그램을 실행할 때, 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기술이다. ..
순서가 있는 작업을 차례로 진행해야 할때 순서를 결정해 주기 위해 사용하는 알고리즘. 사이클이 없는 방향 그래프의 모든 노드를 주어진 방향성에 어긋나지 않게 순서를 나열한다. 동작 과정 1. 진입 차수가 0인 모든 노드를 큐에 삽입한다. 2. 큐가 공백 상태가 될때 까지 반복 수행한다. 2-1) 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다. ( 연결된 노드의 진입 차수를 감소시킨다.) 2-2) 새롭게 진입 차수가 0이 된 노드를 큐에 삽입한다. 3. 큐에서 꺼내지는 순서가 위상 정렬을 수행한 결과이다. 위상정렬 - Queue import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public cl..
최단 경로 구하기 하나의 시작 정점에서 끝 정점가지의 최단 경로를 구한다. 다익스트라 알고리즘은 음의 가중치를 허용하지 않는다. 탐욕 기법을 사용한 알고리즘. MST(Minimum spanning tree)의 프림 알고리즘과 유사. 동작 과정 1. 출발 노드를 설정. 2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장. 3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택. 4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신한다. 5. 위 과정에서 3~4번을 반복한다. 다익스트라 - 우선순위 큐 import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.Pri..
크루스칼이 간선을 선택했다면, 프림은 정점을 선택한다. 어떤 정점에서 시작하는지는 상관없다. 동일한 결과. 프림 알고리즘 과정 1. 시작 정점 r의 연결 비용을 0으로, 나머지 정점들의 연결 비용을 무한대로 초기화한다.2. 정점 r을 집합 S의 첫번째 원소로 포함시킨다. 그 후 r에 연결된 나머지 정점들을 살핀다. 그 정점들에 연결된 간선의 비용들을 배열에 저장한다.3. 최소 비용이 드는 정점을 새로 집합 S에 포함시킨다. 그 후 새로 포함된 정점에 연결된 다른 정점들의 비용도 업데이트 한다.4. 모든 정점이 S에 포함될 때까지 3을 반복한다 * 슈도 코드 MST_PRIM(G,r) // G: 그래프, r : 시작 정점 For u in G.V u.key 우선순위 큐를 이용한 프림 알고리즘..
신장 트리 : 그래프의 모든 정점과 간선의 부분 집합으로 구성되는 트리. 신장 트리는 여러가지. 최소 신장 트리 : 신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 트리. 최소 신장 트리도 여러가지 나올 수 있다. 특징 : 무방향 가중치 그래프, 사이클을 포함해서는 안된다. N개의 정점을 가지는 그래프에 대해 반드시 (N-1)개의 간선을 사용해야 한다. 크루스칼 알고리즘 간선을 하나씩 선택해서 최소 신장 트리를 찾는 알고리즘 1. 모든 간선을 가중치에 따라 오름차순 정렬 2. 가중치가 낮은 간선부터 선택하면서 트리를 증가시킨다. - 사이클이 존재하면 다음으로 가중치가 낮은 간선을 선택한다. 3. n-1개의 간선이 선택될때까지 2를 반복. * 슈도 코드 MST-KRUSKAL(G,w) A
상호 배타 집합에 대한 연산 // makeset(x) : 유일한 멤버 x를 포함하는 새로운 집합을 생성하는 연산static void makeset(int i){ p[i] = i;}// findset(x) : x를 포함하는 집합을 찾는 연산static void findset(x){ if(x==p[x]) return x; return findset(p[x]);}// union(x,y) : x와 y를 포함하는 두 집합을 통합하는 연산static void union(x,y) { p[findset(y)] = findset(x);}문제점 : 편향 트리의 경우 대표 원소를 탐색하는데 시간이 오래 걸린다. 이를 해결하기 위해 rank와 path compression을 사용한다. 1. rank를 이용한 union..
BFS 알고리즘으로 트리 탐색 트리 : 사이클이 없는 부모와 자식관계가 있는 1: N의 관계 1. Queue 사용하기 * 슈도 코드 BFS(v){ Queue 생성; Queue.add(v); while(!Queue.isEmpty(){ curr = Queue.deq(); // 데이터를 뺀다. curr 방문 For w (curr의 모든자식) Queue.add(w) } } BFS 알고리즘으로 그래프 탐색 트리처럼 하면 stackoverflow 발생 => 방문했는지 안했는지를 check하는 것이 필요하다. 미리 방문처리를 해야한다. Queue에서 꺼내졌을때 방문처리를 하면 중복된 값이 들어가서 메모리 낭비가 발생한다. 최단거리를 구할때 BFS를 많이 쓴다. import java.util.LinkedList; im..
