[99club/TIL] 2주차 - 금요일 TIL(Today I Learned)

안녕하세요. delay100 입니다!

오늘은 오랜만에 고등학교 때 친구를 만나고 왔어요.

그래서 시간이 많이 늦었지만(문제 풀기 전 - 오후 10시 50분) 그래도 오늘의 문제는 풀어보았습니다.

---

미들러 문제. 행렬의 곱셈

https://school.programmers.co.kr/learn/courses/30/lessons/12949

프로그래머스

 

이 문제를 풀기 위해 행렬의 곱셈에 대해 다시 리마인드가 필요합니다. 저도 잘 기억나지 않아서 아래에 링크를 보고 다시 파악하고 왔습니다.

https://mathbang.net/562#gsc.tab=0

행렬의 곱셈, 행렬의 거듭제곱

사실 행렬의 곱셈을 실제로 할 수 있으면 코드를 짜는 것은 크게 어렵지 않습니다.

먼저, 정답 배열은 ansewr = [arr1 배열의 가로열 개수][arr2 배열의 세로열 개수]로 나타냅니다.

그리고 정답 배열에 각각의 자리에 값을 넣어주기 위한 2중 for문을 만듭니다.

 

마지막으로 코드에서 핵심 부분인데요,

int temp = 0;
for(int k=0; k<arr1Length; k++) { // arr1Length = arr1[1].length;
    temp += (arr1[i][k] * arr2[k][j]);
}

i값과 j값은 위의 2중 for문으로 고정해두고, 각 행렬의 값을 계산하기 위해 1개의 for문을 더 만들었습니다.

k값을 증가시키면서 arr1의 행과 arr2의 열에 위치한 값을 꺼내옵니다.

 

코드에서 for문을 3개 사용하여 시간복잡도는 O(n^3)이지만,

arr1, arr2의 행과 열의 길이는 2 이상 100 이하를 만족시켜야하는 문제의 조건은 만족합니다. 

최대 100*100*100이기 떄문이죠!

*사실 2중 for문만 이용하고 싶었지만 temp 부분의 코드를 어떻게 더 간소화 해야할 지 감이 오질 않아서 3중 for문을 이용하게 되었습니다..ㅠㅠ

class Solution {
    public int[][] solution(int[][] arr1, int[][] arr2) {
    // 정답 배열은 ansewr = [arr1 배열의 가로열 개수][arr2 배열의 세로열 개수]
        int[][] answer = new int[arr1.length][arr2[1].length];
        int answerLength = answer.length;
        int answer1Length = answer[1].length;
        int arr1Length = arr1[1].length;
        
     // 그리고 정답 배열에 각각의 자리에 값을 넣어주기 위한 2중 for문을 만듭니다.
        for(int i=0; i<answerLength; i++) {
            for(int j=0; j<answer1Length; j++) {
                int temp = 0;
                for(int k=0; k<arr1Length; k++) {
                    temp += (arr1[i][k] * arr2[k][j]);
                }
                answer[i][j] = temp; // 정답 배열의 각 자리에 값을 넣어줌
            }
        }
        
        return answer;
    }
}

---

+ 비기너 문제

나누어 떨어지는 숫자 배열(https://school.programmers.co.kr/learn/courses/30/lessons/12910)

프로그래머스

+ 챌린저 문제

디펜스 게임 (https://school.programmers.co.kr/learn/courses/30/lessons/142085)

프로그래머스

---

오늘도 봐 주셔서 감사합니다.