비트필드와 완전 탐색 최적화 (Bit DP)

흔히 비트 DP (Bit DP)라고 하는 거 같다.

문제를 읽는데 n이 15~20 정도 되는, 작지만 n!은 아닌 범위가 주어지면 십중팔구 얘.

시간복잡도도 십중팔구 2^n * n or 2^n * n^2.

멀쩡한 dp문제를 기하로 변환해서 푸는 Convex Hull Trick과 함께 가장 변태적인 dp 테크닉 중 하나라고 자부한다.

(그래도 얘가 Convex Hull Trick보다는 나은듯...)

각설하고.

보통 dp하면 항상 예제로 자주 나오는게 피보나치 함수를 최적화하는 것이다.

f(n){

if(n == 0) return 0;

if(n == 1) return 1;

if(memoized) return memo;

else return f(n-1) + f(n-2);

}

이러한 최적화를 적용시킬 수 있는 이유는 자명하다.

피보나치 함수는 n이 일정할때 항상 일정한 값만 내뱉는다.

쉽게 말해서 피보나치 5는 지구가 멸망해도 8이다. (수학적 정의니까)

그래서 보통 dp를 쓸때는 x,y가 일정할때 f(x,y)가 일정하다는 가정하에 dp를 쓴다.

그러면

f(int* visited, int depth){

for each element{

if(!visited[element]){

visited[element] = 1;

f(visited,depth+1);

visited[element] = 0;

}

}

}

아주 일반적인 완전 탐색으로 시간 복잡도는 n!인데,

얘는 과연 visited와 depth가 일정하면 같은 값을 내뱉을까?

당연하다. 그 외에 영향을 주는 인자가 없기 때문이다.

그러면... dynamic table을

DP [ Visited 배열 ] [ 현재 깊이 ]

이런 식으로 저장하면 테이블 하나를 채우는 데 n이고

테이블 개수가 n * 2^n이니까 (Visited 배열은 2^n의 상태를 가질 수 있다. 각각 꺼져있거나 켜져있거나)

에 문제를 풀 수 있겠다.

물론 배열을 그냥 넣는 건 말이 안된다.

그래서 비트필드를 쓴다.

내 설명이 존나 쓰레기라서 위키백과 등을 뒤적거리는 것을 추천한다만 그래도 설명은 해야할거 같다.

비트필드는 정수를 가지고 나타내는 집합인데

01010011 막 이런거 있으면 (이진수다)

0번째 1번째 4번째 6번째 원소가 켜져있다 - 이런 식으로 받아들인다.

오른쪽에서 역순으로 읽으면 실제로 1이 그렇게 켜져있는 것을 알 수 있다.

t = 01010011이라면

비트연산자를 통해서 원소가 들어있는지 없는지는 일단 알 수 있다.

6번째 원소의 값은 (t>>6)%2일 것이다.

(보통 (t>>6)&1이라고 표현한다)

이걸로 !visited[element]를 대체할 수 있다.

그러면 원소를 넣는 건 어떻게?

2번째 원소를 들어있다고 표현하게 해보자.

t = 01010011 이라는 집합에다가 합집합 연산을 하면 된다.

어떤 집합이랑 ? u = 00000100 ( = (1<<2) ) 이랑 하면 된다.

어떻게? OR 연산으로.

이러면 f(visited | (1<<element) , depth + 1) 이런 식으로 표현가능하다.

f(int visited, int depth){

if(memoized) return memo;

for each element{

if(!(visited>>(element))&1)

f(visited|(1<<element),depth+1);

}

}

훨씬 더 우아한 소스코드로 더 빠른 성능을 낼 수 있다. (비트연산은 O(1)연산 중에 가장 빠른 연산 중 하나다)

비트필드를 스위핑하는 테크닉이 추가로 있는데 귀찮으니 혼자 생각해 보길.. (어차피 프로그래밍 콘테스트 챌린징에 다 있다)

추천 문제 :

http://koistudy.net/?mid=prob_page&NO=713

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

https://www.acmicpc.net/problem/5559 (난 이문제를 진심으로 사랑한다. 근데 제일 어렵다)