전치 행렬 (Transpose matrix) : 왜 중요한가?

 원래 이 포스트는 곱셈까지 다루려고 했습니다. 그런데, 생각보다 내용이 길어질 듯 싶어서, 이 부분만 먼저 다루도록 하겠습니다. 전치 행렬은, 원본 행렬에서, 행과 열을 서로 맞바꾼 것을 말합니다. 예를 들어 [[1,2],[3,4]]의 전치 행렬은 [[1,3],[2,4]]가 됩니다. 희소 행렬 곱셈을 배우기 위해서, 먼저, transpose matrix에 대해서 배우는데요. 사실. 그렇게 해야 조금 더 쉽고 빠르게, 그리고 cache를 더 잘 써먹을 수 있기 때문에 그러지 않나 싶기도 하네요.

 

 

---

 예를 들어 원본 행렬에서 2행 3열에 7이라는 값이 있었습니다. 그러면, 전치 행렬에서는 3열 2행에, 7이라는 값이 있어야 합니다. 이걸 어떻게 하면 좋을까요? 데이터가 m개 있다면, 열 번호를 1번째 기준으로, 행 번호를 2번째 기준으로 한 다음에, sort를 호출하면 O(mlogm)에 정렬할 수 있습니다. 그런데, 이것보다 더 빠르게 하는 방법이 있습니다.

 

 원본이, 행 오름차, 2차 열 오름차로 정렬이 되어 있다는 점을 생각해 봅시다.

 

 

 대충 이렇게 정렬이 되어 있다면, 일단 열 데이터가 몇 개 나왔나 체크를 해 볼 수는 있을 겁니다. 예를 들자면, 1열 데이터가 몇 개가 있고, 2열 data가 몇 개나 있는지요. 위 그림에서는 1열 데이터는 1개, 2열 1개, 3열 2개, 4열 1개, 5열 1개가 있습니다.

 

 

 이 정보를 count 배열에 담습니다. 이것을 토대로 누적합을 구해줄 건데요. for loop를 돌면서, co[i] += co[i-1]을 적용시켜주면 될 거에요. 예를 들어서, co[1]은 co[1] + co[0]인데, co[0]의 값이 0이니까, co[1]은 그대로 1이 됩니다.

 

 

 다음에 co[2] 값은 어떻게 되나요? co[2] += co[1]이라 했으니까, 1에 1을 더하면 2가 됩니다. 그렇기 때문에 co[2]의 값은 2로 업데이트가 됩니다.

 

 

 다음에 co[3]은 co[3] += co[2]입니다. co[2]가 2, co[3]이 2이므로, co[3]의 값은 4로 업데이트 됩니다.

 

 

 이런 식으로 co 배열을 다 채워나가면 위와 같이 업데이트가 됩니다. 이것이 무엇을 의미하는지는 아래에서 계속 설명해 드리도록 하겠습니다.

 

 

---

 이제, 위에 있던 배열을 가지고, 새로운 배열에 채워보도록 하겠습니다. 우리가 주목해서 보아야 할 속성은, 원본에서 배열을 읽을수록, 행은 무조건 증가한다는 것입니다. 이 점을 이용한다면, 생각보다 수월하게 전치 행렬을 구현할 수 있는데요. 어떻게 할 것이냐. 거꾸로 읽습니다. 일단 원본 배열에서, (r,c) k를 읽었다고 합시다. 그러면, Transpose 된 배열의 co[c]번째에 데이터를 넣으면 됩니다. 그리고, co[c]의 값은 하나 감소시킵니다. 이것만 봐서는 무슨 소리인지는 잘 모르겠군요. 차근 차근 보여드리겠습니다.

 

 

 먼저 (4,2) 2를 읽습니다. 이 때, co[2]의 값이 2입니다. 따라서, 2번째 요소에 (4,2) 2를 넣을 건데요. 이 때, 행과 열은 바꿔서 넣습니다. 그러면, 실제로 들어갈 때에는 (2,4) 2가 들어갈 겁니다. 그리고, co[2]의 값을 하나 감소시킵니다.

 

 

 다음에 (2,4) 5를 읽습니다. 이 때, co[4]의 값은 5입니다. 따라서 5번째 위치에, (2,4) 5 데이터를 넣을 건데요. 이 때, 행과 열이 바뀌어야 하므로, 실제로는 (4,2) 5가 들어가면 되겠네요.

 

 

다음에, (2,3) 5를 넣으려고 해요. 어떻게 해야 하나요? co[3]을 읽습니다. 이 값이 4군요. 따라서, 4번째 위치에, (2,3) 5를 넣을 건데 역시 행/열이 바뀌어야 하므로, 실제로 들어가는 값은 (3,2) 5가 되겠습니다. 그리고, co[3]의 값은 하나 감소합니다.

 

 

다음에 (2,1) 3을 넣을 겁니다. 어떻게 하면 좋을까요? co[1]의 값을 읽었더니 1입니다. 그러니까, 1번째 위치에 (2,1) 3을 넣을 건데 행/열이 바뀌어야 하니까 실제로 들어가는 값은 (1,2) 3일 거에요. 그런가요? 따라서 1번째 위치에 (1,2) 3이 들어가고, co[1]의 값은 하나 감소합니다.

 

 

 그 다음에 (1,5) 3이 들어왔어요. co[5]의 값을 읽어오니 6이였네요. 따라서 6번째 위치에 행/열이 swap이 된, (5,1) 3이 들어가고, co[5]의 값은 하나 감소합니다.

 

 

 마지막으로 (1,3) 7은 어디에 넣으면 될까요? row, col이 바뀌면 데이터가 (3,1) 7로 바뀔 거고요. co[3]의 값이 3이므로, 3번째에 넣으면 됩니다. 그리고 co[3]을 감소시키면 될 거에요. 대략적으로 보면 counting sort와 유사해 보이지 않나요? 심지어, row 오름차순으로도 정렬이 되어 있기 때문에, 이러한 기법을 쓸 수 있었어요. 다음 시간에는 희소 행렬의 곱셈을 해 보도록 하겠습니다.