230909 TIL #186 알고리즘 정리 - 2

김춘복·2023년 9월 9일
0

TIL : Today I Learned

목록 보기
186/454

Today I Learned

내일 칠 프로그래머스 코테를 대비해 저번에 정리한 알고리즘을 뒤이어 마저 정리하고 복습하는 시간을 가졌다.


알고리즘 정리 2

최소 신장 트리(MST)

TIL #154

네트워크의 모든 정점을 가장 적은 수의 간선과 비용(가중치)으로 연결하는 것

  • 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(유니온파인드)

TIL #155

두 노드가 같은 그래프에 속하는지 판단하는 알고리즘

  • 크루스칼에서 사이클 형성 여부를 판단할 때 사용한다.

  • 부모 노드를 찾는 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 (다익스트라)

TIL #163

음의 가중치가 없는 그래프의 한 정점에서 다른 모든 정점까지의 최단거리를 구하는 알고리즘

  • 최단 거리를 저장할 배열을 만들고 우선순위큐를 이용해 구현한다.

  • 시간복잡도는 우선순위큐를 사용할 경우 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(플로이드 워셜)

TIL #167

가능한 모든 노드 쌍에 대한 최단 경로를 구하는 알고리즘

  • 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);
    }
}

기타

에라토스테네스의 체

TIL #156

주어진 범위에서 소수를 구하는 알고리즘

  • 소수가 되는 수의 배수를 지우면 남는 수가 소수가 된다.

  • 코드 예시

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());

  }

}

유클리드 호제법

TIL #164

두 정수의 최대 공약수를 찾는 효율적인 알고리즘

  • 큰 수를 작은 수로 나머지가 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)
profile
꾸준히 성장하기 위해 매일 log를 남깁니다!

0개의 댓글