알고리즘-수학2

수학

수학2에서는 수학1에서 다뤘던 내용을 기반으로 조금 더 응용하는 문제를 다뤄보겠습니다. 수학1 게시글(https://foxtrotin.tistory.com/95)을 보고 오면 도움이 되실 겁니다.

 

 

1. 나머지 연산

나머지 연산을 쓰는 유형에는 몇 가지가 있습니다. 나머지의 값이 필요할 때, 특정 수의 배수인지 판별, 짝수인지 홀수인지 판별, 몇 개의 수를 계속 돌리고 싶을 때, 너무 큰 수가 정답일 때 나머지 연산 후 정답을 출력할 때 등등.. 여기서는 몇 개의 수를 계속 돌리고 싶은 경우 어떻게 해야 하는지 알아보겠습니다.

 

#include <stdio.h>
int main(){
    int a[3] = { 1,2,3 };
 
    for (int i = 0; i < 6; i++) {
        printf("%d ", a[i % 3]);
    }
}

 

맨 처음 돌 때 i = 0입니다. a[0]을 출력합니다.

두 번째 돌 때는 i = 1입니다. a[1]을 출력합니다.

세 번째 돌 때는 i = 2입니다. a[2]을 출력합니다.

그러면 네 번째 돌 때는? i = 3이고 3%3 = 0이니까 a[0]을 다시 출력합니다.

 

이런 식으로 나머지 연산을 이용하면 특정 수들을 계속 반복해서 사용할 수 있습니다.

 

 

2. 소수

어떤 수가 소수인지 알 수 있는 간단한 방법으로는 2부터 그 수 이전까지의 모든 수를 하나씩 나머지 연산을 해보면서 나누어 떨어지는지 검사하는 것입니다. 그런데 이 방법을 엄청 큰 수에도 사용할 수 있을까요? 아니면 어떤 수 이하의 모든 소수를 출력하라는 문제에서도 하나씩 검사해야 할까요? 더 효율적인 방법이 필요합니다.

 

생각해봅시다. 6은 2와 3의 배수입니다. 2와 3은 소수입니다. 15는 3과 5의 배수입니다. 3과 5는 소수입니다. 21은 3과 7의 배수입니다. 3과 7도 소수입니다.

규칙이 보이나요? 어떤 수가 소수인지 알기 위해서는 굳이 전부 돌리지 않아도 됩니다. 어떤 수보다 작은 수의 소수들로만 나누어보면 되는 것입니다.

 

다른 방법을 생각해봅시다. 어떤 수까지의 모든 소수를 구하고 싶습니다. 어떤 수보다 작은 수를 전부 배열에 넣고 소수가 아닌 수를 지워버리면 소수만 남습니다. 2를 제외한 모든 2의 배수를 지우고, 3을 제외한 모든 3의 배수를 지우고, 4는 이미 지워졌으니까 패스, 5를 제외한 모든 5의 배수를 지우고..를 반복합니다. 이것은 ‘에라토스테네스의 체’라는 알고리즘입니다.

 

 

구현 자체는 어렵지 않습니다. 코드를 보지 않고 직접 해보시는 것을 추천합니다.

int a[10000001];
long long solution(int N) {
    long long answer = 0;
    for (int i = 2; i <= N; i++) {
        a[i] = i;
    }
    for (int i = 2; i <= sqrt(N); i++) {
        if (a[i]) {
            for (int j = i * 2; j <= N; j += i) {
                a[j] = 0;
            }
        }
    }
    for (int i = 2; i <= N; i++) {
        if (a[i] != 0) answer += a[i];
    }
    return answer;
}

 

 

3. 팩토리얼

고등학교에서 배꿨던 팩토리얼을 이제는 컴퓨터한테 계산을 시켜봅시다. 6! 이후의 팩토리얼 수부터 시작하겠습니다. 6!은 720, 7!은 5040, 8!은 40320, 9!은 362880, 10!은 368800… 25!은 1551121004*10^25, 50!은 3041409320*10^64. 뭔가 반복되는 점이 보입니다. 계산을 할수록 뒤에 0이 계속 늘어나고 있습니다. 0은 10을 얼마나 곱하느냐에 따라 결정됩니다. 즉, 팩토리얼 뒤에 붙는 0의 개수는 팩토리얼을 이루는 수의 소인수 중, 2와 5의 개수에 따라 결정됩니다.

 

정리를 해보겠습니다.

10! = 1*2*3…*10

10! = 1*2*3*(2*2)*5*(2*3)…*(2*5)

10! = 2^8 * 3^4 * 5^2 * 7

10! = (2^2 * 5^2) * 2^6 * 3^4 * 7

10! = 10^2 * 2^6 * 3^4 * 7

 

따라서 2와 5의 개수 중 작은 값이 0의 개수(=10의 개수)가 됩니다. 여기서는 두 개네요.

 

 

추천 문제

https://www.acmicpc.net/problem/2991

2991번: 사나운 개

https://www.acmicpc.net/problem/2960

2960번: 에라토스테네스의 체

https://www.acmicpc.net/problem/4948

4948번: 베르트랑 공준

https://www.acmicpc.net/problem/1676

1676번: 팩토리얼 0의 개수

https://www.acmicpc.net/problem/2553

2553번: 마지막 팩토리얼 수

https://www.acmicpc.net/problem/7489

7489번: 팩토리얼