CS/Algorithm

[알고리즘] 플로이드-워샬 알고리즘

플로이드-워샬 알고리즘 모든 쌍 최단 경로 알고리즘: 모든 정점 쌍 사이의 최단 경로를 구하는 방법 단순 최단 경로 알고리즘 m개의 간선을 사용해서 i에서 j까지 이르는 최단거리 모든 정점 k에 대해 최대 m-1개의 간선을 사용해서 i에서 k까지 이르는 최단거리 $d_{ik}^{m-1}$에다가 $w_{kj}$를 더한 값을 구하고, 이 중 가장 짧은 것을 택함 for (i=1 to n) for (j=1 to n) d(i to j, k=0) = w[i][j]; for (m=2 to n-1) for (i=1 to n) for (j=1 to n) d(i to j, k=m) = min(d(i to k, k=m-1) + w[k][j]) 시간 복잡도: $\theta(n^4)$ 플로이드-워샬 $d_{ij}^{k}$ =..

[알고리즘] 위상 정렬 Topological Sort (자바 Java)

위상 정렬 사이클이 없는 유향 그래프 G=(V,E)에서 V의 모든 정점을 정렬 간선 (i, j)가 존재하면 정점 i는 반드시 j보다 앞에 위치 방식 1: 큐 활용 topologicalSort(G, V) { for i

[알고리즘] 유니온-파인드 (Union-Find) (자바 Java)

목차 유니온 파인드 (Union-Find) 서로소 집합(Disjoint-sets) 서로 중복 포함된 원소가 없는 집합들 → 교집합이 없다 집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분, 이를 대표자(representative)라고 함 연산 Make-Set(x): 원소 x로만 구성된 집합을 만든다 Find-Set(x): 원소 x를 가진 집합을 알아낸다 Union(x, y): 원소 x를 가진 집합과 원소 y를 가진 집합을 하나로 합친다 표현 방법 연결 리스트, 트리 1. 연결 리스트 같은 집합의 원소들은 하나의 연결리스트로 관리 연결리스트의 맨 앞의 원소를 집합의 대표원소로 삼음 각 원소는 집합의 대표원소를 가리키는 링크를 갖는다 2. 트리 하나의 집합을 하나의 트리로 표현 자식 노드가 부모노드를 ..

[알고리즘] 최단 경로 알고리즘 - 다익스트라(Dijkstra), 벨만-포드 (Bellman-Ford) (자바/Java)

목차 최단 경로 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중 간선의 가중치의 합이 최소인 경로 하나의 시작 정점에서 끝 정점까지의 최단 경로 다익스트라 (dijkstra): 음의 가중치 허용x 벨만-포드(Bellman-Ford) : 음의 가중치 허용o 모든 정점들에 대한 최단 경로 플로이드-워샬(Floyd-Warshall) 알고리즘 1. Dijkstra 알고리즘 시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식 탐욕 기법을 사용 - 프림 알고리즘과 유사 시작 정점(s)에서 끝 정점(t)까지의 최단 경로에 정점 x가 존재 이때 최단 경로는 s에서 x까지의 최단 경로와 x에서 t까지으 ㅣ최단 경로로 구성됨 s→t = s→x + x→t 시간복잡도 : O(ElogV) 과..

[알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree) (자바/Java)

목차 최소 신장 트리 (MST) 신장트리: 그래프의 모든 정점과 간선의 부분 집합으로 구성되는 트리 최소신장트리: 신장 트리 중에서 사용된 가중치의 합이 최소인 트리 특징 무방향 가중치 그래프 그래프의 가중치 합이 최소여야 한다 N개의 정점을 가지는 그래프에 대해 반드시 N-1개의 간선을 사용 사이클을 포함하면 안된다. 크루스칼 알고리즘 간선을 하나씩 선택해서 MST를 찾는 알고리즘 최초, 모든 간선을 가중치에 따라 올므차순으로 정렬 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가 사이클이 존재하면 다음으로 가중치가 낮은 간선 선택 (사이클 존재: 대표가 같으면 사이클(Find-Set)) n-1개의 간선이 선택될 때까지 2)를 반복 Kruskal(G) { A

[알고리즘] 최장 공통 부분 수열 (Longest Common Subsequence LCS)

목차 LCS (Longest Common Subsequence) 최장 공통 부분 수열 LCS의 길이 찾기 $$ x_m = y_n 이면 LCS(X_m, Y_n) = LCS(X_{m-1}, Y_{n-1})+1 $$ $$ x_m \neq y_n 이면 LCS(X_m, Y_n) = max(LCS(X_{m-1}, Y_{n}), LCS(X_{m}, Y_{n-1})) $$ https://velog.io/@emplam27/알고리즘-그림으로-알아보는-LCS-알고리즘-Longest-Common-Substring와-Longest-Common-Subsequence 문제 예시 9251번: LCS C[i-1][j] = A의 i-1번째, B의 j번째까지의 LCS Xi와 Yj가 같지 않다면 새로운 값을 추가할 수 없으니, 이전의 LC..

[알고리즘] 비트 연산자 & 부분집합 (자바/Java)

비트 연산자 &둘 다 1 이면 1 / 해당 비트가 있는지 검사! System.out.println(3 & 5); // 3 = 011 // 5 = 101 // -------- // 001 -> 1 | 하나라도 1이면 1 System.out.println(3 | 5); // 3 = 011 // 5 = 101 // -------- // 111 -> 7 ^ XOR - 서로 다르면 1 System.out.println(3 ^ 5); // 3 = 011 // 5 = 101 // -------- // 110 -> 6 A >1); // 5 / (2^1) = 2 // 101 -> 010 = 2 부분집합 N개의 원소를 가진 집합에서 전체 부분집합의 개수 = 2^N 1. 재귀 부분집합은 공집합부터 원소가 1개, 2개, … ..

[알고리즘] 너비 우선 탐색 BFS & 깊이 우선 탐색 DFS (자바/Java)

목차 BFS & DFS 그래프에서 모든 정점을 방문하는 방법 [참고] 그래프의 인접 노드 구현 1. 인접 행렬 n * n 행렬에 (i, j) (j, i)에 1 (또는 가중치)를 할당 장점 이해하기 쉬움 간선의 존재 여부를 빠르게 알 수 있음 단점 n^2에 해당하는 공간이 필요 모든 원소를 채우는 데에도 시간이 오래 걸림 2. 인접 리스트 보통 연결 리스트를 사용, 각 정점마다 인접한 정점들을 연결 리스트에 표현 장점 행렬에 비해 공간 낭비가 없다. (간선의 총 수에 비례하는 양만큼만 공간이 필요) 단점 만약 거의 모든 정점에 대해 간선이 존재한다면 (dense) 연결 리스트의 정보를 표현하기 위한 오버헤드가 많이 든다. 간선이 존재하는지 알아볼 때 리스트에서 차례로 훑어야 하기 때문에 인접 행렬보다 시간..

[알고리즘] 기본 수학 - 순열 조합 중복순열 중복조합 (자바/Java)

순열/조합 순열, 조합, 중복 순열, 중복 조합을 dfs를 이용하여 구할 수 있다. 백준의 N과 M시리즈가 순열/조합을 공부하기 좋은 문제들이다. https://www.acmicpc.net/workbook/view/2052 1. 순열 순열은 N개의 수에서 R개의 수를 뽑아 순서대로 나열하는 것이다. {1, 2, 3, 4} 4개의 수에서 2개의 수를 뽑아 나열하는 경우의 수는 {1, 2} {1, 3} {1, 4} {2, 1} {2, 3} {2, 4} {3, 1} {3, 2} {3, 4} {4, 1} {4, 2} {4, 3} 의 12가지다. $$ nPr = n*(n-1) * ... (n-r+1) $$ 순열을 구하기 위해서는 dfs를 활용한다. static void dfs(int N, int M, int cn..

[알고리즘] 조합론 - 이항 계수 (자바/Java)

목차 조합론 이항계수 https://shoark7.github.io/programming/algorithm/3-ways-to-get-binomial-coefficients 정의 이항 계수는 집합에서 원하는 개수만큼 순서없이 뽑는 조합의 가짓수를 의미한다. 즉 nCr을 구하는 알고리즘이다. 구현 1: 팩토리얼 이용 $$ nCk = \frac{n!}{{n-k}!*k!} $$ 첫 번째 정의는 팩토리얼 재귀함수를 이용하여 알고리즘으로 구현할 수 있다. public class MyBinoCo { public static void main(String[] args) { int N = 10; int K = 3; // 팩토리얼 System.out.println(fact(N) / fact(N - K) / fact(K))..