70일차 - TIL

오늘 한 것

• 그래프 고급 알고리즘 - 최소신장트리를 구하는 크루스칼 알고리즘

크루스칼 알고리즘을 이용한 최소신장트리(MST) 구하기
1-1. 크루스칼 알고리즘 - 탐욕 알고리즘과 Union-Find 알고리즘을 이용해 구현

1-2. 구현하기 위해 사용하는 알고리즘의 특징
(1) 탐욕 알고리즘 : 현재 시점에서 최소 비용을 선택해서, 최적의 결과를 찾도록 하는 알고리즘
(2) Union-Find 알고리즘 : 트리 구조를 활용해 Disjoint Set을 표현하는 알고리즘으로,
노드들 중에 연결된 노드를 찾거나, 노드들을 서로 연결할 때 사용한다.

(2)-1. Disjoint Set : 서로소 집합 자료구조로, 중복되지 않는 부분 집합들로 나눠진 원소들을 저장하는 자료구조

(2)-2. Union-Find 알고리즘 구현 : 간선으로 연결된 두 노드의 루트 노드가 서로 다르도록 합친다.
(1) n개의 원소가 개별 집합이 되도록 만든다. - 초기화
(2) 두 개별 집합인 두 트리를 하나의 트리로 만들기 위해 하나의 집합으로 합친다. - Union
(3) 존재 하는 여러 노드 중 두 개의 노드를 선택,
 선택한 두 노드가 하나의 그래프에 속하는지 각 그룹의 최상단 원소인 루트 노드로 확인한다. - Find

(2)-3. 높이가 늘어나지 않도록 관리해, 효율적으로 루트 노드를 계산 하기 위한 기법
(1) union-by-rank 기법 : rank는 0부터 시작
 각 트리의 높이를 기억해 서로 다른 두 트리를 union할 때 높이가 낮은 트리를 높이가 높은 트리에 붙인다.
-> 높이가 큰 트리의 루트 노드가 합친 집합의 루트노드가 되도록 한다.
만약, 서로의 높이가 같다면 하나의 트리의 높이를 늘려서 다른 트리를 해당 트리의 루트 노드에 붙인다.

(2) path compression 기법  : Find 실행시에 동작
Find를 실행한 노드에서 거쳐간 노드를 루트노드의 자식으로 직접 연결하는 기법으로,
-> Find를 실행한 노드 이후의 노드들은 루트 노드를 한번에 알 수 있게 된다.

 

