[ICPC Sinchon] 25W 알고리즘 캠프 초급 강의 3회차 과제 에디토리얼

3회차 - n log n 정렬, 기초 수학

 

---

</2751> 수 정렬하기 2

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

C++ STL에 있는 정렬 함수를 사용한 풀이입니다. 정렬 함수를 사용하기 위해 <algorithm> 헤더를 포함시켰습니다.

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

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

    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    sort(a.begin(), a.end());

    for (int i = 0; i < n; i++) cout << a[i] << '\n';
}

 

---

</10989> 수 정렬하기 3

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

2751번과 같은 풀이로 풀면 메모리 초과를 받게 됩니다.

수가 아무리 커도 10000이라는 것을 이용하여 다음과 같이 카운트 배열을 만들어서 풀 수 있습니다.

#include <iostream>
using namespace std;

int cnt[10001];

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

    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        cnt[x]++;
    }

    int idx = 1;
    while (idx < 10001) {
        while (cnt[idx]--) cout << idx << '\n';
        idx++;
    }
}

 

---

</11650> 좌표 정렬하기 2

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

pair를 원소로 하는 vector를 만들어 정렬해주었습니다. 
그냥 sort 써주면 기본적으로 pair의 첫번째 원소로 오름차순 정렬하고 같다면 두번째 원소로 오름차순 정렬해줍니다. 
민재 멘토님이 말씀하신 compare의 함수를 연습해보고 싶다면 11651번 문제도 추천합니다.

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

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

    int n;
    cin >> n;

    vector<pair<int, int>> a;

    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        a.emplace_back(x, y);
    }

    sort(a.begin(), a.end());

    for (int i = 0; i < n; i++) cout << a[i].first << ' ' << a[i].second << '\n';
}

 

---

</1978> 소수 찾기

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

각 수에 대해서 2부터 나눠보면서 소수인지 판별하는 방식으로 구현하였습니다.

소수 판별법 중 가장 간단한 방법입니다.

#include <iostream>
#include <cmath>
using namespace std;

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

    int n;
    cin >> n;

    int cnt = 0;

    while (n--) {
        int x;
        cin >> x;

        if (x < 2) continue;

        bool isPrime = true;
        int tmp = sqrt(x);
        for (int i = 2; i <= tmp; i++) {
            if (x % i == 0) {
                isPrime = false;
                break;
            }
        }

        if (isPrime) cnt++;
    }

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

 

---

</1929> 소수 구하기

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

에라토스테네스의 체의 정석이라고 할 수 있는 문제입니다.

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

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

    int m, n;
    cin >> m >> n;

    // 소수 판별을 위한 배열 생성 (기본값은 true)
    vector<bool> a(n + 1, true);
    a[0] = a[1] = false; // 0과 1은 소수가 아님
    int tmp = sqrt(n);

    // 에라토스테네스의 체
    for (int i = 2; i <= tmp; i++) {
        if (a[i]) { // i가 소수라면
            for (int j = i + i; j <= n; j += i) a[j] = false;
        }
    }

    for (int i = m; i <= n; i++) {
        if (a[i]) cout << i << '\n';
    }

    return 0;
}

 

---

</24039> 2021은 무엇이 특별할까?

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

에라토스테네스의 체의 활용 문제입니다.

에라토스테네스의 체를 이용하여 소수를 구해둔 다음, 두 인접한 소수를 곱해가며 정답을 출력하면 됩니다.

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

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

    int n;
    cin >> n;

    // pn: 배열 p의 크기
    int pn = 110;
    // p: 소수 판별을 위한 배열 (기본값은 true)
    vector<bool> p(pn, true);
    p[0] = p[1] = false; // 0과 1은 소수가 아님

    // 에라토스테네스의 체
    int tmp = sqrt(n);
    for (int i = 2; i <= tmp; i++) {
        if (p[i]) { // i가 소수라면
            for (int j = i + i; j <= n; j += i) p[j] = false;
        }
    }

    int pre = 2; // 이전 소수
    int cur; // 현재 소수
    for (int i = 3; i < pn; i++) {
        if (!p[i]) continue; // 소수가 아니라면 건너뛰기
        cur = i;
        int mul = pre * cur; // 이전 소수와 현재 소수의 곱 = 특별한 수
        if (mul > n) { // 특별한 수가 n보다 크면 출력
            cout << mul << '\n';
            return 0;
        } else { // 작으면 계속 반복
            pre = cur;
        }
    }
}

