1. 모든 원소 쌍의 XOR 합 $A_{0}, A_{1}, ... , A_{n-1}$에 대하여 $\sum_{i=0}^{i=n-1} \sum_{j=i+1}^{j=n-1} A_{i} \oplus A_{j}$을 구하는 문제 단순하게 풀면 $O(N^{2})$이지만 조금 더 생각해본다면 $O(N)$에 가깝게 해결할 수 있다. 결국 구하고자 하는 값은 $V = A_{i} \oplus A_{j}$라고 할 때, 이 V들의 합이다. 그런데 V를 2진수로 나타낸다면.. $$V = a_{k}2^{k} + a_{k-1}2^{k-1} + ... + a_{1}*2 + a_{0}$$로 나타낼 수 있다. 여기서 $a_{i} = 0$이거나 $a_{i} = 1$이다. 만약 모든 $V = A_{i} \oplus A_{j}$에 대하여 최대..
1. 연속하는 부분열에 대한 XOR n개의 음이 아닌 정수 $A_{1}, A_{2}, ... , A_{n}$에 대하여 L번부터 R번까지의 XOR $A_{L} \oplus A_{L+1} \oplus ... A_{R}$의 값은? 만약 $V_{0} = 0, V_{i} = A_{1} \oplus A_{2} \oplus ... \oplus A_{i}$라고 하자. $V_{L-1} = A_{1} \oplus A_{2} \oplus A_{3} .... \oplus A_{L-1}$이다. 그러면, $0 \oplus x = x, x \oplus x = 0$이므로.. 0을 xor해도 값이 달라지지 않는다. $$A_{L} \oplus A_{L+1} \oplus ... A_{R} = 0 \oplus (A_{L} \oplus A_..
1. 기본 성질 정수 x,y,z에 대하여... $$ x \oplus 0 = x $$ $$ x \oplus x = 0 $$ $$ x \oplus y = y \oplus x $$ $$ (x \oplus y) \oplus z = x \oplus (y \oplus z)$$ 사실 교환법칙, 결합법칙이 성립하고 0을 xor하면 그대로 나오고 자기자신을 xor하면 0이 나온다는거 아는데 만약 n개의 원소 a1,a2,a3,...,an에 대하여.. a1 ^ a2 ^ a3 ^ ... ^ an을 생각해보자. a2 ^ a3 ^ a4 ^ ... ^ an의 값을 알고 싶다면 어떻게 해야할까? a1+a2+a3+...+an을 알고있다면 그냥 a1을 뺀다면 되는데 xor에서는 이런 빼기 연산이 있는건가? 다시 a2,a3,..,an을 ..
1. 방향 비순환 그래프(Directed acyclic graph) 사이클이 존재하지 않는 방향 그래프 정점 u에서 출발했을때, u로 돌아오는 방법이 없다. 다음과 같은 그래프는 방향 비순환 그래프(DAG)이다. 2. 한 정점에서 다른 정점까지 가장 긴 경로의 길이 정점 v에 대하여 DP[v]를 v에서 출발할때 도달할 수 있는 가장 긴 경로의 길이라고 정의한다면... 다음과 같이 v에서 c1,c2,c3,...로 갈 수 있을텐데, c1,c2,c3,...에서 출발하여 도달할 수 있는 가장 긴 경로의 길이 DP[c1],DP[c2],...가 이미 구해져있다면... DP[v] = max(wi + DP[ci])으로 구할 수 있을 것이다. 다이나믹 프로그래밍은 이미 해결한 작은 문제를 이용해서 더 큰 문제를 해결하는..
1. 문제 11429번: Tree (acmicpc.net) 11429번: Tree The input file contains the description of the tree. The first line of the input file contains one integer N, 2
1. 문제 19542번: 전단지 돌리기 (acmicpc.net) 19542번: 전단지 돌리기 현민이는 트리 모양의 길 위에서 오토바이를 타고 전단지를 돌리려고 한다. 현민이의 목표는 케니소프트에서 출발하여 모든 노드에 전단지를 돌리고, 다시 케니소프트로 돌아오는 것이다. 현민 www.acmicpc.net 2. 풀이 트리로 구성된 그래프에서 모든 노드에 전단지를 돌려야하는데, 현재 노드에서 거리가 D이하인 모든 노드에 전단지를 한번에 돌릴 수 있다고 한다 트리 구조이기 때문에 부모 > 자식으로 내려가면서 각 노드마다 가장 먼 자식 노드까지의 거리를 안다면, 어디 노드까지만 방문해도 되는지를 파악할 수 있을 것이다. 10만개의 노드가 있어서 한번의 DFS로 각 노드마다 가장 먼 자식 노드까지의 거리를 구해야..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