//1-3. 크루스칼 알고리즘 구현 순서
    //(1) 모든 정점을 연결된 간선을 제거한 상태로 만든다.
    //(2) 모든 간선을 비용 기준으로 정렬해 최소 비용 간선부터 양 끝의 두 정점을 비교한다.
    //(3) 비교해 최소 비용의 간선을 선택할 때, 두 정점사이에 사이클이 존재하지 않도록 연결한다.
    //-> 따라서, 사이클이 생기지 않도록 구현하기 위해 두 정점의 Union-Find 알고리즘을 이용해 최상위 정점을 확인해 서로 다를 때만 연결한다.
    //(4) 모든 정점을 사이클 없이 연결한 경우 최소신장트리 완성
    HashMap<String, String> parent =new HashMap<>();
    HashMap<String, Integer> rank=new HashMap<>();


    public static void main(String[] args) {
        //1. 간선과 노드을 담는 리스트 선언 및 초기화
        ArrayList<Edge> edges=new ArrayList<>();
        edges.add(new Edge(7, "A","B"));
        edges.add(new Edge(5, "A","D"));
        edges.add(new Edge(7, "B","A"));
        edges.add(new Edge(8, "B","C"));
        edges.add(new Edge(9, "B","D"));
        edges.add(new Edge(7, "B","E"));
        edges.add(new Edge(8, "C","B"));
        edges.add(new Edge(5, "C","E"));
        edges.add(new Edge(5, "D","A"));
        edges.add(new Edge(9, "D","B"));
        edges.add(new Edge(7, "D","E"));
        edges.add(new Edge(6, "D","F"));
        edges.add(new Edge(7, "E","B"));
        edges.add(new Edge(5, "E","C"));
        edges.add(new Edge(7, "E","D"));
        edges.add(new Edge(8, "E","F"));
        edges.add(new Edge(9, "E","G"));
        edges.add(new Edge(6, "F","D"));
        edges.add(new Edge(8, "F","E"));
        edges.add(new Edge(11, "F","G"));
        edges.add(new Edge(9, "G","E"));
        edges.add(new Edge(11, "G","F"));

        ArrayList<String> vertices=new ArrayList<>(Arrays.asList("A","B","C","D","E","F","G"));
        System.out.println("edges = " + edges);
        System.out.println("vertices = " + vertices);

        Kruskal_2 kruskal =new Kruskal_2();
        System.out.println("kruskal.kruskalFunc(edges, vertices) = " + kruskal.kruskalFunc(vertices, edges));
    }
    public ArrayList<Edge> kruskalFunc(ArrayList<String> vertices,ArrayList<Edge> edges){
        //변수 선언
        //: <노드, 해당 노드의 부모노드>의 해시맵 (해당 노드가 부모노드라면 자기자신을 가리키도록)
        //: <노드, 해당 노드의 높이>의 해시맵
//        HashMap<String, String> parent= new HashMap<>();
//        HashMap<String, Integer> rank = new HashMap<>();
        ArrayList<Edge> mst = new ArrayList<>();
        Edge currentEdge;

        //(1) 반복문을 이용해 인자로 모든 노드를 전달해 초기화 메서드 호출
//        for(String node : vertices){
//            makeSet(node);
//        }
        for(int index=0;index<vertices.size();index++){
            makeSet(vertices.get(index));
        }
        //(2) 간선리스트를 가중치를 기준으로 오름차순 정렬
        Collections.sort(edges);

        //(3) 가장 가중치가 작은 간선부터 뽑아서 사이클이 생기지 않으면 간선 연결한다.
        //-> 서로의 부모노드가 같은지 확인해 사이클이 존재여부 판단
//        for(Edge node : edges){
//            if(find(node.getNodeV())!=find(node.getNodeU())){
//                union(node.getNodeV(), node.getNodeU());
//                mst.add(node);
//            }
//        }
        for(int index=0;index<edges.size();index++){
            currentEdge=edges.get(index);
            if(find(currentEdge.getNodeV())!=find(currentEdge.getNodeU())){
                union(currentEdge.getNodeV(), currentEdge.getNodeU());
                mst.add(currentEdge);
            }

        }
        return mst;
    }
    //2. Union-Find 알고리즘의 메서드 작성
    //: union-by-rank, path compression 기법을 이용해 효율적인 메서드 작성
    //(1) 초기화
    public void makeSet(String node){
        //(1)-(1). 노드 하나만 있기 때문에 해당 노드가 루트노드
        parent.put(node,node);
        //(1)-(2). 노드 하나만 있기 때문에 높이도 0;
        rank.put(node, 0);
    }

    //(2) Union
    //: 사이클이 존재하지 않을 때만 호출한다고 가정하고, union-by-rank기법을 이용해 간선을 잇는 메서드
    public void union(String nodeV, String nodeU){
        String root1 = find(nodeV);
        String root2 = find(nodeU);


        //union-by-rank 기법
        //(1) 높이가 다를 경우
        //: 높이가 작은 쪽의 트리의 부모노드를 높이가 높은 쪽의 루트 노드의 자식 노드로 붙인다.
        //(2) 높이가 같은 경우
        //: 한 트리의 높이를 한 칸 높여서, 높이가 작은 쪽의 트리의 부모노드를 높이가 높은 쪽의 루트 노드의 자식 노드로 붙인다.

        //구현
        //(1) 루트노드의 높이를 비교한다.
        if(rank.get(root1)>rank.get(root2)){
            //높이가 큰 쪽에 작은 노드의 루트노드를 붙인다.
            parent.put(root2, root1);
        }
        //(2) 높이가 서로 같거나 루트1의 높이가 낮을 때
        else {
            //(3) 루트2보다 루트1의 높이가 낮을 때
            parent.put(root1, root2);
            //(4) 만약에 높이가 같을 경우
            if(rank.get(root1)==rank.get(root2)){
                //(5) 루트2의 부모를 루트1의 자식노드로 붙였기 때문에
                //-> 루트1의 높이를 +1한다.
                rank.put(root2, rank.get(root2)+1);
            }
        }

    }

    //(3) Find
    //: 해당 노드의 루트 노드를 반환하는 메서드로, path compression을 이용해 루트노드에 모든 자손 노드들을 자식 노드로 연결한다.
    public String find(String node){
        //(3)-(1). 현재 노드가 루트 노드가 아니면, 부모노드가 루트노드인지 재귀적으로 확인

        if(parent.get(node)!=node){
            //-> path compression 기법을 이용해 직접 확인
            parent.put(node, find(parent.get(node)));
        }
        return parent.get(node);
    }
}

 

