분할 정복을 이용한 거듭제곱3 [자바] 백준 10830 - 행렬 제곱 (java) 문제 : boj10830 필요 알고리즘 개념 행렬 곱셈 (수학) 행렬끼리 곱하는 방법을 알아야 한다. 분할정복을 이용한 거듭제곱 분할정복을 이용해 거듭제곱을 최적화하는 방법을 알아야 한다. 나머지 연산의 분배법칙 나머지 연산의 분배법칙을 알고 있어야 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 행렬끼리 곱하는 방법을 모른다면, 구글링을 통해 알아보자. 기초 수학이므로 반드시 알고 있어야 한다. N이 3인.. 2022. 8. 2. 백준 11444 자바 - 피보나치 수 6 (boj 11444 java) 문제 : boj11444 분할 정복을 이용한 거듭제곱 최적화(이 글)을 보면 풀 수 있다! 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { private static final long MOD = 1_000_000_007l; private long[][] matrixMult(long[][] a, long[][] b) { long[][] arr = new long[2][2]; arr[0][0] = (a[0][0]*b[0][0]%MOD + a[0][1]*b[1][0]%MOD)%MOD; arr[1][0] = (a[0][0]*b[0][1]%MOD + a[0][1]*b[1][1]%MOD)%.. 2022. 4. 13. 백준 2749 자바 - 피보나치 수 3 (boj 2749 java) 문제 : boj2749 일단 10^18 이므로 그냥 구하기는 절대로 불가능한 수치임을 알 수 있다 ㅋㅋㅋ. 내 경우엔 피보나치의 경우 행렬의 거듭 제곱으로 풀 수 있다는걸 이미 알고 있었으므로 공식만 찾아서 풀었다. 공식은 f(n)이 n번째 피보나치라 할 때, 아래와 같다. 이 때 거듭 제곱의 계산은, 분할 정복을 활용해서 O(logN)에 빠르게 구할 수 있다. 예를들어 A^8 = ((A^2)^2)^2 임을 활용하는 것이다. 혹시 모른다면 예전에 백준 게시판에 답글달았던 이 글을 참고하면 된다. 그보다, 다른분의 풀이도 보다보니 '피사노 주기'라는 것도 알게 되었다. 피보나치 수를 어떠한 수로 나눈 나머지는 항상 주기성을 가진다고 한다. 수의 세계는 신비로운 것 같다. 코드 : github import .. 2022. 4. 5. 이전 1 다음
