반응형
SMALL
Generic Queries
-
16713번 Generic Queries알고리즘 2023. 1. 21. 10:15
문제 설명 주어진 수열에서 XOR 연산을 하는 query를 여러 개 수행한 결과값들을 다시 XOR연산을 한 값을 구하는 문제입니다. 문제 풀이 선행 지식 XOR Python에서 XOR 연산은 "^"를 통해 이루어진다. XOR 연산의 결과 값 0 ^ 0 = 0 0 ^ 1 = 1 1 ^ 0 = 1 1 ^ 1 = 0 a1^a2^a3^a4 = A라고 할 경우 A^a1 = a2^a3^a4이다. 풀이 개념 이번 문제는 XOR의 개념을 생각하는 데에 오래 걸린 것 같습니다.. 수열의 길이 N과 쿼리의 개수가 모두 10^6로 큰 수 입니다. 그러므로 한 쿼리마다 XOR 연산을 하는 것은 비효율적이므로 누적합을 통해 이용해보도록 하겠습니다. 여기서 헷깔렸던 점은 수열의 홀수번째부터 시작하는 누적합과 짝수번째부터 시작하는..