서로소 집합에 대한 연산 makeSet(v) 유일한 노드 v를 포함하는 새로운 집합을 생성하는 연산입니다 왜 -1로 초기화 시키는 걸까? index는 음수가 될 수 없기 때문에 편하게 나타내기 위해 음수로 나타냅니다. 그리고 음수는 해당 집합의 "대표자"를 나타내게 됩니다. findSet(v) v를 포함하는 집합을 찾는 연산입니다. 즉, 대표자를 찾는 연산이라고 생각하시면 됩니다. unionSet(u, v) u와 v를 포함하는 두 집합을 "통합"하는 연산, 즉, "대표자"를 같게 해줍니다 v를 포함한 집합의 대표자는 u를 포함하는 집합의 대표자를 가르키게 됩니다 해당 연산들은 나중에 "최소 신장 트리"를 구하는데 필요한 자료구조입니다 코드 static int parent[] = new int[6]; pu..

그래프에서 최소 비용 문제 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리 두 정점 사이의 최소 비용의 경로 찾기 신장 트리 신장 트리는 N개의 정점으로 이루어진 연결 그래프에서 N개의 정점과 N-1개의 간선으로 이루어진 트리입니다. 즉, N-1개의 간선으로 "모든 정점들이 연결"되어있습니다. 당연히 트리이기 때문에 사이클이 존재하면 안됩니다~~ 최소 신장 트리 무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리 구하는 알고리즘으로는 "프림"과 "크루스칼"이 있습니다. 크루스칼 알고리즘 가중치가 가장 작은 간선이 사이클을 만들지 않을 때에만 그리디하게 간선을 추가시킵니다. 간선의 개수가 M개라고 할 때, 시간 복잡도는 가중치로 정렬 : O(MlogM) 간..

그래프 그래프는 정점(Vertex)와 간선(Edge)로 이뤄져있다. 간선은 무방향과 방향, 그리고 가중치의 유무로 나뉠 수 있다. 차수 차수란 정점의 연결된 간선의 수를 의미함. 즉, degree(x)는 정점 x에 연결된 간선의 수를 뜻함. 모든 정점의 차수 합 == 간선 개수의 2배를 만족함. 위 조건은 시간 복잡도에 이용되기 때문에 알아야함. 그래프 저장하는 방법 그래프를 저장하는 방법은 인접 행렬과 인접 리스트가 있다. 서로 장단점이 있다. 기준은 필요 공간, 한 정점에서 다른 정점으로 갈 수 있는지, 한 정점에서 갈 수 있는 정점들을 구할 때으로 나눠봄. 인접 행렬 필요 공간 : O(V^2) 정점의 개수만큼(VxV) 이차원 배열을 만들어야함. 정점 A에서 정점 B로 갈 수 있는지 판단 : O(1)..

에라토스테네스의 체 시간 복잡도 에라토스테네스의 체는 소수를 찾는 방법이다. 대량 소수를 찾는데 최적화된 방법이다. 원래 두 수 사이의 소수를 구하려면 시간 복잡도가 아마 O(N^2)가 걸릴 텐데, 에라토스테네스의 체를 이용하면 O(Nlog(logN))이 된다. 그래서 많은 소수를 구하려면 이 방법을 사용해야 TLE가 걸리지 않는다. 에라토스테네스의 체 개념 소수의 배수들을 체크하여 체크하지 않은 곳이 바로 소수이다. 구하려는 소수의 범위에서 2, 3, 5, 7 ... √n까지의 배수들을 체크하고, 체크하지 않은 곳들을 출력하면 소수들을 구할 수 있다. 에라토스테네스의 체 구현코드 1 2 3 4 5 6 7 8 9 10 11 12 import java.io.*; import java.util.*; publ..

카운팅 정렬 Counting Sort(계수 정렬)은 숫자들의 대소 비교를 하지 않고 나오는 횟수를 가지고 정렬을 하는 알고리즘 방법이다. 숫자가 몇 개 나오는지 센 다음 정렬을 한다. 그래서 시간 복잡도는 O(n)이 나오게 된다. 이번에 카운팅 정렬이라는 것을 처음 보았다. 퀵 정렬, 힙 정렬들의 시간 복잡도는 일반적으로 O(nlogn)으로 정렬 중에 이보다 더 작아질 수 없다고 배웠는데 O(n) 정렬이 있었던 것이다. index를 가지고 정렬을 함 배열의 값은 count의 index로 사용됨. count의 값은 배열의 값이 몇 번 나왔는지 횟수를 의미. count 배열의 값을 누적합으로 변환시킴(이유는 아래에서) count 배열의 값 - 1은 res 배열에서 index를 나타내고, count 배열의 i..

이분 탐색에 있어서, 숫자가 중복인지 아닌지 알아채는 게 중요하다. 중복이면 HashMap을 사용하고 아니면 그냥 일반적으로 풀면 된다. 가장 많이 하는 실수 중에 하나가 범위가 int형인지 int형을 넘어선 long형인지 잘 구분해야한다. 또한, 이분 탐색은 정렬된 상태에서 해야함을 잊지 말아야한다. O(logN)에 특정 값을 찾을 수 있다. Binary Search, Upperbound, Lowerbound 코드를 작성해보자. Binary Search 처음에 while을 빠져나오는 조건에서 궁금한 점이 생겼다. 어떤 코드는 등호가 들어가고, 어떤 코드는 등호가 들어가지 않았다. 차이점은 등호가 들어가게 되면 ed = mid가 되고 등호가 들어가지 않으면 ed = mid - 1로 설정이 되있다. 1 2..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 import java.io.*; import java.util.*; public class Main { static ArrayList ad[]; static boolean[] visit; static int nV,nE; //노드, 간선 갯수 static Queue Q; static LinkedList link; p..

이번에 백준 1325번 문제를 풀고 인접 행렬과, 인접 리스트의 차이에 대해 공부를 했다. 인접 행렬은 2차원배열로 dfs 그래프를 구현한 것이다. 그래서 장점으로는 구현이 쉽고, 노드끼리 연결이 되어있는지 아닌지 O(1)로 쉽게 알 수 있다. fc [i][j]에서 0인지 1인지만 구분하면 되기 때문이다. 단점은 노드 i에 연결되있는 노드들을 확인하기 위해서는 fc [i][0] ~ fc [i][V]까지 전체 노드를 방문해야 하기 때문에 O(V)만큼 걸리기 때문이다. 만약에 노드가 수천만개이고, 간선이 달랑 3,4개라고 생각해보면 노드들이 어떻게 연결되어있는지 알아보기 위해서는 O(V^2)만큼 걸리는데, 간선이 노드에 비해 매우 적기 때문에 손해이다. 그래서 이러한 단점을 커버 치기 위해 인접 리스트가 존..

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 import java.util.*; //dfs 기본 public class Main { static int nV; //정점의 개수 static int nE; //간선의 개수 static boolean[] visit; //방문 배열 static int[][] arr; static int dfs_count(){ int..