240424: 클래스 2 금장 달성 ⭐ 구현과 시뮬레이션, 스택

2024-04-24

Solved.ac 클래스 2 금장 달성 ⭐

오늘부로 Solved.ac 클래스 2 금장을 달성했다. 이제 확실히 알고리즘 초보는 벗어난듯.
클래스 3은 골드 문제도 나오던데 내일부턴 클래스 3 금장을 목표로 하겠다. 이번년도 목표는 클래스 6 금장까지 깨기!

 

---

solved.ac (수학, 구현, 정렬)

이 문제는 Solved.ac의 알고리즘 난이도 티어 시스템을 모방하는 문제다.

어떤 문제의 난이도는 그 문제를 푼 사람들이 제출한 난이도 의견을 바탕으로 결정한다. 난이도 의견은 그 사용자가 생각한 난이도를 의미하는 정수 하나로 주어진다. solved.ac가 사용자들의 의견을 바탕으로 난이도를 결정하는 방식은 다음과 같다.

아직 아무 의견이 없다면 문제의 난이도는 0으로 결정한다.
의견이 하나 이상 있다면, 문제의 난이도는 모든 사람의 난이도 의견의 30% 절사평균으로 결정한다.

절사평균이란 극단적인 값들이 평균을 왜곡하는 것을 막기 위해 가장 큰 값들과 가장 작은 값들을 제외하고 평균을 내는 것을 말한다. 30% 절사평균의 경우 위에서 15%, 아래에서 15%를 각각 제외하고 평균을 계산한다. 따라서 20명이 투표했다면, 가장 높은 난이도에 투표한 3명과 가장 낮은 난이도에 투표한 3명의 투표는 평균 계산에 반영하지 않는다는 것이다.

제외되는 사람의 수는 위, 아래에서 각각 반올림한다. 25명이 투표한 경우 위, 아래에서 각각 3.75명을 제외해야 하는데, 이 경우 반올림해 4명씩을 제외한다.

마지막으로, 계산된 평균도 정수로 반올림된다. 절사평균이 16.7이었다면 최종 난이도는 17이 된다.

사용자들이 어떤 문제에 제출한 난이도 의견 목록이 주어질 때, solved.ac가 결정한 문제의 난이도를 계산하는 프로그램을 작성하시오.

요구사항은 복잡하지만 구현은 간단하다. 주어진 N의 15% 절사평균을 위아래로 자르고 평균을 구하면 된다. round 처리에만 신경쓰면 쉽게 풀 수 있었다.

// 백준: solved.ac
// https://www.acmicpc.net/problem/18110
// 2024-04-24

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

int round15Percent(int n) { return static_cast<int>(round(n * 0.15)); }

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    if (N == 0) {
        cout << "0";
        return 0;
    }

    vector<int> scores(N, 0);
    for (int i = 0; i < N; ++i) {
        cin >> scores[i];
    }
    sort(scores.begin(), scores.end());
    int trim_s = round15Percent(N);
    ll sum = 0;
    for (int i = trim_s; i < N - trim_s; ++i) {
        sum += scores[i];
    }
    if (sum == 0)
        cout << "0";
    else
        cout << round(sum / static_cast<double>((N - (trim_s * 2))));
    return 0;
}

---

프린터 큐 (구현, 시뮬레이션, 자료 구조)

프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.
1. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
2. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.

현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내시오.

프린터 큐 문제는 문제의 규칙대로 푸는 간단한 시뮬레이션 문제였다.
이제 이런 문제는 사실, 고민할 필요도 없이 푸는 것 같다. 실버 중반대의 문제를 잘 푸는 걸 보면,, 확실히 알고리즘 실력이 작년에 비해 훨씬 늘었다.

물 흐르듯이 풀어서 딱히 더 쓸 말이 없다. 좋은거겠지 !

