C++ 행렬 순회 완전 정복: 행 우선(Row-Major) vs 열 우선(Column-Major)

2차원 행렬(matrix)은 크게 두 가지 방식으로 순회(traversal)할 수 있습니다. 행 우선(row-major) 순회는 첫 번째 행부터 시작하여 두 번째 행, 세 번째 행 순으로 마지막 행까지 차례대로 방문하며, 각 행의 요소는 인덱스 0부터 마지막 인덱스까지 순서대로 읽습니다.

반면 열 우선(column-major) 순회는 첫 번째 열부터 마지막 열까지 순서대로 요소를 탐색하는 방식입니다.

2차원 행렬을 M[i][j]로 표현할 때, 인덱스 i는 행(row)을, 인덱스 j는 열(column)을 나타냅니다.

행 우선 순회의 인덱스 흐름

• i = 0번째 행, 0 ≤ j < 마지막 인덱스
• i = 1번째 행, 0 ≤ j < 마지막 인덱스
• ...
• i = 마지막 행, 0 ≤ j < 마지막 인덱스

열 우선 순회의 인덱스 흐름

• j = 0번째 열, 0 ≤ i < 마지막 인덱스
• j = 1번째 열, 0 ≤ i < 마지막 인덱스
• ...
• j = 마지막 열, 0 ≤ i < 마지막 인덱스

어떤 순회 방식을 사용하더라도 2차원 배열 M[i][j]에서 인덱스의 의미는 동일합니다. 즉, i는 항상 행을, j는 항상 열을 나타냅니다.

예제

입력 −

int arr[MAX][MAX] = { {1,2,3,4,5},{6,7,8,9,0},
   {5,4,3,2,1},{0,0,0,0,0},
   {8,9,7,6,1}};

출력 −

Row Major Traversal
1 2 3 4 5
6 7 8 9 0
5 4 3 2 1
0 0 0 0 0
8 9 7 6 1
Column Major Traversal
1 6 5 0 8
2 7 4 0 9
3 8 3 0 7
4 9 2 0 6
5 0 1 0 1

설명 − 행 우선 순회에서는 각 행이 그대로 한 줄씩 출력되고, 열 우선 순회에서는 같은 열에 속한 요소들이 한 줄에 모여 출력되는 것을 확인할 수 있습니다.

입력 −

int arr[MAX][MAX] = { {1,1,1,1,1},{2,2,2,2,2},
   {3,3,3,3,3},{4,4,4,4,4},
   {5,5,5,5,5}};

출력 −

Row Major Traversal
1 1 1 1 1
2 2 2 2 2
3 3 3 3 3
4 4 4 4 4
5 5 5 5 5
Column Major Traversal
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5

설명 − 모든 행이 같은 값으로 이루어진 경우, 행 우선 순회에서는 행 번호별 값이, 열 우선 순회에서는 열 방향으로 값이 반복되어 출력됩니다.

알고리즘 접근 방식

이 접근법에서는 중첩된 두 개의 for 루프를 사용하여 입력된 2차원 행렬을 행 우선 및 열 우선 방식으로 출력합니다.

• 2차원 행렬을 나타내는 배열 arr[][]를 준비합니다.
• 행 요소와 열 요소의 인덱스로 사용할 변수 i와 j를 선언합니다.
• 행 우선 순회: i = 0부터 i < MAX까지 바깥쪽 for 루프를 실행하여 행 단위로 이동합니다.
• 그 안에서 j = 0부터 j < MAX까지 중첩 for 루프를 실행하여 i번째 행의 모든 요소를 탐색합니다.
• arr[i][j]를 출력합니다.
• 열 우선 순회: j = 0부터 j < MAX까지 바깥쪽 for 루프를 실행하여 열 단위로 이동합니다.
• 그 안에서 i = 0부터 i < MAX까지 중첩 for 루프를 실행하여 j번째 열의 모든 요소를 탐색합니다.
• arr[i][j]를 출력합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
#define MAX 5
int main(){
   int arr[MAX][MAX] = { {1,2,3,4,5},{6,7,8,9,0},{5,4,3,2,1},{0,0,0,0,0},{8,9,7,6,1}};
   int i, j;
   cout<<"Row Major Traversal "<<endl;
   for(i=0;i<MAX;i++){
      cout<<endl;
      for(j=0;j<MAX;j++){
         cout<<" "<<arr[i][j];
      }
   }
   cout<<endl<<endl;
   cout<<"Column Major Traversal "<<endl;
   for(j=0;j<MAX;j++){
      cout<<endl;
      for(i=0;i<MAX;i++){
         cout<<" "<<arr[i][j];
      }
   }
   return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

Row Major Traversal
1 2 3 4 5
6 7 8 9 0
5 4 3 2 1
0 0 0 0 0
8 9 7 6 1
Column Major Traversal
1 6 5 0 8
2 7 4 0 9
3 8 3 0 7
4 9 2 0 6
5 0 1 0 1

핵심 포인트

두 순회 방식의 차이는 오직 루프 변수의 역할뿐입니다. 행 우선 순회에서는 바깥쪽 루프가 행(i)을 담당하고, 열 우선 순회에서는 바깥쪽 루프가 열(j)을 담당합니다. 시간 복잡도는 두 방식 모두 O(N×M)으로 동일하지만, C++은 배열을 메모리에 행 우선으로 저장하기 때문에 캐시 지역성(cache locality) 측면에서 행 우선 순회가 일반적으로 더 빠른 성능을 보입니다.