* pn(배열 p의 크기)을 110으로 설정한 이유?

우선 n은 10000 이하의 자연수입니다.

1929번의 코드를 실행시키고 1 120 이라고 입력하시면 다음과 같은 결과를 얻으실 수 있습니다.

2
3
5
...
89
97
101
103
107
109
113

두 인접한 소수인 101과 103을 곱하면 10000을 넘는 것을 확인할 수 있습니다.

따라서, 약간 여유있게 110으로 잡은 것입니다. 

계산을 최대한 줄이려고 이렇게 한 것이지만 귀찮다면 그냥 적당히 큰 값을 넣어주는 것도 괜찮은 방법입니다.

 

---

</23048> 자연수 색칠하기

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

에라토스테네스의 체를 활용하여 풀 수 있습니다.

에라토스테네스의 체와 다른 점은 크게 아래 두 가지입니다. 

1. 색을 칠해야 하므로 bool 배열이 아닌 int 배열을 사용합니다.

2. 변수 j를 활용하는 반복문을 보면, j가 i + i 부터 시작하는 것이 아니라, i 부터 시작합니다. 이 문제에서는 소수도 색을 칠해줘야 하기 때문입니다.

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

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

    int n;
    cin >> n;

    // 색을 저장하는 배열 생성 (기본값은 0)
    vector<int> p(n + 1, 0);
    p[1] = 1;

    // 에라토스테네스의 체를 활용하여 색칠하기
    int color = 2;
    for (int i = 2; i < n + 1; i++) {
        if (p[i] == 0) { // i가 소수라면
            for (int j = i; j <= n; j += i) {
                p[j] = color;
            }
            color++;
        }
    }

    cout << color - 1 << '\n';
    for (int i = 1; i < n + 1; i++) cout << p[i] << ' ';
    cout << '\n';
}

 

---

</27172> 수 나누기 게임

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

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

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

    int n;
    cin >> n;
    vector<int> x(n);
    vector<int> s(n, 0);

    for (int i = 0; i < n; i++) cin >> x[i];

    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (x[i] > x[j] && x[i] % x[j] == 0) {
                s[i]--;
                s[j]++;
            } else if (x[j] > x[i] && x[j] % x[i] == 0) {
                s[i]++;
                s[j]--;
            }
        }
    }

    for (int i = 0; i < n; i++) cout << s[i] << ' ';
    cout << '\n';
}

위 코드는 단순히 모든 쌍에 대해 나눠서 확인하는 코드입니다. 이렇게 제출하게 되면 시간 초과를 받게 됩니다.

시간을 줄이기 위해서는 불필요한 연산을 줄여야 합니다.

이 게임에서는 어떤 수가 어떤 수의 배수인지 아닌지만 중요하기 때문에, 그 관계에 속하지 않는 수들은 확인할 필요가 없습니다. 즉, 나눌 필요가 없는 것입니다.

앞의 말을 반대로 말하면, 배수의 관계에 있는 수들에 대해서만 계산을 하면 됩니다.

아이디어는 모든 수에 대해 배수들을 차례로 구하면서 그 배수를 가진 플레이어가 있었다면 점수를 갱신하도록 합니다.

이를 위해서 애초에 플레이어가 가진 수들을 입력 받을 때 체크를 해주어야 합니다.

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

