이 문제에서는 크기가 n인 배열 arr[]가 주어지며, 배열에서 만들 수 있는 모든 쌍의 합에 대해 XOR 연산을 수행한 최종 결과를 구하는 프로그램을 작성해야 합니다.
문제 이해하기
입력: arr[] = {5, 7, 9}
출력: 22
설명:
(5+5) ^ (5+7) ^ (5+9) ^ (7+5) ^ (7+7) ^ (7+9) ^ (9+5) ^ (9+7) ^ (9+9) = 22
즉, 자기 자신과의 쌍을 포함하여 인덱스 i와 j로 만들 수 있는 모든 순서쌍의 합을 구한 뒤, 그 값들을 차례대로 XOR하여 최종 결과를 얻습니다.
방법 1: 중첩 반복문을 사용한 단순한 접근
가장 직관적인 해결 방법은 중첩 반복문을 사용해 배열에서 만들 수 있는 모든 쌍을 생성하고, 각 쌍의 합에 대해 XOR 연산을 누적하는 것입니다.
알고리즘
XorSum을 0으로 초기화합니다.
- 1단계: i를 0부터 n-1까지 반복합니다.
- 1.1단계: j를 0부터 n-1까지 반복합니다.
- 1.1.1단계: XorSum을 갱신합니다. 즉, XorSum = XorSum ^ (arr[i] + arr[j]).
- 2단계: XorSum을 반환합니다.
구현 예제
#include <iostream>
using namespace std;
int findSumXORPair(int arr[], int n) {
int XorSum = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
XorSum = XorSum ^ (arr[i] + arr[j]);
return XorSum;
}
int main() {
int arr[] = {5, 7, 9};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"배열의 모든 쌍의 합에 대한 XOR: "<<findSumXORPair(arr, n);
return 0;
}
출력
배열의 모든 쌍의 합에 대한 XOR: 22
이 방법은 이해하기 쉽지만, 모든 쌍을 하나씩 확인해야 하므로 시간 복잡도가 O(n²)입니다. 따라서 배열의 크기가 커지면 실행 시간이 급격히 늘어나 비효율적입니다.
방법 2: XOR의 성질을 활용한 효율적인 접근
XOR의 성질을 활용하면 훨씬 효율적으로 문제를 해결할 수 있습니다. 배열의 모든 원소에 대한 XOR 값을 먼저 계산한 뒤, 그 값에 2를 곱하면 됩니다. 각 원소는 (i, j)와 (j, i) 형태의 쌍에 대칭적으로 기여하기 때문에, 전체 쌍의 합에 대한 XOR 결과는 배열 전체의 XOR 값의 두 배와 같아집니다.
알고리즘
XorSum을 0으로 초기화합니다.
- 1단계: i를 0부터 n-1까지 반복하면서 XorSum = XorSum ^ arr[i]로 갱신합니다.
- 2단계: XorSum에 2를 곱한 뒤 반환합니다.
구현 예제
#include <iostream>
using namespace std;
int findSumXORPair(int arr[], int n) {
int XorSum = 0;
for (int i = 0; i < n; i++)
XorSum = XorSum ^ arr[i];
XorSum = 2 * XorSum;
return XorSum;
}
int main() {
int arr[] = {5, 7, 9};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"배열의 모든 쌍의 합에 대한 XOR: "<<findSumXORPair(arr, n);
return 0;
}
출력
배열의 모든 쌍의 합에 대한 XOR: 22
마무리
중첩 반복문을 사용하는 단순한 방식은 O(n²)의 시간 복잡도를 가지는 반면, XOR의 성질을 활용한 방식은 단 한 번의 순회만으로 결과를 계산할 수 있어 시간 복잡도가 O(n)입니다. 배열의 크기가 큰 경우에는 후자의 접근 방식을 사용하는 것이 훨씬 효율적입니다.