공부 기록

문제의 크기가 클 경우에는 문제를 절반으로 나누어서 문제를 푼 후 두 개를 합치는 방식을 이용한다.

배열의 크기가 N인 집합이 있을 때 부분집합의 합이 M이 나오는 갯수를 찾는 문제이다.

이 문제의 경우는 N<=40이고 모든 부분 집합을 만들면 2^40가지가 나오므로 모든 경우의 수를 파악할 수 없다.

따라서 문제의 크기를 절반으로 나누어서 한쪽 절반과 다른쪽 절반에서 각각 푼 다음에 문제를 합쳐서 풀도록 한다.

먼저 절반에서 구한 모든 값들을 list에 넣고 left list의 값과 right list의 값의 합이 s인 가짓수를 찾는다.

부분집합의 크기는 양수이므로 둘 다 0인 경우는 마지막에 빼준다.

import java.util.*;
import java.io.*;

public class Main {
	public static long ans = 0;
	public static int arr[];
	public static int n, s;
	public static ArrayList<Integer> left, right;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		s = in.nextInt();
		arr = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = in.nextInt();
		}
		left = new ArrayList<Integer>();
		right = new ArrayList<Integer>();

		findAllSums(0, 0, n / 2, left);
		findAllSums(0, n / 2, n, right);

		Collections.sort(left);
		Collections.sort(right);
		int leftIndex = 0;
		int rightIndex = right.size() - 1;
		while (leftIndex < left.size() && rightIndex >= 0) {
			int leftSum = left.get(leftIndex);
			int rightSum = right.get(rightIndex);

			if (leftSum + rightSum == s) {
				long leftSame = 0;
				while (leftIndex < left.size() && left.get(leftIndex) == leftSum) {
					leftIndex++;
					leftSame++;
				}
				long rightSame = 0;
				while (rightIndex >= 0 && right.get(rightIndex) == rightSum) {
					rightIndex--;
					rightSame++;
				}
				ans += leftSame * rightSame;
			} else if (leftSum + rightSum < s) {
				// 찾으려고 하는 수는 더 크기 때문에 left를 오른쪽으로 한 칸 움직여준다.
				leftIndex++;
			} else {
				// 마찬가지로 rightIndex 한칸 왼쪽으로 움직여준다.
				rightIndex--;
			}
		}

		if (s == 0) {
			ans -= 1;
		}

		System.out.println(ans);
	}

	public static void findAllSums(int sum, int index, int end, ArrayList<Integer> list) {
		if (index == end) {
			list.add(sum);
			return;
		}

		findAllSums(sum + arr[index], index + 1, end, list);
		findAllSums(sum, index + 1, end, list);
	}
}

그래프에서 사이클의 길이 중 최소 길이를 찾는 문제이다.

d[i][i]를 무한대로 초기화해 준 뒤 플로이드 알고리즘을 적용하면 i->i로 가는 어떠한 경로 중 최소 길이를 얻을 수 있다.

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();
		int mat[][] = new int[n + 1][n + 1];

		for (int i = 1; i <= n; i++) {
			Arrays.fill(mat[i], Integer.MAX_VALUE);
		}
		for (int i = 0; i < m; i++) {
			int start = in.nextInt();
			int end = in.nextInt();
			int cost = in.nextInt();
			mat[start][end] = Math.min(mat[start][end], cost);
		}

		for (int k = 1; k <= n; k++) {
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					if (mat[i][k] != Integer.MAX_VALUE && mat[k][j] != Integer.MAX_VALUE) {
						mat[i][j] = Math.min(mat[i][j], mat[i][k] + mat[k][j]);
					}
				}
			}
		}

		int min = mat[1][1];
		for (int i = 2; i <= n; i++) {
			min = Math.min(min, mat[i][i]);
		}

		if (min == Integer.MAX_VALUE) {
			min = -1;
		}
		System.out.println(min);
	}
}

플로이드 알고리즘의 결과가 주어졌을 때,

가능한 경우의 그래프의 최소 간선 수를 구하고, 모든 도로의 cost 합을 구하는 문제이다.

원래 플로이드 알고리즘은

• i->j로 가는 비용이 x보다 클 때, i->k->j로 가는 비용이 x이면 i->j로 가는 도로의 cost를 x로 바꿔준다

이 것을 반대로 적용해보면

• i->j로 가는 비용이 x일 때, i->k->j로 가는 비용이 x이면 i->j로 가는 도로는 필요없다.

