소수
소수의 정의
소수 : 1과 자기 자신으로만 나누어지는 수 = 약수가 2개인 수
합성수 : 1과 자기 자신을 제외한 다른 약수를 가지고 있는 수
1은 소수가 아니다
2~N-1 돌면서 나누어진다면? 소수
합성수 N에서 1을 제외한 가장 작은 약수는 루트N 이하이다.
2~루트(N) 돌면 되지만 sqrt()함수를 사용하면 오차가 생겨서 안된다.
i*i < n 으로 조건식을 작성하자.
만약 2~N까지의 범위내에서 소수를 찾는다면 모든 수에 대해서 소수를 판별하면 된다.
다만, 2부터 루트(N) 까지 도는게 아니라, 소수인 범위로 돌면 더욱 최적화 할 수 있다.
3, 5, 7, 11 이렇게 작은수부터 소수를 찾아나가면서 12를 소수판별할 때 3, 5, 7, 11루프만 돌면 되는 형식이다.
"에라토스테네스의 체" 라는 더 효율적인 방법이 있다.
N칸 짜리 배열을 만든다.
소수일 경우 true 아닌경우 false
초기값으로는 1만 true
2의 경우 true이니까 2의 배수를 false로 만든다.
3의 경우 true이니까 3의 배수를 false로 만든다.
4의 경우 false니까 넘어간다.
5의 경우 true이니까 5의 배수를 false로 만든다.
그런데 불필요한 과정이 많다. 이미 false인 곳을 다시 조사하기 때문이다.
이를 최적화 할 수 있다.
5의 경우를 다시보자.
2,3,4는 이미 판별을 했다. 그래서 5 2, 5 3, 5 * 4 는 사실상 건너뛰어도 된다.
그래서 시작을 5 * 5 부터 하면 된다.
vector<int> sieve(int i){
vector<int> prime;
vector<bool> state(n+1, true);
state[1] = false;
for(int i = 2; i * i <= n; i++){
if(!state[i]) continue;
for(int j = i * i; j <= n; j+= i)
state[j] = false;
}
for(int i = 2; i <= n; i++){
if(state[i]) primes.push_back(i);
}
}참고로 C배열을 bool타입의 C 배열을 선언하면 한칸당 1바이트씩 할당되는데 vector는 최적화를 하여 1비트만 차지하도록 한다.
그래서 공간도 8배 차이나고 캐시히트도 좋다.
소인수 분해
1100 = 2 x 2 x 5 x 5 x 11
어떻게 구현해야 할까?
N을 2로 나누고 나누고 나누고 안나눠떨어질때까지 나눈다. 2의 횟수를 따로 저장한다.
3으로 나누고 나누고 ....
4로 나누고...(근데 이미 2로 나눠서 의미없음)
5로 나누고 나누고...
N이 1이 되는 순간 종료
최대공약수
약수 = 어떤 수를 나누어떨어지게 하는 수
18의 약수 = 1 2 3 6 9 18
최대공약수 = 두 자연수의 공통된 약수 중 가장 큰 약수
GCD라고 부름(Greatest Common Diviser)
유클리드 호제법이라고 효율적인 방법이 있음
GCD(A, B) = GCD(B, r)
GCD(20,12) = GCD(12, 8) = GCD(8, 4) = GCD(4, 0) = 4
int gcd(int a, int b){
if(a == 0) return b;
return gcd(b%a, a);
}최소공배수
A x B = GCD(A, B) X LCM(A,B)
int lcm(int a, int b){
return a / gcd(a, b) * b; // 오버플로우 방지로 먼저 나누고 곱함
}연립합동방정식
- 6명씩 조를 짰을 때 3명이 남았다
- 5명씩 조를 짰을 때 2명이 남았다.
- 학생은 30명 미만이다.
이를 풀고자한다면
1~29 for문을 돌면서 6과 5로 나누어 보는 것이다.
그런데 이 방법 대신에
6명씩 조를 짰을 때 3명이 남았을 경우를 구해보면 9, 15, 21, 27이다.
그 후 9, 15, 21, 27 을 대상으로 5로 나눠보면 된다.
이렇게 하면 시간복잡도를 줄일 수 있다.
BOJ_6064: 카잉달력
문제
최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 <x:y>와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 <1:1>로 표현하고, 두 번째 해를 <2:2>로 표현하였다. <x:y>의 다음 해를 표현한 것을 <x':y'>이라고 하자. 만일 x < M 이면 x' = x + 1이고, 그렇지 않으면 x' = 1이다. 같은 방식으로 만일 y < N이면 y' = y + 1이고, 그렇지 않으면 y' = 1이다. <M:N>은 그들 달력의 마지막 해로서, 이 해에 세상의 종말이 도래한다는 예언이 전해 온다.
예를 들어, M = 10 이고 N = 12라고 하자. 첫 번째 해는 <1:1>로 표현되고, 11번째 해는 <1:11>로 표현된다. <3:1>은 13번째 해를 나타내고, <10:12>는 마지막인 60번째 해를 나타낸다.
네 개의 정수 M, N, x와 y가 주어질 때, <M:N>이 카잉 달력의 마지막 해라고 하면 <x:y>는 몇 번째 해를 나타내는지 구하는 프로그램을 작성하라.
입력
입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. 각 줄에는 네 개의 정수 M, N, x와 y가 주어진다. (1 ≤ M, N ≤ 40,000, 1 ≤ x ≤ M, 1 ≤ y ≤ N) 여기서 <M:N>은 카잉 달력의 마지막 해를 나타낸다.
출력
출력은 표준 출력을 사용한다. 각 테스트 데이터에 대해, 정수 k를 한 줄에 출력한다. 여기서 k는 <x:y>가 k번째 해를 나타내는 것을 의미한다. 만일 <x:y>에 의해 표현되는 해가 없다면, 즉, <x:y>가 유효하지 않은 표현이면, -1을 출력한다.
예제 입력 1
3
10 12 3 9
10 12 7 2
13 11 5 6
예제 출력 1
33
-1
83
풀이
(M, N)은 결국 M과 N의 최소공배수이다.
M = 10, N = 12, x = 3, y = 9 이면
결과값을 result라 할때
result % 10 = 3
result % 12 = 9 이다.
(1, 1) 은 첫 해라 했으니 (0, 0) 은 사실상 (M, N) 이고
(M, N) 은 result 를 M으로 나눈 나머지가 0, N으로 나눈 나머지가 0 이므로 (M, N)은 M과 N의 최소공배수인 해이다.
또한 입출력을 보면 알 수 있다시피, (M, N)에 포함되지 않는 (x, y)가 있을 수 도 있다.
이항계수
nCr = n! / (n-r)!r!
nPr = n! / (n-r)!
BOJ_11050: 이항계수 1
이항 계수 1 성공
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 256 MB 88498 57373 49673 64.583%
문제
자연수
(N)과 정수
(K)가 주어졌을 때 이항 계수
(\binom{N}{K})를 구하는 프로그램을 작성하시오.
입력
첫째 줄에
(N)과
(K)가 주어진다. (1 ≤
(N) ≤ 10, 0 ≤
(K) ≤
(N))
출력
(\binom{N}{K})를 출력한다.
예제 입력 1
5 2
예제 출력 1
10
풀이
int main(void){
int n,k;
cin >> n >> k;
int ret = 1;
for(int i = 1; i <= n; i++) ret *= i;
for(int i = 1; i <= k; i++) ret /= k;
for(int i = 1; i <= (n-k); i++) ret /= i;
cout << ret;
}n과 k가 커지면 어떻게 될까?
BOJ_11051번: 이항계수 2
이항 계수 2
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 256 MB 69187 26704 21039 38.776%
문제
자연수
(N)과 정수
(K)가 주어졌을 때 이항 계수
(\binom{N}{K})를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오.
입력
첫째 줄에
(N)과
(K)가 주어진다. (1 ≤
(N) ≤ 1,000, 0 ≤
(K) ≤
(N))
출력
(\binom{N}{K})를 10,007로 나눈 나머지를 출력한다.
예제 입력 1
5 2
예제 출력 1
10
풀이
팁
nCr = (n-1)Ck + (n-1)C(k-1)
특정 하나라를 선택했을 때 그게 포함될 경우의수 + 포함안될 경우의 수 = 전체 경우의 수
DP로 풀면 된다.
