79. Bit DP

비트마스크를 이용한 동적 계획법(Bit DP)에 대해 다룬다. 일반적으로 이 유형의 문제들은 제한이 $20$ 이하로 작은 변수가 주어지는 경우가 많으며, 이 변수에 대한 각각의 상태를 비트마스크로 나타냄으로써 문제를 해결할 수 있다. 동적 계획법이 비트마스크를 이용할 경우 이때의 DP 테이블을 비트필드(Bitfield)라고도 한다.

 

[연습문제]

 

BOJ 1562. 계단 수 (Gold I)

현재까지 사용된 숫자의 조합과 수의 길이를 기준으로 비트필드를 채운다. 사용된 숫자의 조합은 $2^{10}$개 이하로 나오며 (아무 숫자도 사용하지 않는 경우나 사용한 숫자가 연속되지 않는 경우가 모두 제외된다. 다만 실제로 문제를 풀 때는 별로 신경쓰지 않아도 된다) $\Theta(2^{10} \cdot N)$ 시간에 전체 문제가 해결된다. 초기화 과정에서 수의 길이가 $1$인 경우를 모두 처리하고 수의 길이가 $2$ 이상인 경우부터 반복문으로 처리하는 것이 편리하다.

 

BOJ 2098. 외판원 순회 (Gold I)

Traveling Salesman Problem(TSP)이라고 불리는 유명한 문제이다. 정점의 수 $n$이 크지 않을 경우 (대략 $20$ 이하) 비트필드를 이용해서 문제를 해결할 수 있다. 시작 정점을 하나로 고정하고, 방문한 정점의 집합, 현재의 정점을 기준으로 비트필드를 채우면 되는데 각각의 칸을 채우는 데 $\Theta(n)$ 시간이 걸리므로 총 $\Theta(2^n \cdot n^2)$ 시간에 문제가 해결된다. 시작 정점을 마지막 정점으로 고정하고 정점들의 번호를 1-based에서 0-based로 바꾸면 구현이 조금 더 간단해진다.

 

정점이 더 많은 경우의 TSP를 해결하는 방법은 이전부터 많은 사람들의 연구 대상이었고, 다양한 최적화를 이용하면 상당히 빠르게 답을 얻을 수 있다고 한다.

 

BOJ 1086. 박성원 (Platinum V)

현재까지 사용한 수들의 집합, 현재까지 이어붙인 수를 $K$로 나눈 나머지를 기준으로 비트필드를 채운다. 각각의 칸을 채우는 데 $\Theta(N)$ 시간이 걸리므로 총 시간복잡도는 $\Theta(2^N \cdot NK)$가 된다.

 

BOJ 3056. 007 (Platinum V)

현재까지 사용한 미션의 집합을 기준으로 비트필드를 채운다. 각각의 칸에는 해당 집합의 미션을 모두 성공적으로 수행할 확률의 최대값을 저장한다. (단순히 double 배열을 사용해도 실수 오차 문제는 안 생기는 것으로 보인다) 각각의 칸을 채우는 데 $\Theta(N)$ 시간이 걸리므로 총 시간복잡도는 $\Theta(2^N \cdot N)$이다.

 

BOJ 1014. 컨닝 (Platinum IV)

줄의 번호, 그 줄에서 학생이 앉은 자리의 집합을 기준으로 비트필드를 채운다. 각각의 칸은 이전 줄의 각각의 상태를 고려해서 채워나가면 된다. 이 문제의 경우 효율적인 구현을 하기 위해서 몇 가지 알아두면 좋은 점이 존재하는데, 먼저 두 줄의 학생 배치가 적절한지 확인할 때 서로 인접한 열에 학생이 앉은 경우가 없는지를 확인할 필요가 있다. 이때 두 줄의 학생 배치를 나타내는 값을 각각 $x, y$라고 한다면, 다음과 같은 비트 연산으로 이를 확인할 수 있다.

• $x \And x<< 1$
• $x \And y<< 1$
• $y \And x<< 1$
• $y \And y<< 1$

네 가지 식의 값이 모두 $0$인 경우에만 유효한 배치가 된다. $x$와 $y$의 범위가 $2^{10}$ 미만이므로 각각의 값을 전부 전처리해 놓으면 중간 구현에서 값을 일일히 구하지 않아도 된다.

또한 한 줄에 가능한 학생의 배치 역시 많지 않으므로 ($M = 10$인 경우 학생을 배치하는 방법은 $2^{10} = 1024$가지가 있으나 이중 인접한 학생이 존재하지 않는 경우는 $144$가지밖에 없다) 처음부터 그 배치에 대해서만 고려하면 속도가 빨라진다. 총 시간복잡도는 $\Theta(CN \cdot 2^{2M})$이며, 여러 가지 최적화를 하면 상수가 많이 작아진다.

 

BOJ 1648. 격자판 채우기 (Platinum III)

줄의 번호, 그 줄에서 도미노로 덮인 칸의 집합을 기준으로 비트필드를 채운다. 이때 각각의 줄에 대해 이전 줄들이 모두 도미노로 덮여 있어야 한다는 조건이 붙는다. 이 문제도 첫 번째 줄을 직접 초기화하는 것이 좋은데, 첫 줄에 도미노가 놓일 수 있는 배치의 값은 $(x \And x<< 1) = 0$을 만족하는 $x$에 대해 $3x$가 된다.

 

→ solved.ac tag: dp_bitfield