// 재귀
public long gcd(int w, int h) {
if (h == 0) {
return w;
}
return gcd(h, w % h);
}
// 반복문
public static long gcd2(int w, int h) {
int n;
if (w < h) {
int temp = w;
w=h;
h = temp;
}
while (h != 0) {
n = w % h;
w=h;
h = n;
}
return w;
}(각 숫자 / 최대공약수) * 최대공약수 // 두 개만 비교할 때에 두 수의 곱 / 최대공약수가 최소공배수가 됨
public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9};
int[] combArr = new int[3];
boolean[] visit = new boolean[5];
// combination(visit, 5, 3, 0, arr);
permutation(visit, 5, 3, arr, combArr, 0);
}
private static void combination(boolean[] visit, int totalCount, int leftPick, int start, int[] givenArr) {
if (leftPick == 0) {
for (int i = 0; i < visit.length; i++) {
if(visit[i]) System.out.print(givenArr[i]+" ");
}
System.out.println();
return;
}
for (int i = start; i < totalCount; i++) {
visit[i] = true;
combination(visit, totalCount, leftPick - 1, i + 1, givenArr);
visit[i] = false;
}
}
private static void permutation(boolean[] visit, int totalCount, int pick, int[] givenArr, int[] combArr, int index) {
if (pick == index) {
for (int i = 0; i < 3; i++) {
System.out.print(combArr[i]+" ");
}
System.out.println();
return;
}
for (int i = 0; i < totalCount; i++) {
if(visit[i]) continue;
combArr[index] = givenArr[i];
visit[i] = true;
permutation(visit, totalCount, pick, givenArr, combArr, index + 1);
visit[i] = false;
}
}LowerBound : 찾고자 하는 값 이상이 처음 발견되는 위치를 찾기 위한 알고리즘
UpperBound : 찾고자 하는 값 초과 값이 처음 발견되는 위치를 찾기 위한 알고리즘
// lowerBound
private static int lowerBound(List<Integer> value, int score) {
int left = 0;
int right = value.size(); //해당 list의 가장 큰 값 보다 큰 값이 들어올 수 있으니 size()로 시작
while (right > left) {
int mid = (left + right) / 2;
if (value.get(mid) < score) {
left = mid + 1;
continue;
}
right = mid;
}
return right;
}
//upperBound
private static int upperBound(List<Integer> value, int score) {
int left = 0;
int right = value.size();
while (right > left) {
int mid = (left + right) / 2;
if (value.get(mid) <= score) { //lowerBound와 이곳이 다름. lowerBound는 같아도 시작점을 찾아야 하니 좌측으로 이동, upperBound는 같으면 그 초과값을 찾아야하니 우측으로 이동이라고 생각하면 된다.
left = mid + 1;
continue;
}
right = mid;
}
return right;
}모든 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘
for (int i = 1; i < length; i++) {
for (int j = 1; j < length; j++) {
for (int k = 1; k < length; k++) {
if (adjDistance[j][i] == 1 && adjDistance[i][k] == 1) {
adjDistance[j][k] = 1;
}
}
}
}위의 코드는 프로그래머스 순위 문제의 코드이다. 형식은 같다.
i -> j, j -> k 일 때에 i -> k 가 가능하다가 기본전제이다. 유의할 점은 가운데 끼는 정점이 기준이 되어야 한다.
따라서 위의 코드를 보면 알 수 있듯이 첫 번째 for문의 변수인 i가 중간에 끼는 점인 것을 알 수 있다.
위의 조건식인 if (adjDistance[j][i] == 1 && adjDistance[i][k] == 1) 을 문제에 맞게 변환해서 사용하면 된다.
프림 알고리즘과 크루스칼 알고리즘은 MST(Minimum Spanning Tree)를 구하는 알고리즘이다.
프림은 정점을 기준으로 삼고, 크루스칼은 간선을 기준으로 삼는다.
프림 : O(n^2)
크루스칼 : O(e log(2e))
간선이 많다면 프림, 그렇지 않다면 크루스칼을 사용하면 된다.
프림 알고리즘
public static class Edge implements Comparable<Edge> {
public int to;
public int weight;
public Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
@Override
public int compareTo(Edge o) {
return this.weight - o.weight;
}
}
public static int solution(int n, int[][] costs) {
int[][] adj = new int[n][n];
for (int[] cost : costs) {
adj[cost[0]][cost[1]] = cost[2];
adj[cost[1]][cost[0]] = cost[2];
}
return prim(n, adj);
}
private static int prim(int n, int[][] adj) {
Queue<Integer> edgeQue = new LinkedList<>();
PriorityQueue<Edge> pq = new PriorityQueue<>();
boolean[] visit = new boolean[n];
edgeQue.add(0);
int totalWeight = 0;
while (!edgeQue.isEmpty()) {
Integer currentEdge = edgeQue.poll();
visit[currentEdge] = true;
for (int i = 0; i < n; i++) {
if (adj[currentEdge][i] != 0 && !visit[i]) {
pq.add(new Edge(i, adj[currentEdge][i]));
}
}
while (!pq.isEmpty()) {
Edge edge = pq.poll();
if (!visit[edge.to]) {
edgeQue.add(edge.to);
totalWeight += edge.weight;
break;
}
}
}
return totalWeight;
}
//Queue를 사용하지 않고 풀 수도 있다.
private static int prim(int n, int[][] adj) {
PriorityQueue<Edge> pq = new PriorityQueue<>();
boolean[] visit = new boolean[n];
int currentEdge = 0;
int totalWeight = 0;
while (true) {
visit[currentEdge] = true;
for (int i = 0; i < n; i++) {
if (adj[currentEdge][i] != 0 && !visit[i]) {
pq.add(new Edge(i, adj[currentEdge][i]));
}
}
currentEdge = -1;
while (!pq.isEmpty()) {
Edge edge = pq.poll();
if (!visit[edge.to]) {
totalWeight += edge.weight;
currentEdge = edge.to;
break;
}
}
if (currentEdge == -1) {
break;
}
}
return totalWeight;
}크루스칼 알고리즘
싸이클을 확인하기 위해서 유니온 파인드를 이용한다.
public static class Edge implements Comparable<Edge> {
public int from;
public int to;
public int weight;
public Edge(int from, int to, int weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
@Override
public int compareTo(Edge o) {
return this.weight - o.weight;
}
}
public static int solution(int n, int[][] costs) {
int totalWeight = 0;
int[] parent = new int[n];
List<Edge> edges = new ArrayList<>();
Arrays.fill(parent, -1);
for (int[] cost : costs) {
edges.add(new Edge(cost[0], cost[1], cost[2]));
}
Collections.sort(edges);
for (Edge edge : edges) {
if (isCycle(edge.to, edge.from, parent)) {
continue;
}
totalWeight += edge.weight;
union(edge.to, edge.from, parent);
}
return totalWeight;
}
private static void union(int a, int b, int[] parent) {
int aRoot = find(a, parent);
int bRoot = find(b, parent);
if (aRoot == bRoot) {
return;
}
if (aRoot < bRoot) {
parent[bRoot] += parent[aRoot];
parent[aRoot] = bRoot;
return;
}
parent[aRoot] += parent[bRoot];
parent[bRoot] = aRoot;
}
private static boolean isCycle(int to, int from, int[] parent) {
return find(to, parent) == find(from, parent);
}
private static int find(int node, int[] parent) {
if (parent[node] < 0) {
return node;
}
return parent[node] = find(parent[node], parent);
}