• 그래프 고급 알고리즘 - 최소신장트리를 구하는 프림 알고리즘
  1. 필요한 변수 선언
     • 현재 연결된 간선을 담은 리스트, 연결할 후보 간선을 담은 리스트
     • 모든 정점을 담은 리스트
     • 간선에 연결된 노드를 표현한 Map
  2. 연결 정보 초기화
     • 각각의 노드 초기화
     • 간선 리스트를 돌면서 맵에서 리스트를 얻고, 초기화한 노드들에 연결된 간선들을 현재 간선 리스트에 추가한다.
  3. 초기값 설정
     • 시작점을 연결된 리스트에 추가
     • 간선 후보 리스트를 시작점을 키로 해시맵에서 없으면 만들어서 가져온다.
     • 간선 후보 리스트를 돌면서 우선순위큐에 해당 간선들을 추가한다.
  4. 우선순위큐 반복
     • 시작점과 연결된 최소 가중치 간선부터 꺼낸다.
     • 연결된 노드 리스트에 존재한다면,
       • 연결할 경우 사이클이 생기므로 continue;
     • 연결할 노드가 연결된 노드 리스트에 없으면,
       • 연결한 노드에 추가하고 결과리스트에 해당 간선 정보를 추가한다.
       • 해시맵에서 연결할 노드에 연결된 간선 리스트를 가져와서,
         해당 간선에 연결된 노드들을 인접한 노드이므로, 우선순위큐에 추가한다.

 

2. 프림 알고리즘
- 탐욕 알고리즘을 이용해 특정 정점의 최소 가중치인 간선부터 연결 시작하면서 구현
: 간선이 연결되면, 해당 정점에서 최소 가중치이고, 사이클이 생기지 않도록 하는 간선의 연결을 반복한다.

2-1. 프림 알고리즘 구현 순서
(1) 임의의 정점을 선택하고, 연결된 노드 집합에 삽입한다.
(2) 선택한 정점에 연결된 간선들을 간선 리스트에 삽입한다.
(3) 간선 리스트를 오름차순 정렬해 가장 최소 가중치인 간선부터 뽑는다.
(4) 뽑은 간선이 해당 조건을 충족하는지 확인
-해당 간선에 연결된 인접 정점이 '연결된 노드 집합'에 이미 들어 있다면, 사이클이 생길 수 있으므로 다음 간선을 다시 뽑는다.
-해당 간선에 연결된 인접 정점이 '연결된 노드 집합'에 들어 있지 않다면, 해당 간선을 선택해 최소 신장 트리에 삽입
(5) 선택한 간선은 간선 리스트에서 제거한다.
(6) 간선 리스트에 더 이상의 간선이 남아 있지 않을 때 까지 반복한다.

 

package org.algorithms.graph.minimumspanning.prim;

import org.algorithms.graph.minimumspanning.SpanningTree;
import org.algorithms.graph.minimumspanning.SpanningTree.Edge;
import org.algorithms.graph.minimumspanning.kruskal.Kruskal_1;

import java.util.*;

