Bitmasks (3) 썸네일형 리스트형 82. Sum Over Subsets 집합이 존재할 때 각각의 부분집합에 대해 그 집합의 부분집합의 합(Sum Over Subsets, SOS)을 빠르게 계산하는 방법에 대해서 다룬다. 이 방법은 DP 테이블을 채우면서 부분집합의 합을 계산하기 때문에 SOS DP라고 불린다. 원소의 개수가 $n$인 집합의 부분집합의 개수가 $2^n$이고, SOS DP의 기본 시간복잡도가 $\Theta(2^n \cdot n)$이기 때문에 일반적으로 $n$은 $20$ 이하이다. SOS DP는 집합을 비트마스크로 표현하며, 따라서 비트필드를 이용하게 된다. 집합을 0-based로 나타내면 $0 \le p 두 집합 $A, B$를 나타내는 정수가 각각 $x, y$일 때 $(x \And y) = y$인 경우 $B \subset A$이고 $(y \And x) = x$.. 79. Bit DP 비트마스크를 이용한 동적 계획법(Bit DP)에 대해 다룬다. 일반적으로 이 유형의 문제들은 제한이 $20$ 이하로 작은 변수가 주어지는 경우가 많으며, 이 변수에 대한 각각의 상태를 비트마스크로 나타냄으로써 문제를 해결할 수 있다. 동적 계획법이 비트마스크를 이용할 경우 이때의 DP 테이블을 비트필드(Bitfield)라고도 한다. [연습문제] BOJ 1562. 계단 수 (Gold I)더보기현재까지 사용된 숫자의 조합과 수의 길이를 기준으로 비트필드를 채운다. 사용된 숫자의 조합은 $2^{10}$개 이하로 나오며 (아무 숫자도 사용하지 않는 경우나 사용한 숫자가 연속되지 않는 경우가 모두 제외된다. 다만 실제로 문제를 풀 때는 별로 신경쓰지 않아도 된다) $\Theta(2^{10} \cdot N)$ 시간.. 26. Bitmasks 비트마스크(Bitmasks)(비트마스킹(Bitmasking)으로 불리는 경우도 있음)는 Bool 값으로 표현할 수 있는 대상이 여러 개 존재할 때 이를 정수의 비트를 이용해서 표현하는 기법이다. Bool 값으로 표현할 수 있는 대상은 대비되는 두 개의 속성만을 가지고 있어야 한다. 예를 들어 참(True)과 거짓(False), 켜진 상태(ON)와 꺼진 상태(OFF), 선택한 상태와 선택하지 않은 상태 등이 있다. 일반적으로 $8$바이트 정수 자료형으로 $64$개의 비트를 한번에 표현할 수 있고 그보다 큰 정수 자료형이 잘 쓰이지 않기 때문에 이보다 적은 비트만을 사용해서 문제를 풀 수 있는 경우에 주로 사용되지만 정수 배열을 이용해서 더 많은 비트를 사용하고 메모리와 실행 시간의 측면에서 더 성능이 좋은.. 이전 1 다음