입력이 이미 최단경로가 주어져있는데 다시 최단경로를 계산해보니 더 짧아진 경우는 입력이 모순이 되므로 -1을 출력하도록 했다.

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int mat[][] = new int[n + 1][n + 1];
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				mat[i][j] = in.nextInt();
			}
		}

		int ans = 0;
		boolean isEdge[][] = new boolean[n + 1][n + 1];
		for (int i = 1; i <= n; i++) {
			Arrays.fill(isEdge[i], true);
		}

		Floyd: 
		for (int k = 1; k <= n; k++) {
			for (int i = 1; i <= n; i++) {
				if (k == i) {
					continue;
				}
				for (int j = 1; j <= n; j++) {
					if (k == j || i == j) {
						continue;
					}

					if (mat[i][j] > mat[i][k] + mat[k][j]) {
						ans = -1;
						break Floyd;
					}

					if (mat[i][j] == mat[i][k] + mat[k][j]) {
						isEdge[i][j] = false;
						isEdge[j][i] = false;
					}
				}
			}
		}

		if (ans != -1) {
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					if (isEdge[i][j]) {
						ans += mat[i][j];
					}
				}
			}
			ans /= 2; // 양방향이므로 2로 나눠준다.
		}
		System.out.println(ans);
	}
}

플로이드 알고리즘: 모든 쌍의 최단 경로를 구하는 알고리즘

c.f. 벨만 포드/다익스트라 알고리즘: 시작점이 1개일 때

이 문제는 플로이드 알고리즘을 써서 풀 수 있다.

그런데, 도시 i에서 도시 j로 가는 최소 비용에 포함되어 있는 도시의 개수 K를 출력해야 하기때문에

그동안 지나왔던 경로도 저장해야 한다.

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();
		int mat[][] = new int[n + 1][n + 1];
		for (int i = 0; i <= n; i++) {
			Arrays.fill(mat[i], 1000000);
			mat[i][i] = 0;
		}
		for (int i = 0; i < m; i++) {
			int start = in.nextInt();
			int end = in.nextInt();
			int cost = in.nextInt();
			mat[start][end] = Math.min(mat[start][end], cost);
		}

		int route[][] = new int[n + 1][n + 1];
		for (int k = 1; k <= n; k++) {
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					if (mat[i][j] > mat[i][k] + mat[k][j]) {
						route[i][j] = k; // i~j를 갈 때 k를 거친다
						mat[i][j] = mat[i][k] + mat[k][j];
					}
				}
			}
		}

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				System.out.print(mat[i][j] + " ");
			}
			System.out.println();
		}

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (i == j) {
					System.out.println("0");
				} else {
					LinkedList<Integer> list = new LinkedList<Integer>();
					routeList(i, j, route, list);
					System.out.print(list.size() + " ");
					for (int k = 0; k < list.size(); k++) {
						System.out.print(list.get(k) + " ");
					}
					System.out.println();
				}
			}
		}
	}

	public static void routeList(int start, int end, int route[][], LinkedList<Integer> list) {
		if (route[start][end] == 0) { // i~j를 갈 때 거치는 점이 없을
			list.add(start);
			if (start != end) {
				list.add(end);
			}
		} else {
			int middle = route[start][end]; // i~j를 갈 때 경유
			routeList(start, middle, route, list);
			list.removeLast(); // 중복 제거
			routeList(middle, end, route, list);
		}
	}
}

그동안 지나왔던 경로를 저장할 때에는 route[i][j]에 i와 j를 지날 때 경유한 점을 저장하도록 한다.

즉, route[i][j]에는 i->j 간선이 원래 어디를 가르켰는지 저장한다.

경유했던 점들의 리스트를 가져올 때에는 routeList에서 list에 하나씩 넣는데

routeList(start, middle, route, list)와 routeList(middle, end, route, list)에서 middle 부분이 list에 두번 중복되어 들어가므로 한 번 제거해줘야한다.

연속된 수들 중 부분합이 S 이상인 최소 길이를 구하면 되므로 투 포인터를 활용하여 풀어본다

부분 합이 sum보다 작을 때에는 오른쪽 인덱스를 가리키는 포인터를 오른쪽으로,

sum보다 클 때에는 왼쪽 인덱스를 가리키는 포인터를 오른쪽으로 옮긴다.

부분합의 가장 작은 길이를 구해야 하므로 while문을 돌면서 min 값을 업데이트 해준다.

import java.util.*;
import java.io.*;

