[BJ] 1062 가르침 (골드4)

[비트마스크 - bitmask]

: 비트 연산을 이용해 여러 가지 상태나 데이터를 효율적으로 표현하고 조작하는 기법

각 비트를 0 또는 1로 설정하여 특정 상태를 나타내며, 주로 집합, 플래그, 상태 등을 나타내는데 사용됨

• 비트 연산
  • AND (&) : 두 비트가 모두 1일 때만 1을 반환
  • OR ( | ) : 두 비트 중 하나라도 1이면 1을 반환
  • XOR (^) : 두 비트가 다를 때 1을 반환
  • NOT (~) : 비트를 반전(1→0, 0→1)시킴
  • 비트 이동 연산 (<<, >> ) : 비트를 좌측 또는 우측으로 이동
• 비트마스크의 활용
  • 집합 표현 : 정수의 비트를 이용해 집합을 표현.
    • e.g.) {a,b,c} 3개의 요소로 구성된 집합은 3비트로 표현 가능
      • 000 : 비어있는 상태
      • 001 : 집합 {c}
      • 101 : 집합 {a,c}
  • 상태 관리 : 여러 개의 플래그를 하나의 정수로 관리
    • |= 연산 : 특정 플래그를 설정할 때 사용
    • &= ~연산 : 특정 플래그를 해제할 때 사용

#include <iostream>

const int FLAG_A = 1 << 0; //0001
const int FLAG_B = 1 << 1; //0010
const int FLAG_C = 1 << 2; //0100

void printFlags(int flags){
	std::cout << "Flags: ";
	//& 연산으로 해당 플래그가 있는지 확인
	if(flags & FLAG_A) std::cout << "A";
  if (flags & FLAG_B) std::cout << "B ";
  if (flags & FLAG_C) std::cout << "C ";
	    std::cout << std::endl;
}

int main() {
    int flags = 0;
    flags |= FLAG_A; // A 플래그 설정
    flags |= FLAG_C; // C 플래그 설정
    //flags : 0101

    printFlags(flags); // 출력: A C

    flags &= ~FLAG_A; // A 플래그 해제

    printFlags(flags); // 출력: C

    return 0;
}

 

• 효율적인 저장 및 조작 : 메모리 및 속도 최적화

[장점]

1. 메모리 효율성 : 상태를 비트로 표현하여 메모리를 절약할 수 있음
2. 속도 : 비트 연산은 매우 빠르므로 상태 체크나 변환이 빠르게 수행됨
3. 단순성 : 여러 상태를 한 번에 처리할 수 있어 코드가 간결해짐

[단점]

1. 가독성 : 비트 연산이 익숙하지 않은 경우 코드의 가독성이 떨어질 수 있음
2. 제한된 크기 : 비트마스크는 정수의 크기에 제한되므로, 표현할 수 있는 상태 수가 제한됨
3. 오류 가능성 : 비트를 잘못 다루면 예상치 못한 오류가 발생할 수 있음

---

[ __builtin_popcount() ]

: 주어진 unsigned int형에서 1로 설정된 비트의 개수를 계산하는 함수

• GCC(GNU Compiler Collection)에서 제공하는 내장 함수
• 이 함수는 빠르고 효율적으로 동작하며, 비트마스크를 사용하여 상태를 관리하거나 특정 비트 패턴을 분석하는 문제에서 유용하게 사용된다

#include <iostream>

int main(){
	int x = 29; //29는 이진수로 11101, 즉 1의 개수는 4
	Int count = __builtin_popcount(x);
	std::cout << count << std::endl; //출력 4
		return 0;
	}

---

<문제에 활용 - 백준 1062 : 가르침>

[문제]

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

 

[접근]

• 각 문자열마다 “anta”, "tica”에 사용되는 a,c,i,n,t 5가지 이외 필요한 알파벳을 정보를 저장
• → 비트마스크 활용
• 이외 K-5개의 알파벳을 추가해서 가장 많은 문자열을 알 수 있는 알파벳을 구하면 될 것 같음
• → 비트 연산자 사용

[코드]

• initStdMask() : a,c,i,n,t를 비트마스크로 나타내 반환하는 함수
• toBitmask(const string &str) : 입력받은 string의 알파벳 정보를 비트마스크로 만들어 반환하는 함수
• countReadableWords(int targetMask, vector<int> &bitmasks) : bitmasks에 있는 모든 bitmask(모든 문자열)에 대해서 targetMask로 읽을 수 있는 단어의 수를 세서 반환하는 함수

#1062_teaching.cpp

#include <iostream>
#include <vector>
#include <bitset>

using namespace std;

int initStdmask;

// void printBits(int num) {
//     std::bitset<sizeof(int) * 8> bits(num);
//     std::string bitString = bits.to_string(); // 비트셋을 문자열로 변환

//     // 8비트씩 끊어서 출력
//     for (size_t i = 0; i < bitString.size(); ++i) {
//         std::cout << bitString[i];
//         if ((i + 1) % 8 == 0 && i != bitString.size() - 1) {
//             std::cout << ' ';
//         }
//     }
//     std::cout << std::endl;
// }

int initStdMask(){
    int stdMask = 0;
    stdMask |= (1 << ('a' - 'a')); //a 저장
    stdMask |= (1 << ('c' - 'a')); //c 저장
    stdMask |= (1 << ('i' - 'a')); //i 저장
    stdMask |= (1 << ('n' - 'a')); //n 저장
    stdMask |= (1 << ('t' - 'a')); //t 저장

    return stdMask;
}

//비트마스크 출력해주는 함수
int toBitmask(const string &str){
    int bitmask=0;
    for(char c : str){
        bitmask |= (1 << ( c - 'a')); //해당 알파벳을 비트마스크에 저장
    }
    return bitmask;
}

//해당 비트마스크로 읽을 수 있는 단어 개수 반환하는 함수
int countReadableWords(int targetMask, vector<int> &bitmasks){
    int count = 0;
    for(int bitmask:bitmasks){
        if((bitmask & targetMask) == bitmask) count++;
    }
    return count;
}

int main(){
    int N,K;
    cin >> N >> K;
    vector<int> bitmasks(N); //각 문자열의 bitmask를 저장하는 벡터
    initStdmask = initStdMask(); //stdMask을 초기화할 때 사용하는

    for(int i=0;i<N;i++){
        string str;
        cin >> str;
        bitmasks[i] = toBitmask(str);
    }

    if(K < 5){ //a,c,i,n,t 5개는 반드시 포함해야 한다
        cout << "0" << endl;
        return 0;
    }

    int maxCount = 0; //리턴값
    
    int stdMask = initStdmask;

    //모든 가능한 비트마스크로 검사
    for(int targetMask = stdMask; targetMask < (1<<26) ;targetMask++){ //a,c,i,n,t를 모두 포함하려면, a,c,i,n.t를 모두 포함하는 비트 마스크보다 큰 수 이다
        stdMask = initStdmask;
        // printBits(targetMask);
        // cout << "stdMask와 & 연산하면 : ";
        // printBits(targetMask & stdMask);
        if(((targetMask | stdMask) == targetMask) && (__builtin_popcount(targetMask) == K)){ 
            //a,c,i,n,t를 포함한 비트마스크(stdMask)를 모두 포함하며, 알파벳 수가 K개인 targetMask를 검사
            int count = countReadableWords(targetMask,bitmasks);
            maxCount = max(maxCount,count);
        }
    }
    cout << maxCount << endl;
    return 0;
}

*참고

(targetMask & bitmask) == bitmask 하면, targetMask로 bitmask를 읽을 수 있는지 확인할 수 있다