240423: 클래스 2. 팩토리얼 0의 개수 구하기와 해시 문제, 수학 시그마

2024-04-23

CLASS 2 문제를 풀었다.

앞으로 CLASS 2 금장 달성까지 4문제 남았다

• 큐 (10845)
• 덱 (10866)
• 팩토리얼 0의 개수 (1676)
• Hashing (15829)
• 부녀회장이 될테야 (2775)
• 덩치 (7568)

대략 브론즈 ~ 실버 문제들이었다. 수학 기믹이 필요한 문제들을 제외하곤 모두 문제없이 풀었다.
기초가 견고해지는 느낌이라 기분이 좋다.

큐, 덱 문제는 너무나 기초 문제니까 설명은 스킵하고.
팩토리얼 0의 개수 문제는 "내가 무슨 수학자야?" 싶은 문제였다. (그니까 알고리즘 잘하려면 이런 기믹까지 생각 해야되나..) 라는 생각

문제는 다음과 같다

N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.
첫째 줄에 N이 주어진다. (N < 501)

그니까, 예를 들어서 12! (12의 팩토리얼) 의 값은 479,001,600이다. 뒤에 붙는 0의 개수가 2개이기 때문에 답은 2다.

여기서 주어지는 수 N의 제한이 500 이하인것으로 보아.. 단순한 해로 풀수는 없어 보인다. (N이 20만 돼도 값은 2,432,902,008,176,640,000가 되고 .. 500!을 계산하는 건 내 삶 내에서 불가능할 것 같다.)

여기서 중요한점은 맨 뒤에 오는 0을 어떤 수가 만드느냐다. 0은 10의 배수만 만들 수 있다. 10의 배수는 2와 5의 곱으로 만들 수 있다 (여기서 들었던 의문점은, 예를 들어서 6 * 5 도 30으로 10의 배수인데. 왜 6과 5는 고려 선상에서 제외하는가? 인데. 사실 6도 5도 2와 5의 배수다. 또 들었던 의문점은 왜 10의 배수를 그냥 구하지 않고 굳이 2와 5의 곱으로 만드는가? 인데. 팩토리얼에서 수는 매우 빠르게 증가하기 때문에 10의 배수를 볼 기회가 많이 없다. 그래서 최대한 10을 만들 수 있는 작은 수 (10의 약수 2와 5)를 고려하는 것이다)

결론적으로, 숫자 맨 뒤에 붙는 0은 10의 배수가 만드는 것이고. 10의 배수는 2와 5의 배수로 만들 수 있다.
즉, 2와 5가 한 짝을 이루는 개수가 숫자 뒤에 붙는 0의 개수와 같다.

그래서 팩토리얼 계산에서 등장하는 2와 5의 개수를 세면 되는데, 예를 들어서 10! 을 계산할 때:
1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10 으로 증가하는데, 단순한 증가 수열에서는 2의 배수가 5의 배수보다 훨씬 많이 나옴을 알 수 있다. 위를 보면 2의 배수는 (2, 4, 6, 8, 10)으로 총 5개인데, 5의 배수는 (5, 10)으로 총 2개이다. 2와 5가 한 짝을 이뤄야만 비로소 10의 배수. (뒤의 0)이 되기 때문에 사실상 2보다 개수가 훨씬 적은 5의 개수로 짝이 제한된다. 즉 5의 배수의 개수만 구하면 문제를 풀 수 있다.

근데 주의할점은, 5의 제곱수 (25, 125) 그리고 그 제곱수의 배수 (50, 75 등)은 결국에 5 * 5로 이루어져 있기에 그 자체로 5가 두개다. 즉 5의 제곱수와 그 배수에 대해서는 0을 두개 추가해야 한다. (한번 더 고려해야 한다)

더 최적화하자면 i를 5부터 시작해서, i를 제곱한 값이 N보다 커질때까지 N을 i로 나눈 값의 몫을 더하는 것이다. 만약 N이 25라면 5의 배수가 총 5번 포함되어 있고. 이걸 하나하나 순회해서 구하는 것보다 N이 i를 제곱한 값보다 크거나 같을동안 N을 i로 나눈 몫을 count에 추가하는 것이다.

어렵고 복잡하다.

코드

// 백준: 팩토리얼 0의 개수
// https://www.acmicpc.net/problem/1676
// 2024-04-22

