Today I Learned
내일 칠 프로그래머스 코테를 대비해 저번에 정리한 알고리즘을 뒤이어 마저 정리하고 복습하는 시간을 가졌다.
알고리즘 정리 2
최소 신장 트리(MST)
네트워크의 모든 정점을 가장 적은 수의 간선과 비용(가중치)으로 연결하는 것
- cycle이 되면 안되고, n-1개의 간선만 사용해 n개의 정점을 연결해야하며, 간선 가중치의 합이 최소여야한다.
Prim Algorithm(프림)
정점을 기준으로 MST를 형성하는 알고리즘
-
시작정점을 정하고 연결된 정점 중 가중치가 가장 적은 정점을 선택해 계속 나아가는 방식
-
시간복잡도는 우선순위큐(최소 힙) 사용 시 O(E log V)
Kruskal Algorithm(크루스칼)
가중치가 적은 간선부터 선택해나가는 방식
-
간선을 오름차순으로 정렬해 사이클을 형성하는 간선을 제외하고 가장 적은 가중치의 간선을 차례대로 선택한다.
-
시간복잡도는 O(E log E) or O(E log V)
-
간선이 적으면 크루스칼, 많으면 프림이 더 유리하다.
-
코드 예시 (TIL #157 섬 연결하기)
import java.util.*;
class Solution {
static int[] root;
static int answer;
static int count;
public void union(int x, int y, int cost){
int rootX = find(x);
int rootY = find(y);
if(rootX == rootY) return;
root[rootY] = rootX;
answer += cost;
count++;
}
public int find(int x){
if(root[x] != x){
root[x] = find(root[x]);
}
return root[x];
}
public int solution(int n, int[][] costs) {
if(n<=1) return 0;
answer = 0;
root = new int[n];
count = 0;
// unionfind 초기화
for(int i=0; i<n; i++){
root[i] = i;
}
// 크루스칼 적용하기 위해 sort
Arrays.sort(costs, Comparator.comparingInt(a -> a[2]));
// 크루스칼로 MST 구현
for(int i=0; i<costs.length; i++){
if(count >= n-1) break;
int x = costs[i][0];
int y = costs[i][1];
int cost = costs[i][2];
union(x,y,cost);
}
return answer;
}
}Union-Find(유니온파인드)
두 노드가 같은 그래프에 속하는지 판단하는 알고리즘
-
크루스칼에서 사이클 형성 여부를 판단할 때 사용한다.
-
부모 노드를 찾는 find와 부모가 같지 않을 경우 합치는 union으로 구성되어 있다.
-
코드 예시
class UnionFind {
private int[] parent;
public UnionFind(int size) {
parent = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i;
}
}
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
parent[rootX] = rootY;
}
}
}최단 경로 알고리즘
Dijkstra Algorithm (다익스트라)
음의 가중치가 없는 그래프의 한 정점에서 다른 모든 정점까지의 최단거리를 구하는 알고리즘
-
최단 거리를 저장할 배열을 만들고 우선순위큐를 이용해 구현한다.
-
시간복잡도는 우선순위큐를 사용할 경우 O((V+E) log V)
-
코드 예시
import java.io.*;
import java.util.*;
public class A_DijkstraPQ {
static List<List<Node>> graph;
static int V;
static int[] distance;
static class Node implements Comparable<Node> {
int vertex;
int weight;
Node(int vertex, int weight) {
this.vertex = vertex;
this.weight = weight;
}
@Override
public int compareTo(Node other) {
return Integer.compare(this.weight, other.weight);
}
}
public static void dijkstra(int index) {
Queue<Node> pq = new PriorityQueue<>();
distance = new int[V];
Arrays.fill(distance, Integer.MAX_VALUE);
distance[index] = 0;
pq.offer(new Node(index, 0));
while(!pq.isEmpty()){
Node node = pq.poll();
int nv = node.vertex;
int nw = node.weight;
if(nw > distance[nv]) continue;
for(Node linkedNode : graph.get(nv)) {
int lv = linkedNode.vertex;
int lw = linkedNode.weight;
if(nw+lw < distance[lv]){
distance[lv] = nw+lW;
pq.offer(new Node(lv, distance[lv]))
}
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
V = Integer.parseInt(st.nextToken()); // 정점의 개수
int E = Integer.parseInt(st.nextToken()); // 간선의 개수
graph = new ArrayList<>();
for(int i=0; i<V; i++){
graph.add(new ArrayList<>());
}
//
for(int j=0; j<E; j++){
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken()); // 시작노드
int end = Integer.parseInt(st.nextToken()); // 도착노드
int w = Integer.parseInt(st.nextToken()); // 가중치(거리)
graph.get(start).add(new Node(end, w));
// 양방향일 경우
graph.get(end).add(new Node(start, w));
}
// 알고리즘 실행
dijkstra(0);
// 결과 출력
for(int i=0; i<V; i++){
System.out.println(i+ "번 정점까지의 최단 거리는 " + distance[i]);
}
}Floyd-Warshall(플로이드 워셜)
가능한 모든 노드 쌍에 대한 최단 경로를 구하는 알고리즘
-
DP를 기반으로 중간 노드를 거쳐 가는 경우를 고려해 최단 경로를 구한다.
-
3중 for문으로 사용해 시간복잡도는 O(V^3)
-
코드 예시
public class A_FloydWarshall {
// Integer.MAX_VALUE는 덧셈과정에서 overflow가 발생할 수있으므로 큰 값으로 초기화
final static int INF = 999999, V = 4;
void floydWarshall(int graph[][]) {
int dist[][] = new int[V][V];
// 초기값 설정
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
dist[i][j] = graph[i][j];
}
}
// 플로이드 워셜 알고리즘 적용
for (int m = 0; m < V; m++) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][m] + dist[m][j] < dist[i][j])
dist[i][j] = dist[i][m] + dist[m][j];
}
}
}
printSolution(dist);
}
// 출력
void printSolution(int dist[][]) {
for (int i=0; i<V; ++i) {
for (int j=0; j<V; ++j) {
if (dist[i][j] == INF)
System.out.print("X ");
else
System.out.print(dist[i][j] + " ");
}
System.out.println();
}
}
public static void main (String[] args) {
int graph[][] = { {0, 5, INF, 10},
{INF, 0, 3, INF},
{4, INF, 0, 1},
{2, 5, 8, 0} };
A_FloydWarshall fw = new A_FloydWarshall();
fw.floydWarshall(graph);
}
}기타
에라토스테네스의 체
주어진 범위에서 소수를 구하는 알고리즘
-
소수가 되는 수의 배수를 지우면 남는 수가 소수가 된다.
-
코드 예시
public class A_Eratos {
static boolean[] primeList;
static List<Integer> primes;
private static void eratos(int n){
if (n<=1) return;
primeList = new boolean[n+1];
primeList[0] = false;
primeList[1] = false;
for (int i=2; i<=n; i++){
primeList[i] = true;
}
for (int i=2; (i*i)<=n; i++){
if (primeList[i]){
for (int j= i*i; j<=n; j+=i) primeList[j] = false;
}
}
primes = new ArrayList<>();
for (int i=0; i<=n; i++){
if (primeList[i]) primes.add(i);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
eratos(n);
System.out.println(primes.toString());
}
}
유클리드 호제법
두 정수의 최대 공약수를 찾는 효율적인 알고리즘
-
큰 수를 작은 수로 나머지가 0이 될때 까지 반복적으로 나눠 그 때의 작은수가 최대 공약수가 된다.
-
코드 예시
public static int gcdRecursion(int a, int b){
if (b==0) return a;
return gcdRecursion(b,a%b);
}- 최소 공배수는 두 수의 곱을 최대 공약수로 나눈 것과 같다.
LCM(a,b) = a * b / GCD(a,b)
꾸준히 성장하기 위해 매일 log를 남깁니다!