#10830 행렬제곱

💯 N * N 행렬을 입력받은 수 만큼 제곱을 시키고 10000으로 나눈 수의 나머지를 행렬로 출력하는 문제인듯

<💭 방법>

🎈 1 분할 정복을 사용하는 방법

• 거듭 제곱의 성질을 이용하여 문제를 푸는 방법
  

출처 https://mygumi.tistory.com/319

• 지수를 입력으로 받는 함수를 만들어 문제를 해결
• 일단 먼저 가장 작은 문제인 지수가 1인 경우로 나누고 병합을 하는 구조
• 홀수인 경우는 지수에서 1을 뺀 값을 반환받아서 지수가 1인 행렬을 한번 더 곱해줌

<😥 첫번째 코드>

def power(exp):
    global matrix_

    if exp == 1:
        return matrix_ % 1000

    if exp % 2 == 0:
        n = power(exp // 2)

        return np.dot(n, n) % 1000

    elif exp % 2 == 1:
        n = np.dot(power(exp-1), matrix_)

        return n % 1000

안된 이유 : 런타임 에러가 자꾸 떠서 왜그런가 싶었는데 다들 그 사실 아시나요 ?? 백준은 numpy가 안된다는 사실을 ???? 저는 방금 알았는데 ,,, for문으로 다시 곱셈해야 될 듯 ..

<😍 두번째 코드>

def power(exp):
    global n, matrix

    matrix_ = [[0 for _ in range(n)] for _ in range(n)]

    if exp == 1:
        for i in range(n):
            for j in range(n):
                matrix[i][j] %= 1000

        return matrix

    if exp % 2 == 0:
        a = power(exp // 2)

        for i in range(n):
            for j in range(n):
                for k in range(n):
                    matrix_[i][j] += a[i][k] * a[k][j]
        
        for i in range(n):
            for j in range(n):
                matrix_[i][j] %= 1000

        return matrix_

    elif exp % 2 == 1:
        a = power(exp-1)
        
        for i in range(n):
            for j in range(n):
                for k in range(n):
                    matrix_[i][j] += a[i][k] * matrix[k][j]

        for i in range(n):
            for j in range(n):
                matrix_[i][j] %= 1000

        return matrix_

• 일단 먼저 행렬을 곱셈 같은 경우에는 한 자리에 들어갈 수 들이 곱셈이 끝나면 모두 더한 결과가 최종 한 자리의 결과가 된다. 저장하는 것을 받을 리스트를 구현해 주고, 최종 return 값은 저장된 것들로 이루어진 리스트로 한다.

느낀점

처음 문제를 봤을 때 분할 정복을 왜 사용해야 되는지 이해가 안갔다. 그냥 계속해서 곱하면 안되는가에 대해 고민을 해봤는데, 생각보다 답을 찾아내는게 쉽지 않았고 결국 백준에서 제공되는 관련된 알고리즘을 본 결과 분할 정복을 이용한 거듭제곱이라는 것이 있다는 것을 알게 되었다. 런타임 에러가 자꾸 떠서 왜그런가 싶었는데 ,,, 다들 numpy를 사용하지 않고 푼 경우 밖에 없었다 ,, 혹시나 했는데 백준은 numpy사용이 안된다 ,, 프로그래머스는 사용 되던데 ㅠㅠ 리스트로 구현하는게 이렇게 어려운 일이었다니 ,, 너무 헷갈린다 ,,