PS/Problems (49) 썸네일형 리스트형 Zero Path (Div2.C) - 최대값, 최소값만 관리하는 테크닉 https://codeforces.com/contest/1695/problem/C Problem - C - Codeforces codeforces.com 정말 멘탈 많이 나갔었는데 최대값과 최소값만 관리하면 그 사이의 값은 모두 가능하다는 팁을 듣고 10분만에 ac... 멘탈 관리 열심히 해야것다. import java.util.*; import java.io.*; public class q3 { static FastScanner fs = new FastScanner(); static PrintWriter pw = new PrintWriter(System.out); static int n, m; static boolean[][] map; static int[][][] ends; public static .. [Java] 백준 24041번 성싶당 밀키트 - 이분 탐색 https://www.acmicpc.net/problem/24041 24041번: 성싶당 밀키트 첫 번째 줄에 $N, G, K$가 공백으로 구분되어 주어진다. 두 번째 줄부터 $N$ 개의 줄 중 $i$ 번째 줄에는 $i$ 번째 재료에 대한 정보인 부패 속도 $S_i$, 유통기한 $L_i$와 중요한 재료인지를 나타내는 www.acmicpc.net 5달만에 풀었다... import java.util.*; import java.io.*; public class g4_24041 { static FastScanner fs = new FastScanner(); static PrintWriter pw = new PrintWriter(System.out); static long n, g, k; static long l.. [Java] 백준 3015번 오아시스 재결합 - Stack https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net https://nahwasa.com/entry/%EB%B0%B1%EC%A4%80-3015-%EC%9E%90%EB%B0%94-%EC%98%A4%EC%95%84%EC%8B%9C%EC%8A%A4-%EC%9E%AC%EA%B2%B0%ED%95%A9-BOJ-3015-JAVA 백준 3015 자바 - 오아시스 재결합 (BOJ 3015 JAVA) 문제 : https://www.acmicpc.. [Java] 백준 1761번 정점들의 거리 - LCA 응용 https://www.acmicpc.net/problem/1761 1761번: 정점들의 거리 첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에 M이 주어지고, 다음 M개의 줄에 거리를 알고 싶은 노드 쌍이 한 줄에 한 쌍씩 www.acmicpc.net 기존의 LCA 문제에서 나아가, 간선들의 길이의 합에 대한 정보도 필요하다. 처음에는 세그먼트 트리를 생각해보았지만 간선이 연결되는 각 경우마다 트리를 만들 수는 없으므로 각 노드의 2^i 위의 부모에 대한 정보를 담은 parents 배열처럼 2^i 위의 부모까지의 길이정보를 담는 distances 배열을 새로 고안했다. 예술이네 import java.util.*; import java... [Java] 백준 11438번 LCA 2 - LCA (최소 공통 조상) https://www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net https://pangtrue.tistory.com/262 [백준 11438 : JAVA] LCA 2 / 최소 공통 조상 문제 풀이 LCA(Lowest Common Acestor_최소 공통 조상) 알고리즘을 사용하는 기본 유형의 문제다. 해당 문제에서 주의깊게 봐둬야할 건 각 노드의 2^i 번 째 조상노드를 테이블에 저장하기 위해 DP를 사용 pangtrue.tistory.com impo.. [Java] 백준 13334번 철로 - 스위핑 https://www.acmicpc.net/problem/13334 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 스위핑이라는건 눈치는 채긴 했는데 정렬 기준이 왼쪽이 아니라 오른쪽인 건 눈치를 못챘다. import java.util.*; import java.io.*; public class g2_13334 { static FastScanner fs = new FastScanner(); static PrintWriter pw = new PrintWriter.. [Java] 백준 2533번 사회망 서비스 - Dynamic Programming https://www.acmicpc.net/problem/2533 부모 노드가 adapter인 경우와 그렇지 않은 경우를 나누어 dp[n][1], dp[n][0] 로 구분해 dp를 적용한 것이 인상깊었다. import java.util.*; import java.io.*; public class g3_2533_adapter { static FastScanner fs = new FastScanner(); static PrintWriter pw = new PrintWriter(System.out); static Node[] nodes; static int n; static int[][] dp; public static void main(String[] args) { n = fs.nextInt(); nodes.. [Java] 백준 3653 영화 수집 - Lazy Segment Tree https://www.acmicpc.net/problem/3653 3653번: 영화 수집 각 테스트 케이스에 대해서 한 줄에 m개의 정수를 출력해야 한다. i번째 출력하는 수는 i번째로 영화를 볼 때 그 영화의 위에 있었던 DVD의 개수이다. 상근이는 매번 영화를 볼 때마다 본 영화 DVD www.acmicpc.net leaf 노드의 경우 좌측부터 i번 영화가 node[i] 번째에 놓여있도록 하였다. 하지만 탐색 회수를 최적화하기 위해 해당 노드를 root로 가지는 트리에 대하여 mintree, maxtree로 나누어서 mintree[node] >= v 라면 그 트리는 놓여있는 위치의 값을 더해선 안되므로 return maxtree[node] < v 라면 그 트리의 모든 노드는 1을 더해주므로 minla.. 이전 1 2 3 4 ··· 7 다음
