내가 보려고 적는 알고리즘 총정리 - 1편

본 포스트는 JAVA 를 기준으로 작성되었습니다 😊

 

1. 다익스트라, 플로이드워셜

다익스트라, 플로이드 워셜 그 차이에 대하여 !!

 

우선 다익스트라는 한 지점에서 다른 지점으로 가는 최단 거리를 구한다 ! 

즉, 모든 지점을 확인하려면 지점마다 돌려서 확인을 해야된다 !

정점의 수를 V, 간선의 수를 E 라 했을 때, 위의 경우 시간복잡도는 (우선순위 큐를 사용했다는 전제하에 ) O(VE logV) 가 될 것이다!

근데 만약, 간선이 굉장히 많은 경우라면 ..? E = V^2 이라면 ? O(V^3 logV) 가 된다 (비효율적..🤔)

 

이 때 플로이드 워셜은 모든 쌍에 대한 최단 거리를 구해준다

이 알고리즘은 매우 쉬운 3중 반복문인데 O(V^3)으로 비효율적으로 보일 수 있다..! 하지만!

앞서 언급한 다익스트라을 사용하기 안좋은 경우엔, 

정점의 수가 많지 않거나, 모든 쌍에 대한 최단 거리를 구해야만 할 때엔 플로이드 워셜을 사용하는 것이 좋다 😁

 

1. 다익스트라

특정 시작점에서 다른 모든 정점으로 가는 최단거리를 구해줘 !

 

무조건 우선순위 큐를 사용하자

 

우선 시작점을 정하고, 그 시작점으로부터의 거리를 구할 dist 배열을 만든다!

시작점(dist = 0)을 제외한 나머지 정점의 dist 를 INF 로 설정한다

 

우선순위 큐는 이 거리값을 넣어 연결된 값중에 가장 최소거리인 다음 정점을 찾아주는 역할을 한다

코드를 보면 이해가 될 것이다

주석을 보며 읽어보자 

public class DijkstraTest {

	public static class Node{
    	int x, dist;
        public Node(int x, int dist) {
        this.x = x;
        this.dist = dist;
    }
    
    }
    public static int N = 5; // 정점 수
    public static ArrayList<Node>[] graph = new ArrayList[N + 1]; //정점 번호를 그대로 사용할 경우
    public static PriorityQueue<Node> pq = new PriorityQueue<>();
    
    public static int[] dist = new int[N + 1];

    public static void main(String[] args) {
        // 정점의 수 : 5, 간선의 수 : 8인 그래프
        int n = 5, m = 8;

        // 그래프를 인접리스트로 표현합니다.
        for(int i = 1; i <= n; i++)
            graph[i] = new ArrayList<>();
        
        for(int i = 1; i <= m; i++) {
            int x = 입력.시작점;
            int y = 입력.도착점;
            int z = 입력.가중치;
            graph[x].add(new Node(y, z));
        }
        
  
        // 초기값 설정
        // INT_MAX 그 자체로 설정하면 덧셈 진행시 overflow가 발생할 수 있음에 유의!!!!
        
        for(int i = 1; i <= n; i++)
            dist[i] = (int)1e9;

        // 시작위치 dist값 = 0
        dist[5] = 0;


        pq.add(new Node(5, 0));

        while(!pq.isEmpty()) {
            // 가장 거리가 가까운 정보 poll
            Node now = pq.poll();
            int nowIndex = now.x;
            int nowDist = now.dist;

            // 우선순위 큐를 이용하면 같은 정점의 원소가 여러 번 들어가는 문제가 발생할 수 있어
            // nowDist가 최신 dist[nowIndex] 보다 크면 어짜피 최소값이 아니므로 pass
            
            if(nowDist > dist[nowIndex])
                continue;

            for(int j = 0; j < graph[nowIndex].size(); j++) {
            	//연결된 정점 체크 -> 시작점으로부터의 최단거리 값을 갱신
                int nextIndex = graph[nowIndex].get(j).index;
                int nextDist = graph[nowIndex].get(j).dist;
                
                // 현재 위치에서 연결된 간선으로 가는 것이 더 작다면
                int newDist = dist[nowIndex] + nextDist;
                if(dist[nextIndex] > newDist) {
                    // 값을 갱신해주고, 우선순위 큐에 add
                    dist[nextIndex] = newDist;
                    pq.add(new Node(nextIndex, newDist));
                }
            }
        }

        // 시작점으로부터 각 지점까지의 최단거리 값
        for(int i = 1; i <= n; i++)
            System.out.print(dist[i] + " ");
    }
}

 

