XOR
정의
XOR연산은
두 비트가 다르면 1, 같으면 0이다.
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0
0 XOR 0 = 0
PS에서의 응용을 위한 성질
1. A XOR B = C라하자.
B = A XOR C
A = B XOR C이다.
따라서 위 식이 주어질때, A,B,C중 2개를 알고있다면 나머지 하나는 정해진다. 그리고 그것은 분명 유일하게 존재한다.
2. A XOR A = 0이다.
모든 비트가 같을 것이므로 0이다.
3. A XOR 0 = A이다.
4. 예를들어 A XOR B XOR C XOR D == B XOR D XOR C XOR A이다. 즉 순서가 바뀌어도 결과는 같다.
5. 역시나 D = A XOR B XOR C 라하자. D XOR E = A XOR B XOR C XOR E이다.
문제
https://www.acmicpc.net/problem/15710
15710번: xor 게임
첫째 줄에 정수 a, b (0 ≤ a, b < 231), n(0 < n ≤ 109)이 공백으로 구분되어 주어진다.
www.acmicpc.net
1번과 5번성질을 보자.
아무거나 n-1번 고른다.
그렇게 해서 어떤수 x를 얻었다.
x XOR ? = b라하자.
?는 x XOR b이다.
즉 우리는 n-1번까진 아무거나 고르고 n번째에 특정한 수를 고르면 b로 만들 수 있다.
https://www.acmicpc.net/problem/20118
20118번: 호반우가 길을 건너간 이유
격자의 왼쪽 위가 0, 0 이고 오른쪽 밑이 N-1, M-1 입니다. 경로에는 시작 지점과 끝 지점이 포함되어야 합니다.
www.acmicpc.net
xor결과가 0이되기 위해선
같은수를 서로 xor해야한다.
시작부터 xor을 해갔을때, 마지막에 갈 칸에 있는 수와 같아지는 경로를 찾는건 너무 어렵다.
따라서 모든 칸을 2번씩 방문해서 xor값을 0으로 만드는 경우를 생각할 수 있다.
시작점부터 끝점까지 가는 최단거리는 대각선으로 가능한만큼 가고, 남는만큼 직선으로 가면 된다.
이는 2*max(N,M)이므로 2*(N+M)을 넘지않을 것이다.
단 그 거리가 홀수라면, 끝점이 남으므로 끝점에서 추가로 1번 더 아무칸으로 왕복해야한다.
17943번: 도미노 예측
보드게임 카페에서 아르바이트를 하는 정기는 사장님 몰래 도미노 놀이를 하는 취미가 있다. 도미노 놀이는 줄지어 세운 도미노의 한쪽 끝을 밀어 다른 도미노들을 연속적으로 넘어트리는 놀이
www.acmicpc.net
질문자는
INFO[i] = domino[i] XOR domino[i+1]을 알려준다.
INFO에서 i ~ j까지를 모두 XOR를 한다면 (N - 1 > j > i >= 0)
domino[i] XOR domino[i+1] XOR domino[i+1] XOR donimo[i+2] XOR ... XOR domino[j-1] XOR donimo[j] XOR domino[j] XOR domino[j+1]을 하는 것과 같다.
이는 domino[i] XOR domino[j+1]과 같다.
이것을 이용해 1번쿼리와 2번쿼리를 구할 수 있다. (1번은 그래도 출력하면 되고 2번쿼리는 1번성질을 이용한다.)
하지만, 이를 쿼리마다 구하려면 O(N)일 것이고 비효율적이다.
INFO를 0부터 j까지 XOR한 값, INFO를 0부터 i-1까지 XOR한 값을 알고있다고 하자.
전자는 domino[0] XOR domino[j+1]이다.
후자는 domino[0] XOR donino[i]이다.
이를 XOR하면 domino[i] XOR domino[j+1] XOR domino[0] XOR domino[0]이므로
원하는 값을 구할 수 있다.
이런 꼴은 처음에 누적합과 비슷하게 배열을 선언해주면 O(1)에 구할 수 있다.
https://www.acmicpc.net/problem/14258
14258번: XOR 그룹
N*M 격자에 서로 다른 수가 하나씩 들어가 있다. XOR 그룹이라는 것을 정의를 하여 합을 최대로 하려한다. XOR 그룹이란 위, 아래, 오른쪽, 왼쪽으로 인접한 칸에 수가 있다면, 그 칸과 연결되어 그
www.acmicpc.net
수를 지워나가며 그룹을 분리하는 것은 힘든 일이다.
따라서 비어있는 격자판에서 큰수부터 추가해가는 문제를 생각해보자.
그렇다면 union find를 이용해 그룹을 합쳐나가면 된다.
오프라인 쿼리 문제이다.
그룹을 합칠 때, XOR의 성질에 의해 서로다른 두 그룹의 값을 XOR해주면 합친그룹의 XOR값이 나온다.(연결의 원인이 되는 수도 XOR해줘야한다.)
연산만 XOR일 것이지,
그룹의 최대값
그룹의 합
등등....
이런걸 구하는 것과 로직은 똑같은 문제이다.
응용
배열에 있는 수 중에서 주어진 수 X와 XOR했을 때 최대값 또는 최소값이 되는 경우
O(배열크기)로 풀어도 되겠으나 , O(가장 큰 수의 비트수)로 구할 수 있다.
후자가 일반적으론 더 최적이다.후자의 의미는 log2(가장 큰수)인데, log는 엄청난 효율성을 자랑한다.
이것을 가능하게 하는 것은 trie 자료구조이다.
우선, 배열의 원소를 문자열로 바꾼다.
가능한 input중 가장 큰 수의 비트길이만큼 스케일을 늘려줘야한다.
왼쪽에 부족한 비트길이만큼 0을 붙히면 된다.
배열에 있는 비트들로 trie를 만든다.
최대값을 구한다고 생각해보자.
for (int i = 0; i<X의비트길이; i++){
if i가 마지막 인덱스라면{
탐색완료한 비트문자열을 수로 바꾸고 종료한다.
}
if X[i]가 0라면{
if trie에서 value가 1인 정점을 탐색가능하면{
해당 노드로 탐색한다.
}
else{
있는 노드라도 탐색한다.
}
}
else {
if trie에서 value가 0인 정점을 탐색가능하면{
해당 노드로 탐색한다.
}
else{
있는 노드라도 탐색한다.
}
}
}이런 로직으로 구할 수 있다.
더 나아가서
누적합, 세그먼트 트리에 적용가능한 연산이 또 무엇이 있을까
있다면 그런 연산을 뭐라고 할까(진짜 몰라요)