시나위

https://www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net nCk = n! / {(n-k)! * k!} (mod bignum)이다 곱셉에선 모듈로 연산이 각각 들어가도 되었지만 나눗셈도 가능한지 몰랐다. 그래서 구글링을 했고 페르마의 소정리라는 것을 알게 되었다. 모듈로 연산에 쓰이는 값이 소수인경우 곱셉의 역원으로 b^-1 (mod pn) = b^(pn-2) (mod pn)가 된다. 1,000,000,007 이란 값은 소수이므로(이것도 구글링해봤다.) nCk 또한 페르마 소정..

https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net #include #include using namespace std; typedef long long ll; typedef vector matrix; #define DIVMOD 1000000007; matrix operator *(matrix a, matrix b) { ll i, j, k; matrix ret(2, vector(2)); for (i = 0; i < a.size(); ++i) { for (j = 0; j < a.size(); ++j) { for (k = 0; ..

https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 오랜만에 분할정복 문제이다. dp를 사용하지 않아서 알고리즘 자체는 어렵지 않는데 c++사용할때 조금 문제가 있었다. #include #include using namespace std; void copy(int* dest, const int* origin, int N) { // N: size of dest(same as size of origin) for (int i = 0; i < N; ++i) { for ..

https://programmers.co.kr/learn/courses/30/lessons/68936?language=python3 코딩테스트 연습 - 쿼드압축 후 개수 세기 [[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]] [4,9] [[1,1,1,1,1,1,1,1],[0,1,1,1,1,1,1,1],[0,0,0,0,1,1,1,1],[0,1,0,0,1,1,1,1],[0,0,0,0,0,0,1,1],[0,0,0,0,0,0,0,1],[0,0,0,0,1,0,0,1],[0,0,0,0,1,1,1,1]] [10,15] programmers.co.kr def solution(arr): # 분할 정복 answer = devideAndConquer(0,0,arr,len(arr)) return an..

https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. www.acmicpc.net import sys input = sys.stdin.readline def devide(r, c, size): global m1, z, p1 if check(r, c, size): if paper[r][c] == -1: m1 += 1 elif paper[r][c] == 0: z += 1 else: p1 += 1 return # 분할 for i in range(r, r + size, si..

https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net import sys; input = sys.stdin.readline def divNConq(size, r, c): global answer if size == 1: answer += str(matrix[r][c]) return if chk_arr(size, r, c, matrix[r][c]): answer += str(matrix[r][c]) return half = size // ..

www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net # 분할정복 import sys; input = sys.stdin.readline a, b, c = map(int, input().split()) def divNconq(a, b, c): if b == 1: return a % c tmp_a = divNconq(a, b // 2, c) return a * tmp_a * tmp_a % c if b & 1 else tmp_a * tmp_a % c print(divNconq(a,b,c)) 분할정복문제이다 dp방식으로 해보려했으나 메..

www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서 www.acmicpc.net N, r, c = map(int, input().split()) def z(N, r, c): result = 0 while N > 0: if N == 1: result += r * 2 + c break else: flag = 4 ** (N - 1) half = (2 ** N) >> 1 N -= 1 if r < half and c < half: continue elif r < half: result += ..

www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net import sys; input = sys.stdin.readline N = int(input()) color_paper = [list(map(int, input().split())) for _ in range(N)] def check(color, r, c, size): for i in range(r, r + size, visit[r][c]): for j in range(c, c + ..