// 백준: 프린터 큐
// https://www.acmicpc.net/problem/1966
// 2024-04-14

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int N, M; // 문서 개수 N, 목표 M
        cin >> N >> M;
        queue<pair<int, int>> q;
        for (int i = 0; i < N; ++i) {
            int priority;
            cin >> priority;
            q.push({priority, i});
        }

        int counter = 0;

        while (!q.empty()) {
            int cur_priority = q.front().first;
            int cur_index = q.front().second;
            q.pop();
            q.push({cur_priority, cur_index});
            // 자기보다 큰 것을 찾을때까지 루프
            bool flag = true;
            while (q.front().second != cur_index && flag) {
                int next_priority = q.front().first;
                int next_index = q.front().second;
                if (next_priority > cur_priority) { // 다음 큐가 자신 우선순위보다 크면 종료
                    flag = false;
                    break;
                } else { // 다음 큐가 자신 우선순위보다 작으면 뒤로 보내기
                    q.pop();
                    q.push({next_priority, next_index});
                }
            }
            if (flag) { // 한 바퀴를 돌았지만 자신보다 큰 우선순위를 찾지 못했다면
                counter++;
                q.pop();              // 출력
                if (cur_index == M) { // 목표가 출력됐다면 반환
                    cout << counter << "\n";
                    break;
                }
            }
        }
    }
    return 0;
}

---

스택 수열 (자료구조, 스택)

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다.
이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자.
임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지,
있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다.
이를 계산하는 프로그램을 작성하라.

스택 수열은 정말 불친절한 문제였다. 지문을 30분동안 쳐다보는데도 무슨 소리인지 이해가 안 됐다. 질문 게시판을 확인해보니까 나만 이런게 아니었다. 출제자의 의도를 추리해서 풀어야 하는 문제는 좀 너무하다는 생각이 든다.

문제의 지문만 읽으면.. 읽는 사람에 따라 문제를 해석하는 방식이 너무 차이가 있다.
나는 수열의 길이 N과 수열 정보가 주어지면, 1부터 N을 오름차순으로 push 혹은 pop 하면서 해당 수열을 똑같이 만들 수 있는지를 말하는 줄 알았다. 아마 많은 사람도 이렇게 생각했을 것 같은데.. 테스트 케이스가 완전 딴판이다.

결론적으로 이 문제가 원하는 건..

1부터 N까지의 수를 스택에 넣고, 특정 시점에서 뺀다.
뺀 수들을 순서대로 배치함으로써, 주어진 수열을 그대로 만들 수 있는지. 만들 수 있다면 어떤 순서로 연산을 수행해야 하는지 묻는다.

예를 들어서, 1, 2, 3을 가지고 스택 수열을 만든다고 할 때 셋 다 넣고 셋다 pop 하는 방식으로 3, 2, 1을 만들 수 있다. 1과 2를 넣고 2를 pop 한다음 3 넣고 나머지를 모두 pop 하는 방식으로 2, 3, 1도 만들 수 있다.

그니까 이 문제에서 중요한 건 .pop() 이다. pop 했을때의 수를 스택에 차곡 차곡 쌓는다고 생각했을 때, 모두 pop 되고 나서의 수가 처음에 주어진 수열이 될 수 있냐! 라고 묻는 문제다. 그리고 push 할 수 있는 숫자는 1부터 N까지의 오름차순 순서다.

문제 풀이

문제의 핵심을 이해하니까 약간은 복잡한 구현 문제였다. 문제에서 제공하는 목표 수열을 저장할 큐.
시뮬레이션 할 스택, push와 pop 기록을 로그할 log 벡터를 만들어서 풀었다.

// 백준: 스택 수열
// https://www.acmicpc.net/problem/1874
// 2024-04-24

/*
문제 지문이 불친절하다
*/

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N;
    cin >> N;
    queue<int> goal;  // 목표 수열
    stack<int> st;    // 시뮬레이션 스택
    vector<char> log; // push, pop 기록 로그
    for (int i = 0; i < N; ++i) {
        int temp;
        cin >> temp;
        goal.push(temp);
    }
    int index = 1;
    while (!goal.empty()) {
        // 스택의 맨 윗값이 현재 찾는 값인지 확인
        if (!st.empty() && st.top() == goal.front()) {
            goal.pop();
            st.pop();
            log.push_back('-');
        } else {
            st.push(index);
            log.push_back('+');
            ++index;
            if (index > N + 1) {
                cout << "NO";
                return 0;
            }
        }
    }

    for (const char &next : log) {
        cout << next << "\n";
    }

    return 0;
}

---

마인크래프트 (구현, 브루트포스)

마인크래프트 문제는 처음에 되게 복잡해보이는 문제였다.

팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 땅을 파거나 집을 지을 수 있는 게임이다.

