코딩테스트 : 1629번 곱셈
| 0.5 초 (추가 시간 없음) | 128 MB | 152310 | 43910 | 31775 | 27.813% |
문제
자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다.
출력
첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다.
public class BackJoon
{
static void Main()
{
int[] abc = Console.ReadLine().Split().Select(int.Parse).ToArray();
int a = abc[0];
int b = abc[1];
int c = abc[2];
long temp = 1;
for (int i = 1; i <= b; i++)
{
temp *= a;
temp %= c;
}
Console.WriteLine(temp);
}
}
이게 왜 분할정복 칸에 있을까 하면서 단순하게 풀었더니 시간초과가 떴다.
당연히.. 생각이 있으시니까... 분할정복에...
public class BackJoon
{
static void Main()
{
int[] abc = Console.ReadLine().Split().Select(int.Parse).ToArray();
int a = abc[0];
int b = abc[1];
int c = abc[2];
Console.WriteLine(Power(a,b,c));
}
public static long Power(int a, int b, int c)
{
if (b == 0) return 1;
long half = Power(a, b / 2, c);
long result = (half * half) % c;
if (b % 2 != 0)
{
result = (result * a) % c;
}
return result;
}
}
시간 복잡도를 O(log₂b)로 줄여서 풀게 되었다.
코딩테스트 : 2740번 행렬 곱셈
| 1 초 | 128 MB | 22123 | 14992 | 13064 | 68.954% |
문제
N*M크기의 행렬 A와 M*K크기의 행렬 B가 주어졌을 때, 두 행렬을 곱하는 프로그램을 작성하시오.
입력
첫째 줄에 행렬 A의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 순서대로 주어진다. 그 다음 줄에는 행렬 B의 크기 M과 K가 주어진다. 이어서 M개의 줄에 행렬 B의 원소 K개가 차례대로 주어진다. N과 M, 그리고 K는 100보다 작거나 같고, 행렬의 원소는 절댓값이 100보다 작거나 같은 정수이다.
출력
첫째 줄부터 N개의 줄에 행렬 A와 B를 곱한 행렬을 출력한다. 행렬의 각 원소는 공백으로 구분한다.
using System.Text;
public class BackJoon
{
public static void Main()
{
int[] NM = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
int N = NM[0];
int M = NM[1];
int[,] A = new int[N, M];
for (int row = 0; row < N; row++)
{
int[] rowData = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
for (int col = 0; col < M; col++)
{
A[row, col] = rowData[col];
}
}
int[] MK = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
int K = MK[1];
int[,] B = new int[M, K];
for (int row = 0; row < M; row++)
{
int[] rowData = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
for (int col = 0; col < K; col++)
{
B[row, col] = rowData[col];
}
}
int[,] answer = new int[N, K];
StringBuilder sb= new StringBuilder();
for (int row = 0; row < N; row++)
{
for (int col = 0; col < K; col++)
{
int temp = 0;
for (int i = 0; i < M; i++)
{
temp += A[row,i] * B[i,col];
}
answer[row, col] = temp;
sb.Append(answer[row,col] + " ");
}
sb.AppendLine();
}
Console.WriteLine(sb.ToString());
}
}
코딩테스트 : 10830번 행렬 제곱
| 1 초 | 256 MB | 46823 | 16956 | 13443 | 34.747% |
문제
크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.
입력
첫째 줄에 행렬의 크기 N과 B가 주어진다. (2 ≤ N ≤ 5, 1 ≤ B ≤ 100,000,000,000)
둘째 줄부터 N개의 줄에 행렬의 각 원소가 주어진다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0이다.
출력
첫째 줄부터 N개의 줄에 걸쳐 행렬 A를 B제곱한 결과를 출력한다.
using System.Text;
public class BackJoon
{
public static void Main()
{
int[] AB = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
int A = AB[0];
int B = AB[1];
int[,] matrix = new int[A, A];
int[,] temp = new int[A, A];
for (int i = 0; i < A; i++)
{
int[] row = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
for (int j = 0; j < A; j++)
{
matrix[i, j] = row[j];
temp[i, j] = row[j];
}
}
for (int i = 1; i < B; i++)
{
temp = Multiply(temp, matrix);
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < A; i++)
{
for (int j = 0; j < A; j++)
{
sb.Append(temp[i, j] + " ");
}
sb.AppendLine();
}
Console.WriteLine(sb);
}
public static int[,] Multiply(int[,] A, int[,] B)
{
int[,] C = new int[A.GetLength(0), A.GetLength(1)];
for (int row = 0; row < A.GetLength(0); row++)
{
for (int col = 0; col < A.GetLength(1); col++)
{
int temp = 0;
for (int i = 0; i < A.GetLength(0); i++)
{
temp += ((A[row, i] * B[i, col])) % 1000;
}
C[row, col] = temp % 1000;
}
}
return C;
}
}
당연하게도 오류가 발생했다. (OverFlow)
using System.Text;
public class BackJoon
{
public static void Main()
{
long[] AB = Console.ReadLine().Split(' ').Select(long.Parse).ToArray();
long A = AB[0];
long B = AB[1];
long[,] temp = new long[A, A];
for (long i = 0; i < A; i++)
{
long[] row = Console.ReadLine().Split(' ').Select(long.Parse).ToArray();
for (long j = 0; j < A; j++)
{
temp[i, j] = row[j];
}
}
temp = Power(temp, B);
StringBuilder sb = new StringBuilder();
for (long i = 0; i < A; i++)
{
for (long j = 0; j < A; j++)
{
sb.Append(temp[i, j] + " ");
}
sb.AppendLine();
}
Console.WriteLine(sb);
}
public static long[,] Multiply(long[,] tempMatrix, long[,] baseMatrix)
{
long[,] C = new long[tempMatrix.GetLength(0), tempMatrix.GetLength(1)];
for (long row = 0; row < tempMatrix.GetLength(0); row++)
{
for (long col = 0; col < tempMatrix.GetLength(1); col++)
{
long temp = 0;
for (long i = 0; i < tempMatrix.GetLength(0); i++)
{
temp += ((tempMatrix[row, i] * baseMatrix[i, col])) % 1000;
}
C[row, col] = temp % 1000;
}
}
return C;
}
public static long[,] Power(long[,] matrix, long count)
{
if (count == 1)
{
int size = matrix.GetLength(0);
long[,] result = new long[size, size];
for (int i = 0; i < size; i++)
for (int j = 0; j < size; j++)
result[i, j] = matrix[i, j] % 1000;
return result;
}
if (count % 2 == 0)
{
var half = Power(matrix, count / 2);
return Multiply(half, half); // 중복 호출 제거!
}
else
{
var half = Power(matrix, count / 2);
return Multiply(Multiply(half, half), matrix);
}
}
}
세 가지 정도를 고치는데 오래걸렸고, 그 중 한 가지는 도저히 모르겠어서 도움을 받았다.
1. Mulitply와 Power의 분리
분리를 하는 것이 좋다, 처음에 할 때에는 Multiply 안에 분할해서 곱하는 재귀적인 함수도 같이 구현을 했는데,
이는 로직을 잘게 분리해서 하는 것보다 복잡하고 꼬일 가능성이 높다.
단일 함수는 단일 역할만을 할 수 있도록 분리해 주었다.
2. 중복 호출 제거
처음에는 Power함수에서 return Multiply ( Power(matrix, count/2) ,Power(matirx,count/2)로 해 주었다,
이렇게 하면 Power라는 함수로 하는 의미가 줄어든다. ( 함수를 중복 계산하기 때문에 )
한 번 계산한 것을 할당해서 진행해주었다.
3 . 참조 변화
if (count == 1)
{
int size = matrix.GetLength(0);
long[,] result = new long[size, size];
for (int i = 0; i < size; i++)
for (int j = 0; j < size; j++)
result[i, j] = matrix[i, j] % 1000;
return result;
}
처음에는 count가 1이면 그냥 matrix를 return해 주었다. 다만
들어오는 matrix가 참조형이기 때문에, 예기치 않은 변화가 존재하고 다른 연산에 다시 쓰이게 된다면 오류가 발생한다.
따라서 안전하게 복사해서 리턴해주어 원본을 보호하고 참조 오류를 방지했다.
다시 풀 문제에 저장했다. 위의 두 문제를 혼합하는 방식이다.
'코딩테스트' 카테고리의 다른 글
| 11444 피보나치 수 6 (0) | 2025.04.12 |
|---|---|
| 2630번 색종이 만들기, 1992번 쿼드 트리 (0) | 2025.04.07 |
| 1541번 잃어버린 괄호 (0) | 2025.04.05 |
| 25682번 체스판 다시 칠하기 2, 1931번 회의실 배정 (0) | 2025.04.03 |
| 16139번 인간-컴퓨터 상호 작용 , 10986번 나머지 합 , 11660번 구간 합 구하기 5 (0) | 2025.04.02 |