public class Main {
	public static int n;
	public static long sum;
	public static int arr[];

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		sum = in.nextInt();
		arr = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = in.nextInt();
		}

		int leftIndex = 0;
		int rightIndex = leftIndex;
		int ans = n + 1;
		long subSum = arr[leftIndex];
		while (leftIndex <= rightIndex) {
			if (subSum < sum) {
				rightIndex++;

				if (rightIndex == n) {
					break;
				}

				subSum += arr[rightIndex];
			} else if (subSum == sum) {
				ans = Math.min(ans, rightIndex - leftIndex + 1);

				rightIndex++;

				if (rightIndex == n) {
					break;
				}

				subSum += arr[rightIndex];
			} else {
				ans = Math.min(ans, rightIndex - leftIndex + 1);

				subSum -= arr[leftIndex];
				leftIndex++;
			}
		}

		if (ans > n) {
			ans = 0;
		}
		System.out.println(ans);

	}
}

아래와 같이 다른 다익스트라 문제와 동일하게 풀었는데 메모리 초과 및 시간초과가 나왔다.

인접 행렬로 풀면 V==20000일 때 인접행렬은 4억개이고 정수형이니 각 크기가 8B면 3200 MB가 되어서 그렇다고 함,,,

import java.util.*;

public class Main {
	public static long MAX = 20000 * 300000 * 10 + 1;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int e = in.nextInt();
		int startPoint = in.nextInt();
		long mat[][] = new long[n + 1][n + 1];
		for (int i = 0; i <= n; i++) {
			Arrays.fill(mat[i], MAX);
		}
		for (int i = 0; i < e; i++) {
			int start = in.nextInt();
			int end = in.nextInt();
			long weight = in.nextLong();

			mat[start][end] = Math.min(mat[start][end], weight);
		}

		long dist[] = dijkstra(startPoint, n, mat);
		for (int i = 1; i <= n; i++) {
			if (dist[i] >= MAX) {
				System.out.println("INF");
			} else {
				System.out.println(dist[i]);
			}
		}
	}

	public static long[] dijkstra(int startPoint, int n, long mat[][]) {
		long[] dist = new long[n + 1];
		boolean[] isVisited = new boolean[n + 1];

		Arrays.fill(dist, MAX);

		for (int i = 1; i <= n; i++) {
			dist[i] = mat[startPoint][i];
		}
		dist[startPoint] = 0;
		isVisited[startPoint] = true;

		for (int i = 1; i < n; i++) {
			int index = -1;
			long min = MAX;
			for (int j = 1; j <= n; j++) {
				if (min > dist[j] && !isVisited[j]) {
					min = dist[j];
					index = j;
				}
			}

			if (index == -1) {
				break;
			}
			isVisited[index] = true;

			for (int j = 1; j <= n; j++) {
				if (dist[j] > dist[index] + mat[index][j]) {
					dist[j] = dist[index] + mat[index][j];
				}
			}

		}

		return dist;
	}
}

그리고 V<=20000이기 때문에 시간복잡도 O(V^2)로는 4억(약 4초)가 걸린다.

다익스트라 알고리즘을 구하는 순서를 다시 보면 아래와 같다.

1. 체크되어 있지 않은 정점 중에서 D의 값이 가장 작은 정점 index 를 선택한다. : O(V)
2. index틑 체크한다.
3. index와 연결된 모든 정점에 대해 최단거리 갱신: 인접행렬의 경우 O(V^2), 인접리스트의 경우 O(V+E)

여기서 시간을 줄일 수 있는 부분은 1번이다.

(정점 번호, Dist)값을 heap이나 priorityQueue에 넣어서 가장 작은 정점을 선택할 수 있도록 한다.

이떄 시간복잡도는 모든 간선이 들어가는 것이나 마찬가지이다.

왜냐면 dist배열이 업데이트 될때마다 들어가는데, 업데이트 된다는 것의 의미는

어떤 정점에 연결되어 있는 간선에 대해 비교를 한 것과 같다.

따라서 O(ElogE), 즉 (정점 번호, Dist)쌍이 E번 들어갔다가 나오는 시간이 걸린다.

위 풀이를 적용하여 다시 문제를 풀어볼 예정

가능한 경로 2가지

• 1 -> v1 -> v2 -> N
• 1 -> v2 -> v1 -> N

다익스트라 알고리즘을 시작점 1, v1, v2로 하여 각각 구한뒤 더했을 때 최솟값을 구하도록 한다

import java.util.*;