목재를 충분히 모은 lvalue는 집을 짓기로 하였다. 하지만 고르지 않은 땅에는 집을 지을 수 없기 때문에 땅의 높이를 모두 동일하게 만드는 ‘땅 고르기’ 작업을 해야 한다.

lvalue는 세로 N, 가로 M 크기의 집터를 골랐다. 집터 맨 왼쪽 위의 좌표는 (0, 0)이다. 우리의 목적은 이 집터 내의 땅의 높이를 일정하게 바꾸는 것이다. 우리는 다음과 같은 두 종류의 작업을 할 수 있다.

좌표 (i, j)의 가장 위에 있는 블록을 제거하여 인벤토리에 넣는다.
인벤토리에서 블록 하나를 꺼내어 좌표 (i, j)의 가장 위에 있는 블록 위에 놓는다.
1번 작업은 2초가 걸리며, 2번 작업은 1초가 걸린다. 밤에는 무서운 몬스터들이 나오기 때문에 최대한 빨리 땅 고르기 작업을 마쳐야 한다. ‘땅 고르기’ 작업에 걸리는 최소 시간과 그 경우 땅의 높이를 출력하시오.

단, 집터 아래에 동굴 등 빈 공간은 존재하지 않으며, 집터 바깥에서 블록을 가져올 수 없다. 또한, 작업을 시작할 때 인벤토리에는 B개의 블록이 들어 있다. 땅의 높이는 256블록을 초과할 수 없으며, 음수가 될 수 없다.

핵심만 정리하자면, 마인크래프트에서 집을 지을 맵 N*M의 높이 정보가 주어졌을 때. 지형을 평탄화 (모든 칸을 똑같은 높이를 가지게) 하는데에 가장 적게 드는 시간을 요구하는 알고리즘이다.

블럭을 부수는데에는 2초, 블럭을 설치하는데에는 1초가 걸린다. 블럭을 부수면 인벤토리에 블럭이 하나 추가되고, 인벤토리에 블럭이 있어야만 블럭을 설치할 수 있다.

처음에는 많은 조건 분기와 그리디 문제라고 생각했다. 어떻게 각 데이터에 대해서 최선의 선택을 결정할 수 있는지에 대해 고민하다가, 거의 불가능함을 깨달았다. 아예 그리디적 해법이 감이 안잡힌다.

모든 칸의 높이가 아예 제각각으로 주어지고, 설치할 수 있는 블럭의 개수도 제한되어 있는데 이렇게 많은 조건 분기를 어떻게 그리디적으로 해결하는가?

문제 풀이

일단 그리디로 푸는 것은 거의 불가능하다고 확신했다. 그래서 단순한 브루트포스 구현으로 넘어갔는데, 시간 제한이 1초라서 가능한 모든 해를 탐색하는건 TLE가 날 것 같아서 최대한 효율적으로 로직을 구상했다.

일단 대부분의 상황에서 가장 가능성이 높은 방법이 무엇일까?

처음에는 이렇게 생각했다. 이미 평탄화가 조금이라도 되어있는 층이 있으면, 나머지 지역의 높이를 이미 평탄화가 조금이라도 되어있는 높이에 맞추는 게 효율적이라고 생각했다. 그래서 set 자료구조를 사용해서 한 칸이라도 이미 맞춰져있는 높이를 unique하게 저장했다. (unique하게 저장하면서도, 자동으로 정렬이 되는 set 자료구조를 사용했다. 왜냐하면, 블럭이 부족한 상황에서는 나머지 지역을 더 낮은 층으로 깎으면서 하는 것이 유효할 것이고. 블럭이 넘치는 상황에서는 나머지 지역을 높은 층으로 쌓으면서 하는게 유효할 것이기 때문이라고 생각해서. 주어진 데이터에 따라서 유동적으로 순회 순서를 바꾸고, 탐색중의 가중치가 이미 알려진 시간을 초과한다면 바로 가지치기를 하려고 했다)

근데, 이것보다 더 좋은 방법이 생각났다.

이미 해당 층의 높이를 가지는 칸이 있는 층을 먼저 탐색하고, 알려진 최단 시간을 갱신한 뒤 가지치기를 하는 방법도 유효하지만. 이미 해당 층의 높이를 가지는 칸의 개수가 제일 빈번한 층부터 탐색을 한다면 훨씬 효율적이라고 생각했다. 대부분의 상황에선 이미 어느정도 평탄화가 된 지역을 나머지 지역이 맞추는 게 더 효율적이다, 만약 칸 30개가 이미 1층으로 맞추어져 있고, 나머지 5칸이 2층이라면 5칸을 깎는쪽이 정답일 확률이 유력하고 이후에 가지치기가 좀 더 효율적으로 진행 될 수 있을 거라고 생각했다.