2. 플로이드 워셜

모든 쌍에 대해 최단거리를 구해줘 !
A -> B 로 가는 경로보다 A -> X -> B 로 가는 경로가 더 짧다면 그걸로 갱신!

 

다익스트라 때 처럼 dist 배열은 전부 최댓값 INF 로 채워준다 ( 물론 자기 자신 -> 자기 자신은 0 으로 )

그 다음 과정은 경유해서 가는 경우와, 바로 가는 경우 중 작은 값을 dist 에 갱신해주는 것인데

너무 간단한 알고리즘이라 이 부분만 코드를 작성해보자면,

 for(int k = 1; k <= n; k++){ // 경유지 k (1부터 N)
    for(int i = 1; i <= n; i++){ // 모든 쌍 (i, j)
        for(int j = 1; j <= n; j++){
            // i에서 j로 가는 거리가 k를 경유해 가는 것이 더 좋다면,
            // dist[i][j]값을 갱신
            dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
        }
    }
}

//결과
for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= n; j++) {
        if(dist[i][j] == (int)1e9) // 이동이 불가능 한 경우
            System.out.print(-1 + " ");
        else
            System.out.print(dist[i][j] + " ");
    }
    System.out.println();
}

 

2. Kruskal, Prim

다익스트라, 플로이드 워셜 그 차이에 대하여 !!

간적쿠 간만프 🙋‍♀️

1. 크루스칼

가중치가 작은 간선부터 고른다!

근데 이제, 가중치가 같은 경우엔 아무거나 선택..

근데 이제, 사이클이 발생하면 안되는..

   (MST 를 만족해야하니까!)

 

그럼 사이클은 어떻게 안 발생하게 하는가 ?!

🙋‍♀️ Union - Find

 

두 노드를 union 연산을 수행해야하는데, 만약 두 노드가 이미 같은 union 에 속한 상태이면 합치지 않고 넘어간다!

정리하자면,

간선의 가중치가 작은 것부터 순서대로 보면서, 두 노드의 부모값을 비교하여 일치하지 않은 경우에만 (사이클이 발생하지 않았다는 말) 간선을 선택해주고 union 연산을 진행한다!

 

크루스칼 알고리즘은 정렬한번이면 구현이 가능하다.

간선의 수가 E 일때 정렬에 O(ElogE), 각 간선에 대해 union-find 는 O(logN)이므로 ElogE + ElogN 이 되어 

총 시간복잡도는 O(ElogE) 이다

 

우선, Union-Find 부분 코드는 아래와 같다

private static void union(int a, int b) {
		a = find(a);
		b = find(b);
		if (a > b) {
			parent[a] = b;
		} else {
			parent[b] = a;
		}
	}

	private static int find(int x) {
		if (parent[x] == x)
			return x;
		else
			return find(parent[x]);
	}
}

아래는 크루스칼 알고리즘을 진행하는 코드이다.

		parent = new int[V];
		final_cost = 0;

		// 간선 비용 순으로 오름차순 정렬
		Arrays.sort(graph, (o1, o2) -> Integer.compare(o1[2], o2[2]));

		// makeSet
		for (int i = 0; i < V; i++) {
			parent[i] = i;
		}

		// 낮은 비용부터 크루스칼 알고리즘 진행
		for (int i = 0; i < E; i++) {

			// 사이클이 존재하지 않는 경우에만 간선을 선택한다(여기서는 최종 비용만 고려하도록 하겠다).
			if (find(graph[i][0] - 1) != find(graph[i][1] - 1)) {
				//부모가 다른 경우에만

				System.out.println("<선택된 간선>");
				System.out.println(Arrays.toString(graph[i]));
				union(graph[i][0] - 1, graph[i][1] - 1);
				final_cost += graph[i][2];
				System.out.println("<각 노드가 가리키고 있는 부모>");
				System.out.println(Arrays.toString(parent) + "\n");
				continue;
			}
		}
        System.out.println("최종 비용 : " + final_cost);

 

2. 프림

그래프상에 존재하는 모든 노드들을 최소비용으로 연결시키는 알고리즘,

 

