기록

문제 https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 1) 분할 정복을 이용한 거듭제곱 number을 n번 곱한다고 하면, 아래처럼 적을 수 있다. 이를 행렬에도 적용하면, 문제를 해결할 수 있다. def power(number, n) : if n==0 : return 1 elif n이 짝수 : return power(number², n//2) elif n이 홀수 : return number*power(number², n//2) 문제에서는 n의 최대값을..

문제1016번: 제곱 ㄴㄴ 수첫째 줄에 min과 max가 주어진다. min은 1보다 크거나 같고, 1,000,000,000,000보다 작거나 같은 자연수이고, max는 min보다 크거나 같고, min+1,000,000보다 작거나 같은 자연수이다.www.acmicpc.net풀이에라토스테네스의 체를 이용한 문제로, 위 코드에서는 1) 소수 구하기와 2) a, b사이의 값이 제곱수로 나누어지는지 확인하는 두 가지 기능이 한 번에 작성되어 있다. ans에 탐색해야하는 자연수의 개수를 담고, '제곱수의 배수'를 만날 때마다 1씩 값을 줄여나간다.코드def solution(a, b) : ans = b-a+1 prime = [i for i in range(floor(b**0.5)+1)] # 소수를 저장할 공간 num..