sncap Style

리스트에서 순환되는 점 찾기근데 어렵다. 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..

BOJ#2666 벽장문의 이동풀이법을 몰라서 서핑을 통해서 참조함[참조 : http://stack07142.tistory.com/157] * 문제https://www.acmicpc.net/problem/2666 * 풀이1. 문제 이해벽장문을 이동을 열려있는 문이 이동한다는 것으로 바꿔서 생각해봅시다. 훨씬 편하게 문제를 이해할 수 있습니다.열려있는 문은 항상 2개 뿐이므로 하나를 F, 나머지를 S라고 해봅시다. 열려있는 문이 이동하므로 2가지 경우가 발생합니다. 1) F가 이동하는 경우2) S가 이동하는 경우 2. 풀이 설계이 문제는 벽장문의 사용 순서에 따라 탐색이 진행되고, 완전 탐색이 되어야 합니다.이 과정에서 필요한 것, 저장시켜야 하는 것, 변화하는 것들을 이용하여 dp를 정의하고 점화식을 세워..

문제n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. (각각의 동전은 몇 개라도 사용할 수 있다.)입력첫째줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.출력첫째 줄에 경우의 수를 출력한다. 경우의 수는 2^31보다 작다. 입력 :3 10 1 2 5 결과 10 D[N] = D[N-1] + D[N-2] + D[N-5] 풀이import java.io.BufferedReader; import java.io.FileInputStream; import java..

https://www.hackerearth.com/practice/notes/computational-geometry-i-1/ https://www.hackerearth.com/practice/math/geometry/line-sweep-technique/tutorial/ https://www.hackerearth.com/practice/math/geometry/line-intersection-using-bentley-ottmann-algorithm/tutorial/

기본 이항개수 알고리즘 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..

최단경로 구하는 알고리즘 : 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..