비트마스크

[알고리즘] 백준 11723번: 집합 (비트마스크) W_node.js

문제 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오. add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다. remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다. check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20) toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20) all: S를 {1..

[알고리즘] 비트마스크 Bit Mask

비트마스크 꺼져있다 = 0, 켜져있다 = 1 로 표현할 수 있는 2진수의 특성을 활용해 자료구조로 활용하는 기법. 비트를 마스킹처리하여 비트 연산을 활용해 2진 비트를 처리하는 작업이다. 장점 1. 수행 시간이 빠르다. 다른 자료구조에 비해 수행 시간이 빠르다. 비트 마스크 연산은 비트Bit 연산으로 O(1)로 동작한다. 2. 간결한 코드 다양한 집합 연산들을 비트연산자 한 줄로 작성할 수 있기 때문에 코드가 간결해진다. 3. 적은 메모리 사용량 2진수의 특성상 하나의 정수로 많은 경우의 수를 표현할 수 있기 때문에 메모리를 효율적으로 활용할 수 있다. 비트연산자 [JavaScript] 비트 연산 Bit Operation 비트연산자 비트(bit)단위, 즉 2진수 단위로 논리연산을 위해 사용하는 연산자 비..

[JavaScript] 비트 연산 Bit Operation

비트연산자 비트(bit)단위, 즉 2진수 단위로 논리연산을 위해 사용하는 연산자 비트 단위로 전체 비트를 오른쪽, 왼쪽 이동시킬 때에도 사용한다. 실행 과정 : 2진수 변환 → 비교(연산 실행) → 결과 반환(10진수) 비트연산자의 종류 a & b : AND 연산 대응되는 비트가 모두 1일 때 1을 반환한다. (둘 다 1이면 1, 아니라면 0을 반환) 1 & 3; // 1 = 0001(2) // 3 = 0011(2) --------------- // 0001(2) = 1 a | b : OR 연산 대응되는 비트 중 하나라도 1이면 1을 반환한다. (하나라도 1이면 1, 둘 다 0이면 0을 반환) 1 | 3; // 1 = 0001(2) // 3 = 0011(2) --------------- // 0011(2..