프림 알고리즘은 한 지점에서 시작한다!

아무 정점이나 같은 결과가 나오기때문에, 시작하기 편한 정점에서 시작하면 된다

 

이 정점에서 연결된 간선들 중 가중치가 가장 작은 간선을 고르고, 이 간선이 MST 에 들어가게 된다그 후엔, MST 에 있는 노드들과 연결된 모든 Edge 들을 확인하고, 그 중에서

가중치가 가장 작은 간선을 골라 MST 에 붙여준다

 

프림알고리즘도 우선순위 큐를 사용하는데, 다익스트라 코드와 정확히 2줄만 다르고 나머지는 전부 동일하다.

하지만 다른 부분에 주의해야하는데!

 

다익스트라 알고리즘의 경우, 현재 노드를 n라 했을 때 dist[v]와 dist[n] + length(n, v)를 비교하여 갱신해주는 것이였다면,

prim은 단순히 dist[v]와 length(n, v)를 비교하여 갱신해준다. 즉, 

 

dist 배열을 사용하는데, 프림알고리즘에서의 dist 배열은

현재까지 만들어진 MST 와 노드 x를 연결하기 위해 필요한 최소 비용이다

 

class Edge implements Comparable<Edge>{
	int w; 
	int cost; 
	
	Edge(int  w, int cost){
		this.w = w;
		this.cost = cost;
	}
	
    // 간선 오름차순으로 정렬
	@Override
	public int compareTo(Edge o) {
		return this.cost - o.cost;
	}
}

// 프림 알고리즘
public static void prim(int start, int n) {
	boolean[] visit = new boolean[n + 1];
		
	PriorityQueue<Edge> pq = new PriorityQueue<>();
	pq.offer(new Edge(start, 0));
		
	int total = 0;
	while(!pq.isEmpty()) {
		Edge edge = pq.poll();
		if(visit[edge.w]) continue;
        
		visit[edge.w] = true;
		ans += edge.cost;
		
		for(Edge next : graph[v]) {
			if(!visit[next.w]) {
				pq.add(next);
			}
		}
	}
    
    // 완성된 최소 신장 트리의 총 가중치 합 출력
	System.out.println(ans);
}

 

프림은 다익스트라와 달리 두 노드 사이의 거리가 최단 거리가 아닐 수도 있다!

프림과 다익스트라는 서로를 보장해주지 않는다!

 

3. 순열, 완탐, 조합

각각의 특징에 대해서는 다 아니까 패스

3 미만이면 그냥 for 문 돌리기~

1. 순열 

 

1. 그냥 순열

 

- 중복허용을 안하니까 visit 처리해야 함

public class PermTest {
	
	static int[] p = {1,2,3,4,5};
	static int N = p.length;
	static int R;
	static int count;
	static int [] nums;
	static boolean [] visited;
	static List<int[]> ans = new ArrayList<>();
	
	public static void main(String[] args) {
		R = 3;
		nums = new int [R];
		visited = new boolean[N];
		count = 0;
		perm(0);
		System.out.println(count);
		for (int[] i : ans) {
			System.out.println(Arrays.toString(i));
		}
	}

	private static void perm(int cnt) {
		
		//끝나는 조건 명시
		if (cnt == R) {
			count ++;
			ans.add(nums.clone());
			return;
		}
		
		//그렇지않으면
		for (int i = 0; i < N; i++) {
			if (visited[i]) {
				continue;
			}
			nums[cnt] = p[i];
			visited[i] = true;
			perm(cnt+1);
			visited[i] = false;
		}
		
	}

}

 

 

2. 중복 순열

public class PermTest2 {
	
	static int[] p = {1,2,3,4,5};
	static int N = p.length;
	static int R;
	static int count;
	static int [] nums;
	static boolean [] visited;
	static List<int[]> ans = new ArrayList<>();
	
	public static void main(String[] args) {
		R = 3;
		nums = new int [R];
		visited = new boolean[N];
		count = 0;
		piperm(0);
		System.out.println(count);
		for (int[] i : ans) {
			System.out.println(Arrays.toString(i));
		}
	}

	private static void piperm(int cnt) {
		
		//끝나는 조건 명시
		if (cnt == R) {
			count ++;
			ans.add(nums.clone());
			return;
		}
		
		//그렇지않으면
		for (int i = 0; i < N; i++) {
			
			nums[cnt] = p[i];
			piperm(cnt+1);
		}
		
	}

}

 

