행렬제곱2 [알고리즘] 분할 정복 & 백준(곱셈, 행렬 제곱) 분할 정복(Divide & Conquer) 분할 정복은 문제를 여러개로 나누어서 푸는 알고리즘이다. 교수님께서 미친듯이 강조해서 "디바이드앤퀀쿼"만 기억이 난다.. * 동적 계획법(DP)과의 차이점 1. 동적 계획법은 분할한 문제들이 서로 영향을 미침. 2. 분할 정복은 분할한 문제들이 서로 영향을 미치지 않음. * 분할 정복의 필요조건 1. 문제를 나눌 수 있어야 한다. 2. 부분 문제의 답을 이용하여 원래 문제의 답을 계산하는 방법이 있어야 한다. * 분할 정복의 알고리즘의 접근법 1. 분할: 문제를 작은 문제로 분할하는 과정 2. 정복: 분할한 작은 문제들을 해결 3. 조합: 작은 문제에 대한 결과를 원본 문제에 대한 결과로 조합한다. 분할 정복을 이용한 거듭제곱 먼저, 거듭제곱이란 주어진 수를 주.. 2022. 10. 5. [알고리즘] 행렬 곱셈, 행렬 제곱 행렬 제곱의 문제를 풀어야하는데, 행렬 곱셈을 하는 법부터 정확히 알지 못 했기 때문에 정리하는 글이다. 1. 2740: 행렬 곱셈 문제 N*M크기의 행렬 A와 M*K크기의 행렬 B가 주어졌을 때, 두 행렬을 곱하는 프로그램을 작성하시오. => 행렬의 곱셈 공식에 의해서 N*M, M*K 행렬을 곱하면 N*K 행렬이 된다. 오른쪽 사진에 의하면, 3 x 2 행렬과 2 x 3 행렬이다. 3 x 2 행렬과 2 x 3 행렬을 곱하면 3 x 3 행렬이 만들어진다. 두 행렬을 곱하면 위의 왼쪽 사진과 같은 결과가 나온다. 1) N과 K에 대해 이중 for문을 돌면서, 2) 벡터의 크기 M만큼 for 돌면서 행벡터와 열벡터의 각 요소 곱의 더하기 값을 구해주고 3)결과 행렬에(2차원 리스트) 넣어주면 된다. impo.. 2022. 10. 4. 이전 1 다음