따라서, 계수 정렬이 떠올랐다. Counting sort는 각 인덱스를 층으로 보고, 해당 층의 등장마다 요소에 +1을 해서 최종적으로 제일 큰 요소를 가지는 인덱스가 가장 빈번하게 나오는 층인 것이다.

계수 정렬로 각 층의 등장 횟수를 모두 세고, 이걸 다시 반복해서 층의 등장 횟수를 내림차순 정렬하면 제일 확률이 유력한 쪽부터 탐색할 수 있을 것이다.

근데 여기서 층의 등장 횟수를 내림차순 하는게 이중 포문으로 비효율적인 시간복잡도를 가질 것 같아서, Utility STL의 pair을 사용해서 .first에는 등장 횟수, .second에는 인덱스(층)을 기록했다. 그리고 algorithm STL의 sort를 사용해서 pair의 .first를 기준으로 내림차순 정렬했고, 이후에 .second를 조회하면서 빈번하게 등장한 층 순서대로 탐색했다.

이렇게 가지치기 (알려진 시간을 초과하면 스킵) 을 적용해서 현재 목표 층으로 나머지 칸을 가공하는데에 걸리는 시간을 계산했다.

여기서 주의해야할 점은 인벤토리 B에 대해서다. 단순히 순회로 브루트포스를 돌리면 인벤토리에 있는 블럭의 개수가 음수가 되는 순간이 오는데, 처음에는 인벤토리가 음수가 되면 바로 해당 목표를 종료하고 다음 탐색을 시작하도록 했는데. 사실은 다른 블럭의 높이를 낮추는 과정에서 새로운 블럭을 수급하고, 그걸 이전 칸을 올리는데에 쓸 여지가 있었기 때문에 그렇게 하면 안됐다. 모든 탐색이 끝나고 최종적으로 인벤토리가 음수인지만 확인해야 했다.

또, 동일한 시간을 가지는 결과가 있을 경우 더 높은 지점으로 평탄화 한다는 점에 유의했다.

처음에는 탐색을 돌리면서 만약 현재 목표 층이 한번도 나온적이 없으면 탐색 종료를 하도록 로직을 구성했는데, 이건 완전히 오류였다. 현재 맵에 층이 존재하지 않더라도 중간 층에서 더 효율적인 루트를 찾을 가능성이 있었는데 이걸 생각 못했다.

전체적으로 이 문제는 생각해야 할게 많은 복잡한 시뮬레이션 브루트포스 문제였다.
그래도 문제를 푸는 동안 재밌었고, 결국에 푸니까 뿌듯했다 ! (조금 많이 삽질한 것 같긴 하다. 사실 계수 정렬, set, 가지치기 이런거 안해도 그냥 풀리는 문제였던듯)

정답 코드

// 백준: 마인크래프트
// https://www.acmicpc.net/problem/18111
// 2024-04-24

/*
브루트포스 구현 문제, 불필요한 수를 제거하는 가지치기도 사용해서 효율적으로 구현했다.

1. 가장 빈번한 층부터 평탄화 작업을 시뮬레이션한다. (해답일 확률이 높기 때문에)
2. 만약 알려진 최단 시간을 초과하면 바로 다음 층을 시뮬레이션한다.
3. B가 음수가 될때 바로 종료하면 안된다. 작업 순서에 따라 B를 다른 칸에서 얻고 사용할수도 있으니 모든 작업이 끝나고 음수가 아닌지만 확인하면 된다.
*/