// MAX_SIZE: x의 최댓값 + 1
int const MAX_SIZE = 1000001;
// ex: 특정 수가 플레이어의 카드 중에 있었는지 저장하는 배열
bool ex[MAX_SIZE];
// s: 특정 수의 점수를 저장하는 배열
int s[MAX_SIZE];

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

    int n;
    cin >> n;
    vector<int> x(n);

    for (int i = 0; i < n; i++) {
        cin >> x[i];
        ex[x[i]] = true; // 플레이어 카드 중에 등장했으므로 ex에 체크
    }

    for (int i = 0; i < n; i++) {
        // i번째 카드에 적힌 수의 배수(= j)를 하나씩 확인
        for (int j = x[i] + x[i]; j < MAX_SIZE; j += x[i]) {
            if (ex[j]) { // j가 플레이어 카드 중에 있었다면
                s[x[i]]++; // i번째 카드에 적힌 수의 점수는 + 1
                s[j]--; // j의 점수는 - 1
            }
        }
    }

    for (int i = 0; i < n; i++) cout << s[x[i]] << ' ';
    cout << '\n';
}

어떤 수가 플레이어 카드 중에 있었는지 저장하는 배열 ex와 그 수에 대한 점수를 저장하는 배열 s를 만들어 구현했습니다.

 

---

</11656> 접미사 배열

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

문자열의 모든 접미사를 배열로 만든 후, C++ STL에 있는 sort 함수를 통해 정렬하였습니다. 
* str.substr(n): str의 n번째 index부터 끝까지의 문자를 부분 문자열로 반환하는 함수

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

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

    // s: 문자열
    string s;
    cin >> s;

    // n = 문자열 s의 길이 = 접미사 배열 a의 크기
    int n = s.size();
    // a: 접미사를 담는 배열
    vector<string> a;

    for (int i = 0; i < n; i++) a.push_back(s.substr(i));

    sort(a.begin(), a.end());

    for (string tmp: a) cout << tmp << '\n';
}

 

---

</18870> 좌표 압축

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

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

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

    int n;
    cin >> n;

    vector<pair<int, int>> data(n); // (값, 원래 인덱스) 저장
    vector<int> ans = vector<int>(n); // 압축된 결과를 저장
    for (int i = 0; i < n; i++) {
        cin >> data[i].first; // 값 저장
        data[i].second = i; // 원래 인덱스 저장
    }

    sort(data.begin(), data.end()); // 첫번째 원소(값) 기준으로 정렬

    int cnt = 0;
    ans[data[0].second] = 0; // 가장 작은 값은 0으로 설정
    int pre = data[0].first; // 이전 값 저장
    for (int i = 1; i < n; i++) {
        if (data[i].first != pre) cnt++; // 값이 다르면 새로운 번호 부여
        ans[data[i].second] = cnt; // 원래 인덱스에 압축된 값 저장
        pre = data[i].first; // 이전 값 갱신
    }

    for (int x: ans){
        cout << x << ' ';
    }
    cout << '\n';
}

값과 원래 인덱스를 함께 저장한 뒤, 정렬된 순서에 따라 새로운 번호를 부여하고, 이를 원래 순서대로 출력하는 방식으로 구현했습니다.

 

---

</18110> solved.ac

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

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

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

    int n;
    cin >> n;

    if (n == 0) { // 입력이 0일 경우 0 출력 후 종료 (division 에러가 생기지 않도록)
        cout << 0 << '\n';
        return 0;
    }

    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    sort(a.begin(), a.end()); // 오름차순 정렬

    int ex = floor(n * 0.15 + 0.5); // 상하위 15% 절사값 계산 (반올림)
    int sum = 0;

    // 절사 평균을 위한 값 합산
    for (int i = ex; i < n - ex; i++) {
        sum += a[i];
    }

    double avg = double(sum) / (n - 2 * ex); // 절사 평균 계산

    cout << floor(avg + 0.5) << '\n'; // 평균을 반올림한 후 출력

    return 0;
}

 

---

</15711> 환상의 짝꿍

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

이 문제는 아이디어를 떠올리기도 어렵고, 애초에 기반이 되는 배경 지식도 생소해서 어려우실 것이라고 생각합니다. 따라서, 골드바흐의 추측이 사용된다는 점을 인지하시고 이에 대한 기본 지식을 가진 상태에서 푸는 것을 추천드립니다.

 

실제로 찾아보면 엄밀한 증명도 아직 이루어지지 않았고 생각보다 복잡한 내용들이 있지만 이 문제를 풀기 위해서는 아래의 내용만 알고 계시면 됩니다.