public class Main {
	public static long MAX = 800 * 200000 * 1000 + 1;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int e = in.nextInt();
		long mat[][] = new long[n + 1][n + 1];
		for (int i = 0; i <= n; i++) {
			Arrays.fill(mat[i], MAX);
		}
		for (int i = 0; i < e; i++) {
			int start = in.nextInt();
			int end = in.nextInt();
			long weight = in.nextLong();

			mat[start][end] = Math.min(mat[start][end], weight);
			mat[end][start] = Math.min(mat[end][start], weight);
		}

		int v1 = in.nextInt();
		int v2 = in.nextInt();

		long distFrom1[] = dijkstra(1, n, mat);
		long distFromV1[] = dijkstra(v1, n, mat);
		long distFromV2[] = dijkstra(v2, n, mat);

		long ans = -1;
		// 갈 수 없는 경우 체크
		if (distFrom1[v1] < MAX && distFromV1[v2] < MAX && distFromV2[n] < MAX) {
			ans = distFrom1[v1] + distFromV1[v2] + distFromV2[n];
		}
		if (distFrom1[v2] < MAX && distFromV2[v1] < MAX && distFromV1[n] < MAX) {
			ans = Math.min(ans, distFrom1[v2] + distFromV2[v1] + distFromV1[n]);
		}
		System.out.println(ans);
	}

	public static long[] dijkstra(int startPoint, int n, long mat[][]) {
		long[] dist = new long[n + 1];
		boolean[] isVisited = new boolean[n + 1];

		Arrays.fill(dist, MAX);

		for (int i = 1; i <= n; i++) {
			dist[i] = mat[startPoint][i];
		}
		dist[startPoint] = 0;
		isVisited[startPoint] = true;

		for (int i = 1; i < n; i++) {
			int index = -1;
			long min = MAX;
			for (int j = 1; j <= n; j++) {
				if (min > dist[j] && !isVisited[j]) {
					min = dist[j];
					index = j;
				}
			}

			if (index == -1) {
				break;
			}
			isVisited[index] = true;

			for (int j = 1; j <= n; j++) {
				if (dist[j] > dist[index] + mat[index][j]) {
					dist[j] = dist[index] + mat[index][j];
				}
			}

		}
		
		return dist;
	}
}

2020/07/07 - [알고리즘 공부] - boj 1916: 최소비용 구하기

위의 풀이와 똑같지만, 최소 비용을 갖는 경로를 방문하는 도시 순서대로 출력하기 위해서는

경로의 최솟값이 업데이트 될 때의 위치를 저장하도록 하면 된다.

마지막에 답을 구할 때에는 이전 위치를 저장하도록 했으므로

도착지점->시작지점 순으로 스택에 넣고 빼면서 프린트 한다.

import java.util.*;

public class Main {
	public static int MAX = 1000000000;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();

		int bus[][] = new int[n + 1][n + 1];
		for (int i = 0; i <= n; i++) {
			Arrays.fill(bus[i], MAX);
		}
		for (int i = 0; i < m; i++) {
			int start = in.nextInt();
			int end = in.nextInt();
			int time = in.nextInt();

			bus[start][end] = Math.min(bus[start][end], time);
		}

		int start = in.nextInt();
		int end = in.nextInt();
		int dist[] = new int[n + 1];
		boolean isVisited[] = new boolean[n + 1];
		int route[] = new int[n + 1];
		Arrays.fill(route, start);
		Arrays.fill(dist, MAX);
		for (int i = 1; i <= n; i++) {
			dist[i] = bus[start][i];
		}
		dist[start] = 0;
		route[start] = 0;
		isVisited[start] = true;

		for (int i = 1; i < n; i++) {

			int index = -1;
			int min = MAX;
			for (int j = 1; j <= n; j++) {
				if (min > dist[j] && !isVisited[j]) {
					min = dist[j];
					index = j;
				}
			}
			if (index == -1) {
				break;
			}
			isVisited[index] = true;
			
			for (int j = 1; j <= n; j++) {
				if (dist[j] > dist[index] + bus[index][j]) {
					dist[j] = dist[index] + bus[index][j];
					route[j] = index;
				}
			}

		}
		
		System.out.println(dist[end]);
		Stack<Integer> answerSet=new Stack<Integer>();
		int now=end;
		while(true) {
			if(now==start) {
				answerSet.add(now);
				break;
			}
			
			answerSet.add(now);
			now=route[now];
		}
		
		System.out.println(answerSet.size());
		while(!answerSet.isEmpty()) {
			System.out.print(answerSet.pop()+" ");
		}
	}
}