분할정복 (4) 썸네일형 리스트형 [백준] 10830번: 행렬 제곱 - JAVA 🔗 문제 링크 BOJ 10830번: 행렬 제곱 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 📝 풀이 과정 [백준] 1629번: 곱셈 - JAVA에서 확장된 문제다. 거듭제곱을 분할 정복으로 계산하는 같은 방식의 문제이지만, 행렬이라는 조건이 추가되었다. 행렬의 곱셈에서 A x B의 (i, j)의 값을 구하기 위해서는 A의 i열의 곱과 B의 j행의 곱을 순차적으로 더해 구해야 한다는 것을 이용해 곱셈하는 함수인 multipleMatrix(m1, m2)를 만들어 주었다. 기존 거듭제곱 문제에서는 거듭 제곱값으로 주어진 값이 .. [백준] 1629번: 곱셈 - JAVA 🔗 문제 링크 BOJ 1629번: 곱셈 📝 풀이 과정 주어진 숫자를 제곱해야 하는데 단순하게 반복문으로 제곱수를 구하게 되면 시간복잡도는 B의 크기만큼 소요되게 되고 B의 최대 크기는 $2^{31}-1$로 시간 제한을 초과하게 된다. 따라서 정해진 제곱을 분할하는 방식을 사용해 시간을 줄여야 한다. $$ A^{10} = A^{5 + 5} = A^5 \times A^5 $$ 먼저 제곱은 위의 식처럼 분할이 가능하다. 따라서 제곱을 순차적으로 하나씩 곱하면서 구하지 않고, $A^5$를 구한 뒤 그 수를 제곱하면 $A^{10}$을 쉽게 구할 수 있는 것이다. 만약 제곱수가 11(홀수)이라면 $A^5$(절반)를 제곱한 뒤 그 수에 $A$를 곱하면 되기 때문에 빠르게 답을 구할 수 있게 된다! static lon.. [백준] 1074번: Z - JAVA 🔗 문제 링크 BOJ 1074번:Z 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서 www.acmicpc.net 📝 풀이 과정 N = 2일 때의 탐색 모형이다. 처음 큰 $2^2$ x $2^2$의 사각형을 4등분으로 분할한 뒤 Z모양으로 탐색하고, $2^1$ x $2^1$을 Z모향으로 탐색을 하게 되면 위와 같은 그림이 나오게 된다. 처음 문제를 봤을 때, 단순 분할 + 재귀 문제라고 생각하고 모든 칸을 방문하며 count 했고, 실패했다... 시간 복잡도를 잘 따지지 않아 생겼던 문제인데, N의 범위는 1 [백준] 2630번: 색종이 만들기 - JAVA 문제 링크 BOJ 2630번: 색종이 만들기 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 풀이 과정 문제의 조건이 주어지고 만약 조건이 성립하지 않으면 분할하여 반복하는 구조 ⇒ 분할정복 시작점을 두고 시작점과 주어진 칸들의 값이 일치한다면 카운트, 아니라면 4분할 하는 방법으로 접근하였다 이 문제에서 핵심적인 부분은 divide함수 부분이다. 색종이의 길이를 n, 좌상단 시작점을 (y, x)로 변수명을 정하고 시작하였다. 만약 시작점과 종이의 칸의 숫자가 다르다면 분할을 해야하.. 이전 1 다음
