codewars Matrix Determinant

문제 링크입니다: https://www.codewars.com/kata/matrix-determinant/train/cpp

역행렬 determinant를 구하는 문제였습니다.

3*3 행렬 이후로도 determinant를 쉽게 구할 수 있다는 점이 놀라웠습니다.

한가지 주의할 점은 다음과 같이 3*3 행렬이 주어졌을 때

#include <iostream>

#include <vector>

using namespace std;

 

long long recursive(vector<vector<long long>> m)

{

        //기저 사례: 우리가 흔히 아는 공식

        if (m.size() == 2)

               return (m[0][0] * m[1][1]) - (m[1][0] * m[0][1]);

        long long result = 0;

        int sign = 1; //결과와 부호

        for (int i = 0; i < m[0].size(); i++)

        {

               vector<vector<long long>> newMatrix;

               for (int j = 1; j < m.size(); j++) //m[1][idx]부터가 minor 시작

               {

                       vector<long long> temp;

                       //중요 포인트

                       //|a b c|

                       //|d e f|

                       //|g h i|

                       //과 같은 행렬인 경우 b_minor는

                       //|f d| 가 아니라 |d f| 이다

                       //|i g|           |g i|

                       /*

                       if (i == m[0].size() - 2)

                       {

                              temp.push_back(m[j][m[0].size() - 1]);

                              for (int k = 0; k < i; k++)

                                      temp.push_back(m[j][k]);

                       }

                       */

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

                              if (k != i)

                                      temp.push_back(m[j][k]);

                       newMatrix.push_back(temp);

               }

               //m[0][i]와 m[0][i]_minor를 곱해주고 부호를 정해준다.

               //부호의 순서는 +, -, +, -, ...

               result += m[0][i] * sign * recursive(newMatrix);

               sign *= -1;

        }

        return result;

}

 

long long determinant(vector< vector<long long> > m)

{

        // TODO: Return the determinant of the square matrix passed in

        if (m.size() == 1)

               return m[0][0];

        //우리가 흔히 아는 공식

        else

               return recursive(m);

}

 

int main(void)

{

        vector<vector<long long>> v;

        for (int i = 0; i < 3; i++)

        {

               vector<long long> temp;

               for (int j = 0; j < 3; j++)

               {

                       long long num;

                       cin >> num;

                       temp.push_back(num);

               }

               v.push_back(temp);

        }

        cout << determinant(v) << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~