C++105 [C++] 백준 2740번 : 행렬 곱셈 https://www.acmicpc.net/problem/2740 2740번: 행렬 곱셈 첫째 줄에 행렬 A의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 순서대로 주어진다. 그 다음 줄에는 행렬 B의 크기 M과 K가 주어진다. 이어서 M개의 줄에 행렬 B의 원소 K개 www.acmicpc.net 문제 풀이 쉬운 행렬의 곱셈을 구하는 문제이다. 느낀 점 크게 어렵진 않으나 행렬 연산을 줄이는 방법으로 '스트라센 알고리즘'이 있다. 추가적인 공부가 필요할 것 같다. 코드 #include using namespace std; int n, m, k; int m1[101][101]; int m2[101][101]; int m3[101][101]; int main() { ios_b.. 2021. 7. 30. [C++] 백준 11401번 : 이항 계수 3 https://www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 풀이 이전 정수론 단계에서 풀었던 문제의 확장 버전이다. n과 k에 대해서 조합을 구하는 문제인데 n과 k의 범위가 400만이다. 오버플로우가 무조건 발생하기 때문에 1000000007로 나눈 나머지를 구해야 한다. 범위가 너무 크기 때문에 일반적인 방법으로 풀 수 없어 여기서 곱셈의 역원을 이용해야 한다. 곱셈의 역원은 을 만족하는 을 의미한다. 나머지 연산 중 나눗셈에 대해서는 분배 법칙이 성립하지 않아 곱셈의.. 2021. 7. 30. [C++] 백준 2004번 : 조합 0의 개수 https://www.acmicpc.net/problem/2004 2004번: 조합 0의 개수 첫째 줄에 정수 $n$, $m$ ($0 \le m \le n \le 2,000,000,000$, $n \ne 0$)이 들어온다. www.acmicpc.net 문제 풀이 'BOJ 1676번 : 팩토리얼의 0의 개수'와 비슷한 문제이다. 조합이기 때문에 (N! / (N-M)! M!) 의 2의 개수, 5의 개수 중 최솟값이 정답이다. 이전 'BOJ 1676번 : 팩토리얼의 0의 개수'에선 압도적으로 2의 개수가 많을 수밖에 없기에 5의 개수만 따졌지만 조합에서는 다르기 때문에 어느 것이 작은지 따져줘야한다. 브루트 포스로 해결하려면 시간이 절대적으로 모자라기 때문에 아이디어가 필요하다. N을 K^i로 지속적으로 나누.. 2021. 7. 28. [C++] 백준 1629번 : 곱셉 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 문제 풀이 브루트 포스로 문제를 풀게 되면 절대 시간 초과가 발생하는 문제이다. 문제를 풀기 위해선 아이디어가 절대적으로 필요하다. 나머지 연산은 분배법칙이 성립한다. 즉, A × B % C = (A % C × B % C) % C 이 성립한다. 함수 pow는 b가 홀수인지 짝수인지에 따라서 연산이 다르다. b가 홀수인 경우는 a를 한 번 더 곱하고 나머지 연산을 한 번 더 해준다. 왜냐하면 a^10은 a^5 × a^5로 한번 더 연산을 할 필요가 없지만 a^5는.. 2021. 7. 27. [C++] 백준 1780번 : 종이의 개수 https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. www.acmicpc.net 문제 풀이 이전 문제들과 다르게 4 분할이 아닌 9 분할이다. 이전 문제와 비슷하게 코드를 구현할 수 있지만 '-1, 0, 1'을 조금만 바꾸면 문제가 아주 쉬워진다. 각각의 숫자를 +1 해서 '0, 1, 2'로 바꾸면 카운트할 때도 출력할 때도 쉬워진다. 느낀 점 처음에 이전 문제와 비슷하게 코드를 구현했다. 코드가 길고 썩 깔끔한 구석이 없었다. 다른 분들의 코드를 비교하던 중 아주.. 2021. 7. 27. [C++] 백준 1992번 : 쿼드트리 https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 문제 풀이 이전 문제인 "BOJ 2630번 : 색종이 만들기"와 유사한 문제이다. 쿼드트리를 만들고 맞게 1과 0을 출력하면 된다. 다른 점은 입력받는 방법과 출력 시 '( )'을 맞춰서 출력해야 한다는 점이다. 입력은 공백이 없기 때문에 단순하게 cin으로 받을 수 없어서 string형으로 받고 str [i]가 char라서 아스키코드를 변환하는 방식으로 입력받는다. 출력 시 생성되는.. 2021. 7. 27. 이전 1 ··· 5 6 7 8 9 10 11 ··· 18 다음