백준 다이아까지 3걸음

세계4대진미_돼지국밥 2022. 6. 23. 18:12

# 가장 인상적이었던 문제

비트마스킹을 이용해 브루트포스 알고리즘을 얼마나 최적화할 수 있냐에 TLE 여부가 달린 문제였다. 아무리 머리를 굴려봐도 내 로직의 시간 복잡도는 O(NM)이 한계였고, 최악의 경우 8억의 배수만큼의 기본 연산을 하게 되어 4초를 넘길 것이었다. 돌멩이 하나 던져보는 심정으로 로직을 구현해서 제출했더니 이게 웬일? TLE가 뜨지 않았다. N과 M 모두 최댓값인 케이스는 빠져 있는 게 분명했다.

#include <iostream>
using namespace std;

const int MAX_N = 1e4, NUM_CHAR = 26;

int n, m;
string arrStr[MAX_N];
int bit[MAX_N];
int forget;

int countWords() {
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        cnt += ((bit[i] & forget) == 0);
    }
    return cnt;
}

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

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> arrStr[i];
    }
    for (int i = 0; i < n; i++) {
        for (char& c : arrStr[i]) {
            bit[i] |= 1 << (c-'a');
        }
    }
    int o; char x;
    for (int i = 0; i < m; i++) {
        cin >> o >> x;
        if (o == 1) {
            forget |= 1 << (x-'a');
        } else {
            forget ^= 1 << (x-'a');
        }
        cout << countWords() << '\n';
    }
}

AC 받은 것과는 별개로, 시간 복잡도는 O(NM)이기 때문에, 제약 조건에 따르면 최악의 경우 시간 제한이라는 요구 사항을 충족하지 못할 로직이어서 상당히 불만족스러웠다. 그래서 질답게를 찾아다니다 보니 약 21 * 2^21회 이하의 루프를 통한 전처리로 시간 복잡도 O(M)을 달성한 로직(sait2000 님의 풀이, 제출번호: 17338374)을 발견했다. 처음에는 전처리 과정이 이해가 잘 안 되었지만, 코드가 깔끔해서 그런지 금방 이해할 수 있었다. 그걸 보고 새로 구현해서 제출하니 마음이 편안해졌다.

#include <iostream>
using namespace std;


const int MAX_N = 1e4;
int bit[MAX_N], cnt[1 << 21];
const int trans[26] {
    -1, 0, 1, 2, -1, 3, 4, 5, -1, 6, 7, 8, 9, 10, -1, 11,
    12, 13, 14, 15, -1, 16, 17, 18, 19, 20
};

inline int charToPos(char c) {
    return trans[c-'a'];
}

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

    int n, m; cin >> n >> m;
    int pos;
    string inp;
    for (int i = 0; i < n; i++) {
        cin >> inp;
        
        for (char& c : inp) {
            pos = charToPos(c);
            if (pos >= 0) {
                bit[i] |= 1 << pos;
            } 
        }
        cnt[bit[i]]++;
    }

    for (int i = 1; i < (1 << 21); i <<= 1) {
        for (int j = 0; j < (1 << 21); j += i << 1) {
            for (int k = 0; k < i; k++) {
                cnt[i | j | k] += cnt[j | k];
            }
        }
    }
    
    int remember = (1 << 21) - 1;
    int o; char x;
    for (int i = 0; i < m; i++) {
        cin >> o >> x;

        remember ^= 1 << charToPos(x);

        cout << cnt[remember] << '\n';
    }
}

한편으로는 생각이 닫혀 있는 자신을 돌아보게 되었다. 나는 나름 최적화란 걸 해본답시고 비트마스크의 배열을 그려놓고 그것만 살펴 보고 있었다. '문자열이 N개인데 1번의 연산으로 조건을 만족하는 문자열의 개수를 구할 수가 있나? 각 비트마스크의 조건 만족 여부는 서로 독립적이어서 하나씩 다 따져보는 수밖에 없는데...' 내 생각이 각각의 비트마스크에 갇혀 있는 동안 진전은 없었다. 각각의 비트마스크를 집합이라는 관점에서 봤다면, 나아가 합집합의 개념을 떠올릴 수 있었다면, 2^21개의 비트마스크 각각의 부분집합의 개수를 계산해 놓을 발상에 이를 수 있었을 테다.

최근 고급 알고리즘들을 학습하기 시작했고, 특히 문자열, 차순위로 기하 알고리즘을 학습할 계획이다. 하지만 이것들은 어디까지나 지엽적인 것일 뿐이다. 웰노운인지 여부를 떠나서 새로운 문제를 만났을 때 해결하는 능력을 기르려면, 폭넓은 사고를 하는 훈련을 해야 한다. 지금하는 알고리즘 공부에 가장 큰 의미를 더해주는 본질은 바로 그것이 아닐까? 다이아를 찍을 때만큼은 이 질문에 확실한 답을 가지고 있기를.