류나의 갓생살기

20대의 마지막을 갓생으로 장식하기

Programming/Algorithms

UCPC 2022 예선 D-21 문제풀이 일지

Ryuna (류준범) 2022. 6. 11. 22:02

블로그 업데이트는 오랜만입니다.

지난 두 달 동안은 공부한 내용을 굳이 공개된 곳에 전부 깔끔히 정리해 포스팅할 필요는 없지 않을까~라는 생각에 개인 GoodNotes 계정에만 정리해두고 있었습니다. 굿노트가 워낙 효율이 좋아서인지 기존보다 훨씬 많은 공부량을 뽑아낼 수 있었지만, 최근 며칠 동안은 공부할 의욕이 잘 나지 않아 고민하던 차에 업데이트가 뜸하던 블로그가 생각났습니다.

UCPC 2022에 출전하게 됨에 따라 예선(그리고 잘 되면 본선까지..)을 대비해 매일 일정 수의 문제를 풀어보려고 하는데, 푼 문제를 블로그에 일지 형식으로 정리해보면 좋겠다고 판단해서 글을 작성하기 시작했습니다.

목차

1. 오늘의 알고리즘 진도

- 2941번: 크로아티아 알파벳

- 1193번: 분수찾기

- 10757번: 큰 수 A+B

- 2581번: 소수

- 11653번: 소인수분해

- 4948번: 베르트랑 공준

- 9020번: 골드바흐의 추측

- 10870번: 피보나치 수 5

- 17478번: 재귀함수가 뭔가요?

2. BOJ 랜덤 디펜스

- 1645번: 성지의 생일파티

- 10332번: Shopping

- 6161번: iCow

- 9693번: 시파르


오늘의 알고리즘 진도

최근 2주 정도 웹 개발하느라 알고리즘 문제풀이를 소홀히 했기 때문에 'BOJ 단계별로 풀어보기' 초반부의 풀지 않았던 문제를 풀어보면서 감을 되찾는 과정을 시행하기로 했습니다.

이에 따라 어제는 1~5단계를 완료했고, 오늘은 10단계 정도까지 완료할 생각으로 임했습니다.

※ C++ 코드 템플릿

혹시 제 코드를 참고하실 분들은 코드 최상단에 아래의 코드를 붙여넣어 주세요.

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <algorithm>
#include <utility>
#include <tuple>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define MT make_tuple
#define forn(i, a, b) for (int i = a; i <= b; i++)
#define all(v) v.begin(), v.end()

2941번: 크로아티아 알파벳

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

 

2941번: 크로아티아 알파벳

예전에는 운영체제에서 크로아티아 알파벳을 입력할 수가 없었다. 따라서, 다음과 같이 크로아티아 알파벳을 변경해서 입력했다. 크로아티아 알파벳 변경 č c= ć c- dž dz= đ d- lj lj nj nj š s= ž z=

www.acmicpc.net

처리해야 할 것이 8가지밖에 되지 않으니 무지성 if 문으로 구현할 수 있을 듯한 문제입니다. 주어진 문자열을 순회하면서 하나씩 세되 크로아티아 알파벳이 나온다면 그 길이만큼 건너뛰면 되겠죠.

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    string s;
    cin >> s;

    int n = s.size();
    int ans = 0;
    forn(i, 0, n-1) {
        ++ans;
        if (i == n-1) break;
        if (s[i] == 'c') {
            if (s[i+1] == '=' || s[i+1] == '-') ++i;
        }
        else if (s[i] == 'd') {
            if (s[i+1] == '-') ++i;
            else if (i+2 < n && s[i+1] == 'z' && s[i+2] == '=') i += 2;
        }
        else if (s[i] == 'l' && s[i+1] == 'j') ++i;
        else if (s[i] == 'n' && s[i+1] == 'j') ++i;
        else if (s[i] == 's' && s[i+1] == '=') ++i;
        else if (s[i] == 'z' && s[i+1] == '=') ++i; 
    }

    cout << ans;

    return 0;
}

알고리즘 분류: 구현, 문자열

현 시점 난이도: 실버 V

1193번: 분수찾기

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

 

1193번: 분수찾기

첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다.

www.acmicpc.net

X번째 분수가 몇 번째 대각선에 있는지 어떻게 알까요?

저는 떠오르는 방법이 마땅치 않아서 이분탐색을 쓰고 구현하느라 좀 고생했는데 인터넷 검색을 해 보니 그냥 1, 2, 3, ...을 순차적으로 X에서 빼면 되더라구요.

