알고리즘 공부방

문제 https://codeforces.com/contest/1187/problem/E 트리에서 어떤 노드를 시작으로 선택한 노드들과 인접한 노드들을 골라 검정색으로 칠하는 과정을 계속 반복한다. 이때 노드 하나를 선택할 때 아직 색칠되지 않은 컴포넌트의 크기만큼의 점수를 얻을 때, 점수의 최댓값을 구하는 문제이다. 풀이 가장 먼저, 처음에 선택하는 노드를 하나 정해놓고 생각해보자. 다음에 선택하는 노드는 그 노드와 연결되어 있는 점이어야 하고, 다음에 선택할 점들을 어떤 순서로 골라도 상관이 없다. 이를 이용하면, 다음을 알 수 있다. 루트 하나를 고정시켜 놓은 트리에서, 각 노드마다 서브트리의 크기를 구하면 그 서브트리 크기의 합이 바로 답이 된다. 이는 트리 DP를 이용하여 구할 수 있다. dp[v..

문제 https://codeforces.com/contest/482/problem/B 길이 N의 배열에 l~r 구간에 대해 모든 값들을 & 한 결과값들이 m개 주어져 있을 때, 이 모든 조건을 만족하는 배열을 구하는 문제이다. 풀이 bitwise 연산이 들어간 문제의 대다수는 각 비트를 따로 생각해주면 풀리는 경우가 많다. 이 문제도 n번째 칸의 i번째 비트가 켜져 있는지, 꺼져 있는지 각각 구해주자. 만약 l~r 까지의 & 값이 켜져 있다는 말은, l~r 의 i번째 비트는 모두 다 켜져 있다는 뜻이다. 따라서 먼저 모든 m을 보며 l~r의 i번째 비트를 켜준다. 그 후에 켜져 있지 않은 비트는 무조건 꺼져 있다고 생각해도 답에 영향을 미치지 않는다. 마지막으로 꺼져 있는 비트에 대해서 검사를 하며, l..