1304
-
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 연산을 하는 것은 비효율적이므로 누적합을 통해 이용해보도록 하겠습니다. 여기서 헷깔렸던 점은 수열의 홀수번째부터 시작하는 누적합과 짝수번째부터 시작하는..
-
1304번 지역알고리즘 2023. 1. 20. 18:27
문제 설명 이번 문제는 1~N의 도시에서 1->2, 2->3, i->i+1, N-1->N으로 가는 고속 도로가 있고 문제에서 일반 도로가 주어질 경우, 아래 조건을 만족하도록 지역을 나눌 경우 지역의 개수의 최대값을 구하는 문제입니다. 조건 지역 A의 어떤 도시에서 지역 B의 어떤 도시로 넘어갈 수 있는 경로가 있다면, B에 속해 있는 어떤 도시에서 A에 속해 있는 어떤 도시로 가는 경로는 없어야 합니다. 모든 지역의 도시 개수는 같아야 한다. 문제 풀이 아이디어 1 문제의 조건을 다시 생각해보기 위의 조건에 만족하도록 지역을 나눌 경우를 생각해보겠습니다. 모든 도시는 이미 자기보다 +1이 되는 도시로 향하는 도로가 하나씩 있다. 그렇다는 말은, 1에서 3으로 2에서 8로 X에서 Y(X E인 경우만 생각..