SY DevLog

10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 백준 2740번 : 행렬 곱셈을 응용한 문제이다. B의 범위가 매우 크기 때문에 단순히 2740번 문제에서 for문을 하나 더 추가해서 문제를 풀면 시간초과가 난다. 이 문제는 행렬을 곱하는 똑같은 과정을 반복하기 때문에 이미 한번 계산한 결과는 다시 재사용하면 계산 횟수를 줄일 수 있다. 따라서 분할과 정복 방법으로 문제를 해결하였다. 만약 B가 짝수라면, B번 행렬을 곱한 결과는 B/2번 행렬을 곱한 결과 * B/2번 행렬을 곱한 결과가 된다. 이 때 B/2번 행렬을 곱한 ..

1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서 www.acmicpc.net 분할하여 같은 동작을 반복하기 때문에 재귀를 이용하여 풀 수 있다. 처음에는 1, 2, 3, 4 분면의 모든 경우의 수를 다 재귀함수 호출을 했더니 시간 초과가 나왔다. 그래서 조건문을 이용하여 (r, c)이 포함된 사각형만 선별적으로 재귀를 실행하도록 변경하였다. 2차원 배열의 정보를 가장 왼쪽 위 좌표(i, j) 와 한 변의 길이 size로 나타낼 때, 이 2차원 배열을 4등분한 각각의 사각형은 다음과 같이 표현이 가능하다. - 2사분면 : (i, j..