25309번: K개의 소수 (acmicpc.net) 정수 n을 k개의 소수 합으로 표현하라는 문제 여기서 핵심은 서로 다른 k개의 소수가 아니라, 같은 소수를 사용해도 좋다. 그리고 문제는 n이 최대 $10^{8}$이고 k는 최대 10000이라 단순한 방법으로는 어렵다 먼저 생각할 수 있는 것은 가장 작은 소수가 2이기 때문에, 2를 k개 사용하여 2k가 만들 수 있는 정수의 최솟값이다. 따라서 n = 2k이면 일단 분해하는 것이 가능하다. n,k = map(int,input().split())if n 만약 k = 1이면 n 자체로 소수인지 아닌지 판단하면 된다. $O(\sqrt{n})$에 소수 판단할 수 있다. def is_prime(n): for i in range(2,int(n**..
1. 왜 문자열의 hashing이 필요한가? https://deepdata.tistory.com/960 문자열 해싱(hashing) 기본 개념 배우기String Hashing - Algorithms for Competitive Programming (cp-algorithms.com) String Hashing - Algorithms for Competitive Programming String Hashing Hashing algorithms are helpful in solving a lot of problems. We want to solve the problem of comparing stringdeepdata.tistory.com 두 문자열 S1, S2가 서로 같은지 다른지 비교하고 싶을 때가 있..
SW Expert Academy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 나이트가 (i,j)에 있을때, (i+1,j+2), (i+2,j+1) 둘 중 하나로만 움직일 수 있다고 하자. x,y가 주어질 때, (0,0)에서 출발하여 (x,y)로 이동할 수 있는 경우의 수는? dp[y][x] += dp[y-1][x-2], dp[y][x] += dp[y-2][x-1]로 구할 수 있을 것 같은데 X,Y가 $10^{6}$까지라서 메모리도 안되고 $O(N^{2})$이라 시간복잡도도 안된다 나이트가 (i,j)에서 이동하는 방법이 (i+1,j+2), (i+2,j+1) 2가지만 있다는 것을 생각한다면... (0,0)에서 (..
이미 알고있는 것들인데 블로그에 정리가 안되어 있어서 1. n!을 소수 p로 나눈 나머지 소수 p에 대하여 $n! mod p$를 구하는 문제가 있다. 단 하나의 $n! mod p$를 구해야한다면... $n! = n*(n-1)*(n-2)*...*1$이므로, 1부터 n까지 $O(N)$에 다 곱한 다음, p로 나눈 나머지를 구하는 것이 간단하다. 하지만 n이 매우 크면서, 여러가지 n에 대한 $n! mod p$가 필요하다면 이야기가 달라진다. 여러가지 n에 대한 $n! mod p$가 필요하다면 가능한 모든 n에 대해 $n! mod p$를 구해놓고 O(1)로 접근하면 된다. 여기서 다이나믹 프로그래밍에 의해 이전에 구해놓은 값을 저장해둔다면, O(N)에 모든 n에 대해 $n! mod p$를 구할 수 있다. $n..
컴퓨터는 왜 2진수를 사용하는가? 실리콘이라는 재료로 만든 반도체로 구성됨 이 반도체는 특정 자극을 줄 때 전기가 통해서 전류가 흐르면 1, 전류가 흐르지 않으면 0으로 표현할 수 있기 때문 단순 소수도 이진수로 변환하면 무한소수가 되는 경우가 있다. 이것을 반올림하면 약간의 오차가 발생하는데 요새는 일반적으로는 큰 문제는 없다 아마 이것도 실수오차가 발생하는 이유가 되겠지 10진수 0.1을 2진수로 바꾸면 0.0001…..(2)가 된다
https://en.wikipedia.org/wiki/Prime_gap Prime gap - Wikipedia Number 1 to 27 # gn pn n 1 1 2 1 2 2 3 2 3 4 7 4 4 6 23 9 5 8 89 24 6 14 113 30 7 18 523 99 8 20 887 154 9 22 1,129 189 10 34 1,327 217 11 36 9,551 1,183 12 44 15,683 1,831 13 52 19,609 2,225 14 72 31,397 3,385 15 86 155,921 14,357 16 96 360,653 30,802 17 en.wikipedia.org 1. 문제 23005번: Consecutive Primes (acmicpc.net) 23005번: Consecut..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