/*
N!의 맨 뒤 0의 개수는 10의 배수로 만들어짐을 이용한다.
10의 배수는 2와 5의 곱으로 만들어진다. 즉 2와 5가 이루는 짝의 수 = 0의 개수
즉, 10! 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 인데
여기서 2의 배수는 총 5번 (2, 4, 6, 8, 10) 5의 배수는 총 2번 (5, 10) 등장한다.
모든 수에서 2의 배수보다 5의 배수가 훨씬 적게 등장하므로 2의 배수가 아무리 많더라도 5의 배수의 수로 제한되기에
N!에서 N의 5의 배수의 수를 구하면 풀 수 있다.
*/

#include <iostream>
using namespace std;

int main() {
    int N;
    cin >> N;

    int count = 0;
    for (int i = 5; i <= N; i *= 5) {
        count += N / i;
    }

    cout << count;
    return 0;
}

---

Hashing

Hashing 문제는 주어진 문자열을 요구하는 해시 함수에 맞춰서 변환하는 문제이다. 해시의 기본 원리와 수학 개념의 이해가 필요한 문제.

먼저 시그마가 나왔는데. 시그마에 대해 알아보니 코딩의 for문과 비슷한 점이 많았다. 수학과 코딩이 통하는 부분이 있군..

시그마의 하한이 i=0이고, 상한이 l-1 (l은 문자열의 길이) 인것은 a, b, c, d, e를 순서대로 1 ... 5 라고 가정하고
각 인덱스마다 26보다 큰 소수 31(r값)을 인덱스만큼 제곱한다음 a(i)와 곱하고. 모든 결과를 더한 값임을 알아냈다.

시그마에 대해 알았고, 해시 함수의 내부 구조에 대해 대략 알게 된 교육적인 문제였다.
그리고 모듈러 함수는 덧셈, 뺄셈, 곱셈에 대해 교환 법칙이 성립하고 (대충 아무렇게나 모듈러 해도 결과는 똑같다는 소리) 나눗셈에 대해선 역원을 구해야되는데, 이게 예전에 했던 페르마의 소정리 관련 내용이다. 어려우니까 일단 스킵..

ps. char에 'a'를 빼고 +1 하려고 했는데. a 바로 밑 아스키 값이 백틱 (`) 이라길래 살짝 멋있게 그거 썼다.

// 백준: Hashing
// https://www.acmicpc.net/problem/15829
// 2024-04-23

#define r 31
#define M 1'234'567'891
#include <iostream>
using namespace std;
typedef long long ll;

ll p(ll base, ll exp) {
    ll result = 1;
    while (exp != 0) {
        if (exp % 2 == 1)
            result = (base * result) % M;
        base = (base * base) % M;
        exp /= 2;
    }
    return result;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int L;
    cin >> L;
    ll result = 0;
    for (int i = 0; i < L; ++i) {
        char next;
        cin >> next;
        result += ((ll)(next - '`') * (ll)p(r, i)) % M;
        result %= M;
    }

    cout << result;

    return 0;
}

---

부녀회장이 될테야

간단한 DP문제. DP가 처음엔 정말 어려웠는데. 요즘은 감 잡힌 것 같아서 기분이 좋다. 브론즈~실버 DP는 가볍게 푸는 듯

평소 반상회에 참석하는 것을 좋아하는 주희는 이번 기회에 부녀회장이 되고 싶어 각 층의 사람들을 불러 모아 반상회를 주최하려고 한다.

이 아파트에 거주를 하려면 조건이 있는데, “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다” 는 계약 조항을 꼭 지키고 들어와야 한다.

아파트에 비어있는 집은 없고 모든 거주민들이 이 계약 조건을 지키고 왔다고 가정했을 때, 주어지는 양의 정수 k와 n에 대해 k층에 n호에는 몇 명이 살고 있는지 출력하라. 단, 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다.

그니까, h층의 w호에는 h-1층의 w호부터 1호까지의 모든 인원 합이 산다는 것. 간단하게 3중 for문 DP로 풀었다.
0층의 w호에는 w명이 살기 때문에 이것을 기본 사례로 설정했고. for문을 돌리면서 위의 점화식을 따랐다.

// 백준: 부녀회장이 될테야
// https://www.acmicpc.net/problem/2775
// 2024-04-23

