이 문제에서는 크기가 n × n인 정방 행렬이 주어지며, 우리의 목표는 특정 행 전체 또는 특정 열 전체를 XOR 연산했을 때 나올 수 있는 최댓값을 계산하는 프로그램을 작성하는 것입니다.
문제 이해를 위한 예시
입력
N = 3
mat[N][N] = {{4, 9, 1}
{2, 8, 3}
{10, 12, 11}}
출력
13
설명
행(Row) 기준:
1행: 4 ^ 9 ^ 1 = 12
2행: 2 ^ 8 ^ 3 = 9
3행: 10 ^ 12 ^ 11 = 13
열(Col) 기준:
1열: 4 ^ 2 ^ 10 = 12
2열: 9 ^ 8 ^ 12 = 13
3열: 1 ^ 3 ^ 11 = 9
위 예시에서는 행렬의 모든 행과 열에 대해 각각 XOR 연산을 수행한 뒤, 그 결과값들 중 가장 큰 값인 13을 출력합니다.
해결 접근 방법
이 문제를 해결하기 위해서는 행렬의 모든 행과 열에 대한 XOR 값을 계산한 후, 그중 최댓값을 찾으면 됩니다.
행과 열의 XOR을 구하는 가장 직관적인 방법은 행렬을 두 번 순회하는 것입니다. 첫 번째 순회에서는 행을 처리하고, 두 번째 순회에서는 열을 처리합니다.
하지만 더 효율적인 방법이 있습니다. 주어진 행렬이 정방 행렬(n × n)이므로 단 한 번의 이중 반복문으로 행 방향과 열 방향을 동시에 처리할 수 있습니다.
핵심 아이디어는 다음과 같습니다.
mat[i][j]를 사용하면 i번째 행을 순회합니다.mat[j][i]를 사용하면 i번째 열을 순회합니다.
즉, 인덱스 i와 j의 역할만 바꿔주면 하나의 반복문 내에서 행 XOR(rowXOR)과 열 XOR(colXOR)을 동시에 누적 계산할 수 있습니다. 각 반복이 끝날 때마다 현재까지의 최댓값(maxXOR)과 비교하여 더 큰 값을 갱신해주면 됩니다.
C++ 구현 코드
위 알고리즘을 구현한 프로그램은 다음과 같습니다.
#include<iostream>
using namespace std;
const int MAX = 1000;
int maxRCXOR(int mat[][MAX], int N){
int rowXOR, colXOR;
int maxXOR = 0;
for (int i = 0 ; i < N ; i++){
rowXOR = 0, colXOR = 0;
for (int j = 0 ; j < N ; j++){
rowXOR = rowXOR ^ mat[i][j]; // i번째 행 순회
colXOR = colXOR ^ mat[j][i]; // i번째 열 순회
}
if (maxXOR < max(rowXOR, colXOR))
maxXOR = max(rowXOR, colXOR);
}
return maxXOR;
}
int main() {
int N = 3;
int matrix[][MAX] = {
{4, 9, 1},
{2, 8, 3},
{10, 12, 11}
};
cout<<"모든 행 XOR 및 열 XOR 중 최댓값: "<<maxRCXOR(matrix, N);
return 0;
}
실행 결과
모든 행 XOR 및 열 XOR 중 최댓값: 13
복잡도 분석
- 시간 복잡도: O(N²) — n × n 행렬의 모든 원소를 정확히 한 번씩만 방문합니다.
- 공간 복잡도: O(1) — 추가적인 배열 없이 몇 개의 변수만 사용합니다.
이처럼 행렬이 정방 행렬이라는 특성을 활용하면 불필요한 두 번째 순회 없이도 깔끔하고 효율적으로 문제를 해결할 수 있습니다.