[백준/BOJ] 단계별로 풀어보기 : 기본 수학 2, 정렬 (올클리어)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge(BOJ)의 단계별로 풀어보기 중 '기본 수학 2', '정렬' 문제들 중 제가 풀이하지 않은 문제들에 대한 보충 풀이를 다루고 있습니다.

 

문제 난이도는 Solved.ac 기준 Silver 티어 정도에 해당하며, 각 문제에 필요한 알고리즘은 설명으로 적어두겠습니다.

 

문제의 난이도가 어렵지 않기 때문에 문제에 대해 간단히 요약하고, 풀이 코드와 그 풀이에 대한 간략한 설명만을 기록하도록 하겠습니다.

 

 

4948번 : 베르트랑 공준

 

주어진 n에 대해 n보다 크고 2n보다 작거나 같은 소수의 개수를 구하는 문제입니다.

위의 이미지에는 나오지 않지만 n은 최대 12만 정도까지 입력될 수 있기 때문에, 소수 판별 과정에서 일반적인 방법인 "모두 나누어보기" 방식으로는 시간 초과를 받을 수 있습니다.

따라서 에라토스테네스의 체 알고리즘을 사용하여 소수를 미리 판별하여 배열에 기록해둘 수 있도록 해줍니다.

 

 

#include <bits/stdc++.h>
using namespace std;

bool comp[300000] = {};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    for(int i=2; i*i<=250000; i++)
        for(int j=2; i*j<=250000; j++) comp[i*j] = true;

    while(true) {
        int N; cin >> N;
        if(N == 0) break;

        int cnt = 0;
        for(int i=N+1; i<=N*2; i++)
            if(!comp[i]) cnt++;
        cout << cnt << "\n";
    }
}

 

n이 최대 12만 정도이므로, 코드를 돌리기 전 2n에 해당하는 25만 정도까지의 범위에서 소수 판별을 미리 하여 comp 배열에 저장해줍니다. (여기서 comp는 합성수라는 뜻의 composition을 의미합니다.)

그 다음 각 입력에 대해서 이미 판별이 된 소수 배열에서 체크만 해주면서 count를 해주면 됩니다.

 

 

 

제출해보면 4ms의 시간으로 통과할 수 있습니다.

 

 

9020번 : 골드바흐의 추측

 

주어진 수 n에 대해 합이 n이면서 두 소수의 차이가 가장 작은 쌍을 출력하는 문제입니다.

n/2부터 1씩 줄여가면서 x와 n-x가 모두 소수인지 확인하고, 만약 둘 다 소수라면 그 쌍을 출력해주면 되는 문제입니다.

다만 각 반복문에 대해 그 x가 소수인지를 확인하는 과정에서 시간을 단축시키기 위해 역시 에라토스테네스의 체를 사용해주면 되는 문제입니다.

 

 

#include <bits/stdc++.h>
using namespace std;

bool comp[10005] = {};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    
    for(int i=2; i*i<=10000; i++)
        for(int j=2; i*j<=10000; j++) comp[i*j] = true;

    int T; cin >> T;
    while(T--) {
        int N; cin >> N;
        for(int i=N/2; i>=2; i--)
            if(!comp[i] && !comp[N-i]) {
                cout << i << " " << N-i << "\n";
                break;
            }
    }
}

 

위와 같이 미리 comp에 소수 판별을 하여 그 여부를 저장해두고, 처리할 때는 n/2에서부터 1씩 줄여가면서 i와 N-i가 모두 소수인 첫 수를 찾아주어 출력만 해주면 됩니다.

 

 

 

입력 범위가 크지 않기 때문에 에라토스테네스의 체와 입출력부 딜레이만 없다면 0ms의 시간으로 통과할 수 있습니다.

 

 

 

이렇게 해서 일단 11단계까지는 모두 풀이된 상태가 되었습니다.

(아마 대부분의 문제들은 제가 이전 포스트들에 풀이한 것이 있을 것입니다. 이 포스트에서는 그동안 포스트에서 풀이하지 않은 문제들을 풀이하고 있습니다.)

이제 12단계에 해당하는 정렬 문제들 중에서 안 푼 것들을 풀이해보도록 하겠습니다.

 

 

2108번 : 통계학

 

입력으로 주어진 N개의 수들에 대해 산술평균, 중앙값, 최빈값, 범위를 출력하는 문제입니다.

문제가 어렵지는 않으나 4개의 대푯값을 모두 구해야해서 귀찮아지는 문제입니다.

 

#include <bits/stdc++.h>
using namespace std;

vector<int> arr;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;
    for(int i=0; i<N; i++) {
        int val; cin >> val;
        arr.push_back(val);
    }
    sort(arr.begin(), arr.end());

    double sum = 0;
    for(int i=0; i<N; i++) sum += arr[i];
    if(round(sum/N) > -1 && round(sum/N) < 1) cout << abs(round(sum/N)) << "\n";
    else cout << round(sum/N) << "\n";
    cout << arr[N/2] << "\n";

    int cnt[10000] = {};
    for(int i=0; i<N; i++) cnt[arr[i] + 4000]++;
    int maxFreq = 0;
    for(int i=0; i<=8000; i++)
        if(cnt[i] > maxFreq) maxFreq = cnt[i];
    int maxCnt = 0;
    for(int i=0; i<=8000; i++)
        if(cnt[i] == maxFreq) maxCnt++;
    if(maxCnt > 1) {
        bool check = false;
        for(int i=0; i<=8000; i++)
            if(cnt[i] == maxFreq) {
                if(!check) check = true;
                else {
                    cout << i-4000 << "\n";
                    break;
                }
            }
    }
    else
        for(int i=0; i<=8000; i++)
            if(cnt[i] == maxFreq) cout << i-4000 << "\n";

    cout << arr[N-1] - arr[0];
}

 

