살구의 개발자 첫걸음을 위한

1. 골드바흐의 추측1) 2보다 큰 모든 짝수는 두 소수의 합으로 표현 가능하다.2) 위의 문장에 3을 더하면3) 5보다 큰 모든 홀수는 세 소수의 합으로 표현 가능하다.4) 아직 증명되지 않은 문제 => 추측5) 10^18 이하에서는 참인 것이 증명됨 -6588번(골드바흐의 추측)=>10^6 이하의 짝수에 대해서 골드 바흐의 추측을 검증하는 문제#include using namespace std; int pn;int p[1000000];bool c[1000001];int main(void) {int n; // 2부터 100만 사이의 소수 구하기for (int i = 2; i n;if (n == 0)break;for (int i = 1; i < pn; i++) {if (c[n - p[i]] == fals..

1. 어떤 수 N이 소수인지 아닌지 알아내는데 걸리는 시각 복잡도가 O(루트N) 이라고 하면,1부터 N까지 범위에서 모든 소수를 구하는데 걸리는 시간 복잡도는 O(N루트N) 만큼의 시간이 걸린다.N이 백만인 경우, 1,000,000 * 1,000 = 10^9 = 10억 = 10초 가 걸린다.너무 긴 시간이 필요하므로 이 경우에는 에라토스테네스의 체를 사용한다. 2. 에라토스테네스의 체-1부터 N까지 범위 안에 들어가는 모든 소수를 구할 때 사용1)2부터 N까지 모든 수를 써놓는다.2)아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다.3)그 수는 소수이다.4)이제 그 수의 배수를 모두 지운다. (코드)N이 100 이라고 하면, int p[100]; // 소수 저장int pn=0; // 소수의 개수boo..

1. 소수(Prime Number)-약수가 1과 자기 자신 밖에 없는 수-1부터 100까지 소수2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 1) N이 소수가 되려면, 2보다 크거나 같고, N-1 보다 작거나 같은 자연수로 나누어 떨어지면 안된다.(코드)bool prime(int n){if(n

1. 10진수 -> B진수-10진수 N을 B진수로 바꾸려면 N이 0이 될때 까지 나머지를 계속해서 구함ex) 11을 3진법으로11/3=3 ... 23/3=1 ... 01/3=0 ... 1=>102-11005번 2. B진수 -> 10진수-B진수를 10진수로 바꾸려면 B^K를 곱하면서 더해감ex) 3진수 1021*3^2 + 0*3^1 + 2*3^0 = 11-2745번 3. 2진수를 8진수로, 8진수를 2진수로-1373번-1212번 4. -2진수-2089번 5. A진수 -> B진수-A진수->10진수->B진수 -11576번 8. 문제-11005번 (10진수->B진수)-2745번 (B진수->10진수)-11576번 (A진수->B진수)-1373번, 1212번 (2진수->8진수, 8진수->2진수)-2089번 (-2진수)

1. 최소공배수(Least Common Multiple)-최소공배수는 줄여서 LCM이라고 한다.-두 수의 최소공배수는 두 수의 공통된 배수 중에서 가장 작은 정수-최소공배수는 GCD를 응용해서 구할 수 있다.-두 수 a, b 의 최대공약수를 g라고 했을 때,-최소공배수 l=a*b/g 2. 문제-2609-1934-9613

1. 최대공약수(Greatest Common Divisor)-최대공약수는 줄여서 GCD라고 쓴다.-두 수 A와 B의 최대공약수 G는 A와 B의 공통된 약수 중에서 가장 큰 정수이다.-최대공약수를 구하는 가장 쉬운 방법은 2부터 min(A,B)까지 모든 정수로 나우어 보는 방법-최대공약수가 1인 두 수를 서로소(Coprime)이라고 한다. (코드)int g=1;for(int i=2;i 시간복잡도 O(N) -위의 방법보다 빠른 방법이 있다. => 유클리드 호제법(Euclidean Algorithm) 2. 유클리드 호제법-a를 b로 나눈 나머지를 r이라고 했을 때, gcd(a,b)=gcd(b,r) -r이 0이면 그 때 b가 최대 공약수이다. ex) gcd(24,16)gcd(24,16)=gcd(16,8)=gcd..

1. 나머지 연산 (Modular Arithmetic)-컴퓨터의 정수는 저장할 수 있는 범위가 지정되어 있기 때문에, 답을 M으로 나눈 나머지로 출력하라는 문제가 등장한다. 1) (A+B) mod M = ((A mod M) + (B mod M)) mod M2) (A*B) mod M = ((A mod M) * (B mod M)) mod M3) 나누기의 경우에는 성립하지 않는다. (Modular Inverse를 구해야 함)4) 뺄셈의 경우에는 먼저 mod 연산을 한 결과가 음수가 나올 수 있기 때문에 다음과 같이 해야 한다. (A-B) mod M = ((A mod M) - (B mod M) + M) mod M 2. 문제-10430

1. 문제상근이와 선영이가 다른 사람들이 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화 하기로 했다. 그래서 다음과 같은 대화를 했다.-상근: 그냥 간단히 암호화 하자. A를 1이라고 하고, B는 2로, 그리고 Z는 26으로 하는 거야.-선영: 그럼 안돼. 만약, "BEAN"을 암호화하면 25114가 나오는데, 이걸 다시 글자로 바꾸는 방법은 여러 가지가 있어. -상근: 그렇네. 25114를 다시 영어로 바꾸면, "BEAAD", "YAAD", "YAN", "YKD", "BEKD", "BEAN" 총 6가지가 나오는데, BEAN이 맞는 단어라는 건 쉽게 알 수 있잖아?-선영: 예가 적절하지 않았네ㅠㅠ 만약 내가 500자리 글자를 암호화 했다고 해봐. 그 때는 나올 수 있는 해석이 정말 많은데..

1. 문제 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2 와 2+1 은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다. 2. 입력두 정수 N(1 k;// d[n][1] = 1for (int i = 0; i

#include 2using namespace std;3​4long long d[101];5int main(void) {6 int t;7 cin >> t;8 d[1] = 1;9 d[2] = 1;10 d[3] = 1;11 d[4] = 2;12 while (t--) {13 int n;14 cin >> n;15 for (int i = 5; i