코딩 문제를 풀다보면 XOR 연산을 활용하는 부류가 꽤 있다. 이는 XOR 비트 연산이 가지고 있는 몇가지 특징 때문인데, 이들을 잘 활용하면 Time Complexity와 Space Complexity를 각각 O(n)과 O(1)으로 줄일 수 있다. 따라서 특정 문제들에 대해서는 굉장히 효율적인 답안이 될 수 있다.
XOR 비트 연산 특징
- A ^ B = C -> A ^ C = B. (^ : XOR 연산)
위 식에서 A와 C를 알고 있을 때 B를 구하는 것이 목표이다. 이때 XOR의 연산 특성 사, A와 C 를 XOR 연산한 것이 바로 B이다. ex) 4 ^ 2 = 6 (100 ^ 010 = 110) -> 4 ^ 6 = 2 (100 ^ 110 = 010)
이는 다른 비트 연산들 (AND, OR, NOT)에는 적용이 안되고 XOR 비트 연산에만 있는 특징이다.
아래 Leet Code 문제를 풀어보자.
[LeetCode] 1720 Decode XORred Array
Solution Use principle : A ^ B = C -> A ^ C = B class Solution { public: vector decode(vector& encoded, int first) { vector res; res.push_back(first); for (int i = 0; i != encoded.size(); ++i) { res.push_back(res.back() ^ encoded[i]); } return res; } };
iridescentboy.tistory.com
- A ^ A = 0
- A ^ B ^ A = B
- (A ^ A ^B) = (B ^ A ^ A) = (A ^ B ^ A) = B
위 특징을 활용하면 다음 문제를 풀 수 있다. Int 배열에 모든 서로 다른 값의 원소가 2개씩 저장되어 있다. 그리고 1개의 원소만 단 1개 저장되어 있다. 이 원소를 어떻게 찾을 수 있을까?
위 문제는 얼핏 보면 쉬워 보인다. Map을 활용해 배열 원소를 순차적으로 접근하여 Counting 하는 방법이 있다. 혹은 배열을 Sorting 한 후, 2개씩 연속되지 않는 숫자를 찾아보면 된다. 위와 같은 방법은 Time Compelxity가 각각 O(N), O(NlogN)이고 Space Complexity가 각각 O(N), O(1)이다.
이 문제는 위에 명시한 XOR 연산의 3개의 특징을 활용하면 Time Complexity와 Space Complexity가 각각 O(N), O(1)인 알고리즘을 짤 수 있따. 배열의 모든 원소를 XOR 연산 해주면 그 결과가 바로 1개의 원소 값이 된다. (와우!)
LeetCode 문제는 136. Single Number 이다.
Single Number - LeetCode
Can you solve this real interview question? Single Number - Given a non-empty array of integers nums, every element appears twice except for one. Find that single one. You must implement a solution with a linear runtime complexity and use only constant
leetcode.com
'개념공부 > 기타' 카테고리의 다른 글
| [HDAT-DA] 데이터 분석 과정 (0) | 2023.04.06 |
|---|---|
| PyTorch nn.Linear (0) | 2023.02.06 |
| 파이토치 버전 확인 PyTorch Version Check (0) | 2023.01.25 |
| PyTorch 설치 (0) | 2023.01.25 |
| 아나콘다(Anaconda) 명령어 모음 (0) | 2023.01.25 |