평균값에서 round 함수를 활용해서 반올림 처리를 할 수 있도록 구현하였습니다.

double이 아닌 float를 사용하면 평균값 계산 과정에서 오차 때문에 오답을 받습니다.

(2022/02/21 수정 : round 함수를 사용할 경우 -0이라는 값이 출력될 수 있고, 이 부분이 재채점됨에 따라 정답 기준이 바뀌게 되었습니다. 따라서 이 경우 -1 < 평균값 < 1인 경우 abs 함수를 추가하여 -0이 아닌 0이 출력되도록 해줍시다.)

 

중앙값은 sort 함수로 정렬 후 중앙에 위치하는 값을 출력해주면 됩니다.

배열이 0부터 시작하니 그냥 N/2 위치에 저장되어 있는 값을 출력해주면 됩니다.

 

최빈값이 가장 복잡한데, 최빈값이 여러 개인 경우 두 번째로 작은 최빈값을 출력해주어야 합니다.

따라서 이 경우는 최빈값의 개수를 먼저 구한 다음 최빈값이 2개 이상인 경우는 다시 구해주어야 합니다.

가장 작은 최빈값은 넘어가고 그 다음으로 먼저 나오는 최빈값을 출력해줍니다.

최대한 간단히 짜려했음에도 코드가 상당히 길어집니다.

 

마지막으로 범위는 sort 이후 마지막 위치에 있는 값과 처음 위치에 있는 값의 차를 출력해주면 됩니다.

 

 

 

위의 풀이 코드대로 풀이를 작성하여 제출하면 위와 같은 기록으로 통과할 수 있습니다.

 

 

11651번 : 좌표 정렬하기

 

점의 좌표들을 정렬하되, y좌표가 증가하는 순으로 정렬하고 y좌표가 같을 경우 x좌표가 오름차순이 되도록 정렬하는 문제입니다.

sort 함수를 활용하여 문제를 간단히 해결해보도록 하겠습니다.

 

#include <bits/stdc++.h>
using namespace std;

vector<pair<int, int>> point;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;
    for(int i=0; i<N; i++) {
        int x, y; cin >> x >> y;
        point.push_back({y, x});
    }
    sort(point.begin(), point.end());

    for(int i=0; i<N; i++)
        cout << point[i].second << " " << point[i].first << "\n";
}

 

vector의 pair를 활용하면 쉽게 해결이 가능합니다.

다만 sort 함수의 경우 compare 함수를 정의하여 풀이하는 방식도 있겠지만, 여기서는 x와 y의 순서를 바꾸어 pair에 대입해준 뒤 정렬을 하고, 출력할 때 first와 second의 위치를 바꾸어 출력해주면 아주 간단하게 해결할 수 있습니다.

 

 

 

 

18870번 : 좌표 압축

 

이 포스트에서 풀이할 마지막 문제입니다.

좌표 압축이라고 표현하였으나, 크기 비교를 하여 크기 비교 관계가 달라지지 않도록 최소화시켜 순위 비슷한 개념으로 출력해주면 되는 문제입니다.

 

#include <bits/stdc++.h>
using namespace std;

vector<int> input, arr;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;
    for(int i=0; i<N; i++) {
        int val; cin >> val;
        input.push_back(val), arr.push_back(val);
    }

    sort(arr.begin(), arr.end());
    arr.erase(unique(arr.begin(), arr.end()), arr.end());

    for(int i=0; i<input.size(); i++)
        cout << lower_bound(arr.begin(), arr.end(), input[i]) - arr.begin() << " ";
}

 

이 문제는 특히나 algorithm 헤더 파일의 함수들을 많이 사용해야 간단하게 짤 수 있습니다.

먼저 input과 arr으로 두 개의 벡터를 나누어 둘 모두에 입력값들을 저장해줍니다.

arr 벡터는 값들을 정렬하기 위해 사용하는 것이고, input 벡터는 초기 입력을 순서대로 저장하기 위해 필요합니다.

 

그 다음 unique 함수와 erase 함수를 활용하여 arr에서 중복 값들을 제거해줍니다.

lower_bound 함수를 이용하여 key 값에 해당하는 input[i]가 정렬된 arr에서 몇 번째에 있는지를 체크하고, 이터레이터 형식으로 반환되는 값을 위치로 변환하기 위해 arr.begin()의 주소값을 빼주면 좌표 압축 값을 구할 수 있습니다.

 

 

 

풀이를 제출하면 위와 같은 기록으로 통과할 수 있습니다.

 

---

 

이렇게 해서 12단계에 해당하는 정렬 단계까지 모든 문제들을 풀이해보았습니다.

다음 포스트에서는 백트래킹, 동적 계획법 단계의 문제들을 올클리어 해보도록 하겠습니다.