본문 바로가기

전체 글153

[백준/C,C++] 10830번: 행렬 제곱 www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net hackids.tistory.com/52 [백준/C,C++] 1629번: 곱셈 www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net A의 B제곱을 C로 나눈 나머지를 구.. hackids.tistory.com hackids.tistory.com/55.. 2021. 3. 26.
[백준/C,C++] 2740번: 행렬 곱셈 www.acmicpc.net/problem/2740 2740번: 행렬 곱셈 첫째 줄에 행렬 A의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 순서대로 주어진다. 그 다음 줄에는 행렬 B의 크기 M과 K가 주어진다. 이어서 M개의 줄에 행렬 B의 원소 K개 www.acmicpc.net 행렬 곱을 구현하면 되는 문제입니다. A가 $\begin{pmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{pmatrix}$, B가 $\begin{pmatrix} b_{11} & b_{12} \\ b_{21} & b_{22} \end{pmatrix}$ 라고 가정했을 때 두 행렬의 곱은 $\begin{pmatrix} a_{11}b_{11}+a_{12}b_{2.. 2021. 3. 26.
[백준/C,C++] 11401번: 이항 계수 3 www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 과 비슷한 문제입니다. 다른 점은 입력 값인데 11051번: 이항 계수 2와 비교하여 훨씬 큽니다. 최댓값이 들어올 경우 DP로는 시간 제한에 걸리기 때문에, 분할 정복을 이용하여 풀어야합니다. 이항 계수는 $.. 2021. 3. 26.
[백준/C,C++] 11051번: 이항 계수 2 www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net DP를 이용해 이항 계수를 푸는 문제입니다. 이항 계수 $\binom{N}{K}$ 는 $\frac{n!}{k!(n-k)!}$ 로 나타낼 수 있습니다. 하지만 주어지는 수의 범위가 $1 \le N \le 1,000, 0 \le K \le N$ 으로, 팩토리얼을 그대로 구현해서 쓴다면 값이 매우 커지게 됩니다. 값이 매우 커지기 때문에 모듈러 연산을 한 값을 출력해야 하는데, 모듈러 연산은 분수에 적용하기 힘들어 해당 값을 구할 수 없게 됩니다. 이항 계수를 기하학적 형태로 표현한 파.. 2021. 3. 26.

티스토리툴바