αλγριθμο

문제 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]\)에 다음 값을 저장합니다: ..

문제 https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 풀이 DP를 사용합니다. 주어진 수열 \(A\)에 대하여 배열 \(dp\)를 다음과 같이 정의할 수 있습니다: \(dp[i][j]:\) \(A_{i}\)부터 \(A_{j}\)까지가 팰린드롬인지 아닌지 여부. (팰린드롬이면 1, 팰린드롬이 아니면 0) 다음 수열을 보겠습니다. 1 2 1 3 1 2 1 여기서 첫 번째 수 부터 마지막 수까지는 팰린드롬입니다. 또한, 2번째부터 6번째까지, 3번째부터 5번째까지, 그리고 4번째 모두 팰..

문제 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이 DP를 사용합니다. 바이토닉 수열은 올라갔다 내려갈 수 있고, 올라가기만 할 수도 있으며, 내려가기만 할 수도 있습니다. 하지만, 내려갔다 올라갈 수는 없습니다. 그러므로, 두 가지 경우를 생각해 수열 \(A\)가 주어졌을 때 배열 \(dp\)를 다음과 같이 정의할 수 있습니다: \(dp[i][0]:\) \(A_{i}\)까지의 수열 중 바이토닉 부분 수열이 오름차순일 때 그 수열의 길이의 최대값. \(dp..