sncap Style

최단경로 구하는 알고리즘 : BFS , 다익스트라, 밸만포드 , SPFA, 플로이드와샬 1) 음수 싸이클이 없는 경우 : BFS. 다익스트라2) 음수 싸이클이 있는경우 : 밸만포드, SPFA(밸만포드 개선알고리즘)3) 각 정점사이의 모든 최단경로 문제 : 플로이드와샬 SPFA( Shortest Path Faster Alogrithm) : 음수사이클이 있거나 없거나 모두 사용할 수 있고, 밸만포드 시간복잡도가 O(|V||E|) 인데 반해 SPFA 는 시간복잡도가 O(|E|)임으로 훨씬 빠르게 구현할 수 있다. 뿐만 아니라 구현하는것도 어렵지 않다. 일반적으로 밸만포드와 같은 흐름의 알고리즘을 따르면서 , QUEUE를 우선순위 큐가 아닌 일반큐를 사용하고, 매번 dist 값은 업데이트하지만, qu..

좌표 이동 경우의 수 구하기기본 nCr 문제이다. S A E N x M 의 경우 이며,이동시 경유지점 혹은 도착지점의 경우의 수를 구하면 된다.이동은 왼쪽 > , 아래 V 로 만 이동 가능하다.- 직항 : 출발 (S) > 도착(E)은 출발 점의 수 부터 nCr- 경유 : (출발(S) > 경유(A)) 의 수 x (경유(A) > 도착(E)) 의 수 nCr1 x nCr2[공식]일반 코드n C r = (n-1)C(r-1) + (n-1)C(r) DP code 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] = (bin..

세그먼트 트리는 구간 정보로 사용자가 원하는 아무 값이나 저장해 두는데, 가장 대표적인 사용 예는구간에 속한 원소들의 합구간에 속한 원소들의 곱구간 원소들 중 최댓값구간 원소들 중 최솟값등의 활용처가 있습니다. /** * @param L- 구하고자 하는 범위의 좌측 값 * @param R- 구하고자 하는 범위의 우측 값 * @param nodeNum - 현재 위치 (1번은 root이다.처음에는 1번부터...) * @param nodeL - 현재 nodeNum 값의 범위 중 좌측 값 * @param nodeR - 현재 nodeNum 값의 범위 중 우측 값 * @return */ public static int sum(int L, int R, int nodeNum, int nodeL, int nodeR) {..

이진탐색 방법top boundary 찾을 때int low = 1, high = N, mid; int A[N]; int M, ans; while (low = M){ high = mid - 1; ans = mid; }else if (A[mid] < M) { low = mid + 1; } //else break; } Bottom boundary 찾을 때int low = 1, high = N, mid; int A[N]; int M, ans; while (low M){ high = mid - 1; }else if (A[mid]

기존 Union Find 에서 Group관련 기능이 추가된 code static class DJS{ int[] mom; // grouping int[] cnt; // member count int gnum; // group count public DJS(int n) { mom = new int[n+1]; cnt = new int[n+1]; gnum = n; for (int i = 1; i < n; i++) { mom[i] = i; cnt[i] = 1; } } public int getMom(int n){ if(n==mom[n]) return n; mom[n] = getMom(mom[n]); return mom[n]; } public boolean isSame(int a, int b){ return (ge..

다익스트라 알고리즘 private static void dijkstra(int s, int[] dist) {for (int i = 1; i dist[nd.e] + node.c) {dist[node.e] = dist[nd.e] + node.c;pq.add(new Node(n..

Binary Index Tree를 이용한 풀이를 해야 한다.주요 알고리즘void add(int h, int v){for (int i = h; i 0 ; i-=(i&-i)){r+=tree[i];}return r;} 미리 합을 구해 놓고, 변경되는 내용에 대해서는 다시 차이값을 저장한다. static void add(int h, int v, long[] ar) {for (int i = h; i 0; i-=(i&-i)) result+=ar[i];return result;}

int lower_bound(int arr[], int target, int size) { int mid, start, end; start = 0, end = size-1; while (end > start) // end가 start보다 같거나 작아지면, 그 값이 Lower Bound이므로 반복을 종료한다. { mid = (start + end) / 2; if (arr[mid] >= target) // 중간값이 원하는 값보다 크거나 같을 경우, 끝값을 중간값으로 설정하여 다시 탐색한다. end = mid; else start = mid + 1; // 중간값이 원하는 값보다 작을 경우, 시작값을 중간값+1로 설정하여 다시 탐색한다. } return end; }

세그먼트 트리 공식 void build(int id = 1, int l=0, int r=n){ if(r-l=y)return 0; if(x

세그먼트 트리는 구간 정보로 사용자가 원하는 아무 값이나 저장해 두는데, 가장 대표적인 사용 예는구간에 속한 원소들의 합구간에 속한 원소들의 곱구간 원소들 중 최댓값구간 원소들 중 최솟값등의 활용처가 있습니다. /** * @param L- 구하고자 하는 범위의 좌측 값 * @param R- 구하고자 하는 범위의 우측 값 * @param nodeNum - 현재 위치 (1번은 root이다.처음에는 1번부터...) * @param nodeL - 현재 nodeNum 값의 범위 중 좌측 값 * @param nodeR - 현재 nodeNum 값의 범위 중 우측 값 * @return */ public static int sum(int L, int R, int nodeNum, int nodeL, int nodeR) {..