2. 조합

 

1. 그냥 조합

 

- 반복문의 시작 인덱스는 start !

public class CombiTest {
	
	static int[] p = {1,2,3,4,5};
	static int N = p.length;
	static int R;
	static int count;
	static int [] nums;
	static boolean [] visited;
	static List<int[]> ans = new ArrayList<>();
	
	public static void main(String[] args) {
		R = 3;
		nums = new int [R];
		count = 0;
		combi(0, 0);
		System.out.println(count);
		for (int[] i : ans) {
			System.out.println(Arrays.toString(i));
		}
	}

	private static void combi(int cnt, int start) {
		
		//끝나는 조건 명시
		if (cnt == R) {
			count ++;
			ans.add(nums.clone());
			return;
		}
		
		//그렇지않으면
		for (int i = start; i < N; i++) {
        //start 부터 시작함에 주의!!
			nums[cnt] = p[i];
			combi(cnt+1, i+1);
		}
		
	}

}

 

2. 중복 조합

 

- 반복문의 시작 인덱스는 0 !! 

public class CombiTest2 {
	
	static int[] p = {1,2,3,4,5};
	static int N = p.length;
	static int R;
	static int count;
	static int [] nums;
	static boolean [] visited;
	static List<int[]> ans = new ArrayList<>();
	
	public static void main(String[] args) {
		R = 3;
		nums = new int [R];
		count = 0;
		combi(0, 0);
		System.out.println(count);
		for (int[] i : ans) {
			System.out.println(Arrays.toString(i));
		}
	}

	private static void combi(int cnt, int start) {
		
		//끝나는 조건 명시
		if (cnt == R) {
			count ++;
			ans.add(nums.clone());
			return;
		}
		
		//그렇지않으면
		for (int i = start; i < N; i++) {
			nums[cnt] = p[i];
			combi(cnt+1, i);
		}
		
	}

}

 

3.  Subset (PowerSet)

	static int[] p = {1,2,3,4,5};
	static int N = p.length;
	static int count;
	static boolean [] visited;
	static List<List<Integer>> ans = new ArrayList<>();
	
	public static void main(String[] args) {
		visited = new boolean[N];
		count = 0;
		powerset(0, 0, 1);
		System.out.println(count);
		for (List<Integer> i : ans) {
			System.out.println(Arrays.toString(i.toArray()));
		}
	}

	private static void powerset(int cnt, int sum, int mul) {
		//if (sum <= 0) return; //필요에 따라 걸러주기 더 진행 가능
		//끝나는 조건 명시
		if (cnt == N) {
			count ++;
			List<Integer> temp = new ArrayList<>();
			for (int i = 0; i < N; i++) {
				if(visited[i]) {
					temp.add(p[i]);
				}
			}
			ans.add(temp);
			System.out.println("--->"+sum);
			System.out.println("--->"+mul);
			return;
		}
		
		//그렇지않으면
		visited[cnt] = true;
		powerset(cnt+1, sum + p[cnt], mul*p[cnt]);
		visited[cnt] = false;
		powerset(cnt+1, sum, mul);
		
	}

}

 

4. Next Permutation & Next Combination

- 1. 꼭대기를 찾아라 ! 

   A[i-1] < A[i] 를 만족하는 가장 큰 i 를 찾는다 -> 꼭대기 찾기

 

- 2. 꼭대기 위치의 i-1 번째가 오른쪽 제일 끝에의 j 인덱스 p[j] 보다 작으면 swap

   j >= i 이면서 A[j] > A[i-1] 을 만족하는 가장 큰 j 를 찾는다

  A[i-1]과 A[j] 를 swap 

  A[i]부터 순열을 뒤집는다

 

public class NextPermTest {
	
	static int[] p = {3,1,2,6,4,5};
	static int count ;
	static int N = p.length;
	
	public static void main(String[] args) {
		do {
			count ++;
			System.out.println(Arrays.toString(p));
		}while (np(N-1));
		System.out.println(count);
	}

