알고리즘 문제풀이 - 수학 자주 나오는 개념 총정리

 

많은 수학 문제들이 있지만 가장 자주 나오는 문제부터 살펴보고

나머지는 교양으로 알아보자

 

---

 

나머지

 

나머지는 특히 답에 xxx로 나눈 나머지를 구하시오와 같은 문제로 많이 나오는데

이건 범위를 제한하기 위해서다.

즉, 기본 자료형의 범위를 초과한다고 생각하면 이런 문제가 나온다.

 

나머지에는 특징이 있는데

덧셈, 곱셈, 뺄셈은 이 법칙이 적용이 되고

나눗셈은 안된다.

 

1. 합을 나눈 것은 각자의 나머지의 합의 나머지를 구하는 것과 같다

2. 곱을 나눈 것은 각자의 나머지를 곱해서 나머지를 구하는 것과 같다.

 

3. 뺄셈을 나눈 것은 각자의 나머지를 뺀 것의 나머지를 구하는 것과 같다.

**다만 뺄셈은 음수가 나올 수 있기 때문에 M을 한 번 더해준다.

 

마치 분배법칙을 이용한 것과 같다. 하지만 조금 다르다.

분배를 하면 사라지지만 여전히 결과에 나머지를 구하는 것이 특징이다.

 

 

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

10430번: 나머지

 

이 문제가 딱 알맞다.

 

이 문제는 풀이를 쓰고 말고 할 것이 없다.

그냥 쓰면 된다.

 

**명심하자. 나머지를 적용한 것의 연산결과에 나머지 한 것은 연산결과의 나머지를 구한 것과 같다.

**덧셈, 뺄셈, 곱셈 한정

 

---

 

소수

 

소수의 문제는 2가지 정도가 있다.

 

1. 소수인지 판별하는 것

2.범위 안의 소수를 구하는 것

 

우선 소수 판별은 나머지를 이용해서 구현한다.

bool is_prime(int x) {
    if (x < 2) {
        return false;
    }
    for (int i=2; i*i <= x; i++) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}

 

왜 범위를 i*i < x이냐?

라고 하냐면

 

쉽게 말해서 i보다 큰 수가 x를 만드는 것이 존재한다면 이미 i 전에 발견되었어야 한다.

즉, 작은 i에 대해서 없었으니 그 이후 큰 수도 조사할 필요가 없다는 말이다

 

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

1978번: 소수 찾기

 

#include <iostream>
using namespace std;
bool is_prime(int x) {
    if (x < 2) {
        return false;
    }
    for (int i=2; i*i <= x; i++) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}
int main() {
    int n;
    cin >> n;
    
    int cnt = 0;
    for (int i=0; i<n; i++) {
        int num;
        cin >> num;
        if (is_prime(num)) {
            cnt += 1;
        }
    }

    cout << cnt << '\n';
    return 0;
}

 

 

 

---

 

에라토스테네스의 체

 

이게 바로 범위 안의 소수를 구하는 방법이다.

 

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

1929번: 소수 구하기

 

#include <iostream>
using namespace std;
//최댓값
const int MAX = 1000000;
int prime[MAX]; //0으로 초기화된 배열 => 소수를 담을 배열
int pn; //0부터시작
bool check[MAX+1]; //false로 초기화된 배열


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //소수검사
    for (int i = 2; i <= MAX; i++) {
    	//해당 숫자가 아직 false라면 그것은 소수임.
        if (check[i] == false) {
            prime[pn++] = i; //소수를 0번째 index부터 집어넣음
            
            //해당 숫자에 대한 배수를 모조리 지움 2 * i부터.. n * i 까지
            for (int j = i + i; j <= MAX; j += i) {
                check[j] = true;
            }
        }
    }
    while (true) {
        int n;
        cin >> n;
        if (n == 0) {
            break;
        }
        //소수 출력
        for (int i = 1; i < pn; i++) {
            if (check[n - prime[i]] == false) {
                cout << n << " = " << prime[i] << " + " << n - prime[i] << '\n';
                break;
            }
        }
    }
    return 0;
}

 

 

범위 내 소수를 이용하는 문제는 여기 있다.

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

6588번: 골드바흐의 추측

 

 

#include <iostream>
using namespace std;
const int MAX = 1000000;
int prime[MAX];
int pn;
bool check[MAX+1];

//에라토스테네스의 채와 같다. 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    for (int i = 2; i <= MAX; i++) {
        if (check[i] == false) {
            prime[pn++] = i;
            for (int j = i + i; j <= MAX; j += i) {
                check[j] = true;
            }
        }
    }
    while (true) {
        int n;
        cin >> n;
        if (n == 0) {
            break;
        }
        //다만 출력시에 n - prime[i]인 것처럼
        //n이 소수 2개의 합인지를 체크한다.
        for (int i = 1; i < pn; i++) {
            if (check[n - prime[i]] == false) {
                cout << n << " = " << prime[i] << " + " << n - prime[i] << '\n';
                break;
            }
        }
    }
    return 0;
}

 

 

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

17103번: 골드바흐 파티션

 

 

---

 

최대공약수(유클리드 호제법)

 

최대공약수는 이미 빠른 풀이가 널리 알려져 있다.

유클리드 호제법이다.

int gcd (int a, int b) {
    if (b ==0) {
    	return a;
    } else
    {
    	return gcd(b, a%b);
    }
}

a = bq + r

b= cq + r

...

이런 식으로

나누어지지 않을 때까지 진행한다.

 

물론 나는 재귀를 선호하지만

반복문으로도 만들 수 있다.

int gcd(int a, int b) {
    while (b !=0) {
    	int r = a%b;
        a = b;
        b =r;
    }
    return a;
}

 

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

9613번: GCD 합

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

17087번: 숨바꼭질 6

---

 

최소공배수

 

최소공배수는 최대공약수의 연장이다.

최대공약수를 구할 수 있다면 최소공배수는 거저다.

A = Ga, B = Gb라면

LCD = Gab이다.

 

문제로 그냥 익히면 된다.

 

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

2609번: 최대공약수와 최소공배수

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

1934번: 최소공배수

 

 

---

 

팩토리얼

 

팩토리얼은 정말 빠르게 커지는 숫자로 많이 쓰이진 않지만 쓰이긴 쓰여서 알아봐야 한다.

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

1676번: 팩토리얼 0의 개수

 

 

#include<iostream>

using namespace std;

//0의 개수는 소인수분해 시 2와 5의 개수에 따라 결정된다.
//즉, 모든 숫자에 대해서 2,5의 개수파악, 근데 2의 개수가 압도적으로 많으므로 5의 개수만 파악하면 알아서 되겠다.

int dp[501];



int main(){
    
    int N;
    cin >> N;
    for(int i = 1; i<=N; i++){
        int cnt = 0;
        int temp = i;
        while(1){
            if(temp%5 == 0){
                cnt++;
                temp /= 5;
            }else{
                break;
            }
        }
        dp[i] = cnt;
    }
    int ans = 0;
    for(int i = 1; i<=N; i++){
        ans += dp[i];
    }
    
    cout << ans << '\n' ;
}

 

이것은 모두 소인수분해다.

 

이것도 소인수분해로 풀 수 있다.

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

2004번: 조합 0의 개수

 

 

---

 

x진법

 

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

1373번: 2진수 8진수

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

1212번: 8진수 2진수

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

2089번: -2진수