본 포스트는 JAVA 를 기준으로 작성되었습니다 😊
1. 다익스트라, 플로이드워셜
다익스트라, 플로이드 워셜 그 차이에 대하여 !!
우선 다익스트라는 한 지점에서 다른 지점으로 가는 최단 거리를 구한다 !
즉, 모든 지점을 확인하려면 지점마다 돌려서 확인을 해야된다 !
정점의 수를 V, 간선의 수를 E 라 했을 때, 위의 경우 시간복잡도는 (우선순위 큐를 사용했다는 전제하에 ) O(VE logV) 가 될 것이다!
근데 만약, 간선이 굉장히 많은 경우라면 ..? E = V^2 이라면 ? O(V^3 logV) 가 된다 (비효율적..🤔)
이 때 플로이드 워셜은 모든 쌍에 대한 최단 거리를 구해준다
이 알고리즘은 매우 쉬운 3중 반복문인데 O(V^3)으로 비효율적으로 보일 수 있다..! 하지만!
앞서 언급한 다익스트라을 사용하기 안좋은 경우엔,
정점의 수가 많지 않거나, 모든 쌍에 대한 최단 거리를 구해야만 할 때엔 플로이드 워셜을 사용하는 것이 좋다 😁
1. 다익스트라
특정 시작점에서 다른 모든 정점으로 가는 최단거리를 구해줘 !
무조건 우선순위 큐를 사용하자
우선 시작점을 정하고, 그 시작점으로부터의 거리를 구할 dist 배열을 만든다!
시작점(dist = 0)을 제외한 나머지 정점의 dist 를 INF 로 설정한다
우선순위 큐는 이 거리값을 넣어 연결된 값중에 가장 최소거리인 다음 정점을 찾아주는 역할을 한다
코드를 보면 이해가 될 것이다
주석을 보며 읽어보자
public class DijkstraTest {
public static class Node{
int x, dist;
public Node(int x, int dist) {
this.x = x;
this.dist = dist;
}
}
public static int N = 5; // 정점 수
public static ArrayList<Node>[] graph = new ArrayList[N + 1]; //정점 번호를 그대로 사용할 경우
public static PriorityQueue<Node> pq = new PriorityQueue<>();
public static int[] dist = new int[N + 1];
public static void main(String[] args) {
// 정점의 수 : 5, 간선의 수 : 8인 그래프
int n = 5, m = 8;
// 그래프를 인접리스트로 표현합니다.
for(int i = 1; i <= n; i++)
graph[i] = new ArrayList<>();
for(int i = 1; i <= m; i++) {
int x = 입력.시작점;
int y = 입력.도착점;
int z = 입력.가중치;
graph[x].add(new Node(y, z));
}
// 초기값 설정
// INT_MAX 그 자체로 설정하면 덧셈 진행시 overflow가 발생할 수 있음에 유의!!!!
for(int i = 1; i <= n; i++)
dist[i] = (int)1e9;
// 시작위치 dist값 = 0
dist[5] = 0;
pq.add(new Node(5, 0));
while(!pq.isEmpty()) {
// 가장 거리가 가까운 정보 poll
Node now = pq.poll();
int nowIndex = now.x;
int nowDist = now.dist;
// 우선순위 큐를 이용하면 같은 정점의 원소가 여러 번 들어가는 문제가 발생할 수 있어
// nowDist가 최신 dist[nowIndex] 보다 크면 어짜피 최소값이 아니므로 pass
if(nowDist > dist[nowIndex])
continue;
for(int j = 0; j < graph[nowIndex].size(); j++) {
//연결된 정점 체크 -> 시작점으로부터의 최단거리 값을 갱신
int nextIndex = graph[nowIndex].get(j).index;
int nextDist = graph[nowIndex].get(j).dist;
// 현재 위치에서 연결된 간선으로 가는 것이 더 작다면
int newDist = dist[nowIndex] + nextDist;
if(dist[nextIndex] > newDist) {
// 값을 갱신해주고, 우선순위 큐에 add
dist[nextIndex] = newDist;
pq.add(new Node(nextIndex, newDist));
}
}
}
// 시작점으로부터 각 지점까지의 최단거리 값
for(int i = 1; i <= n; i++)
System.out.print(dist[i] + " ");
}
}
2. 플로이드 워셜
모든 쌍에 대해 최단거리를 구해줘 !
A -> B 로 가는 경로보다 A -> X -> B 로 가는 경로가 더 짧다면 그걸로 갱신!
다익스트라 때 처럼 dist 배열은 전부 최댓값 INF 로 채워준다 ( 물론 자기 자신 -> 자기 자신은 0 으로 )
그 다음 과정은 경유해서 가는 경우와, 바로 가는 경우 중 작은 값을 dist 에 갱신해주는 것인데
너무 간단한 알고리즘이라 이 부분만 코드를 작성해보자면,
for(int k = 1; k <= n; k++){ // 경유지 k (1부터 N)
for(int i = 1; i <= n; i++){ // 모든 쌍 (i, j)
for(int j = 1; j <= n; j++){
// i에서 j로 가는 거리가 k를 경유해 가는 것이 더 좋다면,
// dist[i][j]값을 갱신
dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
//결과
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(dist[i][j] == (int)1e9) // 이동이 불가능 한 경우
System.out.print(-1 + " ");
else
System.out.print(dist[i][j] + " ");
}
System.out.println();
}
2. Kruskal, Prim
다익스트라, 플로이드 워셜 그 차이에 대하여 !!
간적쿠 간만프 🙋♀️
1. 크루스칼
가중치가 작은 간선부터 고른다!
근데 이제, 가중치가 같은 경우엔 아무거나 선택..
근데 이제, 사이클이 발생하면 안되는..
(MST 를 만족해야하니까!)
그럼 사이클은 어떻게 안 발생하게 하는가 ?!
🙋♀️ Union - Find
두 노드를 union 연산을 수행해야하는데, 만약 두 노드가 이미 같은 union 에 속한 상태이면 합치지 않고 넘어간다!
정리하자면,
간선의 가중치가 작은 것부터 순서대로 보면서, 두 노드의 부모값을 비교하여 일치하지 않은 경우에만 (사이클이 발생하지 않았다는 말) 간선을 선택해주고 union 연산을 진행한다!
크루스칼 알고리즘은 정렬한번이면 구현이 가능하다.
간선의 수가 E 일때 정렬에 O(ElogE), 각 간선에 대해 union-find 는 O(logN)이므로 ElogE + ElogN 이 되어
총 시간복잡도는 O(ElogE) 이다
우선, Union-Find 부분 코드는 아래와 같다
private static void union(int a, int b) {
a = find(a);
b = find(b);
if (a > b) {
parent[a] = b;
} else {
parent[b] = a;
}
}
private static int find(int x) {
if (parent[x] == x)
return x;
else
return find(parent[x]);
}
}
아래는 크루스칼 알고리즘을 진행하는 코드이다.
parent = new int[V];
final_cost = 0;
// 간선 비용 순으로 오름차순 정렬
Arrays.sort(graph, (o1, o2) -> Integer.compare(o1[2], o2[2]));
// makeSet
for (int i = 0; i < V; i++) {
parent[i] = i;
}
// 낮은 비용부터 크루스칼 알고리즘 진행
for (int i = 0; i < E; i++) {
// 사이클이 존재하지 않는 경우에만 간선을 선택한다(여기서는 최종 비용만 고려하도록 하겠다).
if (find(graph[i][0] - 1) != find(graph[i][1] - 1)) {
//부모가 다른 경우에만
System.out.println("<선택된 간선>");
System.out.println(Arrays.toString(graph[i]));
union(graph[i][0] - 1, graph[i][1] - 1);
final_cost += graph[i][2];
System.out.println("<각 노드가 가리키고 있는 부모>");
System.out.println(Arrays.toString(parent) + "\n");
continue;
}
}
System.out.println("최종 비용 : " + final_cost);
2. 프림
그래프상에 존재하는 모든 노드들을 최소비용으로 연결시키는 알고리즘,
프림 알고리즘은 한 지점에서 시작한다!
아무 정점이나 같은 결과가 나오기때문에, 시작하기 편한 정점에서 시작하면 된다
이 정점에서 연결된 간선들 중 가중치가 가장 작은 간선을 고르고, 이 간선이 MST 에 들어가게 된다그 후엔, MST 에 있는 노드들과 연결된 모든 Edge 들을 확인하고, 그 중에서
가중치가 가장 작은 간선을 골라 MST 에 붙여준다
프림알고리즘도 우선순위 큐를 사용하는데, 다익스트라 코드와 정확히 2줄만 다르고 나머지는 전부 동일하다.
하지만 다른 부분에 주의해야하는데!
다익스트라 알고리즘의 경우, 현재 노드를 n라 했을 때 dist[v]와 dist[n] + length(n, v)를 비교하여 갱신해주는 것이였다면,
prim은 단순히 dist[v]와 length(n, v)를 비교하여 갱신해준다. 즉,
dist 배열을 사용하는데, 프림알고리즘에서의 dist 배열은
현재까지 만들어진 MST 와 노드 x를 연결하기 위해 필요한 최소 비용이다
class Edge implements Comparable<Edge>{
int w;
int cost;
Edge(int w, int cost){
this.w = w;
this.cost = cost;
}
// 간선 오름차순으로 정렬
@Override
public int compareTo(Edge o) {
return this.cost - o.cost;
}
}
// 프림 알고리즘
public static void prim(int start, int n) {
boolean[] visit = new boolean[n + 1];
PriorityQueue<Edge> pq = new PriorityQueue<>();
pq.offer(new Edge(start, 0));
int total = 0;
while(!pq.isEmpty()) {
Edge edge = pq.poll();
if(visit[edge.w]) continue;
visit[edge.w] = true;
ans += edge.cost;
for(Edge next : graph[v]) {
if(!visit[next.w]) {
pq.add(next);
}
}
}
// 완성된 최소 신장 트리의 총 가중치 합 출력
System.out.println(ans);
}
프림은 다익스트라와 달리 두 노드 사이의 거리가 최단 거리가 아닐 수도 있다!
프림과 다익스트라는 서로를 보장해주지 않는다!
3. 순열, 완탐, 조합
각각의 특징에 대해서는 다 아니까 패스
3 미만이면 그냥 for 문 돌리기~
1. 순열
1. 그냥 순열
- 중복허용을 안하니까 visit 처리해야 함
public class PermTest {
static int[] p = {1,2,3,4,5};
static int N = p.length;
static int R;
static int count;
static int [] nums;
static boolean [] visited;
static List<int[]> ans = new ArrayList<>();
public static void main(String[] args) {
R = 3;
nums = new int [R];
visited = new boolean[N];
count = 0;
perm(0);
System.out.println(count);
for (int[] i : ans) {
System.out.println(Arrays.toString(i));
}
}
private static void perm(int cnt) {
//끝나는 조건 명시
if (cnt == R) {
count ++;
ans.add(nums.clone());
return;
}
//그렇지않으면
for (int i = 0; i < N; i++) {
if (visited[i]) {
continue;
}
nums[cnt] = p[i];
visited[i] = true;
perm(cnt+1);
visited[i] = false;
}
}
}
2. 중복 순열
public class PermTest2 {
static int[] p = {1,2,3,4,5};
static int N = p.length;
static int R;
static int count;
static int [] nums;
static boolean [] visited;
static List<int[]> ans = new ArrayList<>();
public static void main(String[] args) {
R = 3;
nums = new int [R];
visited = new boolean[N];
count = 0;
piperm(0);
System.out.println(count);
for (int[] i : ans) {
System.out.println(Arrays.toString(i));
}
}
private static void piperm(int cnt) {
//끝나는 조건 명시
if (cnt == R) {
count ++;
ans.add(nums.clone());
return;
}
//그렇지않으면
for (int i = 0; i < N; i++) {
nums[cnt] = p[i];
piperm(cnt+1);
}
}
}
2. 조합
1. 그냥 조합
- 반복문의 시작 인덱스는 start !
public class CombiTest {
static int[] p = {1,2,3,4,5};
static int N = p.length;
static int R;
static int count;
static int [] nums;
static boolean [] visited;
static List<int[]> ans = new ArrayList<>();
public static void main(String[] args) {
R = 3;
nums = new int [R];
count = 0;
combi(0, 0);
System.out.println(count);
for (int[] i : ans) {
System.out.println(Arrays.toString(i));
}
}
private static void combi(int cnt, int start) {
//끝나는 조건 명시
if (cnt == R) {
count ++;
ans.add(nums.clone());
return;
}
//그렇지않으면
for (int i = start; i < N; i++) {
//start 부터 시작함에 주의!!
nums[cnt] = p[i];
combi(cnt+1, i+1);
}
}
}
2. 중복 조합
- 반복문의 시작 인덱스는 0 !!
public class CombiTest2 {
static int[] p = {1,2,3,4,5};
static int N = p.length;
static int R;
static int count;
static int [] nums;
static boolean [] visited;
static List<int[]> ans = new ArrayList<>();
public static void main(String[] args) {
R = 3;
nums = new int [R];
count = 0;
combi(0, 0);
System.out.println(count);
for (int[] i : ans) {
System.out.println(Arrays.toString(i));
}
}
private static void combi(int cnt, int start) {
//끝나는 조건 명시
if (cnt == R) {
count ++;
ans.add(nums.clone());
return;
}
//그렇지않으면
for (int i = start; i < N; i++) {
nums[cnt] = p[i];
combi(cnt+1, i);
}
}
}
3. Subset (PowerSet)
static int[] p = {1,2,3,4,5};
static int N = p.length;
static int count;
static boolean [] visited;
static List<List<Integer>> ans = new ArrayList<>();
public static void main(String[] args) {
visited = new boolean[N];
count = 0;
powerset(0, 0, 1);
System.out.println(count);
for (List<Integer> i : ans) {
System.out.println(Arrays.toString(i.toArray()));
}
}
private static void powerset(int cnt, int sum, int mul) {
//if (sum <= 0) return; //필요에 따라 걸러주기 더 진행 가능
//끝나는 조건 명시
if (cnt == N) {
count ++;
List<Integer> temp = new ArrayList<>();
for (int i = 0; i < N; i++) {
if(visited[i]) {
temp.add(p[i]);
}
}
ans.add(temp);
System.out.println("--->"+sum);
System.out.println("--->"+mul);
return;
}
//그렇지않으면
visited[cnt] = true;
powerset(cnt+1, sum + p[cnt], mul*p[cnt]);
visited[cnt] = false;
powerset(cnt+1, sum, mul);
}
}
4. Next Permutation & Next Combination
- 1. 꼭대기를 찾아라 !
A[i-1] < A[i] 를 만족하는 가장 큰 i 를 찾는다 -> 꼭대기 찾기
- 2. 꼭대기 위치의 i-1 번째가 오른쪽 제일 끝에의 j 인덱스 p[j] 보다 작으면 swap
j >= i 이면서 A[j] > A[i-1] 을 만족하는 가장 큰 j 를 찾는다
A[i-1]과 A[j] 를 swap
A[i]부터 순열을 뒤집는다
public class NextPermTest {
static int[] p = {3,1,2,6,4,5};
static int count ;
static int N = p.length;
public static void main(String[] args) {
do {
count ++;
System.out.println(Arrays.toString(p));
}while (np(N-1));
System.out.println(count);
}
private static boolean np(int size) {
int i = size;
while(i>0 && p[i-1] > p[i]) i--;
//A[i-1] < A[i] 를 만족하는 가장 큰 i
if (i == 0) return false;
//i가 0까지 갔다면 모두 내림차순이었으므로 마지막 순열
int j = size;
// j >= i 이면서 A[j] >= A[i-1]을 만족하는 가장 큰 j를 찾음
while(p[i-1] > p[j]) j--;
//A[i-1]과 A[j] 를 swap
int temp = p[i-1];
p[i-1] = p[j];
p[j] = temp;
//A[i]부터 순열을 뒤집음
int k = size;
while(i < k) {
temp = p[i];
p[i] = p[k];
p[k] = temp;
i++;
k--;
}
return true;
}
}
그럼 조합은..? 부등호에서 같음 체크만 추가 하면됨!
public class NextCombiTest {
static int[] p = {0,0,0,1,1,1};
static int[] n = {1,2,3,4,5,6};
static int count ;
static int N = p.length;
public static void main(String[] args) {
do {
count ++;
for (int i = 0; i < N;i++) {
if (p[i] == 1) {
System.out.print(n[i] + " ");
}
}
System.out.println();
System.out.println(Arrays.toString(p));
}while (np(N-1));
System.out.println(count);
}
private static boolean np(int size) {
int i = size;
while(i>0 && p[i-1] >= p[i]) i--;
//A[i-1] < A[i] 를 만족하는 가장 큰 i
if (i == 0) return false;
//i가 0까지 갔다면 모두 내림차순이었으므로 마지막 순열
int j = size;
// j >= i 이면서 A[j] >= A[i-1]을 만족하는 가장 큰 j를 찾음
while(p[i-1] >= p[j]) j--;
//A[i-1]과 A[j] 를 swap
int temp = p[i-1];
p[i-1] = p[j];
p[j] = temp;
//A[i]부터 순열을 뒤집음
int k = size;
while(i < k) {
temp = p[i];
p[i] = p[k];
p[k] = temp;
i++;
k--;
}
return true;
}
}
4. KMP (부분문자열)
: KMP 는 문자열이 다른 문자열의 부분문자열로 나타나는지 판단하는데 사용된다. 우리가 흔히 아는 for 문을 통한 완전 탐색을 하면 시간복잡도가 매우 커질수 있는데, 이 알고리즘을 사용할 경우 O(N+M) 에 구현이 가능하다
KMP 알고리즘은 우선 패턴배열, text 배열 으로 나누어 사용해야한다text 배열은 말그대로, 전체 문자열을 toCharArray()를 통해 넣어둔다.먼저, 부분일치테이블을 만들어야하는데 이것이 패턴배열이다.패턴배열은
문자열 P에서 [1, i]로 이루어진 문자열 중 접두사와 접미사가 일치하는 최장 길이를 뜻한다.
아래 코드를 살펴보자, i 는 접미사 포인터이다.
int pl = pattern.length;
pi = new int[pl];
for(int i = 1, j = 0; i < pl; i++){
//[1 , i-1] 까지는 정확히 길이 j 만큼 접두사와 접미사가 일치할때
while(j > 0 && pattern[j] != pattern[i]){
j = pi[j-1];
}
if (pattern[j] == pattern[i]){
//일치하지 않는다면 j 값을 이동한다
pi[i] = ++j;
}
else{
pi[i] = 0;
}
}
이렇게 부분일치테이블을 완성하면, 찾으려는 문자열을 쉽게 검색할 수 있는 바탕이 완성된 것이다
이제 남은 일은 패턴 테이블과 찾으려는 문자열을 비교하여 부분문자열인지 확인하는 방법이다.
for(int i = 0, j = 0; i < tl; i++){
//i : 텍스트 포인터, j : 패턴포인터
while(j > 0 && pattern[j] != text[i]){
j = pi[j-1];
}
if (pattern[j] == text[i]){ //두 글자가 일치한다면
if (j == pl - 1){ //j 가 패턴의 마지막 인덱스라면
idx.add(i - j + 1);
ans ++;
j = pi[j];
}
else{
j++;
}
}
}
설명으로는 이해가 어려울 수 있어 예제 백준문제 하나 풀어보는 것을 추천한다 👍
https://www.acmicpc.net/problem/1786
1786번: 찾기
첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i~i+m-1번 문자와 P의 1~m
www.acmicpc.net
'Algorithm' 카테고리의 다른 글
신기한 누적합 이야기 (feat. 2022 kakao 파괴되지 않은 건물) (2) | 2023.04.13 |
---|
댓글