	private static boolean np(int size) {
		
		int i = size;
		while(i>0 && p[i-1] > p[i]) i--;
		//A[i-1] < A[i] 를 만족하는 가장 큰 i
		
		if (i == 0) return false;
		//i가 0까지 갔다면 모두 내림차순이었으므로 마지막 순열
		
		int j = size;
		// j >= i 이면서 A[j] >= A[i-1]을 만족하는 가장 큰 j를 찾음
		while(p[i-1] > p[j]) j--;
		
		//A[i-1]과 A[j] 를 swap
		int temp = p[i-1];
		p[i-1] = p[j];
		p[j] = temp;
		
		//A[i]부터 순열을 뒤집음
		int k = size;
		while(i < k) {
			temp = p[i];
			p[i] = p[k];
			p[k] = temp;
			i++;
			k--;
		}
		return true;
	}

}

 

그럼 조합은..? 부등호에서 같음 체크만 추가 하면됨!

public class NextCombiTest {
	
	static int[] p = {0,0,0,1,1,1};
	static int[] n = {1,2,3,4,5,6};
	static int count ;
	static int N = p.length;
	
	public static void main(String[] args) {
		do {
			count ++;
			for (int i = 0; i < N;i++) {
				if (p[i] == 1) {
					System.out.print(n[i] + " ");
				}
			}
			System.out.println();
			System.out.println(Arrays.toString(p));
		}while (np(N-1));
		System.out.println(count);
	}

	private static boolean np(int size) {
		
		int i = size;
		while(i>0 && p[i-1] >= p[i]) i--;
		//A[i-1] < A[i] 를 만족하는 가장 큰 i
		
		if (i == 0) return false;
		//i가 0까지 갔다면 모두 내림차순이었으므로 마지막 순열
		
		int j = size;
		// j >= i 이면서 A[j] >= A[i-1]을 만족하는 가장 큰 j를 찾음
		while(p[i-1] >= p[j]) j--;
		
		//A[i-1]과 A[j] 를 swap
		int temp = p[i-1];
		p[i-1] = p[j];
		p[j] = temp;
		
		//A[i]부터 순열을 뒤집음
		int k = size;
		while(i < k) {
			temp = p[i];
			p[i] = p[k];
			p[k] = temp;
			i++;
			k--;
		}
		return true;
	}

}

 

4. KMP (부분문자열)

: KMP 는 문자열이 다른 문자열의 부분문자열로 나타나는지 판단하는데 사용된다. 우리가 흔히 아는 for 문을 통한 완전 탐색을 하면 시간복잡도가 매우 커질수 있는데, 이 알고리즘을 사용할 경우 O(N+M) 에 구현이 가능하다

KMP 알고리즘은 우선 패턴배열, text 배열 으로 나누어 사용해야한다text 배열은 말그대로, 전체 문자열을 toCharArray()를 통해 넣어둔다.먼저, 부분일치테이블을 만들어야하는데 이것이 패턴배열이다.패턴배열은 

문자열 P에서 [1, i]로 이루어진 문자열 중 접두사와 접미사가 일치하는 최장 길이를 뜻한다.

아래 코드를 살펴보자,  i 는 접미사 포인터이다.

int pl = pattern.length;
pi = new int[pl];

for(int i = 1, j = 0; i < pl; i++){
//[1 , i-1] 까지는 정확히 길이 j 만큼 접두사와 접미사가 일치할때
    while(j > 0 && pattern[j] != pattern[i]){
        j = pi[j-1];
    }
    if (pattern[j] == pattern[i]){
    //일치하지 않는다면 j 값을 이동한다
        pi[i] = ++j;
    }
    else{
        pi[i] = 0;
    }
}

이렇게 부분일치테이블을 완성하면, 찾으려는 문자열을 쉽게 검색할 수 있는 바탕이 완성된 것이다

이제 남은 일은 패턴 테이블과 찾으려는 문자열을 비교하여 부분문자열인지 확인하는 방법이다.

for(int i = 0, j = 0; i < tl; i++){
//i : 텍스트 포인터, j : 패턴포인터
    while(j > 0 && pattern[j] != text[i]){
        j = pi[j-1];
    }
    if (pattern[j] == text[i]){ //두 글자가 일치한다면
        if (j == pl - 1){ //j 가 패턴의 마지막 인덱스라면
            idx.add(i - j + 1);
            ans ++;
            j = pi[j];
        }
        else{
            j++;
        }

    }
}

설명으로는 이해가 어려울 수 있어 예제 백준문제 하나 풀어보는 것을 추천한다 👍

https://www.acmicpc.net/problem/1786

1786번: 찾기