Algorithm

알고리즘 복습..

Loopy_SEOB 2020. 12. 5. 19:43

그래프 알고리즘

노드와 간선으로 이루어져 있음, 간선은 노드와 노드의 연결을 의미.

 

그래프

  • 방향성 및 무방향성
  • 순환 및 비순환
  • 루트 노드 존재 X
  • 부모와 자식 관계 X
  • 네트워크 모델

 

트리

  • 방향 그래프
  • 비순환 그래프
  • 루트 노드 존재
  • 부모와 자식 관계
  • 계층 모델

 

보통 구현은 인접 행렬이나 인접 리스트를 사용하여 구현한다. 각 차이는 메모리와 속도 측면에서 구별해서 사용한다.

 

서로소 집합 알고리즘 (Disjoint SET) - Union&Find

 

공통 원소가 없는 두 집합을 의미.

 

서로소 집합정보가 주어 졌을 시 트리 자료구조를 이용해 집합을 표현하는 서로소 집합 계산 알고리즘

 

  1. Union (합집합) 연산을 확인하여, 서로 연결된 두 노드를 확인한다.
  2. 각 노드의 루트노드를 찾고 보통 앞의 값을 부모노드로 설정한다.
  3. 모든 합집합 연산을 처리할 때 까지 반복 한다.

 

static int parent[] // 루트 노드에 대한 정보를 담는 배열

public static int find(int now){
	if(parent[now]!=now){ // 루트 노드가 아니라면 루트노드를 찾을 때 까지 재귀적 호출
    	return find(parent[now]); //루트까지 거슬러 올라가는 재귀적 호출
     } 25
     return parent[now];//루트노드 반환
}
public static void union(int A, int B){
	A = find(A); // 각 루트 노드를 찾는다
	B = find(B);
    
    if(A<B) // 합집합 연산 
    	parent[B]=A;
    else
    	parent[A]=B;
}

 

서로소 집합을 활용한 사이클 판별

 

  • 서로소 집합의 경우 무방향 그래프 내에서의 사이클을 판별할 때 사용할 수 있다.
  • union 연산은 그래프에서의 간선으로 표현 가능. 간선을 하나씩 확인하며 두 노드가 포함되어 있는 집합의 합연산을 반복하는 것으로 판별이 가능 하다.
  1. 각 간선을 확인하며 두 노드의 루트 노드를 확인한다.
  2. 루트 노드가 다르다면 두 노드에 대한 Union 연산 수행.
  3. 루트 노드가 같다면 사이클이 발생한 것으로 간주 한다.
  4. 그래프에 속한 모든 간선에 대하여 위의 과정을 반복하여 사이클을 판별 한다.

 

신장트리

  • 하나의 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 뜻한다.
  • 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는 조건은 트리의 조건이기도 하다.

 

크루스칼 알고리즘

 

  • 최소한의 비용으로 신장트리를 찾아야 할 때 사용하는 알고리즘. 최소 비용으로 모든 노드를 연결할 때 사용한다.
  • 예를 들어 모든 도시를 연결할 때 최소 비용으로 연결하는 알고리즘 풀때 크루스칼을 사용하면 된다.

 

  1. 일단 모든 간선에 대해 정렬을 수행한다.
  2. 그 뒤 가장 거리가 짧은 간선부터 집합에 포함시킨다. 이때 사이클이 발생하는 간선이면 집합에 포함시키지 않는다.
  3. 모든 간선에 대해 반복 수행 한다.

 

최종적으로 간선의 개수 는 노드의 개수 -1개가 된다. 사이클을 발생시키는 간선을 제외하고 연결해야 최적의 해를 보장한다.

 

public staitc int[] parent

public static int find(int now){
	if(parent[now]!=now){
    	return find(parent[now]);
        }
    return parent[now];
}
public static void union(int A, int B){
	A = find(A);
    B = find(B);
    
    if(A<B)
    	parent[B]=A;
    else
    	parent[A]=B;
}
class Node implements Comparable<Node>{
	int a ;
    int b ;
    int cost;
    
    public Node(int a, int b, int cost){
    	this.a = a;
        this.b = b;
        this.cost = cost;
   }
   @Override
   public int CompareTo(Node o){
   	if(this.cost < o.cost)
    	return -1;
    else
    	return 1;
    }
}

public static void main(args[]){
	
    ArrayList<Node> edges = new ArrayList<>();
    int value = 0;
    
    parent = new int[N+1]
    
    for(int i = 1; i<=N; i++){
    	parent[i] = i;
     } 
     Collections.sort(edges); //비용에 따른 간선 정렬
     
     for(int i = 0; i<edges.size(); i++){
     	int cost = edges.get(i).cost;
        int a = edges.get(i).a;
        int b = edges.get(i).b;
        if(find(a)!=find(b)){ // 사이클이 발생하지 않을 경우 집합에 포함
        	union(a,b);
            result += cost;
            }
       }
     
     


}

 

위상정렬

  • 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘.
  • 방향 그래프의 모든 노드를 방향을 거스르지 않고 순서대로 나열하는 것
  • 진입차수란 특정한 노드로 들어오는 간선의 개수를 의미.
  1. 진입차수가 0인 노드를 큐에 넣는다.
  2. 큐가 빌때까지 다음의 과정을 반복하는 알고리즘이다.
  3. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.
  4. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.

 