#include <iostream>
// #include <set> // unique한 층을 정렬하기 위해서 사용 (계수 정렬로 대체)
#include <algorithm>
#include <functional>
#include <limits.h>
#include <utility>
#include <vector>
using namespace std;
typedef long long ll;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N, M, B; // N*M 맵, B개의 기본제공 블럭
    cin >> N >> M >> B;
    vector<vector<int>> map(N, vector<int>(M));

    // 계수 정렬 (Counting sort)
    // 단순히 계수하고 내림차순하면 n^2의 순회를 필요로 하므로 pair로 인덱스를 기록하고 sort한다.
    vector<pair<int, int>> floors(257);
    for (int i = 0; i <= 256; ++i) {
        floors[i] = {0, i};
    }

    // set을 계수 정렬로 대체함
    // set<int> unique_floors;

    for (int r = 0; r < N; ++r) {
        for (int c = 0; c < M; ++c) {
            int temp;
            cin >> temp;
            map[r][c] = temp;
            floors[temp].first++;
            // unique_floors.insert(temp);
        }
    }

    // 층 빈도를 내림차순으로 정렬
    sort(floors.begin(), floors.end(), [](const pair<int, int> &a, const pair<int, int> &b) { return a.first > b.first; });

    // floors 디버그 체크
    // for (const auto &next : floors) {
    //     cout << next.first << "\n" << next.second << "\n\n***\n\n";
    //     if (next.first == 0)
    //         break;
    // }

    // 최단 시간 저장
    ll known_min_time = LLONG_MAX;
    int known_min_floor = -1;

    // 가장 빈도가 높은 층 순으로 탐색
    for (int i = 0; i <= 256; ++i) {
        int time = 0;                      // 소요된 시간
        int goal_floor = floors[i].second; // 현재 탐색할 목표 층
        int inventory = B;                 // 인벤토리

        // if (floors[i].first == 0) {        // 만약 현재 목표 층이 한번도 나온적이 없으면 탐색 종료
        //     break;
        // }

        // 맵을 순회하면서 비용 계산
        // 블록 제거 : 2초
        // 블록 설치 : 1초 (B 소모, B가 없으면 해당 층 진행 불가능)

        bool gg = false;
        for (int r = 0; r < N && !gg; ++r) {
            for (int c = 0; c < M && !gg; ++c) {
                int cur_floor = map[r][c];   // 현재 탐색중인 칸
                if (cur_floor == goal_floor) // 현재 칸이 이미 목표 층이라면 스킵
                    continue;
                else if (cur_floor > goal_floor) {        // 현재 칸이 목표 층보다 높다면
                    time += (cur_floor - goal_floor) * 2; // 부숴야 할 블럭에 2초씩 적용
                    inventory += cur_floor - goal_floor;  // 인벤토리에 부순 블럭 추가
                } else if (cur_floor < goal_floor) {      // 현재 칸이 목표 층보다 낮다면
                    inventory += cur_floor - goal_floor;  // 칸의 차를 B에 업데이트
                    time += goal_floor - cur_floor;       // 설치 시간 1초 적용
                    // if (inventory < 0) {                          // 방금의 계산으로 B가 음수가 됐다면 이번 층 포기
                    //     gg = true;                        // GG | 이 부분은 오류임. B가 음수가 되어도 다른 칸에서 B를 채울 가능성을 확인해야 한다.
                    //     break;
                    // }
                }

                if (time > known_min_time) {
                    gg = true;
                    break; // 방금의 작업으로 알려진 최단 시간을 초과했다면 이번 층 포기
                }
            }
        }

        // 탐색이 끝났고, 해당 목표 층이 가능했다면
        if (!gg && inventory >= 0) {
            if (time < known_min_time) { // 소요된 시간이 알려진 시간보다 빠르다면
                known_min_time = time;
                known_min_floor = goal_floor;
            } else if (time == known_min_time) { // 복수 정답이면 높은 층을 정답으로
                known_min_floor = max(known_min_floor, goal_floor);
            }
        }
    }

    cout << known_min_time << " " << known_min_floor;

    return 0;
    // 이미 존재하는 층 별로 탐색
    // for (set<int>::iterator it = unique_floors.begin(); it != unique_floors.end(); ++it) {
    //     int cur_floor = *it; // 현재 탐색할 목표 층
    // }
}

---

오늘은 의도치 않게 구현이나 시뮬레이션 문제를 많이 푼 것 같다.
다익스트라같은 pure 알고리즘보다 정말 로직 스킬을 키운 것 같다. 그리고 무엇보다 구현 / 시뮬레이션 / 브루트포스 / 그래프 류는 풀 때 재밌는 것 같다.

수학은 풀 땐 재미없지만 풀고나선 수학 기믹이 신기해서 재밌고...

내일은 솔브닥 클래스 3 금장을 천천히 깨나갈 예정!

끝.