LIPNUS

백준 2042 구간 합 구하기https://www.acmicpc.net/problem/2042 package 구간합구하기; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int N; //숫자개수 static int M; //변경횟수 static int K; //구간합을 구하는 횟수 static long[] tree; static int k; static int treeSize; //크기는 2^k static int startIdx; //리프노드의 시작인덱스 public static void main(String[] args) t..

백준 3020 개똥벌레https://www.acmicpc.net/problem/3020 부분합의 아이디어를 이용한다. package 개똥벌레; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int N; //동굴길이 static int H; //동굴높이 static int[] jong; //종유석 static int[] suck; //석순 static int[] jong_sum; //종유석 칸별 누적 static int[] suck_sum; //석순 칸별 누적 public static void main(String[] args) ..

Union & Find static void union(int a, int b) { int aRoot = find(a); int bRoot = find(b); parent[bRoot] = aRoot; //b는 자기자신을 가리키다가 a를 가리키게 된다 } static int find(int a) { if(parent[a]==a) { return a; } else { parent[a] = find(parent[a]); return parent[a]; } }네트워크연결문제가 이걸 이용한 것. parent[a] = find(parent[a]);이걸로 인해 탐색성능이 향상된다. 하나씩 타고가는게 아니라 모든 하위노드들이 바로 Root에 연결된다.찾는 과정에서 연결해줌.

백준 1922 네트워크연결https://www.acmicpc.net/problem/1922 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class Main { static int N; //노드 수 static int M; //선의 수 static int[] parent; static List edges; public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; edges = n..

백준 11437 LCAhttps://www.acmicpc.net/problem/11437 1번은 DP안써도 풀림. public class Main { static int N; //노드개수 static int M; //공통조상을 알고싶은 쌍의 수 static List[] map; static boolean[] visited; static int[] depth; static int[] parent; public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; N = Integer.parseInt(br...

Heap -> Priority Queue

백준 11286 절댓값 힙https://www.acmicpc.net/problem/11286 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.PriorityQueue; public class Main { static PriorityQueue pq = new PriorityQueue(); public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt( br.readLine() ); for(int ..

백준 11279 최소 힙https://www.acmicpc.net/problem/1927import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Collections; import java.util.PriorityQueue; public class Main { static PriorityQueue pq = new PriorityQueue(); public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt..

프로그래머스 깊이/너비 우선탐색(BFS/DFS) 네트워크https://programmers.co.kr/learn/courses/30/lessons/43162 Union-Find인가? 하고 풀고있었는데.. 그냥 기본적인 탐색 개념만 필요. class Solution { static int[] visited; public static void main(String[] args) { int n=3; int[][] computers = {{1, 1, 0}, {1, 1, 0}, {0, 0, 1}}; int count=0; visited = new int[n]; for(int i=0; i

백준 1753 최단경로https://www.acmicpc.net/problem/1753 52번의 제출. 계속 시간초과. 15시간만에 맞췄다. 다익스트라 개념을 잘못알고 있었음. 잘못된 코드import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.PriorityQueue; import java.util.StringTokenizer; public class Main { static ArrayList[] adj; static int[] cost; //출발점에서 해당 지점까지 가는..

크루스칼은 MST 만들 때 쓴다.무방향 그래프에서 사용 다익스트라는 최단거리 구할 때 쓴다.

http://isukorea.com/blog/home/waylight3/216

백준 5626 제단https://www.acmicpc.net/problem/5626 그냥 DP로 하면 메모리가 부족하다. 그래서 Sliding Widow로 지금거 바로 이전것만 저장하면서 진행.D[0][]과 D[1][] 두개로 돌려막기한다. 홀,짝으로 구분. package 제단; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { static long[][] D; //슬라이딩 윈도우 - i번째(두개로 슬라이딩) 높이가 j인 경우의 수 static final long MOD = 1000000007; pu..

백준 11660 구간 합 구하기https://www.acmicpc.net/submit/11660/11362110 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int[][] map; static int[][] D; public static void main(String[] args) throws Exception{ // TODO Auto-generated method stub BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokeni..

백준 1932 정수삼각형 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int[][] triangle; static int N; static int[][] D; public static void main(String[] args) throws Exception { //N개의 정수를 배열로 받음 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = null; N = Integer.parseInt( br.readLin..

백준 11438 LCA2https://www.acmicpc.net/problem/11438 아직 소스 개선의 여지가 많이 남아있음.package com.company; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main { static int[][] parent; // parent[a][b] a의 2^b번째 부모 static ArrayList[] adj; //트리 static int[] depth; publ..

c = new int[N+1][N+1];//파스칼 삼각형 for(int n=1; n

백준 11653 소인수분해https://www.acmicpc.net/problem/11653 1은 소인수분해하면 아무것도 없어야 한다. 1로 출력하면 틀림. for문에서 N이 계속해서 변하는 것이 특이함.package com.company; import java.util.*; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); int N = sc.nextInt(); if(N==1) return; for(int i=2; i

백준 11266 단절점https://www.acmicpc.net/problem/11266 자신의 자손(다음) Vertex가 자신을 거치지 않고 자신의 조상(이미 거쳐왔던 곳)에 도달할 수 없으면 단절점이다.인접리스트로 바꾸면 좀 더 빨라질 것 같음.package com.company; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int V, E; static int[] order; //방문여부 static int[] cutVertex; //단절점 static int[][] ma..

백준 2085 나무자르기 https://www.acmicpc.net/problem/2805 package com.company; import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws Exception { // TODO Auto-generated method stub BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int N = Integer.parseInt( st.nextToken() ); ..