분류 전체보기 (84) 썸네일형 리스트형 [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] Codeforces Round #787 (Div.3) Solve:5/rank:551/Pef:1625 https://codeforces.com/contest/1675 https://codeforces.com/contest/1675 codeforces.com 국방부장관님 오시기 전날 밤 대회여서 연등이 너무 제한되는 탓에 시간관리가....ㅠㅠ 패널티라도 먹었으면 퍼포 블루도 안나올뻔 했다. [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.. [Java] 백준 10999번 합 구하기 - Lazy Segment Tree https://www.acmicpc.net/problem/10999 10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net import java.util.*; import java.io.*; public class p5_10999 { static FastScanner fs = new FastScanner(); static PrintWriter pw = new PrintWriter(System.out); static int n, m; static long.. [Java] Index Tree / Segment Tree Lazy Propagation https://www.acmicpc.net/blog/view/26 세그먼트 트리 나중에 업데이트 해야지! 글이 업데이트 되었습니다. https://book.acmicpc.net/ds/segment-tree-lazy-propagation 배열 A가 있고, 여기서 다음과 같은 두 연산을 수행해야하는 문제가 있습니다. 10999번 문제: 구간 합 구하기 2 구간 l, r (l www.acmicpc.net https://steady-coding.tistory.com/129 [BOJ] 백준 6549번 : 히스토그램에서 가장 큰 직사각형 (JAVA) 문제 히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그.. [Java] Segment Tree https://www.acmicpc.net/blog/view/9 세그먼트 트리 (Segment Tree) 글이 업데이트 되었습니다. https://book.acmicpc.net/ds/segment-tree 문제 배열 A가 있고, 여기서 다음과 같은 두 연산을 수행해야하는 문제를 생각해봅시다. 구간 l, r (l ≤ r)이 주어졌을 때, A[l] + A[l+1] + .. www.acmicpc.net https://steady-coding.tistory.com/126 [BOJ] 백준 2357번 : 최솟값과 최댓값 (JAVA) 문제 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와.. 이전 1 2 3 4 5 6 ··· 11 다음