#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int k; // 층
        int n; // 호
        cin >> k >> n;
        vector<vector<ll>> dp(k + 1, vector<ll>(n + 1));
        // BASE CASE
        for (int i = 1; i <= n; ++i) {
            dp[0][i] = i; // 0층의 i호에는 i명이 산다 *
        }

        for (int h = 1; h <= k; ++h) {     // 층 루프
            for (int w = 1; w <= n; ++w) { // 호 루프
                // 현재 층에서 가리키고 있는 호에 대해서 0까지 이전 층에서 루프
                for (int i = w; i > 0; --i) {
                    dp[h][w] += dp[h - 1][i];
                }
            }
        }

        cout << dp[k][n] << "\n";
    }
    return 0;
}

---

덩치

브루트포스 알고리즘 + 구현 문제로. 그냥 주어진 문제를 제일 단순한 방법으로 풀면 풀리는 문제.

우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩치가 각각 (x, y), (p, q)라고 할 때 x > p 그리고 y > q 이라면 우리는 A의 덩치가 B의 덩치보다 "더 크다"고 말한다. 예를 들어 어떤 A, B 두 사람의 덩치가 각각 (56, 177), (45, 165) 라고 한다면 A의 덩치가 B보다 큰 셈이 된다. 그런데 서로 다른 덩치끼리 크기를 정할 수 없는 경우도 있다. 예를 들어 두 사람 C와 D의 덩치가 각각 (45, 181), (55, 173)이라면 몸무게는 D가 C보다 더 무겁고, 키는 C가 더 크므로, "덩치"로만 볼 때 C와 D는 누구도 상대방보다 더 크다고 말할 수 없다.

N명의 집단에서 각 사람의 덩치 등수는 자신보다 더 "큰 덩치"의 사람의 수로 정해진다. 만일 자신보다 더 큰 덩치의 사람이 k명이라면 그 사람의 덩치 등수는 k+1이 된다. 이렇게 등수를 결정하면 같은 덩치 등수를 가진 사람은 여러 명도 가능하다. 

학생 N명의 몸무게와 키가 담긴 입력을 읽어서 각 사람의 덩치 등수를 계산하여 출력해야 한다.

첫 줄에는 전체 사람의 수 N이 주어진다. 그리고 이어지는 N개의 줄에는 각 사람의 몸무게와 키를 나타내는 양의 정수 x와 y가 하나의 공백을 두고 각각 나타난다.

문제 설명이 좀 길다. 요구하는 것은 쉬운데 문제 설명을 일부러 길고 복잡하게 적는 문제들이 많다. 이게 나쁘지는 않다고 보는게, 문제 설명이나 열자마자 뜨는 복잡해보이는 그래프, 수학식 같은거에 쫄지 않는 배짱을 키울 수 있어서..

그니까, 각 사람들의 키와 몸무게가 주어지고. 다른 사람보다 키 몸무게 둘다 크면 그 사람의 덩치가 더 크다고 하다.

사람 N명의 키, 몸무게 정보가 주어졌을 때. 순위를 차례대로 출력하는데, 자기보다 덩치가 큰 사람을 k라고 했을 때 자신의 순위는 k+1위다.

2중 포문으로 현재 선택된 사람에 대해서 다른 사람들에 대해 반복을 돌리는 브루트포스 방식으로 가볍게 풀 수 있었다.

// 백준: 덩치
// https://www.acmicpc.net/problem/7568
// 2024-04-23

#include <iostream>
#include <utility>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N;
    cin >> N;
    vector<pair<int, int>> p(N);
    for (int i = 0; i < N; ++i) {
        int weight, height;
        cin >> weight >> height;
        p[i] = make_pair(weight, height);
    }

    for (int i = 0; i < N; ++i) {
        int k = 0;
        int cur_weight = p[i].first;
        int cur_height = p[i].second;
        for (int j = 0; j < N; ++j) {
            if (j == i)
                continue;
            int comp_weight = p[j].first;
            int comp_height = p[j].second;
            if (cur_weight < comp_weight && cur_height < comp_height)
                k++;
        }
        cout << k + 1 << " ";
    }
    return 0;
}

---

이제 클래스 2 금장까지 남은 문제는

• 스택 수열
• Printer Queue
• solved.ac
• 마인크래프트

이번주 내로 끝내기로 하자. ~ 평균 난이도는 실버다.