[프로그래머스 1단계] 알고리즘 5. 행렬 합

문제 출처는 프로그래머스 알고리즘 연습 에서 볼 수 있습니다!(https://programmers.co.kr/learn/challenges)

알고리즘 5. 두 m x n 행렬의 합을 구하시오 (+ m x n , n x k 행렬의 곱 구하기)

#include<iostream>

#include<vector>

using namespace std;

vector<vector<int> > sumMatrix(vector<vector<int> >A, vector<vector<int> >B)

{

  vector<vector<int> > answer = A;

  

  return answer;

}

int main()

{

  vector<vector<int> > a{{1,2},{2,3}}, b{{3,4},{5,6}};

  vector<vector<int> > answer = sumMatrix(a,b);

  for(int i=0;i<answer.size();i++)

  {

    for(int j=0;j<answer[0].size();j++)

    {

      cout<<answer[i][j]<<" ";

    }

    cout<<"\n";

  }

}

풀이: 이건 뭐 쉽다.. 같은 행 같은 열의 행렬이면 같은 자리끼리 더하면 된다. 즉

answer[i][j] = A[i][j] + B[i][j]

이다. 따라서 코드는 다음과 같이 작성할 수 있다.(sumMatrix 부분만 작성하겠다.)

vector<vector<int> > sumMatrix(vector<vector<int> >A, vector<vector<int> >B)

{

  vector<vector<int> > answer = A;

  

for(int i=0; i<answer.size(); i++){

for(int j=0; j<answer[0].size(); j++){

answer[i][j] += B[i][j];

}

}

  return answer;

}

사실 너무 쉬워서 할 말이 없다.. 필자는 이걸 풀면서 1시간 정도 걸렸는데 그 이유는 처음에 문제를 행렬의 곱으로 봐서 그렇다. 그래서 푼게 아까워서 여기에 올려본다. 먼저 코드를 보고 풀이를 보는게 여러모로 잘 이해가 될 듯 싶다. 

vector<vector<int> > mulMatrix(vector<vector<int> > A, vector<vector<int> > B){

  vector<vector<int> > answer;

  for(int i=0; i<A.size(); i++){

    vector<int> tmp_col;

    for(int k=0; k<B[0].size(); k++){

      int sum=0;

      for(int j=0; j<A[0].size(); j++){ //A[0].size() == B.size()

          sum += (A[i][j] * B[j][k]);

      }

      tmp_col.push_back(sum)

    }

    answer.push_back(tmp_col);

  }

  return answer;

}

이거는 행렬 곱은 다음의 조건을 따른다. 

1. A 는 m x n, B 는 n x k 행렬일 때 가능하다. 

2. AB = m x k 행렬이 된다.

이것을 알고 있으면 문제 풀기는 편하다. 각 행의 열은 다음과 같다.

Answer[m][k] =  A[m][0,,n] x B[0..n][k] 의 합 

사실 이 문제는 A[0].size() == B.size() 를 먼저 묻는것이 타당하다. 그러나 어디까지나 문제이기 때문에 생략하였다. 배열의 경우 캐시 친화적인 코드를 작성하여 더 개선할 수 있으나 벡터가 가능한지는 모르겠다... 사실 행렬도 오래 걸리지 말았어야 했는데 아직 부족한게 많나보다.