1. 문제 11653번: 소인수분해 (acmicpc.net) 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 2. 소인수분해 하는 방법? 어렵게 생각할 필요 없이 사람이 소인수 분해를 어떻게 하는지 생각해보자. 100을 소인수분해 한다고 해보자. 암산으로 5*20 >>> 5*4*5 >> 5^2 * 2^2이 나오기는 하는데... 이게 어떻게 이루어지는가??? 처음부터 생각해보자. 소인수분해는 소수들의 곱이다. 그러니까 소수의 최솟값인 2부터 시작해서 주어진 수 100을 나눠보면 된다. 만약에 100이 2로 나누어진다면? 100 = 2 * 50이다. 그러면.. 우리는 어떤 걸 이제 나누어보는가? 100을 2로 나누고 나온 몫인 50을..
1. 문제 https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 00과 1을 이용해서 만들 수 있는 길이 n의 이진수열의 개수를 15746으로 나눈 나머지를 구하는 문제 2. 풀이 가능한 경우의 수를 나열해서 규칙을 찾으면 간단해진다 1,2,3,5,8,...로 이어져서 피보나치 수열이라는 느낌이 온다 그래서 한번 해보면 from sys import stdin n = int(stdin.readline()) dp = [0] * 1000001 dp[1] = 1..
1. 소수를 구하는 방법 컴퓨터가 주어진 수 n이 소수인지 판단할려면 어떻게 해야할까? 1부터 n까지 n에 나눠보면서 n의 약수인지 아닌지 판단해보면 된다. n의 약수가 1과 n만 있어야 n이 소수이다. #숫자 n이 소수이면 True, 아니면 False #단 1은 소수가 아니다 def is_prime(n): if n == 1: return False else: for i in range(2,n): #1과 n으로는 당연히 나누어 떨어지니까, 2~n-1까지 검사 if n % i == 0: return False return True 2. 에라토스테네스의 체 2-1) 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 2-2) 2를 제외한 2의 배수를 모두 지운다 2-3) 3을 제외한 3의 배수를 모두 ..
1. 페르마의 소정리 p가 소수이면 모든 정수 a에 대하여 $a^p$와 a를 p로 나눈 나머지는 서로 같다. 만약 a가 p의 배수가 아닌 서로소라면 $a^{(p-1)}$와 1을 p로 나눈 나머지는 서로 같다 역은 성립하지 않는다. 즉 모든 정수 a에 대하여 $a^p \equiv a (mod p)$임에도 불구하고 p가 합성수일 수 있다 2. 응용 - 이항계수를 빠르게 구하는 방법 n과 r이 10만에서 100만정도 되는 매우 큰 수에 대하여 어떻게 하면 빠르게 구할 수 있을까 파스칼의 삼각형을 이용한 다이나믹 프로그래밍으로는 이제는 불가능하다 그래서 $nCr = n! / ((n-r)! * r!)$을 직접 구할 필요가 있는데 이 경우 n과 r이 매우 크면 직접 나타내기 어려우므로 어떤 소수 p에 대해 나머지를..
1. 파스칼의 삼각형 이항계수에 대한 성질 $$nCr = n-1Cr-1 + n-1Cr$$을 이용하여 이항계수 값들을 미리 테이블에 저장해놓는다 시간복잡도는 $O(n^2)$ n과 r이 10000이상이면 사용하기 힘들지만 충분히 작다면 사용하지 않을 이유가 없을 정도로 충분히 빠르다 2. 알고리즘 2-1) 행의 수 t를 입력받는다 2-2) 1부터 t+1까지 모든 행에 대해 0으로 초기화한 2차원 배열 생성 ------------------- 만약 행의 수가 아니고 최대 1000Cr까지 구하고 싶다면??? 1001개의 행을 받아야한다는 점을 기억해야한다 ------------------- 2-3) 각 행의 맨 처음과 맨 끝은 1로 만들고 2-4) 나머지는 $nCr = n-1Cr-1 + n-1Cr$을 이용하여 ..
1. 최대공약수 두 자연수 a,b가 공통으로 가지는 약수중에서 가장 큰 약수를 최대공약수라고 부른다. 중요한 성질중 하나는 최대공약수의 약수는 a,b의 공약수이다. 2. 유클리드 호제법 두 양의 정수 a,b (a>b)에 대하여 a = bq + r ( r은 0이상 b 미만)이라고 하면, a,b의 최대공약수는 b,r의 최대공약수와 같다. 즉, gcd(a,b) = gcd(b,r)이다. 만약 r=0이라하면, a,b의 최대공약수는 b이다. 3. 유클리드 호제법 활용 단 1번만 사용해서는 그 진짜 힘을 알 수 없다. a = bq + r이면 a,b의 최대공약수는 b,r의 최대공약수와 같다 b를 r로 나눠서 b = rq2 + r2라는 식을 얻는다면, 결국 b,r의 최대공약수는 r,r2의 최대공약수와 같다. 여기서 r을..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
