문제 https://www.acmicpc.net/problem/17422 17422번: 지폐가 넘쳐흘러 첫째 줄에 금고의 개수 N이 주어진다. 양의 정수 k에 대해, N = 2k-1이 항상 성립한다. 둘째 줄에 금고에 들어 있는 지폐의 개수 Wi가 1번 금고부터 순서대로 주어진다. 셋째 줄에 놀이의 횟수 Q가 www.acmicpc.net 알고리즘 트리DP 우선순위 큐 풀이 트리와 각 금고의 지폐의 개수 \(W_{i}\)가 주어졌을 때, 두 배열 \(A, B\)를 만들어 다음과 같이 정의합니다: \(A_{i}:\) \(i\)을 루트로 하는 서브트리 안에 있는 한 리프 노드로부터 \(n\)까지의 경로에 있는 지폐 개수의 최대값. \(B_{i}:\) \(i\)을 루트로 하는 서브트리 안에 있는 지폐 개수의 합..
문제 https://www.acmicpc.net/problem/20506 20506번: Kaisar - 생존 준원이(0/5/3)는 생존해있는 카이사(2/7/0)를 찾으러 소환사의 협곡을 수색하고 있다. 협곡은 정점이 N개 있는 트리 모양이고, 정점은 1번 정점에서 N번 정점까지 번호 붙여져 있다. 준원이는 모든 www.acmicpc.net 풀이 트리DP를 사용합니다. 트리가 주어졌을 때 다음 \(2\)개의 배열을 정의합니다: \(cnt[i]:\) \(i\)를 루트로 하는 서브트리의 크기. (노드의 개수) \(dp[i]:\) \(i\)를 \(lca\)로 가지는 두 노드의 쌍의 개수. \(dp[i]\), 즉, \(i\)를 \(lca\)로 가지는 두 노드의 쌍의 개수를 구하는 방법은 다음과 같습니다: \(i\..
문제 https://www.acmicpc.net/problem/15669 15669번: 나무 위의 입자 트리란, 사이클이 없는 연결 그래프를 의미한다. 위 그림은 트리 모양의 입자가속기와 그 위의 어떤 정점에 놓인 특별한 입자 하나를 표시하고 있다. RB 입자라고 불리는 이 특이한 입자는 안정 www.acmicpc.net 풀이 트리DP를 사용합니다. 트리가 주어졌을 때, 두 배열을 만들어 다음과 같이 정의합니다: \(depth[i]:\) 노드 \(i\)의 깊이. \(dp[i][0], dp[i][1]:\) \(i\)를 루트로 하는 서브트리의 노드 중 깊이가 짝수인 노드의 개수, 홀수인 노드의 개수. 트리를 순회하면서 위 두 배열에 값을 저장한 다음 각 \(M\)개의 쿼리에 대하여 다음 작업을 수행합니다. ..
문제 www.acmicpc.net/problem/1693 1693번: 트리 색칠하기 n개의 정점으로 이루어진 트리가 있다. 이 트리의 각 정점을 색칠하려고 한다. 색칠을 할 때에는 1, 2, 3, …, n번 색깔 중에 하나로 색칠하여야 한다. 각 색깔을 사용하여 한 개의 정점을 색칠할 때 www.acmicpc.net 풀이 트리DP를 사용합니다. 트리가 주어졌을 때 배열 \(dp\)를 다음과 같이 정의할 수 있습니다: \(dp[i][j]:\) \(i\)의 색이 \(j\)일 때 \(i\)를 루트로 하는 서브트리의 총 비용의 최솟값. 여기서 \(j\)를 \(1\)부터 \(N\)까지 전부 다 구하면 \(N\)의 범위가 \(1\)이상 \(100000\)이하이기 때문에 시간초과가 날 수 있습니다. www.acmic..
문제 www.acmicpc.net/problem/7812 7812번: 중앙 트리 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫 줄에는 트리의 정점의 수 n이 주어진다. (1 ≤ n ≤ 10,000) 각 정점은 0번부터 n-1번까지 번호가 붙여져 있다. 다음 n-1개 줄 www.acmicpc.net 풀이 트리DP를 사용합니다. 먼저, 예제에서 나온 트리를 보겠습니다. 위 트리의 \(A\)노드에서 다른 모든 노드들로 이동할 때, 각 간선이 이용되는 횟수는 다음과 같습니다. \(A\)를 루트로 하여 트리를 순회하면서 각 \((B, C, D, E)\)를 루트로 하는 서브 트리의 크기(노드의 개수, 즉, 루트라고 하는 노드와 그 노드의 부모와 이어지는 간선이 이용되는 횟수)에 그 간선의..
문제 www.acmicpc.net/problem/1949 1949번: 우수 마을 첫째 줄에 정수 N이 주어진다. (1≤N≤10,000) 둘째 줄에는 마을 주민 수를 나타내는 N개의 자연수가 빈칸을 사이에 두고 주어진다. 1번 마을부터 N번 마을까지 순서대로 주어지며, 주민 수는 10,000 www.acmicpc.net 풀이 트리DP를 사용합니다. 트리가 주어졌을 때, 배열 \(dp\)를 다음 두 가지 경우로 생각해 정의할 수 있습니다: \(dp[i][0]:\) \(i\)가 우수 마을이 아닐 경우의 마을 주민 수 합의 최대값. \(dp[i][1]:\) \(i\)가 우수 마을일 경우의 마을 주민 수 합의 최대값. \(i\)의 자식 노드들을 \(c_{1}, c_{2}, c_{3}, ... , c_{m}\)이라..
문제 www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 풀이 트리DP를 사용합니다. 트리가 주어졌을 때, 배열 \(dp\)를 다음과 같이 정의할 수 있습니다: \(dp[i]:\) \(i\)를 루트로 하는 서브트리에 속한 정점의 수. 트리를 순회하면서 \(i\)의 자식 노드들을 \(c_{1}, c_{2}, c_{3}, ... , c_{m}\)이라고 할 때, \(dp[i]\)에 다음 값을 저장합니다: ..
- Total
- Today
- Yesterday
- codeforces
- PBA
- Coordinate Compression
- Constructive
- graph
- Priority Queue
- LCA
- knapsack
- Union Find
- Prefix Sum
- Greedy
- Tree DP
- Dijkstra
- Sliding Window
- Combinatorics
- binary search
- Bit Masking
- sorting
- BOJ
- DP Traceback
- Tree
- 737-2
- DP
- hello
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |