[코딩테스트] 수학
reference : 2021 코딩테스트 기초(최백준) 강의를 공부하며 정리한 내용입니다.
나머지 연산
- 더하기와 곱하기의 경우 각각 나눠도 나머지는 같다.
- (A + B) % M = (A % M + B % M) % M
- (A X B) % M = (A % M X B % M) % M
- 뺄셈의 경우 먼저 mod(나머지) 연산을 한 결과가 음수가 나올 수 있기 때문에 다음과 같이 해야 한다.
- (A - B) % M = ((A % M) - (B % M) + M) % M
- 나누기의 경우엔 성립하지 않는다
- ‘정답을 ~로 나눈 나머지를 출력하라’ : int나 long 같은 자료형 범위를 넘어가기 때문
- 나머지 연산은 수가 너무 큰 경우, 그 수를 만들지 않아도 나머지에 의미가 있으면 그 나머지를 이용할 수 있다는 게 장점
1 (백준 4375번)
https://www.acmicpc.net/problem/4375
문제
2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오.
출력
1로 이루어진 n의 배수 중 가장 작은 수의 자리수를 출력한다.
풀이
1 % 7 = 1
11 % 7 = 4
111 % 7 = 6
1111 % 7 = 5
11111 % 7 = 2
111111 % 7 = 0
- 11 = (1 X 10 + 1) % 7 = ((1 % 7) X 10 + 1) % 7 = 11 % 7 = 4
- 111 = (11 X 10 + 1) % 7 = ((11 % 7) X 10 + 1) % 7 = 41 % 7 = 6
- 11111 = (1111 X 10 + 1) % 7 = ((1111 % 7) X 10 + 1) % 7 = 51 % 7 = 2
- 10과 1을 7로 나누지 않는 이유는 필요 없어서. 나머지연산 사용하는 이유는 크기가 너무 커졌을 때 저장 방법이 없어서 하는거니까…
- N으로 나눈 나머지는 [0,N] 범위 안에 있기 때문에, 최대 N번 반복하면 문제 정답 찾을 수 있다.
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNextInt()){
int n = sc.nextInt();
int num = 0;
for(int i=1;;i++){
num = num*10+1;
num %= n;
if(num==0){
System.out.println(i);
break;
}
}
}
}
}
약수
- A의 약수? A = BC를 만족하는 자연수 C
for(int i=1; i<=n; i++){
if(n%1 == 0){
//i는 n의 약수
}
}
- 1부터 N까지 모든 자연수로 나눌때 시간 복잡도 : O(N)
- C가 A의 약수라면, 몫(A/C)도 A의 약수(1과 4, 2와 2)
- 이렇듯 중간 어떤 기준으로 곱하기 형태가 됨. C = A/C 경우 A = C²임. 즉 √A가 중간 기준. 같은 값이 있는거니 그 가운데 수를 빼고 항상 같아지게 됨.
- C가 A의 약수라면 그 몫도 A의 약수여야 하니 1부터 √N까지 나눈다면 시간복잡도 = O(√N)
약수(1037번)
https://www.acmicpc.net/problem/1037
문제
양수 A가 N의 진짜 약수가 되려면, N이 A의 배수이고, A가 1과 N이 아니어야 한다. 어떤 수 N의 진짜 약수가 모두 주어질 때, N을 구하는 프로그램을 작성하시오.
출력
첫째 줄에 N을 출력한다. N은 항상 32비트 부호있는 정수로 표현할 수 있다.
풀이
- 약수 최소값 X 최대값
- N의 진짜 약수 : M개
- 최소 : O(M), 최대 : O(M)
- M + M = 2M 즉 시간 복잡도는 O(M)
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int a = sc.nextInt();
int[] b = new int[a];
for(int i=0; i<a; i++) {
b[i] = sc.nextInt();
}
sc.close();
int small = b[0];
int big = b[a-1];
for(int i=0; i<a; i++) {
if(small>b[i]) {
small = b[i];
}
if(big<b[i]) {
big = b[i];
}
}
System.out.println(small*big);
}
}
- 나는 위처럼 풀었는데 236ms라ㅋㅋㅋㅋㅋㅠㅠ.. https://st-lab.tistory.com/150 이곳 풀이 참고!
약수의 합 2(17427번)
https://www.acmicpc.net/problem/17427
문제
- f(A) = A의 약수의 합, g(N) = f(1) + f(2) + … + f(N)
- N이 주어졌을 때 g(N)을 구하는 문제
- 1 ≤ N ≤ 1,000,000
출력
첫째 줄에 N을 출력한다. N은 항상 32비트 부호있는 정수로 표현할 수 있다.
풀이
- 약수 최소값 X 최대값
- N의 진짜 약수 : M개
- 최소 : O(M), 최대 : O(M)
- M + M = 2M 즉 시간 복잡도는 O(M)
- f(A) : O(A) 또는 O(√A)
- g(N) : N x O(N) = O(N²) 또는 N x O(√N) = O(N√N)
- 시간제한 0.5초인데 N² 1조라고 가정하면 10,000초(2-3시간). 루트 방법은 100만 x √100만 = 100만 x 1000 = 10억 = 10초. 둘 다 불가능함.
- 약수의 반대는 배수다.
N 이하의 자연수 중에서 1을 약수로 갖는 수의 개수는 [N/1]개 -> 약수의 합 1x[N/1]
N 이하의 자연수 중에서 2를 약수로 갖는 수의 개수는 [N/2]개 -> 약수의 합 2x[N/2]
N 이하의 자연수 중에서 3을 약수로 갖는 수의 개수는 [N/3]개 -> 약수의 합 3x[N/3]
…
N 이하의 자연수 중에서 i를 약수로 갖는 수의 개수는 [N/i]개 -> 약수의 합 Nx[N/i] - g(N) = [N/1] x 1 + [N/2] x 2 + [N/3] x 3 + … + [N/[N-1]] x (N-1) + [N/N] x N
- 배수를 이용하면 하나 계산에 시간 복잡도 O(1)이 N개니까 O(N)
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long ans = 0;
for(int i=1; i<=n; i++) {
ans += (n/i)*i;
}
System.out.println(ans);
}
}
약수의 합(17425번)
https://www.acmicpc.net/problem/17425
문제
- f(A) = A의 약수의 합, g(N) = f(1) + f(2) + … + f(N)
- N이 주어졌을 때 g(N)을 구하는 문제
- 1 ≤ 테스트 케이스의 개수 ≤ 100,000
- 1 ≤ N ≤ 1,000,000
출력
첫째 줄에 N을 출력한다. N은 항상 32비트 부호있는 정수로 표현할 수 있다.
풀이
- 앞 문제처럼 풀었을 때 g(N) = O(N) 이므로 테스트케이스가 T라면 O(TN), 하지만 10만(테스트케이스 갯수)x100만 = 1000억, 시간제한이 1000초가 아니라 1초이기 때문에 이렇게 풀면 안 됨.
- N이 100이여도 1000이여도 24의 약수를 구해야함. 즉 변하지 않는 값은 한 번만 구하고 재활용하자. 테스트 케이스 미리 구해두고 그 값을 이용하기
- N = AB로 나타낼 수 있을 때 A와 B는 N의 약수, N은 A와 B의 배수
- g(N) = N의 약수의 합, D[i] = g(i), 모든 D[i]를 구하기 위해선 i의 약수를 모두 구해야 함
- 이렇게 하면 시간복잡도 O(N²)
vector<long long> d(n+1, 1);
for(int i=2; i<=n; i++){ //D[i] 구하는 것
for(int j=1; j<=i; j++){ //j가 i의 약수인지?
if(i%j == 0){ // 약수면 약수의 합을 더하기
d[i] += j;
}
}
}
- 배수 아이디어를 이용하게 바꾼다면.. 어떤 수의 배수를 다 구해서 그 수에 약수를 더해주면 된다
vector<long long> d(n+1, 1);
for(int i=2; i<=n; i++){ //i를 약수로 갖는 모든 수
for(int j=1; i*j<=n; j++){ // i*j를 다 만들고 i*j에 i를 더해주기
d[i*j] += i;
}
}
- 반복문의 횟수는 n/2 + n/3 + … + n/n
- 1 + 1/2 + 1/3 + … + 1/n ≤ ln(n) + 1 이기 때문에 위에 식에 n을 곱한 nlgn이 시간 복잡도, O(NlgN)
- 전체 풀이는 D를 먼저 구한 뒤(테스트케이스 상관없이 미리 구해놓기) 입/출력 하는 부분으로 나눠져 있다.
public class Main {
static final int MAX = 1000000;
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
long[] d = new long[MAX + 1];
for (int i = 1; i <= MAX; i++) {
d[i] = 1;
}
for (int i = 2; i <= MAX; i++) {
for (int j = 1; i * j <= MAX; j++) {
d[i * j] += i;
}
}
long[] s = new long[MAX + 1];
for (int i = 1; i <= MAX; i++) {
s[i] = s[i-1] + d[i];
// s[i]=D[1]+...D[i] 즉 1~i까지의 합이니까 (1부터 i-1까지 합)+i, d[i]=f(i), s[i]=g(i)
}
int t = Integer.parseInt(bf.readLine());
while(t-- >0) {
int n = Integer.parseInt(bf.readLine());
bw.write(s[n]+"\n");
}
bw.flush();
}
}
// 시간복잡도 O(NlgN+T)
최대공약수
- 줄여서 GCD(Greatest Common Divisor), 두 수 A와 B의 최대공약수 G는 A와 B의 공통된 약수 중에서 가장 큰 정수.
- 최대공약수를 구하는 가장 쉬운 방법 : 2부터 min(A,B)까지 모든 정수로 나누기
- 최대공약수가 1인 두 수를 서로소(Coprime)라고 한다.
int g = 1;
for(int i=2; i<min(a,b); i++){
if(a%i==0 && b%i==0){
g=i;
}
}
- 최대공약수 구하는 더 빠른 방법은 유클리드 호제법(Euclidean algorithm)
- a를 b로 나눈 나머지를 r이라고 했을 때 GCD(a,b)=GCD(b,r)
r이 0이면 그 때 b가 최대 공약수.
GCD(24,16) = GCD(16,8) = GCD(8,0) = 8 - 재귀함수를 사용해 구현한 유클리드 호제법
int gcd(int a, int b){
if(b==0){
return a;
} else{
return gcd(b, a%b);
}
}
- 재귀함수를 사용하지 않고 구현한 유클리드 호제법
int gcd(int a, int b){
while(b!=0){
int r = a%b;
a = b;
b = r;
}
return a;
}
- 세 수의 최대공약수 : GCD(a,b,c) = GCD(GCD(a,b),c)
- 네 수, N개의 숫자도 위와 같은 식으로 계속해서 구할 수 있다.
최소공배수
- 줄여서 LCM(Least Common Multiple), 두 수의 최소공배수는 두 수의 공통된 배수 중에서 가장 작은 정수
- GCD를 응용해서 구할 수 있다.
두 수 a,b의 최대공약수를 g라고 했을 때 최대공배수 l = g x (a/g) x (b/g)
최대공약수와 최소공배수(2609번)
https://www.acmicpc.net/problem/2609
문제
두 수의 최대공약수와 최소공배수를 구하는 문제
출력
첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.
풀이
public class Main {
public static int gcd(int x, int y) {
if (y == 0) {
return x;
} else {
return gcd(y, x % y);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int a = sc.nextInt();
int b = sc.nextInt();
int g = gcd(a, b);
int l = a * b / g;
System.out.println(g);
System.out.println(l);
}
}
소수(prime)
- 소수 : 약수가 1과 자기 자신 밖에 없는 수
- N이 소수가 되려면, 2보다 크거나 같고 N-1보다 작거나 같은 자연수로 나누어 떨어지면 안 된다.
- 소수를 구하는 방법
- 어떤 수 N이 소수인지 아닌지? O(N)
- N이하의 모든 소수 구하기 -> 약수의 특징 이용함. 1,N이 아닌 수 중 가장 작은 약수는 2, 가장 큰 약수는 그 대칭인 N/2 이다. 즉 N/2+1 부터 N-1까지 약수는 절대 있을 수 없다. 2 부터 N/2까지 나누어지는지 확인하기, 그래서 복잡도는 O(N/2)=O(N)
- 더 빠른 방법은 2부터 √N까지 검사하는 것. O(√N). 검사했을 때 약수가 없다면 √N 이후에도 약수가 없다는 거니까.
bool prime(int n){ if(n < 2){ return false; } for(int i=2; i*i<=n; i++){ //실수는 근사값을 저장하기 때문에 루트 N 같은 경우 i*i<=n(정수의 표현) 처럼 나타내는게 좋다 if(n % i==0){ return false; } } return true; }
소수 찾기(1978번)
https://www.acmicpc.net/problem/1978
문제
입력으로 주어지는 N개의 소수 중에서 소수가 몇 개인지 구하는 문제
출력
주어진 수들 중 소수의 개수를 출력한다.
풀이
public class Main {
public static boolean is_prime(int x) {
if(x<=1) {
return false;
} else if (x==2) {
return true;
}
for (int i=2; i*i<=x; i++) {
if(x%i==0) {
return false;
}
}
return true;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int ans = 0;
while(n-->0) {
if(is_prime(sc.nextInt())) {
ans+=1;
}
}
System.out.println(ans);
}
}
- 위 풀이로 N이 소수인지 알아보는 시간복잡도는 O(√N)이니까 N이하의 모든 소수를 찾는다면 O(N√N) 이것보다 더 빠른 방법은 에라토스테네스의 체
- 에라토스테네스의 체
- 1부터 N까지 범위 안에 들어가는 모든 소수를 구하기 위한 방법
- 2부터 N까지 모든 수를 써놓는다.
- 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다.
- 그 수는 소수이다.
- 이제 그 수의 배수를 모두 지운다.
- 사실 해당 수의 제곱 이후부터 확인하면 됨
int prime[100]; //소수 저장
int pn=0; //소수의 개수
bool check[101]; //지워졌으면 true
int n = 100; // 100까지 소수
for(int i=2; i<=n; i++){
if(check[i]==false){
prime[pn++] = i;
for(int j=i*i; j<=n; j+=i){
check[j] = true;
}
}
}
소수 구하기(1929번)
https://www.acmicpc.net/problem/1929
문제
N이상 M이하의 소수를 모두 출력하는 프로그램을 작성하시오.
풀이
- 수를 지웠는지 안 지웠는지(true/false)
- 소수의 목록을 유지할 배열 필요
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
boolean[] check = new boolean[m + 1];
check[0] = check[1] = true; // 0과 1은 미리 true(제외)한다.
for (int i = 2; i * i <= m; i++) {
if (check[i] == true) {
continue;
}
for (int j = i + i; j <= m; j += i) { //i의 배수
check[j] = true;
}
}
for (int i = n; i <= m; i++) {
if (check[i] == false) {
System.out.println(i);
}
}
}
}
골드바흐의 추측(6588번)
https://www.acmicpc.net/problem/6588
- 2보다 큰 모든 짝수는 두 소수의 합으로 표현 가능하다.
- 위의 문장에 3을 더하면 5보다 큰 모든 홀수는 세 소수(2+3=5, 짝수+3=홀수, 3)의 합으로 표현 가능하다. 로 바뀐다.
- 아직 증명되지 않은 문제지만 10^18 이하에선 참임이 증명됨.
문제
백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오.
풀이
댓글남기기