골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.

 

다시 문제로 돌아가보면, 두 수가 주어지고 두 수의 합을 두 소수로 쪼갤 수 있는지 없는지를 체크해야 합니다.

골드바흐의 추측에 의해 합이 짝수면 무조건 YES입니다.

합이 홀수인 경우에는 두 소수로 쪼개려면 어떻게 되어야 할까요? 홀수는 짝수 + 홀수입니다. 홀수가 두 소수로 쪼개지려면 짝수와 홀수 모두 소수여야 하므로, 짝수는 소수 중 유일한 짝수인 2여야 하고 나머지 홀수가 소수여야 합니다.

다시 정리하면, 합이 홀수면 합에서 2를 뺀 값이 소수이면 YES, 아니면 NO입니다.

 

여기까지 알면 대충 어떻게 구현해야 할지 큰 틀이 머리 속에 그려질 것이라 생각합니다.

자 그러면 홀수인 경우에는 소수 판정을 해야 하는데, 10의 12승이 넘는 수에 대해 소수인지 어떻게 판단할까요?

다양한 방법이 떠오를 수 있지만, 이 문제는 시간 제한이 빡빡한 편이라 최대한 시간을 줄이기 위한 방법을 끌어모아서 사용해야 합니다.

 

시간을 줄이기 위한 방법
1. 2 × 10^12 의 제곱근까지 에라토스테네스의 체를 이용하여 소수 구하기
    먼저 2 × 10^12 의 제곱근까지 소수를 구합니다. 
    이 때 구한 소수와 동일하면 → 소수임.
    이 때 구한 소수로 나누어 떨어지면 → 소수 아님. / 그렇지 않으면 → 소수임.
    이런식으로 소수를 판정하면 시간을 줄일 수 있습니다.
2. 이렇게 구한 소수를 bool 배열 그대로 사용하는 것이 아니라 소수 배열에 담아둔 후 사용하기
    bool 배열 형태에서 p[i]가 true면 소수 아니면 소수X로 판단하기 보다는, 에라토스테네스의 체로 구한 소수를 따로 배열에 담아두고 사용하는 것이 시간이 더 적게 걸립니다. 
    이는 소수의 밀도를 생각해보면 쉽게 이해하실 수 있을 것입니다.
    그리고 실제로 이것 때문에 시간 초과와 정답이 나뉘기도 합니다.

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

// 구해야 하는 소수의 최대 크기
// (a, b의 최댓값의 제곱근보다 크면 됨)
int const MAX_SIZE = 2000000;

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

    int t;
    cin >> t;

    // p: 소수 판별을 위한 배열 (기본값은 true) <- 시간을 줄이기 위해
    vector<bool> p(MAX_SIZE, true);
    p[0] = p[1] = false; // 0과 1은 소수가 아님
    // prime: 소수를 넣는 배열
    vector<int> prime;

    // 에라토스테네스의 체
    int tmp = sqrt(MAX_SIZE);
    for (int i = 2; i <= tmp; i++) {
        if (p[i]) { // i가 소수라면
            for (int j = i + i; j < MAX_SIZE; j += i) p[j] = false;
        }
    }

    // 소수를 미리 배열에 담아두기 <- 시간을 줄이기 위해
    for (int i = 1; i < MAX_SIZE; i++) {
        if (p[i]) prime.push_back(i);
    }

    while (t--) {
        long long a, b;
        cin >> a >> b;

        if (a + b <= 3) { // 2와 3 예외 처리 주의!
            cout << "NO\n";
        } else if ((a + b) % 2 == 0) { // 짝수면 무조건 YES
            cout << "YES\n";
        } else { // 홀수면 2를 뺀 값이 소수인지 체크
            bool ans = true;
            for (int i: prime) {
                if (a + b - 2 == i) { // 앞에서 구한 소수면 YES
                    break;
                }
                if ((a + b - 2) % i == 0) { // 앞에서 구한 소수로 나누어 떨어지면 NO
                    ans = false;
                    break;
                }
            }
            
            if (ans) cout << "YES\n";
            else cout << "NO\n";
        }
    }
}