최단 경로 알고리즘

말 그대로 가장 짧은 경로를 찾는 알고리즘.

 

총 3가지로 나뉜다.

  1. 한 지점에서 다른 특정 지점까지 최단 경로를 구하는 경우
  2. 한 지점에서 다른 모든 지점까지 최단 경로를 구하는 경우
  3. 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우

최단 경로 알고리즘은 보통 그래프로 표현하고 지점은 노드, 길은 간선이다.

 

다익스트라 알고리즘

 

특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산하는 알고리즘

음의 간선이 존재하지 않을때 사용할 수 있는 알고리즘이다.

 

  1. 출발 노드를 설정하고
  2. 최단 거리 테이블을 초기화 한다.
  3. 방문하지 않은 노드들 중 가장 최단 거리가 짧은 노드를 선택한다.
  4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
  5. 위 두 과정을 반복한다.

 

int Max = Integer.MAXVALUE;

static int [] distance;
static ArrayList<ArrayList<Node>> graph;

class Node implements Comparable<Node>{ // priority que를 사용하기 위한 클래스
	int index;
    int cost;
    
    public Node (int index, int cost){
    	this.index=index;
        this.cost = cost;
    }
    @Override
    public int CompareTo(Node o){
    	if(this.cost<o.cost)
        	return -1;
        else
        	return 1;
   }
}

public static void main(String args[]){
	graph = new ArrayList<>();
	
    int start = 0; //시작 지점
    
    for(int i = 0 ; i<=n; i++){ // 대충 입력값이랑 초기화 작업했다고 가정
    	graph.add(new ArrayList<Node>);
    }
    
    distance = new int[N+1];
    Arrays.fill(distance, Max);
    
    dijkstra(start);
	
    for(int i = 1; i<distance.length; i++){
    	if(distance[i] == Max)
        	INFINITY;
        else
        	distance[i];
}

public static void dijkstra(int start){
	PriorityQueue<Node> que = new PriorityQueue<>();
    que.offer(new Node(start,0)); // 시작 노드를 큐에 넣는것 으로 시작
    distatnce[start]=0; // 시작 노드의 거리 값은 당연히 0으로 설정
    
    while(!que.isEmpty){ //큐가 빌 때 까지 반복
    	int[] nowdata = que.poll();
        int now = nowdata[0];
        int dist = nowdata[1];
        if (distance[now] < dist) // 이미 처리된 노드일 경우 건너뛴다.
        	continue;
        for(int i = 0; i< graph[now].size(); i++){ // 현재 노드와 인접한 다른 노드들 확인
        	int cost = dist + graph.get(now).get(i).cost; 
            if(cost < distance[graph.get(now).get(i).index]){
            //현재 노드를 거쳐 다른 노드로 이동하는 거리가 더 짧을 경우 거리를 갱신해준다.
            	distance[graph.get(now).get(i).index] = cost;
                que.add(new Node(graph.get(now).get(i).index, cost);
                }
        }
    

}

 

힙(HEAP)

우선순위 큐를 구현하기 위한 자료구조 중 하나.

우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 꺼낸다.

데이터를 우선순위에 따라 처리하고 싶을 때 사용한다.

 

플로이드 워셜 알고리즘

 

모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 사용하는 알고리즘.

 

다익스트라는 단계마다 최단 거리를 가지는 노드를 하나씩 반복적 선택하며 해당 노드를 거쳐가는 경로를 확인하고 거리 테이블을 갱신하는 방식으로 동작한다.

플로이드 워셜 또한 단계마다 거쳐 가는 노드를 기준으로 수헹한다. 하지만 매번 방문하지 않은 노드중에서 최단거리를 갖는 노드를 찾을 필요는 없다.

 

노드의 개수가 N개일 때 단계 마다 N^2연산을 N번 수행한다 즉 N^3의 알고리즘 이다.

다익스트라의 경우 출발 노드가 1개이므로 다른 모든 노드까지의 최단거리를 저장하기위해 1차원 리스트를 이용한다.

반면 플로이드 워셜의 경우 2차원 리스트에 최단 거리 정보를 저장한다는 특징이 존재한다. 모든 노드에 대하여 다른 모든 노드로 가는 최단 거리 정보를 담아야 하기 때문이다.

 

다익스트라는 그리디, 플로이드 워셜은 다이나믹 프로그래밍.

 

Dab = min (Dab, Dak+Dkb)

int[][] graph = new int [N][N];

for(int i = 0; i< graph.length; i++){
	Arrays.fill(graph[i],Inetger.MAXVALUE);
}

for(int i = 0; i<graph.length; i++){
	for(int j = 0; j< graph[i].length; j++){
    	if(i==j)
        	graph[i][j]=0;
            }
   }
   
 for(int i = 0; i<graph.length; i++){
 	for(int j = 0; j<graph.length; j++){
    	for(int k = 0; k<graph.length; k++){
        graph[j][k] = Math.min(graph[j][k],(graph[j][i]+graph[i][k]));
    	}
   	}
 }
 
 for(int i=0; i<graph.length; i++){
 	for(int j=0; j<graph.length; j++){
    	if(graph[i][j] == Integer.MAXVALUE)
        	INFINITY;
        else
        	graph[i][j]          
        }
 }