그 방법을 아니까 구현이 매우 쉬울 것 같다는 생각이 드네요...

아래 코드는 이분탐색을 사용한 코드인데 이렇게 하지는 마세요!

int X;

bool valid(int n) {
    int R = n * (n + 1) / 2;
    if (X <= R) return true;
    else return false;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> X;

    int l = 1, r = (int)sqrt(2 * X);
    while (l <= r) {
        int m = (l + r) / 2;
        if (valid(m)) r = m - 1;
        else l = m + 1;
    }

    int s = l * (l + 1) / 2;
    int p = s - X + 1;
    int q = l + 1 - p;

    if (l % 2) cout << p << "/" << q;
    else cout << q << "/" << p;

    return 0;
}

알고리즘 분류: 수학, 구현

현 시점 난이도: 브론즈 I

10757번: 큰 수 A + B

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

 

10757번: 큰 수 A+B

두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오.

www.acmicpc.net

이 문제는 C/C++로 풀기가 상대적으로 어렵습니다. 무지성 A+B가 안 되기 때문이죠!
저는 문자열로 큰 수를 받아서 받아올림을 구현하는 방식으로 풀었습니다.

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    string A, B;
    cin >> A >> B;

    int n = max(A.size(), B.size());
    while (A.size() < n) A = '0' + A;
    while (B.size() < n) B = '0' + B;

    string C = "";
    int sum = 0, up = 0;
    forn(i, 1, n) {
        int ai = A[n-i] - '0';
        int bi = B[n-i] - '0';
        sum = ai + bi + up;
        if (sum > 9) {
            sum -= 10;
            up = 1;
        } else up = 0;
        C = (char)('0' + sum) + C;
    }
    if (up == 1) C = '1' + C;

    cout << C;

    return 0;
}

알고리즘 분류: 수학, 구현, 사칙연산, 임의 정밀도 / 큰 수 연산

현 시점 난이도: 브론즈 V (특정 언어에서 매우 쉬워서 그렇습니다.)

2581번: 소수

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

 

2581번: 소수

M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다.  단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.

www.acmicpc.net

입력이 그다지 크지 않기 때문에 2부터 x-1까지 전부 나눠보는 기본적인 소수 판정법만으로 충분합니다.

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int M, N;
    cin >> M >> N;

    int sum = 0;
    int mn = N+1;
    forn(i, M, N) {
        bool is_prime = true;
        if (i == 1) is_prime = false;
        forn(j, 2, i-1) {
            if (i % j == 0) {
                is_prime = false;
                break;
            }
        }
        if (is_prime) {
            sum += i;
            mn = min(mn, i);
        }
    }

    if (sum == 0) cout << -1;
    else cout << sum << "\n" << mn;

    return 0;
}

알고리즘 분류: 수학, 정수론, 소수 판정

현 시점 난이도: 실버 V

11653번: 소인수분해

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

 

11653번: 소인수분해

첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.

www.acmicpc.net

모든 수로 나눠보면서 찾으려고 하면 시간 초과가 발생합니다. 시간 안에 동작하려면 다음과 같은 최적화가 필요합니다.

1. 소수를 찾으면, 소수 배열에 넣어서 다음으로 큰 소수를 찾는 시간을 줄인다.

2. 소수를 찾을 때, 소수 배열 중에서 판정하려는 수의 제곱근 이하의 값만 보면 된다.

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N;
    cin >> N;

    vector<int> primes;
    forn(i, 2, N) {
        bool is_prime = true;
        for (auto j : primes) {
            if (i % j == 0) {
                is_prime = false;
                break;
            }
            if (j * j > i) break;
        }
        if (is_prime) {
            primes.PB(i);
            while (N % i == 0) {
                cout << i << "\n";
                N /= i;
            }
        }
    }

    return 0;
}

알고리즘 분류: 수학, 정수론, 소수 판정

현 시점 난이도: 실버 V

4948번: 베르트랑 공준

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

 

4948번: 베르트랑 공준

베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼

www.acmicpc.net

소인수분해 문제에서 사용한 방법을 여러 개의 테스트 케이스에 대해서 반복하면 됩니다.

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    while (n > 0) {
        
        vector<int> primes;
        int ans = 0;
        forn(i, 2, 2 * n) {
            bool is_prime = true;
            for (auto p : primes) {
                if (p * p > i) break;
                if (i % p == 0) {
                    is_prime = false;
                    break;
                }
            }
            if (is_prime) {
                primes.PB(i);
                if (i > n) ++ans;
            }
        }

        cout << ans << "\n";
        cin >> n;
    }

    return 0;
}

알고리즘 분류: 수학, 정수론, 소수 판정, 에라토스테네스의 체

현 시점 난이도: 실버 II

9020번: 골드바흐의 추측

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

 

9020번: 골드바흐의 추측

1보다 큰 자연수 중에서  1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아

www.acmicpc.net

소인수분해 문제에서 사용한 방법을 응용한 또 다른 문제입니다.

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int T;
    cin >> T;

    while (T--) {
        int n;
        cin >> n;
        vector<int> primes;
        // find primes below n / 2
        forn(i, 2, n / 2) {
            bool is_prime = true;
            for (auto p : primes) {
                if (p * p > i) break;
                if (i % p == 0) {
                    is_prime = false;
                    break;
                }
            }
            if (is_prime) {
                primes.PB(i);
            }
        }
        // iterate from biggest prime
        // if n - prime is also prime, print the answer
        int cnt = primes.size();
        forn(i, 1, cnt) {
            int num = n - primes[cnt - i];
            bool is_prime = true;
            for (auto p : primes) {
                if (p * p > num) break;
                if (num % p == 0) {
                    is_prime = false;
                    break;
                }
            }
            if (is_prime) {
                cout << primes[cnt - i] << " " << num << "\n";
                break;
            }
        }
    }

    return 0;
}

알고리즘 분류: 수학, 정수론, 소수 판정, 에라토스테네스의 체

현 시점 난이도: 실버 II

10870번: 피보나치 수 5

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

 

10870번: 피보나치 수 5

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가

www.acmicpc.net

입력 제한이 너무 시시하지만... 재귀로 풀어 봅시다.

int fib(int n) {
    if (n <= 0) return 0;
    if (n <= 2) return 1;
    return fib(n-1) + fib(n-2);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    cout << fib(n);

    return 0;
}

알고리즘 분류: 구현, 수학, 재귀

현 시점 난이도: 브론즈 V

17478번: 재귀함수가 뭔가요?

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

 

17478번: 재귀함수가 뭔가요?

평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대

www.acmicpc.net

재귀에 대한 연습이 확실히 되는 문제지만 구현이 귀찮아요!

int n;

string rec(int k) {
    string under = "";
    forn(i, 1, k) {
        under += "____";
    }
    if (k == n) {
        string r = under + "\"재귀함수가 뭔가요?\"\n";
        r += under + "\"재귀함수는 자기 자신을 호출하는 함수라네\"\n";
        r += under + "라고 답변하였지.\n";
        return r;
    }
    string r = "";
    r += under + "\"재귀함수가 뭔가요?\"\n";
    r += under + "\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.\n";
    r += under + "마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.\n";
    r += under + "그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"\n";
    r += rec(k + 1);
    r += under + "라고 답변하였지.\n";
    return r;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    cout << "어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.\n";
    cout << rec(0);

    return 0;
}

알고리즘 분류: 구현, 재귀

현 시점 난이도: 실버 V

BOJ 랜덤 디펜스

쉬운 문제를 빠르게 푸는 연습을 위해 BOJ 랜덤 디펜스를 하기로 했습니다.

사용한 solved.ac 명령어는 ( lang:ko | lang:en ) & *b5..s1 - @$me 이며, 제가 풀지 않은 문제 중 한국어 또는 영어로 된 브론즈 또는 실버 문제를 검색하고 랜덤 4문제를 풀기로 하였습니다. 그리고 4문제 중 1문제 이상을 Python으로 풀기로 했습니다.

저는 현재 골드 I 티어이지만, 쉬운 문제를 빠르게 푸는 능력을 기르는 것 외에도 자신감을 높이기 위한 목적도 있어서 골드 문제를 포함하지 않았습니다.

 

그래서 오늘의 '시프트 마음대로' 결과는...!

1645번: 성지의 생일파티

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

 

1645번: 성지의 생일파티

서울 관악구 신림동에 살고 있는 성지의 생일이 3일 앞으로 다가왔다. (황성지 아닙니다!) 일요일에서 월요일이 되는 12시 정각, 902호에서 자음 퀴즈의 달인 성지의 생일을 기념하는 성대한 파티

www.acmicpc.net

테스트 케이스가 맞길래 제출했다가 3번을 틀리고 나서야 '초대되지 않은 학생의 생각은 고려할 필요 없다'는 것을 깨닫게 되었습니다.

그걸 알고 다시 구현하니 맞더라고요...

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N;
    cin >> N;
    vector<int> ks(N);
    forn(i, 0, N-1) cin >> ks[i];

    sort(all(ks));
    int ans = ks[0];
    if (ans == 0) ans = 1;
    else while (ks[ans-1] > ans-1) ++ans;

    cout << ans;

    return 0;
}

알고리즘 분류: 구현, 정렬

현 시점 난이도: 실버 IV

10332번: Shopping

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

 

10332번: Shopping

Your friend will enjoy shopping. She will walk through a mall along a straight street, where N individual shops (numbered from 1 to N) are aligned at regular intervals. Each shop has one door and is located at the one side of the street. The distances betw

www.acmicpc.net

대충 페어를 잘 정렬해둔 다음에 '강의실 배정' 문제 풀듯이 그리디하게 접근하면 되겠거니 하는 건 금방 알았습니다.

그런데 어찌된 영문인지 정렬을 제대로 했는데도 계속 틀리더라구요. 그래서 우선순위 큐를 쓰는 걸로 바꿔 구현했더니 바로 맞혔어요.

알고 보니까 사용한 자료구조의 문제가 아니라 사소한 실수여서 아쉬웠네요.

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N, m;
    cin >> N >> m;
    priority_queue<pii> res;
    forn(i, 0, m-1) {
        int c, d;
        cin >> c >> d;
        res.push(MP(-c, -d));
    }

    int ans = 0;
    int cur = 0;
    while (!res.empty()) {
        int left = -res.top().F;
        int right = -res.top().S;
        res.pop();
        while (!res.empty() && right >= -res.top().F) {
            right = max(right, -res.top().S);
            left = min(left, -res.top().F);
            res.pop();
        }
        ans += (right - cur) + (right - left);
        cur = left;
    }
    ans += (N + 1) - cur;

    cout << ans;

    return 0;
}

알고리즘 분류: 그리디 알고리즘, 정렬, 스위핑

현 시점 난이도: 실버 I

6161번: iCow

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

 

6161번: iCow

Fatigued by the endless toils of farming, Farmer John has decided to try his hand in the MP3 player market with the new iCow. It is an MP3 player that stores N songs (1 <= N <= 1,000) indexed 1 through N that plays songs in a "shuffled" order, as determine

www.acmicpc.net

그냥 문제 상황을 잘 구현하면 됩니다. 그런데, 이 문제도 계속 틀린 끝에서야 '배분 후 나머지 점수를 주는 기준'이 그냥 인덱스 순이라는 걸 알게 되었습니다...

사실 그걸 바로 알았더라도 아주 만만한 문제는 아니긴 합니다.

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N, T;
    cin >> N >> T;
    vector<int> R(N);
    int mx = 0;
    int mxi = -1;
    forn(i, 0, N-1) {
        cin >> R[i];
        if (mx < R[i]) {
            mxi = i;
            mx = R[i];
        }
    }

    forn(_, 1, T) {
        cout << mxi + 1 << "\n";
        int dist = R[mxi] / (N - 1);
        int left = R[mxi] % (N - 1);
        R[mxi] = 0;
        mx = 0;
        int nmxi = -1;
        forn(i, 0, N-1) {
            if (i != mxi) {
                R[i] += dist;
                if (i < left) R[i] += 1;
                if (left >= mxi && i == left) R[i] += 1;
            }
            if (mx < R[i]) {
                nmxi = i;
                mx = R[i];
            }
        }
        mxi = nmxi;
    }

    return 0;
}

알고리즘 분류: 구현, 시뮬레이션

현 시점 난이도: 브론즈 I

9693번: 시파르

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

 

9693번: 시파르

N이 주어졌을 때, N!/10M이 정수가 되는 M 중 가장 큰 것을 출력하시오.

www.acmicpc.net

Python으로 풀기로 한 문제인데, 계속 시간 초과가 발생해서 파이썬 문제인가 싶었지만..

겨우 통과를 한 다음에 다른 사람들의 코드를 쭉 훑어보니 제가 비효율적으로 짠 게 맞더라고요.

아래는 효율적인 코드를 공유합니다!

import sys
input = sys.stdin.readline

N = int(input())
x = 1
while N:
    # twos are always greater than fives
    fives = 0
    while N:
        fives += N // 5
        N //= 5
    print(f"Case #{x}: {fives}")
    x += 1
    N = int(input())

알고리즘 분류: 수학, 정수론

현 시점 난이도: 실버 IV


생각보다 랜덤 디펜스가 매우 힘들군요...

특히 수학 부분이 약한데, 문제 상황 알아듣는 것에서부터 불협화음이 발생해 버리니 쉽지 않았어요.

빨리 강해지고 싶습니다 ㅠㅠ