sncap Style

* 다익스트라 static int Dijkstra(int s, int e) { PriorityQueue pq = new PriorityQueye(); Arrays.fill(D, Integer.MAX_VALUE); Node cu = new Node(s, 0); pq.add(cu); while(!pq.isEmpty()){ cu = pq.poll; if(cu.e == e) return cu.c; for(Node nd : list[cu.e]) { if(D[nd.e] > cu.c + nd.c) { D[nd.e] = cu.c + nd.c; pq.add(new Node(nd.e, (cu.c+nd.c) ); } } } return -1; } * 조합 (nCr) static int nCr(int n, int k) { i..

www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 증가하는 부분수열을의 개수를 구하는 문제이다. 그동안 DP나 TreeSet.ceiling 을 이용해서 구했는데.. ArrayList를 이용해서 구하면 많이 바르다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.C..

간선으로 연결하려는 두 노드가 이미 같은 집합으로 포함된 것인지를 판단해줌. 간략 코드 static class DJS { int[] mom; DJS(int n) { mom = new int[n+1]; for (int i = 1; i

void update(int node, int start, int end, int index, int val) { if (index end) return; if (start == end) { tree[node] = val; return; } update(tree, node * 2, start, (start + end) / 2, index, val); update(tree, node * 2 + 1, (start + end) / 2 + 1, end, index, val); tree[node] = tree[node * 2] + tree[node * 2 + 1]; } int query(int node, int start, int end, int i, int j) { if (jend) return 0; if (i..

기본적인 BIT(Binary Index Tree : 펜윜트리) 는 빠르게 값을 변경하고, 누적합을 찾을때 사용되는 알고리즘 이다. 하지만, 순차 광역 .. 예를 들어 [a~b] 까지 값을 v 만큼 더해준다... 이런건 어떻게 할까? 이 알고리즘이 바로 Binary Indexed Tree Range Update 임. [참조 : 기타 Index tree 관련 설명은 아래 참조 ] https://medium.com/@harekrishnamahto18/range-sum-and-update-in-arrays-competitive-programming-82ae5039a16f Range Update에 대한 부분은 아래 상세 내용 참조 https://kartikkukreja.wordpress.com/2013/12/02..

[Lower Bound] static int lower_bound(ArrayList arr, int target) { int mid, start, end; start = 0; end = arr.size()-1; while (end > start) { mid = (start + end) / 2; if (arr.get(mid) >= target) end = mid; else { start = mid + 1; } } return end; } [Upper Bound] static int upper_bound(ArrayList arr, int target) { int mid, start, end; start = 0; end = arr.size()-1; while (end > start) { mid = (start..

static int solution(int n, int[][] data) { // 좌표 압축 ArrayList xList = new ArrayList(); ArrayList yList = new ArrayList(); for (int i = 0; i < n; i++) { xList.add(data[i][0]); yList.add(data[i][1]); } ArrayList uniqueXList = new ArrayList(new HashSet(xList)); ArrayList uniqueYList = new ArrayList(new HashSet(yList)); Collections.sort(uniqueXList); Collections.sort(uniqueYList); // 구간합 배열 int[][] ..

절단점 찾는 알고리즘과 싸이클 찾은 알고리즘은 둘다 DFS방식을 이용하지만, 미묘하게 다르다..뭐가 다를까?. 절단선 = 단절선. (Bridge : 단절선) int dfs(int A, int parent) : A와 A의 자식 노드가 A에서 parent노드로 가는 간선을 사용하지 않고 도달할 수 있는 정점 중 가장 먼저 dfs함수가 방문한 정점을 반환한다. static int dfs(int s, int p, int d) { // start, parent, depth D[s]=d; int ck = d; for (Object des : list[s]) { Node nd = (Node)des; if(nd.e==p) continue; if(D[nd.e]==0) { int re = dfs(nd.e, s, d+1);..

리스트에서 순환되는 점 찾기근데 어렵다. public class Main { private static int[] s; private static int[] p; private static int n; private static int T; private static boolean[] vis; private static boolean[] fin; private static int cnt; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = null; T = Integer.parseInt..

기본 이항개수 알고리즘 static int binomial(int n, int k) { if(BI[n][k]>0){ return BI[n][k]; } else if(k==0 || n==k){ return BI[n][k] = 1; } else return BI[n][k] = (binomial(n-1, k-1) + binomial(n-1, k)) % MOD;} BigIntger로 푸는 방법 public class boj2407 { static int N, M; static BigInteger BI[][]; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStream..