zhelddustmq 님의 블로그

1. 에라토스테네스의 체: 2부터 배수들을 지워나가며 지워지지 않은 제일 처음 수가 소수가 되고, 또 그 소수의 배수를 지워나가며 소수를 찾는 방법 2. 1부터 N까지 소수가 몇개인지 판별하는 방법 2-1 약수가 있는지 확인해서 끝까지 조사해서 없으면 소수( 시간 복잡도: O(N^2) ) 2-2 √N까지만 조사해서 없으면 소수( 시간 복잡도: O(NlogN) )  2-3 에라토스테네스의 체 이용( 시간 복잡도: O(Nlog(logN)) ) 3. 에라토스테네스를 활용해, 소수 구분하는 동작 순서 1) 2부터 N까지 모든 정수를 적음2) 아직 지우지 않은 소수 중 가장 작은 소수를 찾음(이 수를 P라고 함)3) 아직 지우지 않은 수들 중, P의 배수를 크기 순서대로 지움4) 아직 모든 수를 지우지 않았다면 ..

0. 파이썬은 python 3.5부터 gcd를 python 3.9부터 lcm을 math라이브러리에서 제공 1. 약수: 나누어 떨어지는 수 1-1 N의 약수 구하는 법:1부터 N이하의 정수로 N을 나누어, 나머지가 0이 되는 수를 찾음( 시간 복잡도: O(N) )1부터 √n이하의 정수로 N을 나누어, 나머지가 0이 되는 수를 찾고, 그 개수에 2를 곱함. N이 제곱수면, √N이 중복되므로 하나 뺌( 시간 복잡도: O(√N) )2. 유클리드 호제법:  A = Bq + R이라 할 때, A, B의 최대공약수 G(A, B)와 B, R의 최대공약수 G(B, R)이 같다. 두 수 A, B가 있고, 그 두 수의 최대공약수가 G라고 하자. (A > B)(단 a, b 는 서로소)A는 아래처럼 나타낼 수도 있다.(q는 몫,..

문제 설명2차원 행렬 arr1과 arr2를 입력받아, arr1에 arr2를 곱한 결과를 반환하는 함수, solution을 완성해주세요.제한 조건행렬 arr1, arr2의 행과 열의 길이는 2 이상 100 이하입니다.행렬 arr1, arr2의 원소는 -10 이상 20 이하인 자연수입니다.곱할 수 있는 배열만 주어집니다.입출력 예arr1arr2return[[1, 4], [3, 2], [4, 1]][[3, 3], [3, 3]][[15, 15], [15, 15], [15, 15]][[2, 3, 2], [4, 2, 4], [3, 1, 4]][[5, 4, 3], [2, 4, 1], [3, 1, 1]][[22, 22, 11], [36, 28, 18], [29, 20, 14]]  정답 코드(이해용):def soluti..

목표량시간 제한: 1초엘리스 토끼는 목표량을 정해 수학 문제를 열심히 풉니다. 목표량은 정수입니다.내일 풀 수학 문제의 개수는 오늘 푼 문제 개수의 수와 숫자의 구성이 같으면서, 오늘 푼 문제 개수의 수보다 큰 수 중 가장 작은 수입니다.예를 들어, 오늘 67문제를 풀었으면 다음 날 76문제를 풉니다.오늘 푼 문제의 개수를 줬을 때 다음날 풀 문제의 개수를 출력하는 프로그램을 작성하세요. 지시사항입력첫 번째 줄에 오늘 푼 문제의 개수인 자연수 N을 입력합니다. 1≤N≤999999 정답이 반드시 있는 경우만 입력값으로 주어집니다.출력다음날 풀 문제의 개수를 출력합니다.입력 예시364Copy출력 예시436  정답 코드:#퀵 소트 정렬 씀def quicksort(arr, start, end): if st..