Java 알고리즘 프레임워크

BFS

public static int[] bfs(List<ArrayList<Integer>> graph, int st) { // 비공변
	int[] dist = new int[10005];

	LinkedList<Integer> q = new LinkedList<>();
    q.offer(st);	
    dist[st] = 1;

	int[] ret = { st, dist[st]};
    while (!q.isEmpty()) {
    	int cur = q.poll();
        List<Integer> nexts = graph.get(cur);
        for (int next : nexts) {
        	if (dist[next] != 0) continue;
            	dist[next] = dist[cur] + 1;
				if (dist[next] > ret[1]) {
					ret[0] = next;
					ret[1] = dist[next];
				}
				q.offer(next);
			}
		}
		return ret;
	} 
}

---

Binary Search

public static int bs(int[] nums, int st, int lst, int key) {
	while (st <= lst) {
    	int mid = (st + lst) >>> 1;
        if (nums[mid] < key) {
        	st = mid + 1;
        } else if (nums[mid] > key) {
        	lst = mid - 1;
        } else {
        	return mid;
        }
    }
    return -(st + 1);
}

---

Union Find

static int[] ranks = new int[100];
static int[] belongsTo = new int[100];
for (int i = 0; i < 100; i++) {
	ranks[i] = 1;
    belongsTo[i] = i;
}

public static int find(int n) {
	if (belongsTo[n] == n) return n;
    belongsTo[n] = find(belongsTo[n]);
    return belongsTo[n];
}

public staic void union(int lhs, int rhs) {
	int lRoot = find(lhs);
	int rRoot = find(rhs);
    
    if (lRoot == rRoot) return;
    if (ranks[lRoot] == ranks[rRoot]) {
    	belongsTo[rRoot] = lRoot;
    	ranks[lRoot]++;
    } else if (ranks[lRoot] < ranks[rRoot]) {
    	belongsTo[lRoot] = rRoot;
    } else {
    	belongsTo[rRoot] = lRoot;
    }
}

---

연속된 정수 리스트 만들기

import java.util.stream.*; // Collectors.toList()
import java.util.*;

List<Integer> nums = IntStream.rangeClosed(1, 6)
.boxed()
.collect(Collectors.toList());

---

Permutation

List<ArrayList<Integer>> permu = new ArrayList<>();

public void permutation(int[] baseArr, int cur, int target, List<Integer> curPermu, List<ArrayList<Integer>> permu) {
	if (cur >= target) {
    	permu.add(new ArrayList<>(curPermu));
        return;
    }
    for (int i = 0; i < baseArr.length; i++) {
    	curPermu.add(baseArr[i]);
        permutation(baseArr, cur + 1, target, curPermu, permu);
        curPermu.remove(curPermu.size() - 1);
    }
}

---

Combination

List<ArrayList<Integer>> comb = new ArrayList<>();

public void combination(int[] baseArr, int cur, int target, int start, List<Integer> curComb, List<ArrayList<Integer>> comb) {
	if (cur >= target) {
    	comb.add(new ArrayList<Integer>(curComb));
        return;
    }
    for(int i = start; i < baseArr.length; i++) {
    	curComb.add(baseArr[i]);
        combination(baseArr, cur + 1, target, start + 1, curComb, comb);
        curComb.remove(curComb.size() - 1);
    }
}

중복 순열 조합은 baseArr 의 각 원소의 수를 target 만큼 만들면 된다.

BFS