문제 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 이 문제는 행렬의 거듭제곱을 이용해 피보나치를 구하는 방법으로 해결할 수 있고 구하는 방법은 다음과 같다. 피보나치 수열을 수식으로 나타내면 $f_{n+2} = f_{n+1} + f_{n}$ 이고, 식을 행렬의 곱으로 나타낼 수 있다. $f_{n+2} = f_{n+1} + f_{n} \\ = 1 \times f_{n+1} + 1 \times f_{n} \\ = \begin{bmatrix}1&1\end{bmatrix} \times \begin{bmatrix}f_{n+1} \\ f_{n}\end{bmatrix}$ 2 X 2 행렬을 만..

문제 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 곱셈 공식을 활용한 분할 정복을 수행하는 재귀 함수로 해결하면 된다. (1629번 곱셈 문제와 같다.) 재귀 함수에서는 다음과 같이 지수를 반으로 나눠가며 계산한다. 지수가 1인 경우에 입력받은 행렬을 그대로 리턴하면 된다. - 지수가 짝수인 경우 $a^n = a^{n/2} \times a^{n/2}$ - 지수가 홀수인 경우 $a^n = a^{n/2} \times a^{n/2}\times a$ 행렬의 곱셈은 다음 이미지와 같은 방식으로 처리되며, 3중 for문으로 구..

문제 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 풀이 문제는 A를 B번 곱한 수를 C로 나눈 나머지를 구하는 것이다. 반복문으로 해결하면 시간초과가 발생한다. 풀기 위해서는 지수 법칙과 모듈러 연산 성질에 대해 알고 있어야 한다. - 지수 법칙: $a^{(n+m)} = a^n \times a^m$ - 모듈러 연산 곱셈 성질: $(a\times b)\mod c = (a\mod c \times b\mod c)\mod c$ 이 두 성질을 활용하여 재귀 함수를 만들면 된다. 함수는 지수가 1이 될 때까지 B를 절반으로 나누어가며 계산한다. - 지수가 짝수인 경우 $a^n = ..

문제 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 풀이 입력받은 종이를 분할정복을 통해 처리하여 각 숫자(1, 0, -1)의 개수를 세는 문제이다. 입력받은 종이를 3X3 크기로 나누어 분할정복을 수행한다. 만약 현재 영역의 숫자가 모두 같다면 해당 숫자의 개수를 세고, 그렇지 않다면 3X3 영역을 다시 9개의 부분 영역으로 나누어 재귀적으로 처리한다. 이를 통해 종이 전체를 처리하면서 1, 0, -1의 개수를 각각 세어 결과를 출력한다. 코드 fun main() { val br = System..

문제 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 풀이 분할정복이란 큰 문제를 작은 문제로 나누어 해결하는 재귀적인 알고리즘이다. 일반적으로 세 단계로 구성된다. - 분할(Divide): 주어진 문제를 더 작은 부분 문제들로 분할한다. 부분 문제들은 원래 문제와 동일한 형태를 가진다. - 정복(Conquer): 부분 문제들을 재귀적으로 해결하여 부분 해를 구한다. - 통합(Combine): 작은 부분 문제들의 해를 결합하여 원래 문제의 해를 구한다. 문제는 분할정복을 활용하여 종..