public class Prim_2 {
    public static void main(String[] args) {
        //1. 간선과 노드을 담는 리스트 선언 및 초기화
        ArrayList<Edge> edges=new ArrayList<>();
        edges.add(new Edge(7, "A","B"));
        edges.add(new Edge(5, "A","D"));
//        edges.add(new Edge(7, "B","A"));
        edges.add(new Edge(8, "B","C"));
        edges.add(new Edge(9, "B","D"));
        edges.add(new Edge(7, "B","E"));
//        edges.add(new Edge(8, "C","B"));
        edges.add(new Edge(5, "C","E"));
//        edges.add(new Edge(5, "D","A"));
//        edges.add(new Edge(9, "D","B"));
        edges.add(new Edge(7, "D","E"));
        edges.add(new Edge(6, "D","F"));
//        edges.add(new Edge(7, "E","B"));
//        edges.add(new Edge(5, "E","C"));
//        edges.add(new Edge(7, "E","D"));
        edges.add(new Edge(8, "E","F"));
        edges.add(new Edge(9, "E","G"));
//        edges.add(new Edge(6, "F","D"));
//        edges.add(new Edge(8, "F","E"));
        edges.add(new Edge(11, "F","G"));
//        edges.add(new Edge(9, "G","E"));
//        edges.add(new Edge(11, "G","F"));

//        ArrayList<String> vertices=new ArrayList<>(Arrays.asList("A","B","C","D","E","F","G"));
        System.out.println("edges = " + edges);
//        System.out.println("vertices = " + vertices);

        Prim_2 prim =new Prim_2();
        System.out.println("prim.primFunc(edges, vertices) = " + prim.primFunc(edges, "A"));
    }
    public ArrayList<Edge> primFunc(ArrayList<Edge> edges, String startNode){
        //1. 필요한 변수 선언
        ArrayList<Edge> currentEdgeList, candidateEdgeList;
        ArrayList<String> connectedNodes=new ArrayList<>();
        ArrayList<Edge> result = new ArrayList<>();
        //간선에 연결된 노드를 표현하기 위한 자료구조
        //: 노드를 키로 각 노드마다 연결된 간선들을 값으로 표현한다.
        HashMap<String, ArrayList<Edge>> adjacentEdges = new HashMap<>();

        //2. 연결정보 초기화
        //(1) 각각의 노드 초기화
        //: Map에 키가 없으면 <키, 간선리스트> 추가
        for(Edge edge:edges){
            if(!adjacentEdges.containsKey(edge.getNodeV())) adjacentEdges.put(edge.getNodeV(),new ArrayList<>());
            if(!adjacentEdges.containsKey(edge.getNodeU())) adjacentEdges.put(edge.getNodeU(),new ArrayList<>());
        }
        //(2) 간선 리스트를 돌면서 맵에서 리스트를 얻고, 초기화한 노드들에 연결된 간선들을 현재 간선 리스트에 추가한다.
        for(Edge edge:edges){
            currentEdgeList=adjacentEdges.get(edge.getNodeV());
            currentEdgeList.add(new Edge(edge.getWeight(), edge.getNodeV(), edge.getNodeU()));

            currentEdgeList=adjacentEdges.get(edge.getNodeU());
            currentEdgeList.add(new Edge(edge.getWeight(), edge.getNodeU(), edge.getNodeV()));
        }

        PriorityQueue<Edge> priorityQueue = new PriorityQueue();
        for(Edge edge :adjacentEdges.getOrDefault(startNode, new ArrayList<>())){
            priorityQueue.add(edge);
        }

        //3. 초기값 설정
        //-시작점 연결된 리스트에 추가
        connectedNodes.add(startNode);

        //-간선 후보 리스트를 시작점을 키로 해시맵에서 없으면 만들어서 가져온다.
        candidateEdgeList=adjacentEdges.getOrDefault(startNode, new ArrayList<>());
        System.out.println("candidateEdgeList = " + candidateEdgeList);


        //-간선 후보 리스트를 돌면서 우선순위큐에 해당 간선들을 추가한다.
        for(Edge edge : candidateEdgeList){
            priorityQueue.offer(edge);
        }

        //4. 우선순위큐 반복
        while(!priorityQueue.isEmpty()) {
            //- 시작점과 연결된 최소 가중치 간선부터 꺼낸다.
            Edge poppedEdge =priorityQueue.poll();
            //A->D

            //연결할 노드가 연결된 노드 리스트에 없으면, 연결한 노드에 추가하고
            //-> 연결된 노드 리스트에 존재한다면, 연결할 경우 사이클이 생기므로 continue;
            if(!connectedNodes.contains(poppedEdge.getNodeU())) {
                connectedNodes.add(poppedEdge.getNodeU());
                //결과리스트에 해당 간선 정보를 추가한다.
                result.add(new Edge(poppedEdge.getWeight(), poppedEdge.getNodeV(), poppedEdge.getNodeU()));

                //해시맵에서 연결할 노드에 연결된 간선 리스트를 가져와서,
                // 해당 간선에 연결된 노드들을 인접한 노드이므로, 우선순위큐에 추가한다.
                ArrayList<Edge> adjacentEdgeNodes = adjacentEdges.getOrDefault(poppedEdge.getNodeU(), new ArrayList<>());
                for (Edge edge : adjacentEdgeNodes) {
                    if (!connectedNodes.contains(edge.getNodeU())) priorityQueue.offer(edge);
                }
            }
        }
        return result;
    }

}

• 자료구조 - 배열, 리스트, 스택, 큐
• 알고리즘 - 시간복잡도 [빅오 표기법]

 

내일 할 것

• 고급 정렬 알고리즘 - 병합정렬, 퀵정렬
• 이진탐색 알고리즘
• 스프링 - MVC 패턴과 스프링 프레임워크